BattletechMUX: src/rbtree.c File Reference

00219 {
00220     rbtree_node *temp;
00221     temp = malloc(sizeof(struct rbtree_node_t));
00222     memset(temp, 0, sizeof(struct rbtree_node_t));
00223     temp->parent = parent;
00224     temp->key = key;
00225     temp->data = data;
00226     temp->count = 1;
00227     return temp;
00228 }

void * rb_delete	(	rbtree	,
		void *	key
	)

Definition at line 660 of file rbtree.c.

References rbtree_head_t::compare_function, rbtree_node_t::count, rbtree_node_t::data, rbtree_head_t::head, rbtree_node_t::key, rbtree_node_t::left, rb_find_successor_node(), rb_unlink_leaf(), rbtree_node_t::right, rbtree_head_t::size, and rbtree_head_t::token.

Referenced by auto_astar_generate_path(), comstar_remove_user_from_channel(), desc_delhash(), do_destroychannel(), hashdelete(), logcache_close(), nhashdelete(), and pcache_trim().

00661 {
00662     rbtree_node *node = NULL, *child = NULL, *tail;
00663     void *data;
00664     int compare_result;
00665 
00666     if(!bt->head) {
00667         return NULL;
00668     }
00669 
00670     node = bt->head;
00671     while (node != NULL) {
00672         compare_result = (*bt->compare_function) (key, node->key, bt->token);
00673         if(compare_result == 0) {
00674             break;
00675         } else if(compare_result < 0) {
00676             if(node->left != NULL) {
00677                 node = node->left;
00678             } else {
00679                 return NULL;
00680             }
00681         } else {
00682             if(node->right != NULL) {
00683                 node = node->right;
00684             } else {
00685                 return NULL;
00686             }
00687         }
00688     }
00689 
00690     if(node == NULL) {
00691         return node;
00692     }
00693 
00694     data = node->data;
00695     bt->size--;
00696 
00697     // XXX: handle deleting the head.
00698 
00699     if(node == bt->head && node->left == NULL && node->right == NULL) {
00700         bt->head = NULL;
00701         free(node);
00702         return data;
00703     }
00704 
00705     /* 
00706      * PROPERTY 3 OF RED BLACK TREES STATES:
00707      * 
00708      * Any two paths from a given node v down to a leaf node contain
00709      * the same number of black nodes.
00710      *
00711      * MEANING:
00712      * That all paths to all leaf nodes should contain the same
00713      * number of black nodes. Thus, we need to handle deleting a
00714      * black node in every situation, even if it is a leaf.
00715      */
00716 
00717     // our child has at most one child (or none.)
00718     if(node->left == NULL || node->right == NULL) {
00719         tail = node;
00720         while (tail) {
00721             tail->count--;
00722             tail = tail->parent;
00723         }
00724         rb_unlink_leaf(bt, node);
00725         free(node);
00726         return data;
00727     }
00728     // If we have full children, then we're guaranteed a successor
00729     // without empty children.
00730 
00731     child = rb_find_successor_node(node);
00732     tail = child;
00733     while (tail) {
00734         tail->count--;
00735         tail = tail->parent;
00736     }
00737     rb_unlink_leaf(bt, child);
00738 
00739     node->data = child->data;
00740     node->key = child->key;
00741 
00742     // XXX: finish delete
00743 
00744     free(child);
00745     return data;
00746 }

void rb_destroy ( rbtree )

Definition at line 186 of file rbtree.c.

References rbtree_head_t::head, rbtree_node_t::left, rbtree_node_t::parent, and rbtree_node_t::right.

Referenced by auto_astar_generate_path(), auto_gun_event(), auto_newautopilot(), auto_update_profile_event(), hashflush(), logcache_destruct(), newfreemech(), and nhashflush().

00187 {
00188     rbtree_node *node, *parent;
00189     node = bt->head;
00190 
00191     if(bt->head) {
00192         while (node != NULL) {
00193             if(node->left != NULL) {
00194                 node = node->left;
00195                 continue;
00196             } else if(node->right != NULL) {
00197                 node = node->right;
00198                 continue;
00199             } else {
00200                 parent = node->parent;
00201                 if(parent && parent->left == node)
00202                     parent->left = NULL;
00203                 else if(parent && parent->right == node)
00204                     parent->right = NULL;
00205                 else if(parent) {
00206                     fprintf(stderr, "serious braindamage.\n");
00207                     exit(1);
00208                 }
00209                 free(node);
00210                 node = parent;
00211             }
00212         }
00213     }
00214     free(bt);
00215     return;
00216 }

