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