Lines Matching +full:parent +full:- +full:child
15 * - Redistributions of source code must retain the above
19 * - Redistributions in binary form must reproduce the above
54 struct ibv_mem_node *parent; member
107 n = sscanf(buf, "%" SCNxPTR "-%" SCNxPTR, &range_start, &range_end); in get_page_size()
148 tmp_aligned = (void *) ((uintptr_t) tmp & ~(size - 1)); in ibv_fork_init()
166 mm_root->parent = NULL; in ibv_fork_init()
167 mm_root->left = NULL; in ibv_fork_init()
168 mm_root->right = NULL; in ibv_fork_init()
169 mm_root->color = IBV_BLACK; in ibv_fork_init()
170 mm_root->start = 0; in ibv_fork_init()
171 mm_root->end = UINTPTR_MAX; in ibv_fork_init()
172 mm_root->refcnt = 0; in ibv_fork_init()
179 if (node->left) { in __mm_prev()
180 node = node->left; in __mm_prev()
181 while (node->right) in __mm_prev()
182 node = node->right; in __mm_prev()
184 while (node->parent && node == node->parent->left) in __mm_prev()
185 node = node->parent; in __mm_prev()
187 node = node->parent; in __mm_prev()
195 if (node->right) { in __mm_next()
196 node = node->right; in __mm_next()
197 while (node->left) in __mm_next()
198 node = node->left; in __mm_next()
200 while (node->parent && node == node->parent->right) in __mm_next()
201 node = node->parent; in __mm_next()
203 node = node->parent; in __mm_next()
213 tmp = node->left; in __mm_rotate_right()
215 node->left = tmp->right; in __mm_rotate_right()
216 if (node->left) in __mm_rotate_right()
217 node->left->parent = node; in __mm_rotate_right()
219 if (node->parent) { in __mm_rotate_right()
220 if (node->parent->right == node) in __mm_rotate_right()
221 node->parent->right = tmp; in __mm_rotate_right()
223 node->parent->left = tmp; in __mm_rotate_right()
227 tmp->parent = node->parent; in __mm_rotate_right()
229 tmp->right = node; in __mm_rotate_right()
230 node->parent = tmp; in __mm_rotate_right()
237 tmp = node->right; in __mm_rotate_left()
239 node->right = tmp->left; in __mm_rotate_left()
240 if (node->right) in __mm_rotate_left()
241 node->right->parent = node; in __mm_rotate_left()
243 if (node->parent) { in __mm_rotate_left()
244 if (node->parent->right == node) in __mm_rotate_left()
245 node->parent->right = tmp; in __mm_rotate_left()
247 node->parent->left = tmp; in __mm_rotate_left()
251 tmp->parent = node->parent; in __mm_rotate_left()
253 tmp->left = node; in __mm_rotate_left()
254 node->parent = tmp; in __mm_rotate_left()
265 hl = verify(node->left);
266 hr = verify(node->left);
273 if (node->color == IBV_RED) {
274 if (node->left && node->left->color != IBV_BLACK)
276 if (node->right && node->right->color != IBV_BLACK)
287 struct ibv_mem_node *parent, *gp, *uncle; in __mm_add_rebalance() local
289 while (node->parent && node->parent->color == IBV_RED) { in __mm_add_rebalance()
290 parent = node->parent; in __mm_add_rebalance()
291 gp = node->parent->parent; in __mm_add_rebalance()
293 if (parent == gp->left) { in __mm_add_rebalance()
294 uncle = gp->right; in __mm_add_rebalance()
296 if (uncle && uncle->color == IBV_RED) { in __mm_add_rebalance()
297 parent->color = IBV_BLACK; in __mm_add_rebalance()
298 uncle->color = IBV_BLACK; in __mm_add_rebalance()
299 gp->color = IBV_RED; in __mm_add_rebalance()
303 if (node == parent->right) { in __mm_add_rebalance()
304 __mm_rotate_left(parent); in __mm_add_rebalance()
305 node = parent; in __mm_add_rebalance()
306 parent = node->parent; in __mm_add_rebalance()
309 parent->color = IBV_BLACK; in __mm_add_rebalance()
310 gp->color = IBV_RED; in __mm_add_rebalance()
315 uncle = gp->left; in __mm_add_rebalance()
317 if (uncle && uncle->color == IBV_RED) { in __mm_add_rebalance()
318 parent->color = IBV_BLACK; in __mm_add_rebalance()
319 uncle->color = IBV_BLACK; in __mm_add_rebalance()
320 gp->color = IBV_RED; in __mm_add_rebalance()
324 if (node == parent->left) { in __mm_add_rebalance()
325 __mm_rotate_right(parent); in __mm_add_rebalance()
326 node = parent; in __mm_add_rebalance()
327 parent = node->parent; in __mm_add_rebalance()
330 parent->color = IBV_BLACK; in __mm_add_rebalance()
331 gp->color = IBV_RED; in __mm_add_rebalance()
338 mm_root->color = IBV_BLACK; in __mm_add_rebalance()
343 struct ibv_mem_node *node, *parent = NULL; in __mm_add() local
347 parent = node; in __mm_add()
348 if (node->start < new->start) in __mm_add()
349 node = node->right; in __mm_add()
351 node = node->left; in __mm_add()
354 if (parent->start < new->start) in __mm_add()
355 parent->right = new; in __mm_add()
357 parent->left = new; in __mm_add()
359 new->parent = parent; in __mm_add()
360 new->left = NULL; in __mm_add()
361 new->right = NULL; in __mm_add()
363 new->color = IBV_RED; in __mm_add()
369 struct ibv_mem_node *child, *parent, *sib, *tmp; in __mm_remove() local
372 if (node->left && node->right) { in __mm_remove()
373 tmp = node->left; in __mm_remove()
374 while (tmp->right) in __mm_remove()
375 tmp = tmp->right; in __mm_remove()
377 nodecol = tmp->color; in __mm_remove()
378 child = tmp->left; in __mm_remove()
379 tmp->color = node->color; in __mm_remove()
381 if (tmp->parent != node) { in __mm_remove()
382 parent = tmp->parent; in __mm_remove()
383 parent->right = tmp->left; in __mm_remove()
384 if (tmp->left) in __mm_remove()
385 tmp->left->parent = parent; in __mm_remove()
387 tmp->left = node->left; in __mm_remove()
388 node->left->parent = tmp; in __mm_remove()
390 parent = tmp; in __mm_remove()
392 tmp->right = node->right; in __mm_remove()
393 node->right->parent = tmp; in __mm_remove()
395 tmp->parent = node->parent; in __mm_remove()
396 if (node->parent) { in __mm_remove()
397 if (node->parent->left == node) in __mm_remove()
398 node->parent->left = tmp; in __mm_remove()
400 node->parent->right = tmp; in __mm_remove()
404 nodecol = node->color; in __mm_remove()
406 child = node->left ? node->left : node->right; in __mm_remove()
407 parent = node->parent; in __mm_remove()
409 if (child) in __mm_remove()
410 child->parent = parent; in __mm_remove()
411 if (parent) { in __mm_remove()
412 if (parent->left == node) in __mm_remove()
413 parent->left = child; in __mm_remove()
415 parent->right = child; in __mm_remove()
417 mm_root = child; in __mm_remove()
425 while ((!child || child->color == IBV_BLACK) && child != mm_root) { in __mm_remove()
426 if (parent->left == child) { in __mm_remove()
427 sib = parent->right; in __mm_remove()
429 if (sib->color == IBV_RED) { in __mm_remove()
430 parent->color = IBV_RED; in __mm_remove()
431 sib->color = IBV_BLACK; in __mm_remove()
432 __mm_rotate_left(parent); in __mm_remove()
433 sib = parent->right; in __mm_remove()
436 if ((!sib->left || sib->left->color == IBV_BLACK) && in __mm_remove()
437 (!sib->right || sib->right->color == IBV_BLACK)) { in __mm_remove()
438 sib->color = IBV_RED; in __mm_remove()
439 child = parent; in __mm_remove()
440 parent = child->parent; in __mm_remove()
442 if (!sib->right || sib->right->color == IBV_BLACK) { in __mm_remove()
443 if (sib->left) in __mm_remove()
444 sib->left->color = IBV_BLACK; in __mm_remove()
445 sib->color = IBV_RED; in __mm_remove()
447 sib = parent->right; in __mm_remove()
450 sib->color = parent->color; in __mm_remove()
451 parent->color = IBV_BLACK; in __mm_remove()
452 if (sib->right) in __mm_remove()
453 sib->right->color = IBV_BLACK; in __mm_remove()
454 __mm_rotate_left(parent); in __mm_remove()
455 child = mm_root; in __mm_remove()
459 sib = parent->left; in __mm_remove()
461 if (sib->color == IBV_RED) { in __mm_remove()
462 parent->color = IBV_RED; in __mm_remove()
463 sib->color = IBV_BLACK; in __mm_remove()
464 __mm_rotate_right(parent); in __mm_remove()
465 sib = parent->left; in __mm_remove()
468 if ((!sib->left || sib->left->color == IBV_BLACK) && in __mm_remove()
469 (!sib->right || sib->right->color == IBV_BLACK)) { in __mm_remove()
470 sib->color = IBV_RED; in __mm_remove()
471 child = parent; in __mm_remove()
472 parent = child->parent; in __mm_remove()
474 if (!sib->left || sib->left->color == IBV_BLACK) { in __mm_remove()
475 if (sib->right) in __mm_remove()
476 sib->right->color = IBV_BLACK; in __mm_remove()
477 sib->color = IBV_RED; in __mm_remove()
479 sib = parent->left; in __mm_remove()
482 sib->color = parent->color; in __mm_remove()
483 parent->color = IBV_BLACK; in __mm_remove()
484 if (sib->left) in __mm_remove()
485 sib->left->color = IBV_BLACK; in __mm_remove()
486 __mm_rotate_right(parent); in __mm_remove()
487 child = mm_root; in __mm_remove()
493 if (child) in __mm_remove()
494 child->color = IBV_BLACK; in __mm_remove()
502 if (node->start <= start && node->end >= start) in __mm_find_start()
505 if (node->start < start) in __mm_find_start()
506 node = node->right; in __mm_find_start()
508 node = node->left; in __mm_find_start()
517 prev->end = node->end; in merge_ranges()
518 prev->refcnt = node->refcnt; in merge_ranges()
532 new_node->start = cut_line; in split_range()
533 new_node->end = node->end; in split_range()
534 new_node->refcnt = node->refcnt; in split_range()
535 node->end = cut_line - 1; in split_range()
547 if (node->start < start) in get_start_node()
551 if (tmp && tmp->refcnt == node->refcnt + inc) in get_start_node()
570 if (start > node->start) { in undo_node()
573 node->refcnt += inc; in undo_node()
580 if (tmp && tmp->refcnt == node->refcnt) in undo_node()
584 if (tmp && tmp->refcnt == node->refcnt) in undo_node()
607 start = (uintptr_t) base & ~(range_page_size - 1); in ibv_madvise_range()
608 end = ((uintptr_t) (base + size + range_page_size - 1) & in ibv_madvise_range()
609 ~(range_page_size - 1)) - 1; in ibv_madvise_range()
613 inc = advice == MADV_DONTFORK ? 1 : -1; in ibv_madvise_range()
617 ret = -1; in ibv_madvise_range()
621 while (node && node->start <= end) { in ibv_madvise_range()
622 if (node->end > end) { in ibv_madvise_range()
624 ret = -1; in ibv_madvise_range()
629 if ((inc == -1 && node->refcnt == 1) || in ibv_madvise_range()
630 (inc == 1 && node->refcnt == 0)) { in ibv_madvise_range()
635 * on start ... node->end (rather than in ibv_madvise_range()
636 * starting at node->start). in ibv_madvise_range()
642 if (start > node->start) in ibv_madvise_range()
643 ret = madvise((void *) start, node->end - start + 1, in ibv_madvise_range()
646 ret = madvise((void *) node->start, in ibv_madvise_range()
647 node->end - node->start + 1, in ibv_madvise_range()
660 if (!tmp || start > tmp->end) in ibv_madvise_range()
662 end = tmp->end; in ibv_madvise_range()
667 node->refcnt += inc; in ibv_madvise_range()
673 if (tmp && node->refcnt == tmp->refcnt) in ibv_madvise_range()
679 ret = -1; in ibv_madvise_range()