/* Bring the targeted splay node to the top of the splaytree */
splaynode = splay(key, splaynode, &match_type, splaytree->compare);
splaytree->root = splaynode;
/* Bring the targeted splay node to the top of the splaytree */
splaynode = splay(key, splaynode, &match_type, splaytree->compare);
splaytree->root = splaynode;
/* Finds the desired node, and changes the tree such that it is the root */
static inline splaynode_t * splay (void * key, splaynode_t * t, int * match_type, int (*compare)()) {
/* Finds the desired node, and changes the tree such that it is the root */
static inline splaynode_t * splay (void * key, splaynode_t * t, int * match_type, int (*compare)()) {
What it does is described above. */
splaynode_t N, *l, *r, *y;
*match_type = CLOSEST_MATCH;
What it does is described above. */
splaynode_t N, *l, *r, *y;
*match_type = CLOSEST_MATCH;
- if (compare(key, t->key) < 0) {
- if (t->left == NULL) break;
- if (compare(key, t->left->key) < 0) {
- y = t->left; /* rotate right */
- t->left = y->right;
- y->right = t;
- t = y;
- if (t->left == NULL) break;
- }
- r->left = t; /* link right */
- r = t;
- t = t->left;
- } else if (compare(key, t->key) > 0) {
- if (t->right == NULL) break;
- if (compare(key, t->right->key) > 0) {
- y = t->right; /* rotate left */
- t->right = y->left;
- y->left = t;
- t = y;
- if (t->right == NULL) break;
- }
- l->right = t; /* link left */
- l = t;
- t = t->right;
- } else {
- *match_type = PERFECT_MATCH;
- break;
- }
+ if (compare(key, t->key) < 0) {
+ if (t->left == NULL) break;
+ if (compare(key, t->left->key) < 0) {
+ y = t->left; /* rotate right */
+ t->left = y->right;
+ y->right = t;
+ t = y;
+ if (t->left == NULL) break;
+ }
+ r->left = t; /* link right */
+ r = t;
+ t = t->left;
+ } else if (compare(key, t->key) > 0) {
+ if (t->right == NULL) break;
+ if (compare(key, t->right->key) > 0) {
+ y = t->right; /* rotate left */
+ t->right = y->left;
+ y->left = t;
+ t = y;
+ if (t->right == NULL) break;
+ }
+ l->right = t; /* link left */
+ l = t;
+ t = t->right;
+ } else {
+ *match_type = PERFECT_MATCH;
+ break;
+ }
splaynode_t * splaynode;
/* Use helper function to delete the node and return the resulting tree */
if ((splaynode = splay_delete_helper(key, splaytree->root, splaytree->compare, splaytree->free_key)) == NULL)
splaynode_t * splaynode;
/* Use helper function to delete the node and return the resulting tree */
if ((splaynode = splay_delete_helper(key, splaytree->root, splaytree->compare, splaytree->free_key)) == NULL)
/* Finished, no errors */
return SUCCESS;
}
/* Deletes a splay node */
static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * splaynode, int (*compare)(), void (*free_key)()) {
/* Finished, no errors */
return SUCCESS;
}
/* Deletes a splay node */
static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * splaynode, int (*compare)(), void (*free_key)()) {
-
- /* If entry wasn't found, quit here */
- if (match_type == CLOSEST_MATCH)
- return NULL;
-
- /* If the targeted node's left pointer is null, then set the new root
- equal to the splaynode's right child */
- if (splaynode->left == NULL) {
- new_root = splaynode->right;
- }
-
- /* Otherwise, do something I don't currently understand */
- else {
- new_root = splay(key, splaynode->left, &match_type, compare);
- new_root->right = splaynode->right;
- }
-
- /* Set splay nodes children pointers to null */
- splaynode->left = splaynode->right = NULL;
-
- /* Free the splaynode (and only this node since its children are now empty */
- free_splaynode(splaynode, free_key);
-
- /* Return the resulting tree */
- return new_root;
-
+
+ /* If entry wasn't found, quit here */
+ if (match_type == CLOSEST_MATCH)
+ return NULL;
+
+ /* If the targeted node's left pointer is null, then set the new root
+ equal to the splaynode's right child */
+ if (splaynode->left == NULL) {
+ new_root = splaynode->right;
+ }
+
+ /* Otherwise, do something I don't currently understand */
+ else {
+ new_root = splay(key, splaynode->left, &match_type, compare);
+ new_root->right = splaynode->right;
+ }
+
+ /* Set splay nodes children pointers to null */
+ splaynode->left = splaynode->right = NULL;
+
+ /* Free the splaynode (and only this node since its children are now empty */
+ free_splaynode(splaynode, free_key);
+
+ /* Return the resulting tree */
+ return new_root;
+
- splaynode_t * splaynode;
- /* Argument checks */
- if (data == NULL)
- return NULL;
-
- if (key == NULL)
- return NULL;
-
- /* Creates the new splay node struct */
- if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
- return NULL;
-
- splaynode->data = data;
- splaynode->type = type;
- splaynode->key = key;
-
- /* Return the new splay node */
- return splaynode;
+ splaynode_t * splaynode;
+ /* Argument checks */
+ if (data == NULL)
+ return NULL;
+
+ if (key == NULL)
+ return NULL;
+
+ /* Creates the new splay node struct */
+ if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
+ return NULL;
+
+ splaynode->data = data;
+ splaynode->type = type;
+ splaynode->key = key;
+
+ /* Return the new splay node */
+ return splaynode;
/* Create a new splay node of symbolic link type */
if ((splaynode = new_splaynode(SYMBOLIC_NODE_TYPE, (key_clone = splaytree->copy_key(alias_key)), data_node)) == NULL) {
/* Create a new splay node of symbolic link type */
if ((splaynode = new_splaynode(SYMBOLIC_NODE_TYPE, (key_clone = splaytree->copy_key(alias_key)), data_node)) == NULL) {
/* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
inline int splay_insert(void * data, void * key, splaytree_t * splaytree) {
/* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
inline int splay_insert(void * data, void * key, splaytree_t * splaytree) {
- splaynode_t * splaynode;
- void * key_clone;
-
- /* Null argument checks */
- if (splaytree == NULL) {
- return FAILURE;
- }
-
- if (key == NULL)
- return FAILURE;
-
- /* Clone the key argument */
- key_clone = splaytree->copy_key(key);
-
- /* Create a new splaynode (of regular type) */
- if ((splaynode = new_splaynode(REGULAR_NODE_TYPE, key_clone, data)) == NULL) {
- splaytree->free_key(key_clone);
- return OUTOFMEM_ERROR;
- }
-
-
- /* Inserts the splaynode into the splaytree */
- if (splay_insert_node(splaynode, splaytree) < 0) {
- splaynode->left=splaynode->right=NULL;
- free_splaynode(splaynode, splaytree->free_key);
- return FAILURE;
- }
-
-
- return SUCCESS;
+ splaynode_t * splaynode;
+ void * key_clone;
+
+ /* Null argument checks */
+ if (splaytree == NULL) {
+ return FAILURE;
+ }
+
+ if (key == NULL)
+ return FAILURE;
+
+ /* Clone the key argument */
+ key_clone = splaytree->copy_key(key);
+
+ /* Create a new splaynode (of regular type) */
+ if ((splaynode = new_splaynode(REGULAR_NODE_TYPE, key_clone, data)) == NULL) {
+ splaytree->free_key(key_clone);
+ return OUTOFMEM_ERROR;
+ }
+
+
+ /* Inserts the splaynode into the splaytree */
+ if (splay_insert_node(splaynode, splaytree) < 0) {
+ splaynode->left=splaynode->right=NULL;
+ free_splaynode(splaynode, splaytree->free_key);
+ return FAILURE;
+ }
+
+
+ return SUCCESS;
-
- void * closest_key;
-
- if (splaytree == NULL)
- return NULL;
- if (splaytree->root == NULL)
- return NULL;
- if (key == NULL)
- return NULL;
-
- closest_key = NULL;
-
- splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);
-
- if (closest_key == NULL) return NULL;
- return splay_find(closest_key, splaytree);
+
+ void * closest_key;
+
+ if (splaytree == NULL)
+ return NULL;
+ if (splaytree->root == NULL)
+ return NULL;
+ if (key == NULL)
+ return NULL;
+
+ closest_key = NULL;
+
+ splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);
+
+ if (closest_key == NULL) return NULL;
+ return splay_find(closest_key, splaytree);
-
- void * closest_key;
-
- if (splaytree == NULL)
- return NULL;
- if (splaytree->root == NULL)
- return NULL;
- if (key == NULL)
- return NULL;
- closest_key = NULL;
-
- splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);
-
- if (closest_key == NULL) {
- return NULL;
- }
-
- return splay_find(closest_key, splaytree);
+
+ void * closest_key;
+
+ if (splaytree == NULL)
+ return NULL;
+ if (splaytree->root == NULL)
+ return NULL;
+ if (key == NULL)
+ return NULL;
+ closest_key = NULL;
+
+ splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);
+
+ if (closest_key == NULL) {
+ return NULL;
+ }
+
+ return splay_find(closest_key, splaytree);
- /* Empty root, return*/
- if (root == NULL)
- return;
-
- /* The root key is less than the previously found closest key.
- Also try to make the key non null if the value is less than the max key */
-
- if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
-
- /* The root key is less than the given max key, so this is the
- smallest change from the given max key */
- if (compare(root->key, min_key) > 0) {
-
- *closest_key = root->key;
-
- /* Look right again in case even a greater key exists that is
- still less than the given max key */
- splay_find_below_max_helper(min_key, closest_key, root->left, compare);
- }
-
- /* The root key is greater than the given max key, and greater than
- the closest key, so search left */
- else {
- splay_find_below_max_helper(min_key, closest_key, root->right, compare);
- }
- }
-
- /* The root key is less than the found closest key, search right */
- else {
- splay_find_below_max_helper(min_key, closest_key, root->left, compare);
- }
-
+ /* Empty root, return*/
+ if (root == NULL)
+ return;
+
+ /* The root key is less than the previously found closest key.
+ Also try to make the key non null if the value is less than the max key */
+
+ if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
+
+ /* The root key is less than the given max key, so this is the
+ smallest change from the given max key */
+ if (compare(root->key, min_key) > 0) {
+
+ *closest_key = root->key;
+
+ /* Look right again in case even a greater key exists that is
+ still less than the given max key */
+ splay_find_below_max_helper(min_key, closest_key, root->left, compare);
+ }
+
+ /* The root key is greater than the given max key, and greater than
+ the closest key, so search left */
+ else {
+ splay_find_below_max_helper(min_key, closest_key, root->right, compare);
+ }
+ }
+
+ /* The root key is less than the found closest key, search right */
+ else {
+ splay_find_below_max_helper(min_key, closest_key, root->left, compare);
+ }
+
- /* Empty root, stop */
- if (root == NULL)
- return;
-
- /* The root key is greater than the previously found closest key.
- Also try to make the key non null if the value is less than the min key */
-
- if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
-
- /* The root key is greater than the given min key, so this is the
- smallest change from the given min key */
- if (compare(root->key, max_key) < 0) {
-
- *closest_key = root->key;
-
- /* Look left again in case even a smaller key exists that is
- still greater than the given min key */
- splay_find_above_min_helper(max_key, closest_key, root->right, compare);
- }
-
- /* The root key is less than the given min key, and less than
- the closest key, so search right */
- else {
- splay_find_above_min_helper(max_key, closest_key, root->left, compare);
- }
- }
-
- /* The root key is greater than the found closest key, search left */
- else {
- splay_find_above_min_helper(max_key, closest_key, root->right, compare);
- }
-}
+ /* Empty root, stop */
+ if (root == NULL)
+ return;
+
+ /* The root key is greater than the previously found closest key.
+ Also try to make the key non null if the value is less than the min key */
+
+ if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
+
+ /* The root key is greater than the given min key, so this is the
+ smallest change from the given min key */
+ if (compare(root->key, max_key) < 0) {
+
+ *closest_key = root->key;
+
+ /* Look left again in case even a smaller key exists that is
+ still greater than the given min key */
+ splay_find_above_min_helper(max_key, closest_key, root->right, compare);
+ }
+
+ /* The root key is less than the given min key, and less than
+ the closest key, so search right */
+ else {
+ splay_find_above_min_helper(max_key, closest_key, root->left, compare);
+ }
+ }
+
+ /* The root key is greater than the found closest key, search left */
+ else {
+ splay_find_above_min_helper(max_key, closest_key, root->right, compare);
+ }
+}
- splaynode_t * splaynode;
-
- if (t == NULL)
- return NULL;
- if (t->root == NULL)
- return NULL;
-
- splaynode = t->root;
-
- while (splaynode->left != NULL)
- splaynode= splaynode->left;
-
- return splaynode->data;
+ splaynode_t * splaynode;
+
+ if (t == NULL)
+ return NULL;
+ if (t->root == NULL)
+ return NULL;
+
+ splaynode = t->root;
+
+ while (splaynode->left != NULL)
+ splaynode= splaynode->left;
+
+ return splaynode->data;
- splaynode_t * splaynode;
-
- if (t == NULL)
- return NULL;
- if (t->root == NULL)
- return NULL;
-
- splaynode = t->root;
-
- while (splaynode->right != NULL) {
- printf("data:%d\n", *(int*)splaynode->key);
- splaynode = splaynode->right;
- }
- return splaynode->data;
+ splaynode_t * splaynode;
+
+ if (t == NULL)
+ return NULL;
+ if (t->root == NULL)
+ return NULL;
+
+ splaynode = t->root;
+
+ while (splaynode->right != NULL) {
+ printf("data:%d\n", *(int*)splaynode->key);
+ splaynode = splaynode->right;
+ }
+ return splaynode->data;