int rb_exists	(	rbtree	,
		void *	key
	)

Definition at line 446 of file rbtree.c.

References rbtree_head_t::compare_function, rbtree_head_t::head, rbtree_node_t::key, rbtree_node_t::left, rbtree_node_t::right, and rbtree_head_t::token.

Referenced by auto_astar_generate_path(), auto_gun_event(), comstar_add_user_to_channel(), comstar_find_channel_by_user_alias(), hashadd(), hashdelete(), logcache_open(), and nhashadd().

00447 {
00448     rbtree_node *node;
00449     int compare_result;
00450     if(!bt->head) {
00451         return 0;
00452     }
00453     node = bt->head;
00454     while (node != NULL) {
00455         compare_result = (*bt->compare_function) (key, node->key, bt->token);
00456         if(compare_result == 0) {
00457             return 1;
00458         } else if(compare_result < 0) {
00459             // Go Left
00460             if(node->left != NULL) {
00461                 node = node->left;
00462             } else {
00463                 return 0;
00464             }
00465         } else {
00466             if(node->right != NULL) {
00467                 node = node->right;
00468             } else {
00469                 return 0;
00470             }
00471         }
00472     }
00473     /* Shouldn't happen. */
00474     fprintf(stderr, "Serious fault in rbtree.c:rb_exists!\n");
00475     exit(1);
00476 }

void * rb_find	(	rbtree	,
		void *	key
	)

Definition at line 413 of file rbtree.c.

References rbtree_head_t::compare_function, rbtree_node_t::data, rbtree_head_t::head, rbtree_node_t::key, rbtree_node_t::left, rbtree_node_t::right, and rbtree_head_t::token.

Referenced by auto_astar_generate_path(), comstar_find_channel_by_name(), comstar_find_channel_by_user_alias(), comstar_find_user_channels(), comstar_remove_user_from_channel(), cque_find(), desc_addhash(), desc_delhash(), do_quitprog(), handle_prog(), hashfind(), hashrepl(), logcache_writelog(), nhashfind(), and pcache_find().

00414 {
00415     rbtree_node *node;
00416     int compare_result;
00417 
00418     if(!bt->head) {
00419         return NULL;
00420     }
00421     node = bt->head;
00422     while (node != NULL) {
00423         compare_result = (*bt->compare_function) (key, node->key, bt->token);
00424         if(compare_result == 0) {
00425             return node->data;
00426         } else if(compare_result < 0) {
00427             // Go Left
00428             if(node->left != NULL) {
00429                 node = node->left;
00430             } else {
00431                 return NULL;
00432             }
00433         } else {
00434             if(node->right != NULL) {
00435                 node = node->right;
00436             } else {
00437                 return NULL;
00438             }
00439         }
00440     }
00441     /* Shouldn't happen. */
00442     fprintf(stderr, "Serious fault in rbtree.c:rb_find!\n");
00443     exit(1);
00444 }

static rbtree_node* rb_find_maximum ( rbtree_node * node ) [static]

Definition at line 96 of file rbtree.c.

References rbtree_node_t::right.

Referenced by rb_search().

00097 {
00098     rbtree_node *child;
00099     child = node;
00100     if(!node)
00101         return NULL;
00102     while (child->right != NULL)
00103         child = child->right;
00104     return child;
00105 }

static rbtree_node* rb_find_minimum ( rbtree_node * node ) [static]

Definition at line 85 of file rbtree.c.

References rbtree_node_t::left.

Referenced by rb_search().

00086 {
00087     rbtree_node *child;
00088     child = node;
00089     if(!node)
00090         return NULL;
00091     while (child->left != NULL)
00092         child = child->left;
00093     return child;
00094 }

static rbtree_node* rb_find_predecessor_node ( rbtree_node * node ) [static]

Definition at line 130 of file rbtree.c.

References rbtree_node_t::left, rbtree_node_t::parent, and rbtree_node_t::right.

Referenced by rb_search().

00131 {
00132     rbtree_node *child, *parent;
00133     if(!node)
00134         return NULL;
00135     if(node->left != NULL) {
00136         child = node->left;
00137         while (child->right != NULL)
00138             child = child->right;
00139         return child;
00140     } else {
00141         child = node;
00142         parent = node->parent;
00143         while (parent != NULL && child == parent->left) {
00144             child = parent;
00145             parent = parent->parent;
00146         }
00147         return parent;
00148     }
00149     return NULL;
00150 }

