Lines Matching full:node
74 tag_get(const struct radix_tree_node *node, unsigned int tag, int pos) in tag_get() argument
76 return (test_bit(pos, node->tags[tag])); in tag_get()
80 tag_set(struct radix_tree_node *node, unsigned int tag, int pos) in tag_set() argument
82 set_bit(pos, node->tags[tag]); in tag_set()
86 tag_clear(struct radix_tree_node *node, unsigned int tag, int pos) in tag_clear() argument
88 clear_bit(pos, node->tags[tag]); in tag_clear()
92 any_tag_set(const struct radix_tree_node *node, unsigned int tag) in any_tag_set() argument
97 if (node->tags[tag][pos]) in any_tag_set()
107 struct radix_tree_node *node; in node_tag_clear() local
111 node = stack[height]; in node_tag_clear()
113 while (node && height <= root->height - 1) { in node_tag_clear()
115 if (!tag_get(node, tag, pos)) in node_tag_clear()
118 tag_clear(node, tag, pos); in node_tag_clear()
119 if (any_tag_set(node, tag)) in node_tag_clear()
123 node = stack[height]; in node_tag_clear()
133 /* Check if the root node should be freed */ in radix_tree_clean_root_node()
144 struct radix_tree_node *node; in radix_tree_lookup() local
149 node = root->rnode; in radix_tree_lookup()
153 while (height && node) in radix_tree_lookup()
154 node = node->slots[radix_pos(index, height--)]; in radix_tree_lookup()
155 if (node) in radix_tree_lookup()
156 item = node->slots[radix_pos(index, 0)]; in radix_tree_lookup()
217 struct radix_tree_node *node; in radix_tree_iter_find() local
227 node = root->rnode; in radix_tree_iter_find()
228 if (node == NULL) in radix_tree_iter_find()
240 *pppslot = node->slots + pos; in radix_tree_iter_find()
242 next = node->slots[pos]; in radix_tree_iter_find()
251 node = next; in radix_tree_iter_find()
263 struct radix_tree_node *node; in radix_tree_delete() local
270 node = root->rnode; in radix_tree_delete()
275 * Find the node and record the path in stack. in radix_tree_delete()
277 while (height && node) { in radix_tree_delete()
278 stack[height] = node; in radix_tree_delete()
279 node = node->slots[radix_pos(index, height--)]; in radix_tree_delete()
282 if (node) { in radix_tree_delete()
284 item = node->slots[idx]; in radix_tree_delete()
295 node->slots[idx] = NULL; in radix_tree_delete()
296 node->count--; in radix_tree_delete()
297 if (node->count > 0) in radix_tree_delete()
299 free(node, M_RADIX); in radix_tree_delete()
300 if (node == root->rnode) { in radix_tree_delete()
306 node = stack[height]; in radix_tree_delete()
323 struct radix_tree_node *node; in radix_tree_insert() local
332 /* get root node, if any */ in radix_tree_insert()
333 node = root->rnode; in radix_tree_insert()
335 /* allocate root node, if any */ in radix_tree_insert()
336 if (node == NULL) { in radix_tree_insert()
337 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); in radix_tree_insert()
338 if (node == NULL) in radix_tree_insert()
340 root->rnode = node; in radix_tree_insert()
356 if (node->count != 0) { in radix_tree_insert()
357 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); in radix_tree_insert()
358 if (node == NULL) { in radix_tree_insert()
368 node->slots[0] = root->rnode; in radix_tree_insert()
369 node->count++; in radix_tree_insert()
370 root->rnode = node; in radix_tree_insert()
378 /* walk down the tree until the first missing node, if any */ in radix_tree_insert()
381 if (node->slots[idx] == NULL) in radix_tree_insert()
383 node = node->slots[idx]; in radix_tree_insert()
388 temp[idx] = malloc(sizeof(*node), M_RADIX, in radix_tree_insert()
401 node->slots[idx] = temp[height - 1]; in radix_tree_insert()
402 node->count++; in radix_tree_insert()
403 node = node->slots[idx]; in radix_tree_insert()
410 if (node->slots[idx]) in radix_tree_insert()
412 node->slots[idx] = item; in radix_tree_insert()
413 node->count++; in radix_tree_insert()
421 struct radix_tree_node *node; in radix_tree_store() local
436 /* get root node, if any */ in radix_tree_store()
437 node = root->rnode; in radix_tree_store()
439 /* allocate root node, if any */ in radix_tree_store()
440 if (node == NULL) { in radix_tree_store()
441 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); in radix_tree_store()
442 if (node == NULL) in radix_tree_store()
444 root->rnode = node; in radix_tree_store()
460 if (node->count != 0) { in radix_tree_store()
461 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); in radix_tree_store()
462 if (node == NULL) { in radix_tree_store()
472 node->slots[0] = root->rnode; in radix_tree_store()
473 node->count++; in radix_tree_store()
474 root->rnode = node; in radix_tree_store()
482 /* walk down the tree until the first missing node, if any */ in radix_tree_store()
485 if (node->slots[idx] == NULL) in radix_tree_store()
487 node = node->slots[idx]; in radix_tree_store()
492 temp[idx] = malloc(sizeof(*node), M_RADIX, in radix_tree_store()
505 node->slots[idx] = temp[height - 1]; in radix_tree_store()
506 node->count++; in radix_tree_store()
507 node = node->slots[idx]; in radix_tree_store()
515 pitem = node->slots[idx]; in radix_tree_store()
516 node->slots[idx] = *ppitem; in radix_tree_store()
520 node->count++; in radix_tree_store()
528 struct radix_tree_node *node; in radix_tree_tag_set() local
533 node = root->rnode; in radix_tree_tag_set()
540 node != NULL, in radix_tree_tag_set()
541 ("Node at index %lu does not exist in radix tree %p", in radix_tree_tag_set()
545 node = node->slots[pos]; in radix_tree_tag_set()
547 if (!tag_get(node, tag, pos)) in radix_tree_tag_set()
548 tag_set(node, tag, pos); in radix_tree_tag_set()
551 item = node->slots[radix_pos(index, 0)]; in radix_tree_tag_set()
564 struct radix_tree_node *node; in radix_tree_tag_clear() local
569 node = root->rnode; in radix_tree_tag_clear()
574 while (height && node) { in radix_tree_tag_clear()
575 stack[height] = node; in radix_tree_tag_clear()
576 node = node->slots[radix_pos(index, height--)]; in radix_tree_tag_clear()
579 if (node) { in radix_tree_tag_clear()
580 item = node->slots[radix_pos(index, 0)]; in radix_tree_tag_clear()