ipp/ipgpc/trie.c

63 	buf->pos = 0;
73  * t_split(c_node, pos, key_len)
96  *        *  * bits = 4 pos = 5 val = 1011 mask = 00111100
102  *                           *  bits = 1 pos = 5 val = 1 mask = 00100000
104  *  bits = 2 pos = 3 val=11*   * (to be inserted: (bits = 2 pos = 3 val = 00
115  *        *  * bits = 4 pos = 5 val = 1011 mask = 00111100
117  *         *   *  (to be inserted: bits = 1 pos = 0 val = 1 mask = 00000001)
121 t_split(node_t **c_node, uint8_t pos, uint8_t key_len)
130 	if (pos == (nodep->pos - nodep->bits)) {
131 		/* pos is past the last bit covered at this node */
136 	} else {		/* pos > (nodep->pos - nodep->bits) */
138 		/* nodep->pos will remain the same */
139 		nodep->bits = nodep->pos - pos;
141 		bit = EXTRACTBIT(nodep->val, pos, key_len);
153 			/* pos is before the last bit covered at this node */
154 			nodep->zero->pos = pos - 1; /* link is one bit */
160 				    (nodep->zero->pos - i),
162 					(nodep->zero->pos - i), key_len),
165 				    (nodep->zero->pos - i), 1, key_len);
180 			/* pos is before the last bit covered at this node */
181 			nodep->one->pos = pos - 1; /* link is one bit */
186 				SETBIT(nodep->one->val, (nodep->one->pos - i),
188 					(nodep->one->pos - i), key_len),
191 				    (nodep->one->pos - i), 1, key_len);
197 		/* clear bits no longer covered by this node, from pos=>0 */
198 		for (i = 0; i <= pos; ++i) {
220 	uint8_t pos;
233 	for (pos = key_len; pos > 0; --pos) {
236 		if (EXTRACTBIT(mask, (pos - 1), key_len) != 1) {
240 				if ((pos - 1) > (c_node->pos - c_node->bits)) {
241 					t_split(&c_node, (pos - 1), key_len);
249 		bit = EXTRACTBIT(key, (pos - 1), key_len);
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);
263 			} else if ((pos - 1) == (c_node->pos - c_node->bits)) {
273 					t_split(&c_node, (pos - 1), key_len);
282 					c_node->pos = (pos - 1);
285 				/* bit at pos for node value should be 0 */
286 				UNSETBIT(c_node->val, (pos - 1), key_len);
287 				SETBIT(c_node->mask, (pos - 1), 1, key_len);
296 					c_node->pos = (pos - 1);
299 				/* bit at pos for node value should be 1 */
300 				SETBIT(c_node->val, (pos - 1), 1, key_len);
301 				SETBIT(c_node->mask, (pos - 1), 1, key_len);
334 	uint8_t pos;
353 		for (pos = type_len; pos > 0; --pos) {
355 			if (EXTRACTBIT(mask.s6_addr32[i], (pos - 1), type_len)
359 			bit = EXTRACTBIT(key.s6_addr32[i], (pos - 1), type_len);
390  * t_traverse_delete(in_node, pos, id, key, mask, tid)
399 t_traverse_delete(node_t **in_node, uint8_t pos, key_t id, uint32_t key,
411 	if ((pos == 0) ||
412 	    (EXTRACTBIT(mask, (pos - 1), (uint8_t)(*tid)->key_len) != 1)) {
435 				c_node->pos = 0;
451 		pos = (c_node->pos - c_node->bits) + 1;
452 		/* search should continue if mask and pos are valid */
453 		if ((pos == 0) ||
454 		    (EXTRACTBIT(mask, (pos - 1), (uint8_t)(*tid)->key_len)
482 					c_node->pos = 0;
492 	bit = EXTRACTBIT(key, (pos - 1), (uint8_t)(*tid)->key_len);
494 		if (t_traverse_delete(&c_node->zero, (pos - 1), id, key, mask,
499 		if (t_traverse_delete(&c_node->one, (pos - 1), id, key, mask,
527 			/* c_node->pos will remain the same */
530 			SETBIT(c_node->mask, (pos - 1), 1,
534 			UNSETBIT(c_node->val, (pos - 1),
553 			/* c_node->pos will remain the same */
556 			SETBIT(c_node->mask, (pos - 1), 1,
560 			SETBIT(c_node->val, (pos - 1), 1,
583 			c_node->pos = 0;
631 	uint8_t pos;
650 		for (pos = type_len; pos > 0; --pos) {
652 			if (EXTRACTBIT(mask.s6_addr32[i], (pos - 1), type_len)
656 			bit = EXTRACTBIT(key.s6_addr32[i], (pos - 1), type_len);
705 	uint8_t pos;
722 	for (pos = (uint8_t)tid->key_len; pos > 0; --pos) {
729 			/* pos is set to next bit not covered by node */
730 			if ((pos = (c_node->pos - c_node->bits) + 1) == 0) {
746 		bit = EXTRACTBIT(key, (pos - 1), (uint8_t)tid->key_len);
782 	uint8_t pos;
805 		for (pos = type_len; pos > 0; --pos) {
806 			/* extract bit at pos */
808 			    EXTRACTBIT(key.s6_addr32[i], (pos - 1), type_len);