static rbtree_node* rb_find_successor_node ( rbtree_node * node ) [static]

Definition at line 107 of file rbtree.c.

References rbtree_node_t::left, rbtree_node_t::parent, and rbtree_node_t::right.

Referenced by rb_delete(), and rb_search().

00108 {
00109     rbtree_node *child, *parent;
00110     if(!node)
00111         return NULL;
00112     if(node->right != NULL) {
00113         child = node->right;
00114         while (child->left != NULL) {
00115             child = child->left;
00116         }
00117         return child;
00118     } else {
00119         child = node;
00120         parent = node->parent;
00121         while (parent != NULL && child == parent->right) {
00122             child = parent;
00123             parent = child->parent;
00124         }
00125         return parent;
00126     }
00127     return NULL;
00128 }

void* rb_index	(	rbtree	bt,
		int	index
	)

Definition at line 895 of file rbtree.c.

References rbtree_node_t::count, rbtree_node_t::data, rbtree_head_t::head, rbtree_node_t::left, rbfail, and rbtree_node_t::right.

00896 {
00897     rbtree_node *iter;
00898     int leftcount;
00899     iter = bt->head;
00900 
00901     while (iter) {
00902         leftcount = (iter->left ? iter->left->count : 0);
00903 
00904         if(index == leftcount) {
00905             return iter->data;
00906         }
00907         if(index < leftcount) {
00908             iter = iter->left;
00909         } else {
00910             index -= leftcount + 1;
00911             iter = iter->right;
00912         }
00913     }
00914     rbfail("major braindamage.");
00915 }

rbtree rb_init	(	int()(void , void , void )	,
		void *
	)

Definition at line 71 of file rbtree.c.

References rbtree_head_t::compare_function, rbtree_head_t::size, and rbtree_head_t::token.

Referenced by auto_astar_generate_path(), auto_gun_event(), comstar_find_user_channels(), comstar_init(), cque_init(), do_createchannel(), hashflush(), hashinit(), logcache_init(), main(), nhashflush(), nhashinit(), and pcache_init().

00072 {
00073     rbtree temp;
00074 
00075     temp = malloc(sizeof(struct rbtree_head_t));
00076     if(temp == NULL)
00077         return NULL;
00078     memset(temp, 0, sizeof(struct rbtree_head_t));
00079     temp->compare_function = compare_function;
00080     temp->token = token;
00081     temp->size = 0;
00082     return temp;
00083 }

void rb_insert	(	rbtree	,
		void *	key,
		void *	data
	)

Definition at line 288 of file rbtree.c.

References rbtree_node_t::color, rbtree_head_t::compare_function, rbtree_node_t::count, rbtree_node_t::data, rbtree_head_t::head, rbtree_node_t::key, rbtree_node_t::left, NODE_BLACK, NODE_RED, rbtree_node_t::parent, rb_allocate(), rb_rotate_left(), rb_rotate_right(), rbtree_node_t::right, rbtree_head_t::size, and rbtree_head_t::token.

Referenced by auto_astar_generate_path(), auto_gun_event(), comstar_add_user_to_channel(), comstar_find_user_channels(), cque_find(), desc_addhash(), desc_delhash(), hashadd(), logcache_open(), nhashadd(), nhashrepl(), and pcache_find().

