Lines Matching refs:c_node
73 * t_split(c_node, pos, key_len)
75 * performs a split on c_node for the following three cases:
80 * when t_split returns, c_node->one and c_node->zero must != NULL
121 t_split(node_t **c_node, uint8_t pos, uint8_t key_len)
126 node_t *nodep = *c_node;
218 node_t *c_node;
230 c_node = tid->trie; /* point at trie root */
238 if (c_node->bits > 0) {
240 if ((pos - 1) > (c_node->pos - c_node->bits)) {
241 t_split(&c_node, (pos - 1), key_len);
242 ASSERT(c_node->one != NULL);
243 ASSERT(c_node->zero != NULL);
251 if (c_node->bits > 0) { /* path compressed node */
253 if ((pos - 1) > (c_node->pos - c_node->bits)) {
255 if (bit != EXTRACTBIT(c_node->val, (pos - 1),
257 t_split(&c_node, (pos - 1), key_len);
258 ASSERT(c_node->one != NULL);
259 ASSERT(c_node->zero != NULL);
263 } else if ((pos - 1) == (c_node->pos - c_node->bits)) {
265 if ((c_node->one == NULL) &&
266 (c_node->zero == NULL) &&
267 (c_node->elements != NULL)) {
273 t_split(&c_node, (pos - 1), key_len);
274 ASSERT(c_node->one != NULL);
275 ASSERT(c_node->zero != NULL);
280 if (c_node->zero == NULL) { /* leaf node */
281 if (c_node->bits == 0) {
282 c_node->pos = (pos - 1);
284 c_node->bits++;
286 UNSETBIT(c_node->val, (pos - 1), key_len);
287 SETBIT(c_node->mask, (pos - 1), 1, key_len);
290 ASSERT(c_node->one != NULL);
291 c_node = c_node->zero; /* internal node */
294 if (c_node->one == NULL) { /* leaf node */
295 if (c_node->bits == 0) {
296 c_node->pos = (pos - 1);
298 c_node->bits++;
300 SETBIT(c_node->val, (pos - 1), 1, key_len);
301 SETBIT(c_node->mask, (pos - 1), 1, key_len);
304 ASSERT(c_node->zero != NULL);
305 c_node = c_node->one; /* internal node */
310 (void) ipgpc_list_insert(&c_node->elements, id);
332 node_t *c_node;
345 c_node = tid->trie; /* point at root of trie */
361 if (c_node->zero == NULL) {
362 c_node->zero = create_node(KM_SLEEP);
364 c_node = c_node->zero;
366 if (c_node->one == NULL) {
367 c_node->one = create_node(KM_SLEEP);
369 c_node = c_node->one;
375 (void) ipgpc_list_insert(&c_node->elements, id);
402 node_t *c_node = *in_node;
406 if (c_node == NULL) {
413 if (ipgpc_list_remove(&c_node->elements, id) == B_FALSE) {
427 if ((c_node->elements == NULL) &&
428 ((c_node->one == NULL) && (c_node->zero == NULL))) {
430 if (c_node->isroot != 1) {
431 kmem_cache_free(trie_node_cache, c_node);
435 c_node->pos = 0;
436 c_node->bits = 0;
437 c_node->val = 0;
438 c_node->mask = 0;
445 if (c_node->bits > 0) {
446 if ((key & c_node->mask) != c_node->val) {
451 pos = (c_node->pos - c_node->bits) + 1;
457 if (ipgpc_list_remove(&c_node->elements,
472 if ((c_node->elements == NULL) &&
473 ((c_node->one == NULL) &&
474 (c_node->zero == NULL))) {
476 if (c_node->isroot != 1) {
478 c_node);
482 c_node->pos = 0;
483 c_node->bits = 0;
484 c_node->val = 0;
485 c_node->mask = 0;
494 if (t_traverse_delete(&c_node->zero, (pos - 1), id, key, mask,
496 c_node->zero = NULL;
499 if (t_traverse_delete(&c_node->one, (pos - 1), id, key, mask,
501 c_node->one = NULL;
511 * * <-- c_node->elements = foo
513 * * * <-- children of c_node
519 * * * <-- p_node adopts children of c_node
521 if ((c_node->one == NULL) && (c_node->zero != NULL)) {
522 if (c_node->elements == NULL) {
524 c_node->elements = c_node->zero->elements;
526 c_node->bits += c_node->zero->bits + 1;
527 /* c_node->pos will remain the same */
528 c_node->mask |= c_node->zero->mask;
530 SETBIT(c_node->mask, (pos - 1), 1,
532 c_node->val |= c_node->zero->val;
534 UNSETBIT(c_node->val, (pos - 1),
537 t_node = c_node->zero;
538 c_node->one = c_node->zero->one;
539 c_node->zero = c_node->zero->zero;
542 ASSERT(c_node->zero->one == NULL);
543 ASSERT(c_node->zero->zero == NULL);
544 kmem_cache_free(trie_node_cache, c_node->zero);
545 c_node->zero = NULL;
547 } else if ((c_node->one != NULL) && (c_node->zero == NULL)) {
548 if (c_node->elements == NULL) {
550 c_node->elements = c_node->one->elements;
552 c_node->bits += c_node->one->bits + 1;
553 /* c_node->pos will remain the same */
554 c_node->mask |= c_node->one->mask;
556 SETBIT(c_node->mask, (pos - 1), 1,
558 c_node->val |= c_node->one->val;
560 SETBIT(c_node->val, (pos - 1), 1,
563 t_node = c_node->one;
564 c_node->zero = c_node->one->zero;
565 c_node->one = c_node->one->one;
568 ASSERT(c_node->one->one == NULL);
569 ASSERT(c_node->one->zero == NULL);
570 kmem_cache_free(trie_node_cache, c_node->one);
571 c_node->one = NULL;
575 if ((c_node->elements == NULL) &&
576 ((c_node->one == NULL) && (c_node->zero == NULL))) {
578 if (c_node->isroot != 1) {
579 kmem_cache_free(trie_node_cache, c_node);
583 c_node->pos = 0;
584 c_node->bits = 0;
585 c_node->val = 0;
586 c_node->mask = 0;
604 node_t *c_node;
615 c_node = tid->trie;
616 (void) t_traverse_delete(&c_node, (uint8_t)tid->key_len, id, key, mask,
629 node_t *c_node;
642 c_node = tid->trie; /* point at root of trie */
658 if (c_node->zero == NULL) {
661 c_node = c_node->zero;
663 if (c_node->one == NULL) {
666 c_node = c_node->one;
671 if (c_node != NULL) {
672 if (ipgpc_list_remove(&c_node->elements, id)) {
708 node_t *c_node;
711 c_node = tid->trie; /* point at root of trie */
714 if (c_node == NULL) {
724 if (c_node->bits > 0) {
725 if ((key & c_node->mask) != c_node->val) {
730 if ((pos = (c_node->pos - c_node->bits) + 1) == 0) {
736 if (c_node->elements != NULL) {
738 c_node->elements, fid_table)) == -1) {
748 c_node = c_node->zero;
751 c_node = c_node->one;
754 if (c_node == NULL) {
761 if (c_node->elements != NULL) {
762 if ((ret = ipgpc_mark_found(tid->info.mask, c_node->elements,
785 node_t *c_node;
789 c_node = tid->trie;
792 if (c_node == NULL) {
810 c_node = c_node->zero;
813 c_node = c_node->one;
816 if (c_node == NULL) {
822 if (c_node->elements != NULL) {
824 c_node->elements, fid_table)) == -1) {