/*---------------------------------------------------------------------------- * RumAVL - Threaded AVL Tree Implementation * * Copyright (c) 2005-2007 Jesse Long * All rights reserved. * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: * * 1. The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * 2. The origin of the Software must not be misrepresented; you must not * claim that you wrote the original Software. * 3. Altered source versions of the Software must be plainly marked as * such, and must not be misrepresented as being the original Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER * DEALINGS IN THE SOFTWARE. *--------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------- * Although not required by the license, I would appreciate it if you would * send me a mail notifying me of bugfixes and enhancements you make to this * code. My email address is *--------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------- * DEVELOPEMENT NOTES * * Links * Each node has two links, link[0] is the left child, and link[1] is the * right child. When a link points to a node that is actually below it in * the BST, the respective thread flag is marked 0. When the link is a * thread, the respective thread flag is marked 1, or 2 if the thread is * to the opposite edge of the BST. * * Direction * In RumAVL we use the numbers -1 (RUMAVL_DESC) and +1 (RUMAVL_ASC) to * indicate direction, where -1 (RUMAVL_DESC) means left or descending in * value, and +1 (RUMAVL_ASC) means right or ascending in value. * * Threads * In RumAVL, the threads (non-bst links of leaves) are implemented in a * sort of circular list. It is important to note that you cannot go * through the entire list by following the same link, as you would when * going through a linked list. Draw an example threaded AVL tree on paper * and see why. * *--------------------------------------------------------------------------*/ #include #include #include "rumavl.h" /* For memory allocation debugging #ifdef USE_MEMBUG #define MEMBUG_DEFINES #include #endif */ /***************************************************************************** * * MACROS - to make readability better * ****************************************************************************/ /* Link numbers */ #define LEFT (0) #define RIGHT (1) /* Direction to link no, expects RUMAVL_DESC or RUMAVL_ASC */ #define LINK_NO(i) (((i) + 1) / 2) /* -1 => 0; 1 => 1 */ /* Get opposite link number, expects LEFT or RIGHT */ #define OTHER_LINK(i) ((i) ^ 1) /* 1 => 0; 0 => 1 */ /* link no to direction, expects LEFT or RIGHT */ #define DIR_NO(i) (((i) * 2) - 1) /* 0 => -1; 1 => 1 */ /* opposite direction, expects RUMAVL_DESC or RUMAVL_ASC */ #define OTHER_DIR(i) ((i) * -1) /* -1 => 1; 1 => -1 */ /* Memory allocation functions */ #define mem_alloc(tree, bytes) mem_mgr((tree), NULL, (bytes)) #define mem_free(tree, ptr) mem_mgr((tree), (ptr), 0) #define mem_relloc(tree, ptr, bytes) mem_mgr((tree), (ptr), (bytes)) /***************************************************************************** * * DATA TYPES * ****************************************************************************/ /* * RUMAVL - the handle on the tree * * All settings for a tree are in the RUMAVL object, including memory * management, delete and overwrite callback functions, and the record * comparison function pointer. */ struct rumavl { RUMAVL_NODE *root; /* root node in tree */ size_t reclen; /* length of records */ int (*cmp)(const void *, /* function to compare records */ const void *, size_t, void *); int (*owcb)(RUMAVL *, RUMAVL_NODE *, void *, const void *, void *); int (*delcb)(RUMAVL *, RUMAVL_NODE *, void *, void *); void *(*alloc)(void *, size_t, void *); void *udata; /* user data for callbacks */ }; /* * RUMAVL_NODE - the node structure * * RUMAVL_NODE's contain all information about a specific node, including * links to the right and left children of the node, and flags (thread) * indicating whether or not the links are threads or not, and the balance * factor of the node. * * The record associated with each node is allocated along with the node, * and can be found directly after the node, by using the NODE_REC() macro. */ struct rumavl_node { RUMAVL_NODE *link[2]; /* links to child nodes */ char thread[2]; /* flags for links, normal link or thread? */ signed char balance; /* balance factor for node */ void *rec; #define NODE_REC(node) ((node)->rec) }; /* * RUMAVL_STACK - a stack of nodes forming a path to a node * * RUMAVL_STACK's are used while deleting and inserting nodes, where effects * could be felt by all parents of the node. RUMAVL_STACK's are implemented * in a singly linked list. This is a change from the method used by most AVL * trees, where a static array node pointers are allocated. Linked lists allow * fo an unlimited height in the AVL tree. * * node is a pointer to the parent node's pointer to the node in question. * dir is the direction of the descent from this node. */ typedef struct rumavl_stack RUMAVL_STACK; struct rumavl_stack { RUMAVL_STACK *next; RUMAVL_NODE **node; int dir; }; /* various other RumAVL specific structs defined in rumavl.h */ /***************************************************************************** * * FORWARD DECLERATIONS * ****************************************************************************/ static RUMAVL_NODE *seq_next (RUMAVL_NODE *node, int dir); static RUMAVL_NODE *node_new(RUMAVL *tree, const void *record); static void node_destroy (RUMAVL *tree, RUMAVL_NODE *node); static int stack_push (RUMAVL *tree, RUMAVL_STACK **stack, RUMAVL_NODE **node, int dir); static void stack_destroy(RUMAVL *tree, RUMAVL_STACK *stack); static void stack_update(RUMAVL *tree, RUMAVL_STACK *stack, signed char diff); static signed char balance (RUMAVL_NODE **node, int dir); static signed char rotate (RUMAVL_NODE **node, int dir); static void *mem_mgr (RUMAVL *tree, void *ptr, size_t size); static int rec_cmp (RUMAVL *tree, const void *reca, const void *recb); static int my_cmp (const void *a, const void *b, size_t n, void *udata); static int insert_cb (RUMAVL *t, RUMAVL_NODE *n, void *r1, const void *r2, void *udata); /***************************************************************************** * * PUBLIC FUNCTIONS * ****************************************************************************/ /*---------------------------------------------------------------------------- * rumavl_new - allocates a new RUMAVL object, and initialises it. This is the * only time the user gets to set the record length and record comparison * function, to avoid data loss. *--------------------------------------------------------------------------*/ RUMAVL *rumavl_new (size_t reclen, int (*cmp)(const void *, const void *, size_t, void *), void *(*alloc)(void *, size_t, void *), void *udata) { RUMAVL *tree; if (reclen < 1) return NULL; if (alloc == NULL) tree = malloc(sizeof(RUMAVL)); else tree = alloc(NULL, sizeof(RUMAVL), udata); if (tree == NULL) return NULL; tree->root = NULL; tree->owcb = NULL; tree->delcb = NULL; tree->alloc = alloc; tree->reclen = reclen; tree->udata = udata; if (cmp == NULL) tree->cmp = my_cmp; else tree->cmp = cmp; return tree; } /*---------------------------------------------------------------------------- * rumavl_destroy - cleanly frees all memory used by the RUMAVL, as well as * all nodes. All nodes are passed to the delete callback function in case the * user has a special way of destroying nodes. The return value of the delete * callback function is ignored, because once we start destroying we cant * simply undestroy half the nodes. *--------------------------------------------------------------------------*/ void rumavl_destroy (RUMAVL *tree) { RUMAVL_NODE *node, *tmp; if (tree->root != NULL){ /* walk through tree deleting all */ node = tree->root; while (node->thread[LEFT] == 0) /* move to bottom left most node */ node = node->link[LEFT]; while (node != NULL){ tmp = seq_next(node, RUMAVL_ASC); if (tree->delcb != NULL){ tree->delcb(tree, node, NODE_REC(node), tree->udata); } node_destroy(tree, node); node = tmp; } } if (tree->alloc == NULL) free(tree); else tree->alloc(tree, 0, tree->udata); } /*--------------------------------------------------------------------------- * rumavl_udata - get a pointer to the tree's user pointer *-------------------------------------------------------------------------*/ void **rumavl_udata (RUMAVL *tree) { return &tree->udata; } int (**rumavl_owcb(RUMAVL *tree))(RUMAVL *, RUMAVL_NODE *, void *, const void *, void *) { return &tree->owcb; } int (**rumavl_delcb(RUMAVL *tree))(RUMAVL *, RUMAVL_NODE *, void *, void *) { return &tree->delcb; } /*---------------------------------------------------------------------------- * rumavl_set - set a node, overwriting if necessary, or creating if the node * does not exist *--------------------------------------------------------------------------*/ int rumavl_set (RUMAVL *tree, const void *record) { RUMAVL_NODE **node, *tmp; RUMAVL_STACK *stack; int ln; if (tree->root == NULL){ /* This is the first node in the tree */ if ((tree->root = node_new(tree, record)) == NULL) return RUMAVL_ERR_NOMEM; tree->root->link[LEFT] = tree->root; tree->root->link[RIGHT] = tree->root; tree->root->thread[LEFT] = 2; tree->root->thread[RIGHT] = 2; return 0; } /* Since the tree is not empty, we must descend towards the nodes ideal * possition, and we may even find an existing node with the same record. * We keep a list parents for the eventual node position, because these * parents may become inbalanced by a new insertion. */ stack = NULL; node = &tree->root; for (;;){ if ((ln = rec_cmp(tree, record, NODE_REC(*node))) == 0){ /* OK, we found the exact node we wish to set, and we now * overwrite it. No change happens to the tree structure */ stack_destroy(tree, stack); if (tree->owcb != NULL && (ln = tree->owcb(tree, *node, NODE_REC(*node), record, tree->udata)) != 0){ return ln; } memcpy(NODE_REC(*node), record, tree->reclen); return 0; } /* *node is not the node we seek */ if (stack_push(tree, &stack, node, ln)){ stack_destroy(tree, stack); return RUMAVL_ERR_NOMEM; } ln = LINK_NO(ln); if ((*node)->thread[ln] > 0){ /* This is as close to the correct node as we can get. We will * now break and add the new node as a leaf */ break; } node = &(*node)->link[ln]; } /* we have reached a leaf, add new node here */ if ((tmp = node_new(tree, record)) == NULL){ stack_destroy(tree, stack); return RUMAVL_ERR_NOMEM; } /* new child inherits parent thread */ tmp->link[ln] = (*node)->link[ln]; tmp->thread[ln] = (*node)->thread[ln]; if (tmp->thread[ln] == 2) tmp->link[ln]->link[OTHER_LINK(ln)] = tmp; tmp->link[OTHER_LINK(ln)] = *node; tmp->thread[OTHER_LINK(ln)] = 1; (*node)->link[ln] = tmp; (*node)->thread[ln] = 0; /* all parentage is now one level heavier - balance where necessary */ stack_update(tree, stack, +1); return 0; } /*---------------------------------------------------------------------------- * rumavl_insert - like rumavl_set, but only works if the node does not * exist. Temporarily replaces overwrite callback with a function that * always prevents overwrite, and calls rumavl_set() *--------------------------------------------------------------------------*/ int rumavl_insert (RUMAVL *tree, const void *record) { int retv; int (*tmp)(RUMAVL *, RUMAVL_NODE *, void *, const void *, void *); tmp = tree->owcb; tree->owcb = insert_cb; retv = rumavl_set(tree, record); tree->owcb = tmp; return retv; } /*---------------------------------------------------------------------------- * rumavl_delete - deletes a node. Beware! this function is the worst part of * the library. Think (and draw pictures) when you edit this function. *--------------------------------------------------------------------------*/ int rumavl_delete (RUMAVL *tree, const void *record) { RUMAVL_NODE **node, *tmpnode; RUMAVL_STACK *stack; int dir, ln; if (tree->root == NULL) /* tree is empty */ return RUMAVL_ERR_NOENT; stack = NULL; node = &tree->root; /* Find desired node */ while ((dir = rec_cmp(tree, record, NODE_REC(*node))) != 0){ if (stack_push(tree, &stack, node, dir) != 0) goto nomemout; if ((*node)->thread[LINK_NO(dir)] > 0){ /* desired node does not exist */ stack_destroy(tree, stack); return RUMAVL_ERR_NOENT; } node = &(*node)->link[LINK_NO(dir)]; } /* OK, we got the node to be deleted, now get confirmation from user */ if (tree->delcb != NULL && (ln = tree->delcb(tree, *node, NODE_REC(*node), tree->udata)) != 0){ stack_destroy(tree, stack); return ln; } if ((*node)->thread[LEFT] > 0){ if ((*node)->thread[RIGHT] > 0){ /* ooh look, we're a leaf */ tmpnode = *node; if (stack != NULL){ /* This node has a parent, which will need to take over a * thread from the node being deleted. First we work out * which (left/right) child we are of parent, then give * parent the respective thread. If the thread destination * points back to us (edge of tree thread), update it to * point to our parent. */ ln = LINK_NO(stack->dir); (*stack->node)->link[ln] = tmpnode->link[ln]; (*stack->node)->thread[ln] = tmpnode->thread[ln]; if ((*stack->node)->thread[ln] == 2) (*stack->node)->link[ln]->link[OTHER_LINK(ln)] = *stack->node; }else{ /* * the only time stack will == NULL is when we are * deleting the root of the tree. We already know that * this is a leaf, so we will be leaving the tree empty. */ tree->root = NULL; } node_destroy(tree, tmpnode); }else{ /* *node has only one child, and can be pruned by replacing * *node with its only child. This block of code and the next * should be identical, except that all directions and link * numbers are opposite. * * Let node being deleted = DELNODE for this comment. * DELNODE only has one child (the right child). The left * most descendant of DELNODE will have a thread (left thread) * pointing to DELNODE. This thread must be updated to point * to the node currently pointed to by DELNODE's left thread. * * DELNODE's left thread may point to the opposite edge of the * BST. In this case, the destination of the thread will have * a thread back to DELNODE. This will need to be updated to * point back to the leftmost descendant of DELNODE. */ tmpnode = *node; /* node being deleted */ *node = (*node)->link[RIGHT]; /* right child */ /* find left most descendant */ while ((*node)->thread[LEFT] == 0) node = &(*node)->link[LEFT]; /* inherit thread from node being deleted */ (*node)->link[LEFT] = tmpnode->link[LEFT]; (*node)->thread[LEFT] = tmpnode->thread[LEFT]; /* update reverse thread if necessary */ if ((*node)->thread[LEFT] == 2) (*node)->link[LEFT]->link[RIGHT] = *node; node_destroy(tree, tmpnode); } }else if ((*node)->thread[RIGHT] > 0){ /* see above */ tmpnode = *node; *node = (*node)->link[LEFT]; while ((*node)->thread[RIGHT] == 0) node = &(*node)->link[RIGHT]; (*node)->link[RIGHT] = tmpnode->link[RIGHT]; (*node)->thread[RIGHT] = tmpnode->thread[RIGHT]; if ((*node)->thread[RIGHT] == 2) (*node)->link[RIGHT]->link[LEFT] = *node; node_destroy(tree, tmpnode); }else{ /* Delete a node with children on both sides. We do this by replacing * the node to be deleted (delnode) with its inner most child * on the heavier side (repnode). This in place replacement is quicker * than the previously used method of rotating delnode until it is a * (semi) leaf. * * At this point node points to delnode's parent's link to delnode. */ RUMAVL_NODE *repnode, *parent; int outdir, outln; /* find heaviest subtree */ if ((*node)->balance > 0){ outdir = +1; /* outter direction */ dir = -1; /* inner direction */ outln = 1; /* outer link number */ ln = 0; /* inner link number */ }else{ outdir = -1; /* same as above, but opposite subtree */ dir = +1; outln = 0; ln = 1; } /* Add node to be deleted to the list of nodes to be rebalanced. * Rememer that the replacement node will actually be acted apon, * and that the replacement node should feel the effect of its own * move */ if (stack_push(tree, &stack, node, outdir) != 0) goto nomemout; parent = *node; repnode = parent->link[outln]; if (repnode->thread[ln] != 0){ /* repnode inherits delnode's lighter tree, and balance, and gets * balance readjusted below */ repnode->link[ln] = (*node)->link[ln]; repnode->thread[ln] = (*node)->thread[ln]; repnode->balance = (*node)->balance; }else{ /* Now we add delnodes direct child to the list of "to update". * We pass a pointer to delnode's link to its direct child to * stack_push(), but that pointer is invalid, because when * stack_update() tries to access the link, delnode would have * been destroyed. So, we remember the stack position at which * we passed the faulty pointer to stack_push, and update its * node pointer when we find repnode to point to repnodes * link on the same side */ RUMAVL_STACK *tmpstack; if (stack_push(tree, &stack, &parent->link[outln], dir) != 0) goto nomemout; tmpstack = stack; parent = repnode; repnode = repnode->link[ln]; /* move towards the innermost child of delnode */ while (repnode->thread[ln] == 0){ if (stack_push(tree, &stack, &parent->link[ln], dir) != 0) goto nomemout; parent = repnode; repnode = repnode->link[ln]; } if (repnode->thread[outln] == 0){ /* repnode's parent inherits repnodes only child */ parent->link[ln] = repnode->link[outln]; }else{ /* parent already has a link to repnode, but it must now be * marked as a thread */ parent->thread[ln] = 1; } repnode->link[0] = (*node)->link[0]; repnode->thread[0] = (*node)->thread[0]; repnode->link[1] = (*node)->link[1]; repnode->thread[1] = (*node)->thread[1]; repnode->balance = (*node)->balance; /* see comment above */ tmpstack->node = &repnode->link[outln]; } node_destroy(tree, *node); *node = repnode; /* innermost child in lighter tree has an invalid thread to delnode, * update it to point to repnode */ repnode = seq_next(repnode, dir); repnode->link[outln] = *node; } /* update parents' balances */ stack_update(tree, stack, -1); return 0; nomemout: stack_destroy(tree, stack); return RUMAVL_ERR_NOMEM; } /*---------------------------------------------------------------------------- * rumavl_find * * Returns a pointer to the record that matches "record". *--------------------------------------------------------------------------*/ void *rumavl_find (RUMAVL *tree, const void *find) { void *record; rumavl_node_find(tree, find, &record); return record; } void *(**rumavl_alloc(RUMAVL *tree))(void *ptr, size_t size, void *udata) { return &tree->alloc; } /*---------------------------------------------------------------------------- * rumavl_record_size - returns size of all records in a tree *--------------------------------------------------------------------------*/ size_t rumavl_record_size (RUMAVL *tree) { return tree->reclen; } /*---------------------------------------------------------------------------- * rumavl_node_find * * Returns a pointer to the node that matches "record". *--------------------------------------------------------------------------*/ RUMAVL_NODE *rumavl_node_find (RUMAVL *tree, const void *find, void **record) { RUMAVL_NODE *node; int ln; if (find == NULL || tree->root == NULL) goto fail; node = tree->root; for (;;){ if ((ln = rec_cmp(tree, find, NODE_REC(node))) == 0){ if (record != NULL) *record = NODE_REC(node); return node; } ln = LINK_NO(ln); if (node->thread[ln] > 0) break; node = node->link[ln]; } /* we didn't find the desired node */ fail: if (record != NULL) *record = NULL; return NULL; } /*---------------------------------------------------------------------------- * rumavl_node_next - find next node *--------------------------------------------------------------------------*/ RUMAVL_NODE *rumavl_node_next (RUMAVL *tree, RUMAVL_NODE *node, int dir, void **record) { /* make sure `dir' is either RUMAVL_ASC or RUMAVL_DESC */ if (dir == 0) goto fail; else if (dir > 0) dir = RUMAVL_ASC; else dir = RUMAVL_DESC; /* if node is uninitialised, start with first possible node in `dir' * direction */ if (node == NULL){ /* unless the tree is empty of course */ if (tree->root == NULL) goto fail; dir = OTHER_LINK(LINK_NO(dir)); node = tree->root; while (node->thread[dir] == 0){ node = node->link[dir]; } goto found; } if ((node = seq_next(node, dir)) == NULL) goto fail; /* fall through */ found: if (record != NULL) *record = NODE_REC(node); return node; fail: if (record != NULL) *record = NULL; return NULL; } /*---------------------------------------------------------------------------- * rumavl_node_record - returns a pointer to the record stored in a node *--------------------------------------------------------------------------*/ void *rumavl_node_record (RUMAVL_NODE *node) { return NODE_REC(node); } /*---------------------------------------------------------------------------- * rumavl_foreach - loop through entire tree, using temporary iterator *--------------------------------------------------------------------------*/ extern int rumavl_foreach (RUMAVL *tree, int dir, int (*cbfn)(RUMAVL *, void *, void *), void *udata) { RUMAVL_NODE *node; int retv; void *record; if (cbfn == NULL) return RUMAVL_ERR_INVAL; retv = RUMAVL_ERR_NOENT; node = NULL; while ((node = rumavl_node_next(tree, node, dir, &record)) != NULL){ if ((retv = cbfn(tree, record, udata)) != 0) break; } return retv; } /*---------------------------------------------------------------------------- * rumavl_strerror - return string description of RumAVL error code *--------------------------------------------------------------------------*/ const char *rumavl_strerror (int errno) { switch (errno){ case 0: return "Operation successful"; case RUMAVL_ERR_INVAL: return "Invalid argument to function"; case RUMAVL_ERR_NOMEM: return "Insufficient memory to complete operation"; case RUMAVL_ERR_NOENT: return "Entry does not exist"; case RUMAVL_ERR_EORNG: return "No more entries in range"; case RUMAVL_ERR_EXIST: return "Entry already exists"; } return "UNKNOWN ERROR"; } /***************************************************************************** * * PRIVATE FUNCTIONS * ****************************************************************************/ /*---------------------------------------------------------------------------- * insert_cb - used by rumavl_insert() to disallow any overwriting by * rumavl_set() *--------------------------------------------------------------------------*/ static int insert_cb (RUMAVL *t, RUMAVL_NODE *n, void *r1, const void *r2, void *udata) { (void) t; (void) r1; (void) r2; (void) udata; (void) n; return RUMAVL_ERR_EXIST; } /*---------------------------------------------------------------------------- * seq_next - return a pointer to the next node in sequence *--------------------------------------------------------------------------*/ static RUMAVL_NODE *seq_next (RUMAVL_NODE *node, int dir) { int ln; ln = LINK_NO(dir); if (node->thread[ln] == 2){ return NULL; }else if (node->thread[ln] == 1){ return node->link[ln]; } node = node->link[ln]; ln = OTHER_LINK(ln); while (node->thread[ln] == 0){ node = node->link[ln]; } return node; } /*---------------------------------------------------------------------------- * node_new - create a new node. MUST update link[] and thread[] after calling * this function *--------------------------------------------------------------------------*/ static RUMAVL_NODE *node_new(RUMAVL *tree, const void *record) { RUMAVL_NODE *node; if ((node = mem_alloc(tree, sizeof(RUMAVL_NODE))) == NULL) return NULL; if ((node->rec = mem_alloc(tree, tree->reclen)) == NULL){ mem_free(tree, node); return NULL; } memcpy(node->rec, record, tree->reclen); node->balance = 0; node->link[0] = NULL; node->link[1] = NULL; node->thread[0] = 0; node->thread[1] = 0; return node; } /*---------------------------------------------------------------------------- * node_destroy - cleanly destroy node *--------------------------------------------------------------------------*/ static void node_destroy (RUMAVL *tree, RUMAVL_NODE *node) { mem_free(tree, node); } /*---------------------------------------------------------------------------- * stack_push - push a node entry onto stack, for rumavl_set() and * rumavl_delete(). If this is the first entry, *stack should == NULL *--------------------------------------------------------------------------*/ static int stack_push(RUMAVL *tree, RUMAVL_STACK **stack, RUMAVL_NODE **node, int dir) { RUMAVL_STACK *tmp; if ((tmp = mem_alloc(tree, sizeof(RUMAVL_STACK))) == NULL) return -1; tmp->next = *stack; *stack = tmp; tmp->node = node; tmp->dir = dir; return 0; } /*---------------------------------------------------------------------------- * stack_destroy - free up a stack *--------------------------------------------------------------------------*/ static void stack_destroy(RUMAVL *tree, RUMAVL_STACK *stack) { RUMAVL_STACK *tmp; while (stack != NULL){ tmp = stack; stack = stack->next; mem_free(tree, tmp); } } /*---------------------------------------------------------------------------- * stack_update - goes up stack readjusting balance as needed. This function * serves as a testiment to the philosophy of commenting while you code, 'cos * hell if I can remember how I got to this. I think is has something to do * with the varying effects on tree height, depending on exactly which sub * tree, or sub-sub tree was modified. TODO study and comment *--------------------------------------------------------------------------*/ static void stack_update(RUMAVL *tree, RUMAVL_STACK *stack, signed char diff) { RUMAVL_STACK *tmpstack; /* if diff becomes 0, we quit, because no further change to ancestors * can be made */ while (stack != NULL && diff != 0){ signed char ob, nb; ob = (*stack->node)->balance; (*stack->node)->balance += diff * (signed char)stack->dir; nb = (*stack->node)->balance; if (diff < 0){ if (stack->dir == -1 && ob < 0){ if (nb > 0) nb = 0; diff = (nb - ob) * -1; }else if (stack->dir == 1 && ob > 0){ if (nb < 0) nb = 0; diff = nb - ob; }else{ diff = 0; } }else{ if (stack->dir == -1 && nb < 0){ if (ob > 0) ob = 0; diff = (nb - ob) * -1; }else if (stack->dir == 1 && nb > 0){ if (ob < 0) ob = 0; diff = nb - ob; }else{ diff = 0; } } while ((*stack->node)->balance > 1){ diff += balance(stack->node, -1); } while ((*stack->node)->balance < -1){ diff += balance(stack->node, 1); } tmpstack = stack; stack = stack->next; mem_free(tree, tmpstack); } /* we may exit early if diff becomes 0. We still need to free all stack * entries */ while (stack != NULL){ tmpstack = stack; stack = stack->next; mem_free(tree, tmpstack); } } /*---------------------------------------------------------------------------- * my_cmp - a wrapper around memcmp() for default record comparison function. *--------------------------------------------------------------------------*/ static int my_cmp (const void *a, const void *b, size_t n, void *udata) { (void) udata; return memcmp(a, b, n); } /*---------------------------------------------------------------------------- * rec_cmp - a wrapper around the record comparison function, that only * returns 0, RUMAVL_ASC or RUMAVL_DESC. *--------------------------------------------------------------------------*/ static int rec_cmp (RUMAVL *tree, const void *reca, const void *recb) { int retv; retv = tree->cmp(reca, recb, tree->reclen, tree->udata); if (retv < 0) return RUMAVL_DESC; if (retv > 0) return RUMAVL_ASC; return 0; } /*---------------------------------------------------------------------------- * Balance - rotate or double rotate as needed. Sometimes simply rotating a * tree is inefficient, as it leaves the tree as inbalanced as it was before * the rotate. To rectify this, we first rotate the heavier child so that the * heavier grandchild is on the outside, then rotate as per normal. * * TODO Check all callers, and make sure that they call this function sanely, * and then remove unnecessary checks. *--------------------------------------------------------------------------*/ static signed char balance (RUMAVL_NODE **node, int dir) { int ln; signed char retv; if (node == NULL || *node == NULL || (dir * dir) != 1) return 0; ln = OTHER_LINK(LINK_NO(dir)); /* link number of new root */ /* new root must exist */ if ((*node)->thread[ln] > 0) return 0; retv = 0; if ((*node)->link[ln]->balance == (char) dir && (*node)->link[ln]->thread[OTHER_LINK(ln)] == 0){ /* double rotate if inner grandchild is heaviest */ retv = rotate (&((*node)->link[ln]), OTHER_DIR(dir)); } return retv + rotate (node, dir); } /*---------------------------------------------------------------------------- * rotate * * rotates a tree rooted at *node. dir determines the direction of the rotate, * dir < 0 -> left rotate; dir >= 0 -> right rotate * * TODO How sure are we that all callers pass decent `dir' values? * TODO Restudy the tree height modification and balance factor algorithms, * and document them. *--------------------------------------------------------------------------*/ static signed char rotate (RUMAVL_NODE **node, int dir) { RUMAVL_NODE *tmp; signed char a, b, ad, bd, retv; int ln; /* force |dir| to be either -1 or +1 */ if (node == NULL || *node == NULL || (dir * dir) != 1) return 0; ln = LINK_NO(dir); ln = OTHER_LINK(ln); /* link number of new root */ /* new root must exist */ if ((*node)->thread[ln] > 0) return 0; /* calculate effect on tree height */ if ((dir == 1 && (*node)->balance < 0 && (*node)->link[0]->balance >= 0)|| (dir == -1 && (*node)->balance > 0 && (*node)->link[1]->balance <= 0)){ retv = 0; }else{ if (dir == 1){ if ((*node)->balance < -1) retv = -1; else if ((*node)->balance == -1) retv = 0; else retv = +1; }else{ if ((*node)->balance > 1) retv = -1; else if ((*node)->balance == 1) retv = 0; else retv = +1; } } /* rotate tree */ tmp = *node; *node = tmp->link[ln]; if ((*node)->thread[OTHER_LINK(ln)] > 0){ tmp->thread[ln] = 1; }else{ tmp->link[ln] = (*node)->link[OTHER_LINK(ln)]; tmp->thread[ln] = 0; } (*node)->link[OTHER_LINK(ln)] = tmp; (*node)->thread[OTHER_LINK(ln)] = 0; /* rebalance factors after rotate matrix */ a = tmp->balance; b = (*node)->balance; if (a > 0) ad = 1; else if (a < 0) ad = -1; else ad = 0; if (b > 0) bd = 1; else if (b < 0) bd = -1; else bd = 0; if (ad == OTHER_DIR(dir)){ if (bd == OTHER_DIR(dir)){ tmp->balance += (b * -1) + dir; if (tmp->balance * dir > 0) (*node)->balance = (tmp->balance - (b * -1)) + dir; else (*node)->balance += dir; }else{ tmp->balance += dir; (*node)->balance += dir; } }else{ if (bd == OTHER_DIR(dir)){ tmp->balance += (b * -1) + dir; (*node)->balance += dir + tmp->balance; }else{ tmp->balance += dir; (*node)->balance += dir + tmp->balance; } } return retv; } /*---------------------------------------------------------------------------- * mem_alloc * * default memory allocation function (malloc wrapper) *--------------------------------------------------------------------------*/ static void *mem_mgr (RUMAVL *tree, void *ptr, size_t size) { if (tree->alloc != NULL) return tree->alloc(ptr, size, tree->udata); return realloc(ptr, size); }