00289 {
00290     rbtree_node *node;
00291     rbtree_node *iter;
00292     int compare_result;
00293 
00294     if(!bt->head) {
00295         bt->head = rb_allocate(NULL, key, data);
00296         bt->size++;
00297         bt->head->color = NODE_BLACK;
00298         return;
00299     }
00300 
00301     node = bt->head;
00302     while (node != NULL) {
00303         compare_result = (*bt->compare_function) (key, node->key, bt->token);
00304         if(compare_result == 0) {
00305             // Key already exists, replace data.
00306             node->key = key;
00307             node->data = data;
00308             return;
00309         } else if(compare_result < 0) {
00310             // Go Left
00311             if(node->left != NULL) {
00312                 node = node->left;
00313             } else {
00314                 node->left = rb_allocate(node, key, data);
00315                 bt->size++;
00316                 node = node->left;
00317                 break;
00318             }
00319         } else {
00320             if(node->right != NULL) {
00321                 node = node->right;
00322             } else {
00323                 node->right = rb_allocate(node, key, data);
00324                 bt->size++;
00325                 node = node->right;
00326                 break;
00327             }
00328         }
00329     }
00330 
00331     iter = node->parent;
00332     while (iter) {
00333         iter->count++;
00334         iter = iter->parent;
00335     }
00336 
00337     node->color = NODE_RED;
00338     if(node->parent && node->parent->color == NODE_RED) {
00339         iter = node;
00340         while (iter != bt->head && iter->parent->parent
00341                 && iter->parent->color == NODE_RED) {
00342             bt->head->color = NODE_BLACK;
00343             if(iter->parent == iter->parent->parent->left) {
00344                 // parent is left child of grandparent
00345                 if(iter->parent->parent->right != NULL &&
00346                         iter->parent->parent->right->color == NODE_RED) {
00347                     // Case 1:
00348                     // The current node has a red uncle and it's parent is parent node is a 
00349                     // red left child. 
00350                     iter->parent->color = NODE_BLACK;
00351                     iter->parent->parent->color = NODE_RED;
00352                     if(iter->parent->parent->right)
00353                         iter->parent->parent->right->color = NODE_BLACK;
00354                     iter = iter->parent->parent;
00355                     continue;
00356                 } else {
00357                     // Case 2 or 3:
00358                     // The current node has a black uncle.
00359                     if(iter->parent->right == iter) {
00360                         // Case 2:
00361                         // The current node has a black uncle and is the right child
00362                         // of the parent. The parent is the red left child. The parent's
00363                         // sibling, the current node's uncle, is black.
00364                         rb_rotate_left(bt, iter->parent);
00365                         iter = iter->left;
00366                     }
00367                     // Case 3:
00368                     // The current node is a left child. It's parent is a red left child
00369                     // and has a black sibling. 
00370                     iter->parent->color = NODE_BLACK;
00371                     iter->parent->parent->color = NODE_RED;
00372                     rb_rotate_right(bt, iter->parent->parent);
00373                     break;
00374                 }
00375             } else {
00376                 // parent is right child of grandparent
00377                 if(iter->parent->parent->left != NULL &&
00378                         iter->parent->parent->left->color == NODE_RED) {
00379                     // Case 1:
00380                     // The current node has a red uncle and it's parent is parent node is a 
00381                     // red right child. 
00382                     iter->parent->color = NODE_BLACK;
00383                     iter->parent->parent->color = NODE_RED;
00384                     if(iter->parent->parent->left)
00385                         iter->parent->parent->left->color = NODE_BLACK;
00386                     iter = iter->parent->parent;
00387                     continue;
00388                 } else {
00389                     // Case 2 or 3:
00390                     // The current node has a black uncle.
00391                     if(iter->parent->left == iter) {
00392                         // Case 2:
00393                         // The current node has a black uncle and is the left child
00394                         // of the parent. The parent is the red right child. The parent's
00395                         // sibling, the current node's uncle, is black.
00396                         rb_rotate_right(bt, iter->parent);
00397                         iter = iter->right;
00398                     }
00399                     // Case 3:
00400                     // The current node is a right child. It's parent is a red right child
00401                     // and has a black sibling. 
00402                     iter->parent->color = NODE_BLACK;
00403                     iter->parent->parent->color = NODE_RED;
00404                     rb_rotate_left(bt, iter->parent->parent);
00405                     continue;
00406                 }
00407             }
00408         }
00409     }
00410     bt->head->color = NODE_BLACK;
00411 }

void rb_release	(	rbtree	bt,
		void()(void , void , void )	release,
		void *	arg
	)

Definition at line 152 of file rbtree.c.

References rbtree_node_t::data, rbtree_head_t::head, rbtree_node_t::key, rbtree_node_t::left, rbtree_node_t::parent, and rbtree_node_t::right.

Referenced by auto_astar_generate_path().

00154 {
00155     rbtree_node *node, *parent;
00156     node = bt->head;
00157 
00158     if(bt->head) {
00159         while (node != NULL) {
00160             if(node->left != NULL) {
00161                 node = node->left;
00162                 continue;
00163             } else if(node->right != NULL) {
00164                 node = node->right;
00165                 continue;
00166             } else {
00167                 parent = node->parent;
00168                 if(parent && parent->left == node)
00169                     parent->left = NULL;
00170                 else if(parent && parent->right == node)
00171                     parent->right = NULL;
00172                 else if(parent) {
00173                     fprintf(stderr, "serious braindamage.\n");
00174                     exit(1);
00175                 }
00176                 release(node->key, node->data, arg);
00177                 free(node);
00178                 node = parent;
00179             }
00180         }
00181     }
00182     free(bt);
00183     return;
00184 }

