Lines Matching refs:p_map
81 static inline cl_map_item_t *__cl_map_root(IN const cl_qmap_t * const p_map)
83 CL_ASSERT(p_map);
84 return (p_map->root.p_left);
132 __cl_map_rot_left(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item)
136 CL_ASSERT(p_map);
138 CL_ASSERT(p_item->p_right != &p_map->nil);
153 if ((*pp_root)->p_left != &p_map->nil)
178 __cl_map_rot_right(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item)
182 CL_ASSERT(p_map);
184 CL_ASSERT(p_item->p_left != &p_map->nil);
198 if ((*pp_root)->p_right != &p_map->nil)
207 void cl_qmap_init(IN cl_qmap_t * const p_map)
209 CL_ASSERT(p_map);
211 memset(p_map, 0, sizeof(cl_qmap_t));
214 p_map->root.p_up = &p_map->root;
215 p_map->root.p_left = &p_map->nil;
216 p_map->root.p_right = &p_map->nil;
217 p_map->root.color = CL_MAP_BLACK;
220 p_map->nil.p_up = &p_map->nil;
221 p_map->nil.p_left = &p_map->nil;
222 p_map->nil.p_right = &p_map->nil;
223 p_map->nil.color = CL_MAP_BLACK;
225 p_map->state = CL_INITIALIZED;
227 cl_qmap_remove_all(p_map);
230 cl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map,
235 CL_ASSERT(p_map);
236 CL_ASSERT(p_map->state == CL_INITIALIZED);
238 p_item = __cl_map_root(p_map);
240 while (p_item != &p_map->nil) {
253 cl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map,
259 CL_ASSERT(p_map);
260 CL_ASSERT(p_map->state == CL_INITIALIZED);
262 p_item = __cl_map_root(p_map);
263 p_item_found = (cl_map_item_t *) & p_map->nil;
265 while (p_item != &p_map->nil) {
278 cl_qmap_apply_func(IN const cl_qmap_t * const p_map,
285 CL_ASSERT(p_map);
286 CL_ASSERT(p_map->state == CL_INITIALIZED);
289 p_map_item = cl_qmap_head(p_map);
290 while (p_map_item != cl_qmap_end(p_map)) {
300 __cl_map_ins_bal(IN cl_qmap_t * const p_map, IN cl_map_item_t * p_item)
304 CL_ASSERT(p_map);
306 CL_ASSERT(p_item != &p_map->root);
322 __cl_map_rot_left(p_map, p_item);
326 __cl_map_rot_right(p_map, p_item->p_up->p_up);
340 __cl_map_rot_right(p_map, p_item);
344 __cl_map_rot_left(p_map, p_item->p_up->p_up);
349 cl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map,
355 CL_ASSERT(p_map);
356 CL_ASSERT(p_map->state == CL_INITIALIZED);
358 CL_ASSERT(p_map->root.p_up == &p_map->root);
359 CL_ASSERT(p_map->root.color != CL_MAP_RED);
360 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
362 p_item->p_left = &p_map->nil;
363 p_item->p_right = &p_map->nil;
368 p_insert_at = &p_map->root;
369 p_comp_item = __cl_map_root(p_map);
371 while (p_comp_item != &p_map->nil) {
384 CL_ASSERT(p_insert_at != &p_map->nil);
385 CL_ASSERT(p_comp_item == &p_map->nil);
387 if (p_insert_at == &p_map->root) {
393 __cl_primitive_insert(&p_map->nil.pool_item.list_item,
413 p_map->count++;
422 __cl_map_ins_bal(p_map, p_item);
424 __cl_map_root(p_map)->color = CL_MAP_BLACK;
434 p_item->p_map = p_map;
441 __cl_map_del_bal(IN cl_qmap_t * const p_map, IN cl_map_item_t * p_item)
445 while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) {
452 __cl_map_rot_left(p_map, p_item->p_up);
465 __cl_map_rot_right(p_map, p_uncle);
471 __cl_map_rot_left(p_map, p_item->p_up);
479 __cl_map_rot_right(p_map, p_item->p_up);
492 __cl_map_rot_left(p_map, p_uncle);
498 __cl_map_rot_right(p_map, p_item->p_up);
506 cl_qmap_remove_item(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item)
510 CL_ASSERT(p_map);
511 CL_ASSERT(p_map->state == CL_INITIALIZED);
514 if (p_item == cl_qmap_end(p_map))
519 CL_ASSERT(p_item->p_map == p_map);
521 if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) {
533 CL_ASSERT(p_del_item != &p_map->nil);
539 p_map->count--;
542 if (p_del_item->p_left != &p_map->nil)
555 __cl_map_del_bal(p_map, p_child);
577 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
581 p_item->p_map = NULL;
585 cl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, IN const uint64_t key)
589 CL_ASSERT(p_map);
590 CL_ASSERT(p_map->state == CL_INITIALIZED);
593 p_item = cl_qmap_get(p_map, key);
595 cl_qmap_remove_item(p_map, p_item);
704 void cl_map_construct(IN cl_map_t * const p_map)
706 CL_ASSERT(p_map);
708 cl_qpool_construct(&p_map->pool);
711 cl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items)
715 CL_ASSERT(p_map);
717 cl_qmap_init(&p_map->qmap);
727 return (cl_qpool_init(&p_map->pool, min_items, 0, grow_size,
731 void cl_map_destroy(IN cl_map_t * const p_map)
733 CL_ASSERT(p_map);
735 cl_qpool_destroy(&p_map->pool);
738 void *cl_map_insert(IN cl_map_t * const p_map,
743 CL_ASSERT(p_map);
745 p_map_obj = (cl_map_obj_t *) cl_qpool_get(&p_map->pool);
753 (cl_map_obj_t *) cl_qmap_insert(&p_map->qmap, key,
758 cl_qpool_put(&p_map->pool, &p_map_obj->item.pool_item);
763 void *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key)
767 CL_ASSERT(p_map);
769 p_item = cl_qmap_get(&p_map->qmap, key);
771 if (p_item == cl_qmap_end(&p_map->qmap))
777 void *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key)
781 CL_ASSERT(p_map);
783 p_item = cl_qmap_get_next(&p_map->qmap, key);
785 if (p_item == cl_qmap_end(&p_map->qmap))
792 cl_map_remove_item(IN cl_map_t * const p_map, IN const cl_map_iterator_t itor)
794 CL_ASSERT(itor->p_map == &p_map->qmap);
796 if (itor == cl_map_end(p_map))
799 cl_qmap_remove_item(&p_map->qmap, (cl_map_item_t *) itor);
800 cl_qpool_put(&p_map->pool, &((cl_map_item_t *) itor)->pool_item);
803 void *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key)
808 CL_ASSERT(p_map);
810 p_item = cl_qmap_remove(&p_map->qmap, key);
812 if (p_item == cl_qmap_end(&p_map->qmap))
816 cl_qpool_put(&p_map->pool, &p_item->pool_item);
821 void cl_map_remove_all(IN cl_map_t * const p_map)
825 CL_ASSERT(p_map);
828 while (!cl_is_qmap_empty(&p_map->qmap)) {
829 p_item = cl_qmap_head(&p_map->qmap);
830 cl_qmap_remove_item(&p_map->qmap, p_item);
831 cl_qpool_put(&p_map->pool, &p_item->pool_item);
833 if (!cl_is_qmap_empty(&p_map->qmap)) {
834 p_item = cl_qmap_tail(&p_map->qmap);
835 cl_qmap_remove_item(&p_map->qmap, p_item);
836 cl_qpool_put(&p_map->pool, &p_item->pool_item);
1012 static inline cl_fmap_item_t *__cl_fmap_root(IN const cl_fmap_t * const p_map)
1014 CL_ASSERT(p_map);
1015 return (p_map->root.p_left);
1063 __cl_fmap_rot_left(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * const p_item)
1067 CL_ASSERT(p_map);
1069 CL_ASSERT(p_item->p_right != &p_map->nil);
1084 if ((*pp_root)->p_left != &p_map->nil)
1109 __cl_fmap_rot_right(IN cl_fmap_t * const p_map,
1114 CL_ASSERT(p_map);
1116 CL_ASSERT(p_item->p_left != &p_map->nil);
1130 if ((*pp_root)->p_right != &p_map->nil)
1139 void cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare)
1141 CL_ASSERT(p_map);
1144 memset(p_map, 0, sizeof(cl_fmap_t));
1147 p_map->root.p_up = &p_map->root;
1148 p_map->root.p_left = &p_map->nil;
1149 p_map->root.p_right = &p_map->nil;
1150 p_map->root.color = CL_MAP_BLACK;
1153 p_map->nil.p_up = &p_map->nil;
1154 p_map->nil.p_left = &p_map->nil;
1155 p_map->nil.p_right = &p_map->nil;
1156 p_map->nil.color = CL_MAP_BLACK;
1159 p_map->pfn_compare = pfn_compare;
1161 p_map->state = CL_INITIALIZED;
1163 cl_fmap_remove_all(p_map);
1166 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map,
1172 CL_ASSERT(p_map);
1173 CL_ASSERT(p_map->state == CL_INITIALIZED);
1175 p_item = __cl_fmap_root(p_map);
1177 while (p_item != &p_map->nil) {
1178 cmp = p_map->pfn_compare(p_key, p_item->p_key);
1192 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map,
1199 CL_ASSERT(p_map);
1200 CL_ASSERT(p_map->state == CL_INITIALIZED);
1202 p_item = __cl_fmap_root(p_map);
1203 p_item_found = (cl_fmap_item_t *) & p_map->nil;
1205 while (p_item != &p_map->nil) {
1206 cmp = p_map->pfn_compare(p_key, p_item->p_key);
1220 cl_fmap_apply_func(IN const cl_fmap_t * const p_map,
1227 CL_ASSERT(p_map);
1228 CL_ASSERT(p_map->state == CL_INITIALIZED);
1231 p_fmap_item = cl_fmap_head(p_map);
1232 while (p_fmap_item != cl_fmap_end(p_map)) {
1242 __cl_fmap_ins_bal(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * p_item)
1246 CL_ASSERT(p_map);
1248 CL_ASSERT(p_item != &p_map->root);
1264 __cl_fmap_rot_left(p_map, p_item);
1268 __cl_fmap_rot_right(p_map, p_item->p_up->p_up);
1282 __cl_fmap_rot_right(p_map, p_item);
1286 __cl_fmap_rot_left(p_map, p_item->p_up->p_up);
1291 cl_fmap_item_t *cl_fmap_insert(IN cl_fmap_t * const p_map,
1298 CL_ASSERT(p_map);
1299 CL_ASSERT(p_map->state == CL_INITIALIZED);
1301 CL_ASSERT(p_map->root.p_up == &p_map->root);
1302 CL_ASSERT(p_map->root.color != CL_MAP_RED);
1303 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
1305 p_item->p_left = &p_map->nil;
1306 p_item->p_right = &p_map->nil;
1311 p_insert_at = &p_map->root;
1312 p_comp_item = __cl_fmap_root(p_map);
1314 while (p_comp_item != &p_map->nil) {
1317 cmp = p_map->pfn_compare(p_key, p_insert_at->p_key);
1329 CL_ASSERT(p_insert_at != &p_map->nil);
1330 CL_ASSERT(p_comp_item == &p_map->nil);
1332 if (p_insert_at == &p_map->root) {
1338 __cl_primitive_insert(&p_map->nil.pool_item.list_item,
1358 p_map->count++;
1367 __cl_fmap_ins_bal(p_map, p_item);
1369 __cl_fmap_root(p_map)->color = CL_MAP_BLACK;
1379 p_item->p_map = p_map;
1386 __cl_fmap_del_bal(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * p_item)
1390 while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) {
1397 __cl_fmap_rot_left(p_map, p_item->p_up);
1410 __cl_fmap_rot_right(p_map, p_uncle);
1416 __cl_fmap_rot_left(p_map, p_item->p_up);
1424 __cl_fmap_rot_right(p_map, p_item->p_up);
1437 __cl_fmap_rot_left(p_map, p_uncle);
1443 __cl_fmap_rot_right(p_map, p_item->p_up);
1451 cl_fmap_remove_item(IN cl_fmap_t * const p_map,
1456 CL_ASSERT(p_map);
1457 CL_ASSERT(p_map->state == CL_INITIALIZED);
1459 CL_ASSERT(p_item->p_map == p_map);
1461 if (p_item == cl_fmap_end(p_map))
1464 if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) {
1476 CL_ASSERT(p_del_item != &p_map->nil);
1482 p_map->count--;
1485 if (p_del_item->p_left != &p_map->nil)
1498 __cl_fmap_del_bal(p_map, p_child);
1520 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
1524 p_item->p_map = NULL;
1528 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map,
1533 CL_ASSERT(p_map);
1534 CL_ASSERT(p_map->state == CL_INITIALIZED);
1537 p_item = cl_fmap_get(p_map, p_key);
1539 cl_fmap_remove_item(p_map, p_item);