Lines Matching refs:p_map
77 static inline cl_map_item_t *__cl_map_root(IN const cl_qmap_t * const p_map) in __cl_map_root() argument
79 CL_ASSERT(p_map); in __cl_map_root()
80 return (p_map->root.p_left); in __cl_map_root()
127 static void __cl_map_rot_left(IN cl_qmap_t * const p_map, in __cl_map_rot_left() argument
132 CL_ASSERT(p_map); in __cl_map_rot_left()
134 CL_ASSERT(p_item->p_right != &p_map->nil); in __cl_map_rot_left()
149 if ((*pp_root)->p_left != &p_map->nil) in __cl_map_rot_left()
173 static void __cl_map_rot_right(IN cl_qmap_t * const p_map, in __cl_map_rot_right() argument
178 CL_ASSERT(p_map); in __cl_map_rot_right()
180 CL_ASSERT(p_item->p_left != &p_map->nil); in __cl_map_rot_right()
194 if ((*pp_root)->p_right != &p_map->nil) in __cl_map_rot_right()
203 void cl_qmap_init(IN cl_qmap_t * const p_map) in cl_qmap_init() argument
205 CL_ASSERT(p_map); in cl_qmap_init()
207 memset(p_map, 0, sizeof(cl_qmap_t)); in cl_qmap_init()
210 p_map->root.p_up = &p_map->root; in cl_qmap_init()
211 p_map->root.p_left = &p_map->nil; in cl_qmap_init()
212 p_map->root.p_right = &p_map->nil; in cl_qmap_init()
213 p_map->root.color = CL_MAP_BLACK; in cl_qmap_init()
216 p_map->nil.p_up = &p_map->nil; in cl_qmap_init()
217 p_map->nil.p_left = &p_map->nil; in cl_qmap_init()
218 p_map->nil.p_right = &p_map->nil; in cl_qmap_init()
219 p_map->nil.color = CL_MAP_BLACK; in cl_qmap_init()
221 p_map->state = CL_INITIALIZED; in cl_qmap_init()
223 cl_qmap_remove_all(p_map); in cl_qmap_init()
226 cl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map, in cl_qmap_get() argument
231 CL_ASSERT(p_map); in cl_qmap_get()
232 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_qmap_get()
234 p_item = __cl_map_root(p_map); in cl_qmap_get()
236 while (p_item != &p_map->nil) { in cl_qmap_get()
249 cl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map, in cl_qmap_get_next() argument
255 CL_ASSERT(p_map); in cl_qmap_get_next()
256 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_qmap_get_next()
258 p_item = __cl_map_root(p_map); in cl_qmap_get_next()
259 p_item_found = (cl_map_item_t *) & p_map->nil; in cl_qmap_get_next()
261 while (p_item != &p_map->nil) { in cl_qmap_get_next()
273 void cl_qmap_apply_func(IN const cl_qmap_t * const p_map, in cl_qmap_apply_func() argument
280 CL_ASSERT(p_map); in cl_qmap_apply_func()
281 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_qmap_apply_func()
284 p_map_item = cl_qmap_head(p_map); in cl_qmap_apply_func()
285 while (p_map_item != cl_qmap_end(p_map)) { in cl_qmap_apply_func()
294 static void __cl_map_ins_bal(IN cl_qmap_t * const p_map, in __cl_map_ins_bal() argument
299 CL_ASSERT(p_map); in __cl_map_ins_bal()
301 CL_ASSERT(p_item != &p_map->root); in __cl_map_ins_bal()
317 __cl_map_rot_left(p_map, p_item); in __cl_map_ins_bal()
321 __cl_map_rot_right(p_map, p_item->p_up->p_up); in __cl_map_ins_bal()
335 __cl_map_rot_right(p_map, p_item); in __cl_map_ins_bal()
339 __cl_map_rot_left(p_map, p_item->p_up->p_up); in __cl_map_ins_bal()
344 cl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map, in cl_qmap_insert() argument
350 CL_ASSERT(p_map); in cl_qmap_insert()
351 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_qmap_insert()
353 CL_ASSERT(p_map->root.p_up == &p_map->root); in cl_qmap_insert()
354 CL_ASSERT(p_map->root.color != CL_MAP_RED); in cl_qmap_insert()
355 CL_ASSERT(p_map->nil.color != CL_MAP_RED); in cl_qmap_insert()
357 p_item->p_left = &p_map->nil; in cl_qmap_insert()
358 p_item->p_right = &p_map->nil; in cl_qmap_insert()
363 p_insert_at = &p_map->root; in cl_qmap_insert()
364 p_comp_item = __cl_map_root(p_map); in cl_qmap_insert()
366 while (p_comp_item != &p_map->nil) { in cl_qmap_insert()
379 CL_ASSERT(p_insert_at != &p_map->nil); in cl_qmap_insert()
380 CL_ASSERT(p_comp_item == &p_map->nil); in cl_qmap_insert()
382 if (p_insert_at == &p_map->root) { in cl_qmap_insert()
388 __cl_primitive_insert(&p_map->nil.pool_item.list_item, in cl_qmap_insert()
408 p_map->count++; in cl_qmap_insert()
417 __cl_map_ins_bal(p_map, p_item); in cl_qmap_insert()
419 __cl_map_root(p_map)->color = CL_MAP_BLACK; in cl_qmap_insert()
429 p_item->p_map = p_map; in cl_qmap_insert()
435 static void __cl_map_del_bal(IN cl_qmap_t * const p_map, in __cl_map_del_bal() argument
440 while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) { in __cl_map_del_bal()
447 __cl_map_rot_left(p_map, p_item->p_up); in __cl_map_del_bal()
460 __cl_map_rot_right(p_map, p_uncle); in __cl_map_del_bal()
466 __cl_map_rot_left(p_map, p_item->p_up); in __cl_map_del_bal()
474 __cl_map_rot_right(p_map, p_item->p_up); in __cl_map_del_bal()
487 __cl_map_rot_left(p_map, p_uncle); in __cl_map_del_bal()
493 __cl_map_rot_right(p_map, p_item->p_up); in __cl_map_del_bal()
500 void cl_qmap_remove_item(IN cl_qmap_t * const p_map, in cl_qmap_remove_item() argument
505 CL_ASSERT(p_map); in cl_qmap_remove_item()
506 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_qmap_remove_item()
509 if (p_item == cl_qmap_end(p_map)) in cl_qmap_remove_item()
514 CL_ASSERT(p_item->p_map == p_map); in cl_qmap_remove_item()
516 if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) { in cl_qmap_remove_item()
528 CL_ASSERT(p_del_item != &p_map->nil); in cl_qmap_remove_item()
534 p_map->count--; in cl_qmap_remove_item()
537 if (p_del_item->p_left != &p_map->nil) in cl_qmap_remove_item()
550 __cl_map_del_bal(p_map, p_child); in cl_qmap_remove_item()
572 CL_ASSERT(p_map->nil.color != CL_MAP_RED); in cl_qmap_remove_item()
576 p_item->p_map = NULL; in cl_qmap_remove_item()
580 cl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, IN const uint64_t key) in cl_qmap_remove() argument
584 CL_ASSERT(p_map); in cl_qmap_remove()
585 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_qmap_remove()
588 p_item = cl_qmap_get(p_map, key); in cl_qmap_remove()
590 cl_qmap_remove_item(p_map, p_item); in cl_qmap_remove()
693 void cl_map_construct(IN cl_map_t * const p_map) in cl_map_construct() argument
695 CL_ASSERT(p_map); in cl_map_construct()
697 cl_qpool_construct(&p_map->pool); in cl_map_construct()
700 cl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items) in cl_map_init() argument
704 CL_ASSERT(p_map); in cl_map_init()
706 cl_qmap_init(&p_map->qmap); in cl_map_init()
716 return (cl_qpool_init(&p_map->pool, min_items, 0, grow_size, in cl_map_init()
720 void cl_map_destroy(IN cl_map_t * const p_map) in cl_map_destroy() argument
722 CL_ASSERT(p_map); in cl_map_destroy()
724 cl_qpool_destroy(&p_map->pool); in cl_map_destroy()
727 void *cl_map_insert(IN cl_map_t * const p_map, in cl_map_insert() argument
732 CL_ASSERT(p_map); in cl_map_insert()
734 p_map_obj = (cl_map_obj_t *) cl_qpool_get(&p_map->pool); in cl_map_insert()
742 (cl_map_obj_t *) cl_qmap_insert(&p_map->qmap, key, in cl_map_insert()
747 cl_qpool_put(&p_map->pool, &p_map_obj->item.pool_item); in cl_map_insert()
752 void *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key) in cl_map_get() argument
756 CL_ASSERT(p_map); in cl_map_get()
758 p_item = cl_qmap_get(&p_map->qmap, key); in cl_map_get()
760 if (p_item == cl_qmap_end(&p_map->qmap)) in cl_map_get()
766 void *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key) in cl_map_get_next() argument
770 CL_ASSERT(p_map); in cl_map_get_next()
772 p_item = cl_qmap_get_next(&p_map->qmap, key); in cl_map_get_next()
774 if (p_item == cl_qmap_end(&p_map->qmap)) in cl_map_get_next()
780 void cl_map_remove_item(IN cl_map_t * const p_map, in cl_map_remove_item() argument
783 CL_ASSERT(itor->p_map == &p_map->qmap); in cl_map_remove_item()
785 if (itor == cl_map_end(p_map)) in cl_map_remove_item()
788 cl_qmap_remove_item(&p_map->qmap, (cl_map_item_t *) itor); in cl_map_remove_item()
789 cl_qpool_put(&p_map->pool, &((cl_map_item_t *) itor)->pool_item); in cl_map_remove_item()
792 void *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key) in cl_map_remove() argument
797 CL_ASSERT(p_map); in cl_map_remove()
799 p_item = cl_qmap_remove(&p_map->qmap, key); in cl_map_remove()
801 if (p_item == cl_qmap_end(&p_map->qmap)) in cl_map_remove()
805 cl_qpool_put(&p_map->pool, &p_item->pool_item); in cl_map_remove()
810 void cl_map_remove_all(IN cl_map_t * const p_map) in cl_map_remove_all() argument
814 CL_ASSERT(p_map); in cl_map_remove_all()
817 while (!cl_is_qmap_empty(&p_map->qmap)) { in cl_map_remove_all()
818 p_item = cl_qmap_head(&p_map->qmap); in cl_map_remove_all()
819 cl_qmap_remove_item(&p_map->qmap, p_item); in cl_map_remove_all()
820 cl_qpool_put(&p_map->pool, &p_item->pool_item); in cl_map_remove_all()
822 if (!cl_is_qmap_empty(&p_map->qmap)) { in cl_map_remove_all()
823 p_item = cl_qmap_tail(&p_map->qmap); in cl_map_remove_all()
824 cl_qmap_remove_item(&p_map->qmap, p_item); in cl_map_remove_all()
825 cl_qpool_put(&p_map->pool, &p_item->pool_item); in cl_map_remove_all()
995 static inline cl_fmap_item_t *__cl_fmap_root(IN const cl_fmap_t * const p_map) in __cl_fmap_root() argument
997 CL_ASSERT(p_map); in __cl_fmap_root()
998 return (p_map->root.p_left); in __cl_fmap_root()
1045 static void __cl_fmap_rot_left(IN cl_fmap_t * const p_map, in __cl_fmap_rot_left() argument
1050 CL_ASSERT(p_map); in __cl_fmap_rot_left()
1052 CL_ASSERT(p_item->p_right != &p_map->nil); in __cl_fmap_rot_left()
1067 if ((*pp_root)->p_left != &p_map->nil) in __cl_fmap_rot_left()
1091 static void __cl_fmap_rot_right(IN cl_fmap_t * const p_map, in __cl_fmap_rot_right() argument
1096 CL_ASSERT(p_map); in __cl_fmap_rot_right()
1098 CL_ASSERT(p_item->p_left != &p_map->nil); in __cl_fmap_rot_right()
1112 if ((*pp_root)->p_right != &p_map->nil) in __cl_fmap_rot_right()
1121 void cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare) in cl_fmap_init() argument
1123 CL_ASSERT(p_map); in cl_fmap_init()
1126 memset(p_map, 0, sizeof(cl_fmap_t)); in cl_fmap_init()
1129 p_map->root.p_up = &p_map->root; in cl_fmap_init()
1130 p_map->root.p_left = &p_map->nil; in cl_fmap_init()
1131 p_map->root.p_right = &p_map->nil; in cl_fmap_init()
1132 p_map->root.color = CL_MAP_BLACK; in cl_fmap_init()
1135 p_map->nil.p_up = &p_map->nil; in cl_fmap_init()
1136 p_map->nil.p_left = &p_map->nil; in cl_fmap_init()
1137 p_map->nil.p_right = &p_map->nil; in cl_fmap_init()
1138 p_map->nil.color = CL_MAP_BLACK; in cl_fmap_init()
1141 p_map->pfn_compare = pfn_compare; in cl_fmap_init()
1143 p_map->state = CL_INITIALIZED; in cl_fmap_init()
1145 cl_fmap_remove_all(p_map); in cl_fmap_init()
1148 cl_fmap_item_t *cl_fmap_match(IN const cl_fmap_t * const p_map, in cl_fmap_match() argument
1155 CL_ASSERT(p_map); in cl_fmap_match()
1156 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_match()
1158 p_item = __cl_fmap_root(p_map); in cl_fmap_match()
1160 while (p_item != &p_map->nil) { in cl_fmap_match()
1162 p_map->pfn_compare(p_key, p_item->p_key); in cl_fmap_match()
1176 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map, in cl_fmap_get() argument
1179 return cl_fmap_match(p_map, p_key, p_map->pfn_compare); in cl_fmap_get()
1182 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map, in cl_fmap_get_next() argument
1189 CL_ASSERT(p_map); in cl_fmap_get_next()
1190 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_get_next()
1192 p_item = __cl_fmap_root(p_map); in cl_fmap_get_next()
1193 p_item_found = (cl_fmap_item_t *) & p_map->nil; in cl_fmap_get_next()
1195 while (p_item != &p_map->nil) { in cl_fmap_get_next()
1196 cmp = p_map->pfn_compare(p_key, p_item->p_key); in cl_fmap_get_next()
1209 void cl_fmap_apply_func(IN const cl_fmap_t * const p_map, in cl_fmap_apply_func() argument
1216 CL_ASSERT(p_map); in cl_fmap_apply_func()
1217 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_apply_func()
1220 p_fmap_item = cl_fmap_head(p_map); in cl_fmap_apply_func()
1221 while (p_fmap_item != cl_fmap_end(p_map)) { in cl_fmap_apply_func()
1230 static void __cl_fmap_ins_bal(IN cl_fmap_t * const p_map, in __cl_fmap_ins_bal() argument
1235 CL_ASSERT(p_map); in __cl_fmap_ins_bal()
1237 CL_ASSERT(p_item != &p_map->root); in __cl_fmap_ins_bal()
1253 __cl_fmap_rot_left(p_map, p_item); in __cl_fmap_ins_bal()
1257 __cl_fmap_rot_right(p_map, p_item->p_up->p_up); in __cl_fmap_ins_bal()
1271 __cl_fmap_rot_right(p_map, p_item); in __cl_fmap_ins_bal()
1275 __cl_fmap_rot_left(p_map, p_item->p_up->p_up); in __cl_fmap_ins_bal()
1280 cl_fmap_item_t *cl_fmap_insert(IN cl_fmap_t * const p_map, in cl_fmap_insert() argument
1287 CL_ASSERT(p_map); in cl_fmap_insert()
1288 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_insert()
1290 CL_ASSERT(p_map->root.p_up == &p_map->root); in cl_fmap_insert()
1291 CL_ASSERT(p_map->root.color != CL_MAP_RED); in cl_fmap_insert()
1292 CL_ASSERT(p_map->nil.color != CL_MAP_RED); in cl_fmap_insert()
1294 p_item->p_left = &p_map->nil; in cl_fmap_insert()
1295 p_item->p_right = &p_map->nil; in cl_fmap_insert()
1300 p_insert_at = &p_map->root; in cl_fmap_insert()
1301 p_comp_item = __cl_fmap_root(p_map); in cl_fmap_insert()
1303 while (p_comp_item != &p_map->nil) { in cl_fmap_insert()
1306 cmp = p_map->pfn_compare(p_key, p_insert_at->p_key); in cl_fmap_insert()
1318 CL_ASSERT(p_insert_at != &p_map->nil); in cl_fmap_insert()
1319 CL_ASSERT(p_comp_item == &p_map->nil); in cl_fmap_insert()
1321 if (p_insert_at == &p_map->root) { in cl_fmap_insert()
1327 __cl_primitive_insert(&p_map->nil.pool_item.list_item, in cl_fmap_insert()
1347 p_map->count++; in cl_fmap_insert()
1356 __cl_fmap_ins_bal(p_map, p_item); in cl_fmap_insert()
1358 __cl_fmap_root(p_map)->color = CL_MAP_BLACK; in cl_fmap_insert()
1368 p_item->p_map = p_map; in cl_fmap_insert()
1374 static void __cl_fmap_del_bal(IN cl_fmap_t * const p_map, in __cl_fmap_del_bal() argument
1379 while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) { in __cl_fmap_del_bal()
1386 __cl_fmap_rot_left(p_map, p_item->p_up); in __cl_fmap_del_bal()
1399 __cl_fmap_rot_right(p_map, p_uncle); in __cl_fmap_del_bal()
1405 __cl_fmap_rot_left(p_map, p_item->p_up); in __cl_fmap_del_bal()
1413 __cl_fmap_rot_right(p_map, p_item->p_up); in __cl_fmap_del_bal()
1426 __cl_fmap_rot_left(p_map, p_uncle); in __cl_fmap_del_bal()
1432 __cl_fmap_rot_right(p_map, p_item->p_up); in __cl_fmap_del_bal()
1439 void cl_fmap_remove_item(IN cl_fmap_t * const p_map, in cl_fmap_remove_item() argument
1444 CL_ASSERT(p_map); in cl_fmap_remove_item()
1445 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_remove_item()
1447 CL_ASSERT(p_item->p_map == p_map); in cl_fmap_remove_item()
1449 if (p_item == cl_fmap_end(p_map)) in cl_fmap_remove_item()
1452 if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) { in cl_fmap_remove_item()
1464 CL_ASSERT(p_del_item != &p_map->nil); in cl_fmap_remove_item()
1470 p_map->count--; in cl_fmap_remove_item()
1473 if (p_del_item->p_left != &p_map->nil) in cl_fmap_remove_item()
1486 __cl_fmap_del_bal(p_map, p_child); in cl_fmap_remove_item()
1508 CL_ASSERT(p_map->nil.color != CL_MAP_RED); in cl_fmap_remove_item()
1512 p_item->p_map = NULL; in cl_fmap_remove_item()
1516 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map, in cl_fmap_remove() argument
1521 CL_ASSERT(p_map); in cl_fmap_remove()
1522 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_remove()
1525 p_item = cl_fmap_get(p_map, p_key); in cl_fmap_remove()
1527 cl_fmap_remove_item(p_map, p_item); in cl_fmap_remove()