static void rb_rotate_left	(	rbtree	bt,
		rbtree_node *	pivot
	)			`[static]`

Definition at line 259 of file rbtree.c.

References rbtree_node_t::count, rbtree_head_t::head, rbtree_node_t::left, rbtree_node_t::parent, and rbtree_node_t::right.

Referenced by rb_insert(), and rb_unlink_leaf().

00260 {
00261     rbtree_node *child;
00262 
00263     if(!pivot || !pivot->right)
00264         return;
00265     child = pivot->right;
00266 
00267     pivot->right = child->left;
00268     if(child->left != NULL)
00269         child->left->parent = pivot;
00270 
00271     child->parent = pivot->parent;
00272 
00273     if(pivot->parent) {
00274         if(pivot->parent->right == pivot)
00275             pivot->parent->right = child;
00276         else
00277             pivot->parent->left = child;
00278     } else
00279         bt->head = child;
00280     child->left = pivot;
00281     pivot->parent = child;
00282     child->count = pivot->count;
00283     pivot->count =
00284         1 + (pivot->left ? pivot->left->count : 0) +
00285         (pivot->right ? pivot->right->count : 0);
00286 }

static void rb_rotate_right	(	rbtree	bt,
		rbtree_node *	pivot
	)			`[static]`

Definition at line 230 of file rbtree.c.

References rbtree_node_t::count, rbtree_head_t::head, rbtree_node_t::left, rbtree_node_t::parent, and rbtree_node_t::right.

Referenced by rb_insert(), and rb_unlink_leaf().

00231 {
00232     rbtree_node *child;
00233 
00234     if(!pivot || !pivot->left)
00235         return;
00236     child = pivot->left;
00237 
00238     pivot->left = child->right;
00239     if(child->right != NULL)
00240         child->right->parent = pivot;
00241 
00242     child->parent = pivot->parent;
00243 
00244     if(pivot->parent) {
00245         if(pivot->parent->left == pivot)
00246             pivot->parent->left = child;
00247         else
00248             pivot->parent->right = child;
00249     } else
00250         bt->head = child;
00251     child->right = pivot;
00252     pivot->parent = child;
00253     child->count = pivot->count;
00254     pivot->count =
00255         1 + (pivot->left ? pivot->left->count : 0) +
00256         (pivot->right ? pivot->right->count : 0);
00257 }

void * rb_search	(	rbtree	,
		int	,
		void *
	)

Definition at line 794 of file rbtree.c.

References rbtree_head_t::compare_function, rbtree_node_t::data, rbtree_head_t::head, rbtree_node_t::key, rbtree_node_t::left, rb_find_maximum(), rb_find_minimum(), rb_find_predecessor_node(), rb_find_successor_node(), rbtree_node_t::right, SEARCH_EQUAL, SEARCH_FIRST, SEARCH_GT, SEARCH_GTEQ, SEARCH_LAST, SEARCH_LT, SEARCH_LTEQ, SEARCH_NEXT, SEARCH_PREV, and rbtree_head_t::token.

Referenced by auto_astar_generate_path(), auto_gun_event(), do_destroychannel(), hash_firstentry(), hash_firstkey(), hash_nextentry(), and hash_nextkey().

00795 {
00796     rbtree_node *node, *last;
00797     int compare_result;
00798     int found = 0;
00799 
00800     if(!bt->head) {
00801         return NULL;
00802     }
00803 
00804     if(method == SEARCH_FIRST) {
00805         node = rb_find_minimum(bt->head);
00806         return node->data;
00807     } else if(method == SEARCH_LAST) {
00808         node = rb_find_maximum(bt->head);
00809         return node->data;
00810     }
00811 
00812     node = bt->head;
00813     while (node != NULL) {
00814         last = node;
00815         compare_result = (*bt->compare_function) (key, node->key, bt->token);
00816         if(compare_result == 0) {
00817             found = 1;
00818             break;
00819         } else if(compare_result < 0) {
00820             // Go Left
00821             if(node->left != NULL) {
00822                 node = node->left;
00823             } else {
00824                 node = NULL;
00825                 break;
00826             }
00827         } else {
00828             if(node->right != NULL) {
00829                 node = node->right;
00830             } else {
00831                 node = NULL;
00832                 break;
00833             }
00834         }
00835     }
00836 
00837     if(found
00838             && (method == SEARCH_EQUAL || method == SEARCH_LTEQ
00839                 || method == SEARCH_GTEQ)) {
00840         if(node)
00841             return node->data;
00842         else
00843             return NULL;
00844     }
00845 
00846     if(!found
00847             && (method == SEARCH_EQUAL || method == SEARCH_NEXT
00848                 || method == SEARCH_PREV)) {
00849         return NULL;
00850     }
00851 
00852     if(method == SEARCH_GTEQ || (!found && method == SEARCH_GT)) {
00853         if(compare_result > 0) {
00854             node = rb_find_successor_node(last);
00855             if(node)
00856                 return node->data;
00857             else
00858                 return node;
00859         } else {
00860             if(last)
00861                 return last->data;
00862             else
00863                 return last;
00864         }
00865     }
00866 
00867     if(method == SEARCH_LTEQ || (!found && method == SEARCH_LT)) {
00868         if(compare_result < 0) {
00869             node = rb_find_predecessor_node(last);
00870             return node->data;
00871         } else {
00872             return last->data;
00873         }
00874     }
00875 
00876     if(method == SEARCH_NEXT || (found && method == SEARCH_GT)) {
00877         node = rb_find_successor_node(node);
00878         if(node)
00879             return node->data;
00880         else
00881             return node;
00882     }
00883 
00884     if(method == SEARCH_PREV || (found && method == SEARCH_LT)) {
00885         node = rb_find_predecessor_node(node);
00886         if(node)
00887             return node->data;
00888         else
00889             return node;
00890     }
00891 
00892     return NULL;
00893 }

unsigned int rb_size ( rbtree )

Definition at line 789 of file rbtree.c.

References rbtree_head_t::size.

Referenced by auto_astar_generate_path(), auto_gun_event(), cque_dump_restart(), do_destroychannel(), hashinfo(), logcache_list(), and mmdb_db_write().

00790 {
00791     return bt->size;
00792 }

static void rb_unlink_leaf	(	rbtree	bt,
		rbtree_node *	leaf
	)			`[static]`

Definition at line 481 of file rbtree.c.

References rbtree_node_t::color, rbtree_head_t::head, rbtree_node_t::left, NODE_BLACK, NODE_RED, rbtree_node_t::parent, rb_rotate_left(), rb_rotate_right(), rbfail, and rbtree_node_t::right.

Referenced by rb_delete().

00482 {
00483     rbtree_node *sibling = NULL, *node;
00484 
00485     node = leaf;
00486 
00487     if(node->color == NODE_RED) {
00488         // if node is red and has at most one child, then it has no child.
00489         if(node->parent->left == node) {
00490             node->parent->left = NULL;
00491         } else {
00492             node->parent->right = NULL;
00493         }
00494         node->parent = NULL;
00495         return;
00496     }
00497     // node is black so it has only one red child, two black children, or no children.
00498     // If it had two children, we would've handled that in rb_delete()
00499     if(node->left) {
00500         if(node == bt->head) {
00501             bt->head = node->left;
00502             node->left->parent = NULL;
00503         } else if(node->parent->left == node) {
00504             node->parent->left = node->left;
00505             node->left->parent = node->parent;
00506         } else {
00507             node->parent->right = node->left;
00508             node->left->parent = node->parent;
00509         }
00510         if(node->color == NODE_BLACK) {
00511             if(node->left->color == NODE_RED) {
00512                 node->left->color = NODE_BLACK;
00513             } else {
00514                 rbfail("shit.");
00515             }
00516         }
00517         node->parent = NULL;
00518         node->left = NULL;
00519         return;
00520     }
00521 
00522     if(node->right) {
00523         if(node == bt->head) {
00524             bt->head = node->right;
00525             node->right->parent = NULL;
00526         } else if(node->parent->right == node) {
00527             node->parent->right = node->right;
00528             node->right->parent = node->parent;
00529         } else {
00530             node->parent->left = node->right;
00531             node->right->parent = node->parent;
00532         }
00533         if(node->color == NODE_BLACK) {
00534             if(node->right->color == NODE_RED) {
00535                 node->right->color = NODE_BLACK;
00536             } else {
00537                 rbfail("shit.");
00538             }
00539         }
00540         node->right = NULL;
00541         node->left = NULL;
00542         return;
00543     }
00544     // node is black and has no children, if it had two children, then rb_delete
00545     // would have handled the situation. Since the node is black and has no
00546     // children, things get complicated.
00547 
00548     while (node != bt->head) {
00549         // First we loop through the Case 2a situations.
00550         // 
00551         if(node->parent->left == node) {
00552             sibling = node->parent->right;
00553         } else {
00554             sibling = node->parent->left;
00555         }
00556         // if the parent is black, it has two black children, or no children.
00557         // since we are a child, we're guaranteed a sibling.
00558         if(!sibling)                    // Sanity Check
00559             rbfail
00560                 ("serious braindamage: black child of black parent has no sibling.");
00561         if(node->parent->color == NODE_BLACK && sibling->color == NODE_BLACK
00562                 && (!sibling->right || sibling->right->color == NODE_BLACK)
00563                 && (!sibling->left || sibling->left->color == NODE_BLACK)) {
00564             sibling->color = NODE_RED;
00565             node = node->parent;
00566             continue;
00567         }
00568         break;
00569     }
00570 
00571     if(node == bt->head) {
00572         node->color = NODE_BLACK;
00573         goto done;
00574     }
00575 
00576     if(node->parent->left == node) {
00577         sibling = node->parent->right;
00578     } else {
00579         sibling = node->parent->left;
00580     }
00581 
00582     if(node->parent->color == NODE_BLACK && sibling && 
00583             sibling->color == NODE_RED && 
00584             (!sibling->right || sibling->right->color == NODE_BLACK) && 
00585             (!sibling->left || sibling->left-> color == NODE_BLACK)) {
00586         node->parent->color = NODE_RED;
00587         sibling->color = NODE_BLACK;
00588         if(node->parent->left == node) {
00589             rb_rotate_left(bt, node->parent);
00590             sibling = node->parent->right;
00591         } else {
00592             rb_rotate_right(bt, node->parent);
00593             sibling = node->parent->left;
00594         }
00595     }
00596 
00597     if(!sibling && node->parent->color == NODE_RED) {
00598         node->parent->color = NODE_BLACK;
00599         goto done;
00600     }
00601 
00602     if(node->parent->color == NODE_RED && sibling->color == NODE_BLACK &&
00603             (!sibling->right || sibling->right->color == NODE_BLACK) &&
00604             (!sibling->left || sibling->left->color == NODE_BLACK)) {
00605 
00606         sibling->color = NODE_RED;
00607         node->parent->color = NODE_BLACK;
00608         goto done;
00609     }
00610 
00611     if(node->parent->left == node) {
00612 
00613         if(sibling->color == NODE_BLACK &&
00614                 (sibling->left && sibling->left->color == NODE_RED) &&
00615                 (!sibling->right || sibling->right->color == NODE_BLACK)) {
00616             sibling->color = NODE_RED;
00617             sibling->left->color = NODE_BLACK;
00618             rb_rotate_right(bt, sibling);
00619             sibling = sibling->parent;
00620         }
00621 
00622         if(sibling->color == NODE_BLACK &&
00623                 (sibling->right && sibling->right->color == NODE_RED)) {
00624             sibling->right->color = NODE_BLACK;
00625             sibling->color = sibling->parent->color;
00626             sibling->parent->color = NODE_BLACK;
00627             rb_rotate_left(bt, sibling->parent);
00628         }
00629     } else {
00630 
00631         if(sibling->color == NODE_BLACK &&
00632                 (sibling->right && sibling->right->color == NODE_RED) &&
00633                 (!sibling->left || sibling->left->color == NODE_BLACK)) {
00634             sibling->color = NODE_RED;
00635             sibling->right->color = NODE_BLACK;
00636             rb_rotate_left(bt, sibling);
00637             sibling = sibling->parent;
00638         }
00639 
00640         if(sibling->color == NODE_BLACK &&
00641                 (sibling->left && sibling->left->color == NODE_RED)) {
00642             sibling->left->color = NODE_BLACK;
00643             sibling->color = sibling->parent->color;
00644             sibling->parent->color = NODE_BLACK;
00645             rb_rotate_right(bt, sibling->parent);
00646         }
00647     }
00648 
00649 done:
00650     if(leaf->parent->left == leaf) {
00651         leaf->parent->left = NULL;
00652     } else if(leaf->parent->right == leaf) {
00653         leaf->parent->right = NULL;
00654     } else {
00655         rbfail("major braindamage.");
00656     }
00657     return;
00658 }

void rb_walk	(	rbtree	,
		int	,
		int()(void , void , int, void )	,
		void *
	)

Definition at line 748 of file rbtree.c.

References rbtree_node_t::data, rbtree_head_t::head, rbtree_node_t::key, rbtree_node_t::left, rbtree_node_t::parent, rbtree_node_t::right, WALK_INORDER, WALK_POSTORDER, and WALK_PREORDER.

Referenced by auto_gun_event(), cque_dump_restart(), hashflush(), hashreplall(), logcache_destruct(), logcache_list(), and mmdb_db_write().

00750 {
00751     rbtree_node *last, *node;
00752     int depth = 0;
00753     if(!bt->head)
00754         return;
00755     last = NULL;
00756     node = bt->head;
00757     while (node != NULL) {
00758         if(last == node->parent) {
00759             if(how == WALK_PREORDER)
00760                 if(!(*callback) (node->key, node->data, depth, arg))
00761                     return;
00762             if(node->left != NULL) {
00763                 depth++;
00764                 last = node;
00765                 node = node->left;
00766                 continue;
00767             }
00768         }
00769         if(last == node->left || (last == node->parent && node->left == NULL)) {
00770             if(how == WALK_INORDER)
00771                 if(!(*callback) (node->key, node->data, depth, arg))
00772                     return;
00773             if(node->right != NULL) {
00774                 depth++;
00775                 last = node;
00776                 node = node->right;
00777                 continue;
00778             }
00779         }
00780         if(how == WALK_POSTORDER)
00781             if(!(*callback) (node->key, node->data, depth, arg))
00782                 return;
00783         depth--;
00784         last = node;
00785         node = node->parent;
00786     }
00787 }

src/rbtree.c File Reference

Data Structures

Defines

Typedefs

Functions

Define Documentation

Typedef Documentation

Function Documentation


Data Structures
struct	rbtree_node_t
struct	rbtree_head_t
Defines
#define	NODE_RED 0
#define	NODE_BLACK 1
#define	SEARCH_EQUAL 0x1
#define	SEARCH_GTEQ 0x2
#define	SEARCH_LTEQ 0x3
#define	SEARCH_GT 0x4
#define	SEARCH_LT 0x5
#define	SEARCH_NEXT 0x6
#define	SEARCH_PREV 0x7
#define	SEARCH_FIRST 0x8
#define	SEARCH_LAST 0x9
#define	WALK_PREORDER 0x100
#define	WALK_INORDER 0x101
#define	WALK_POSTORDER 0x102
#define	rbann(format, args...) printf("%d: " format "\n", __LINE__, ##args)
#define	rbfail(format, args...) do { printf("%d: " format "\n", __LINE__, ##args); abort(); } while (0)
Typedefs
typedef rbtree_node_t	rbtree_node
typedef rbtree_head_t *	rbtree
Functions
rbtree	rb_init (int()(void , void , void ), void *)
void	rb_destroy (rbtree)
void	rb_insert (rbtree, void key, void data)
void *	rb_find (rbtree, void *key)
int	rb_exists (rbtree, void *key)
void *	rb_delete (rbtree, void *key)
void	rb_walk (rbtree, int, int()(void , void , int, void ), void *)
unsigned int	rb_size (rbtree)
void *	rb_search (rbtree, int, void *)
static rbtree_node *	rb_find_minimum (rbtree_node *node)
static rbtree_node *	rb_find_maximum (rbtree_node *node)
static rbtree_node *	rb_find_successor_node (rbtree_node *node)
static rbtree_node *	rb_find_predecessor_node (rbtree_node *node)
void	rb_release (rbtree bt, void(release)(void , void , void ), void *arg)
static rbtree_node *	rb_allocate (rbtree_node parent, void key, void *data)
static void	rb_rotate_right (rbtree bt, rbtree_node *pivot)
static void	rb_rotate_left (rbtree bt, rbtree_node *pivot)
static void	rb_unlink_leaf (rbtree bt, rbtree_node *leaf)
void *	rb_index (rbtree bt, int index)