![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rdxtree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to rdxtree.c CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1 root 1: /*
2: * Copyright (c) 2011-2015 Richard Braun.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms, with or without
6: * modification, are permitted provided that the following conditions
7: * are met:
8: * 1. Redistributions of source code must retain the above copyright
9: * notice, this list of conditions and the following disclaimer.
10: * 2. Redistributions in binary form must reproduce the above copyright
11: * notice, this list of conditions and the following disclaimer in the
12: * documentation and/or other materials provided with the distribution.
13: *
14: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24: *
25: *
26: * Upstream site with license notes :
27: * http://git.sceen.net/rbraun/librbraun.git/
28: */
29:
30: #include <kern/assert.h>
31: #include <kern/slab.h>
32: #include <mach/kern_return.h>
33: #include <stddef.h>
34: #include <string.h>
35:
36: #include "macros.h"
37: #include "rdxtree.h"
38: #include "rdxtree_i.h"
39:
40: /* XXX */
41: #define CHAR_BIT 8U
42: #define ERR_SUCCESS KERN_SUCCESS
43: #define ERR_BUSY KERN_INVALID_ARGUMENT
44: #define ERR_NOMEM KERN_RESOURCE_SHORTAGE
45:
46: /*
47: * Mask applied on an entry to obtain its address.
48: */
49: #define RDXTREE_ENTRY_ADDR_MASK (~0x3UL)
50:
51: /*
52: * Global properties used to shape radix trees.
53: */
54: #define RDXTREE_RADIX 6
55: #define RDXTREE_RADIX_SIZE (1UL << RDXTREE_RADIX)
56: #define RDXTREE_RADIX_MASK (RDXTREE_RADIX_SIZE - 1)
57:
58: #if RDXTREE_RADIX < 6
59: typedef unsigned long rdxtree_bm_t;
60: #define rdxtree_ffs(x) __builtin_ffsl(x)
61: #elif RDXTREE_RADIX == 6 /* RDXTREE_RADIX < 6 */
62: typedef unsigned long long rdxtree_bm_t;
63: #define rdxtree_ffs(x) __builtin_ffsll(x)
64: #else /* RDXTREE_RADIX < 6 */
65: #error "radix too high"
66: #endif /* RDXTREE_RADIX < 6 */
67:
68: /*
69: * Allocation bitmap size in bits.
70: */
71: #define RDXTREE_BM_SIZE (sizeof(rdxtree_bm_t) * CHAR_BIT)
72:
73: /*
74: * Empty/full allocation bitmap words.
75: */
76: #define RDXTREE_BM_EMPTY ((rdxtree_bm_t)0)
77: #define RDXTREE_BM_FULL \
78: ((~(rdxtree_bm_t)0) >> (RDXTREE_BM_SIZE - RDXTREE_RADIX_SIZE))
79:
80: /*
81: * These macros can be replaced by actual functions in an environment
82: * that provides lockless synchronization such as RCU.
83: */
84: #define llsync_assign_ptr(ptr, value) ((ptr) = (value))
85: #define llsync_read_ptr(ptr) (ptr)
86:
87: /*
88: * Radix tree node.
89: *
90: * The height of a tree is the number of nodes to traverse until stored
91: * pointers are reached. A height of 0 means the entries of a node (or the
92: * tree root) directly point to stored pointers.
93: *
94: * The index is valid if and only if the parent isn't NULL.
95: *
96: * Concerning the allocation bitmap, a bit is set when the node it denotes,
97: * or one of its children, can be used to allocate an entry. Conversely, a bit
98: * is clear when the matching node and all of its children have no free entry.
99: *
100: * In order to support safe lockless lookups, in particular during a resize,
101: * each node includes the height of its subtree, which is invariant during
102: * the entire node lifetime. Since the tree height does vary, it can't be
103: * used to determine whether the tree root is a node or a stored pointer.
104: * This implementation assumes that all nodes and stored pointers are at least
105: * 4-byte aligned, and uses the least significant bit of entries to indicate
106: * the pointer type. This bit is set for internal nodes, and clear for stored
107: * pointers so that they can be accessed from slots without conversion.
108: */
109: struct rdxtree_node {
110: struct rdxtree_node *parent;
111: unsigned int index;
112: unsigned int height;
113: unsigned int nr_entries;
114: rdxtree_bm_t alloc_bm;
115: void *entries[RDXTREE_RADIX_SIZE];
116: };
117:
118: /*
119: * We allocate nodes using the slab allocator.
120: */
121: static struct kmem_cache rdxtree_node_cache;
122:
123: void
124: rdxtree_cache_init(void)
125: {
126: kmem_cache_init(&rdxtree_node_cache, "rdxtree_node",
1.1.1.2 ! root 127: sizeof(struct rdxtree_node), 0, NULL, 0);
1.1 root 128: }
129:
130: #ifdef RDXTREE_ENABLE_NODE_CREATION_FAILURES
131: unsigned int rdxtree_fail_node_creation_threshold;
132: unsigned int rdxtree_nr_node_creations;
133: #endif /* RDXTREE_ENABLE_NODE_CREATION_FAILURES */
134:
135: static inline int
136: rdxtree_check_alignment(const void *ptr)
137: {
138: return ((unsigned long)ptr & ~RDXTREE_ENTRY_ADDR_MASK) == 0;
139: }
140:
141: static inline void *
142: rdxtree_entry_addr(void *entry)
143: {
144: return (void *)((unsigned long)entry & RDXTREE_ENTRY_ADDR_MASK);
145: }
146:
147: static inline int
148: rdxtree_entry_is_node(const void *entry)
149: {
150: return ((unsigned long)entry & 1) != 0;
151: }
152:
153: static inline void *
154: rdxtree_node_to_entry(struct rdxtree_node *node)
155: {
156: return (void *)((unsigned long)node | 1);
157: }
158:
159: static int
160: rdxtree_node_create(struct rdxtree_node **nodep, unsigned int height)
161: {
162: struct rdxtree_node *node;
163:
164: #ifdef RDXTREE_ENABLE_NODE_CREATION_FAILURES
165: if (rdxtree_fail_node_creation_threshold != 0) {
166: rdxtree_nr_node_creations++;
167:
168: if (rdxtree_nr_node_creations == rdxtree_fail_node_creation_threshold)
169: return ERR_NOMEM;
170: }
171: #endif /* RDXTREE_ENABLE_NODE_CREATION_FAILURES */
172:
173: node = (struct rdxtree_node *) kmem_cache_alloc(&rdxtree_node_cache);
174:
175: if (node == NULL)
176: return ERR_NOMEM;
177:
178: assert(rdxtree_check_alignment(node));
179: node->parent = NULL;
180: node->height = height;
181: node->nr_entries = 0;
182: node->alloc_bm = RDXTREE_BM_FULL;
183: memset(node->entries, 0, sizeof(node->entries));
184: *nodep = node;
185: return 0;
186: }
187:
188: static void
189: rdxtree_node_schedule_destruction(struct rdxtree_node *node)
190: {
191: /*
192: * This function is intended to use the appropriate interface to defer
193: * destruction until all read-side references are dropped in an
194: * environment that provides lockless synchronization.
195: *
196: * Otherwise, it simply "schedules" destruction immediately.
197: */
198: kmem_cache_free(&rdxtree_node_cache, (vm_offset_t) node);
199: }
200:
201: static inline void
202: rdxtree_node_link(struct rdxtree_node *node, struct rdxtree_node *parent,
203: unsigned int index)
204: {
205: node->parent = parent;
206: node->index = index;
207: }
208:
209: static inline void
210: rdxtree_node_unlink(struct rdxtree_node *node)
211: {
212: assert(node->parent != NULL);
213: node->parent = NULL;
214: }
215:
216: static inline int
217: rdxtree_node_full(struct rdxtree_node *node)
218: {
219: return (node->nr_entries == ARRAY_SIZE(node->entries));
220: }
221:
222: static inline int
223: rdxtree_node_empty(struct rdxtree_node *node)
224: {
225: return (node->nr_entries == 0);
226: }
227:
228: static inline void
229: rdxtree_node_insert(struct rdxtree_node *node, unsigned int index,
230: void *entry)
231: {
232: assert(index < ARRAY_SIZE(node->entries));
233: assert(node->entries[index] == NULL);
234:
235: node->nr_entries++;
236: llsync_assign_ptr(node->entries[index], entry);
237: }
238:
239: static inline void
240: rdxtree_node_insert_node(struct rdxtree_node *node, unsigned int index,
241: struct rdxtree_node *child)
242: {
243: rdxtree_node_insert(node, index, rdxtree_node_to_entry(child));
244: }
245:
246: static inline void
247: rdxtree_node_remove(struct rdxtree_node *node, unsigned int index)
248: {
249: assert(index < ARRAY_SIZE(node->entries));
250: assert(node->entries[index] != NULL);
251:
252: node->nr_entries--;
253: llsync_assign_ptr(node->entries[index], NULL);
254: }
255:
256: static inline void *
257: rdxtree_node_find(struct rdxtree_node *node, unsigned int *indexp)
258: {
259: unsigned int index;
260: void *ptr;
261:
262: index = *indexp;
263:
264: while (index < ARRAY_SIZE(node->entries)) {
265: ptr = rdxtree_entry_addr(llsync_read_ptr(node->entries[index]));
266:
267: if (ptr != NULL) {
268: *indexp = index;
269: return ptr;
270: }
271:
272: index++;
273: }
274:
275: return NULL;
276: }
277:
278: static inline void
279: rdxtree_node_bm_set(struct rdxtree_node *node, unsigned int index)
280: {
281: node->alloc_bm |= (rdxtree_bm_t)1 << index;
282: }
283:
284: static inline void
285: rdxtree_node_bm_clear(struct rdxtree_node *node, unsigned int index)
286: {
287: node->alloc_bm &= ~((rdxtree_bm_t)1 << index);
288: }
289:
290: static inline int
291: rdxtree_node_bm_is_set(struct rdxtree_node *node, unsigned int index)
292: {
293: return (node->alloc_bm & ((rdxtree_bm_t)1 << index));
294: }
295:
296: static inline int
297: rdxtree_node_bm_empty(struct rdxtree_node *node)
298: {
299: return (node->alloc_bm == RDXTREE_BM_EMPTY);
300: }
301:
302: static inline unsigned int
303: rdxtree_node_bm_first(struct rdxtree_node *node)
304: {
305: return rdxtree_ffs(node->alloc_bm) - 1;
306: }
307:
308: static inline rdxtree_key_t
309: rdxtree_max_key(unsigned int height)
310: {
311: size_t shift;
312:
313: shift = RDXTREE_RADIX * height;
314:
315: if (likely(shift < (sizeof(rdxtree_key_t) * CHAR_BIT)))
316: return ((rdxtree_key_t)1 << shift) - 1;
317: else
318: return ~((rdxtree_key_t)0);
319: }
320:
321: static void
322: rdxtree_shrink(struct rdxtree *tree)
323: {
324: struct rdxtree_node *node;
325: void *entry;
326:
327: while (tree->height > 0) {
328: node = rdxtree_entry_addr(tree->root);
329:
330: if (node->nr_entries != 1)
331: break;
332:
333: entry = node->entries[0];
334:
335: if (entry == NULL)
336: break;
337:
338: tree->height--;
339:
340: if (tree->height > 0)
341: rdxtree_node_unlink(rdxtree_entry_addr(entry));
342:
343: llsync_assign_ptr(tree->root, entry);
344: rdxtree_node_schedule_destruction(node);
345: }
346: }
347:
348: static int
349: rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key)
350: {
351: struct rdxtree_node *root, *node;
352: unsigned int new_height;
353: int error;
354:
355: new_height = tree->height + 1;
356:
357: while (key > rdxtree_max_key(new_height))
358: new_height++;
359:
360: if (tree->root == NULL) {
361: tree->height = new_height;
362: return ERR_SUCCESS;
363: }
364:
365: root = rdxtree_entry_addr(tree->root);
366:
367: do {
368: error = rdxtree_node_create(&node, tree->height);
369:
370: if (error) {
371: rdxtree_shrink(tree);
372: return error;
373: }
374:
375: if (tree->height == 0)
376: rdxtree_node_bm_clear(node, 0);
377: else {
378: rdxtree_node_link(root, node, 0);
379:
380: if (rdxtree_node_bm_empty(root))
381: rdxtree_node_bm_clear(node, 0);
382: }
383:
384: rdxtree_node_insert(node, 0, tree->root);
385: tree->height++;
386: llsync_assign_ptr(tree->root, rdxtree_node_to_entry(node));
387: root = node;
388: } while (new_height > tree->height);
389:
390: return ERR_SUCCESS;
391: }
392:
393: static void
394: rdxtree_cleanup(struct rdxtree *tree, struct rdxtree_node *node)
395: {
396: struct rdxtree_node *prev;
397:
398: for (;;) {
399: if (likely(!rdxtree_node_empty(node))) {
400: if (unlikely(node->parent == NULL))
401: rdxtree_shrink(tree);
402:
403: break;
404: }
405:
406: if (node->parent == NULL) {
407: tree->height = 0;
408: llsync_assign_ptr(tree->root, NULL);
409: rdxtree_node_schedule_destruction(node);
410: break;
411: }
412:
413: prev = node;
414: node = node->parent;
415: rdxtree_node_unlink(prev);
416: rdxtree_node_remove(node, prev->index);
417: rdxtree_node_schedule_destruction(prev);
418: }
419: }
420:
421: static void
422: rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned int index)
423: {
424: for (;;) {
425: rdxtree_node_bm_clear(node, index);
426:
427: if (!rdxtree_node_full(node) || (node->parent == NULL))
428: break;
429:
430: index = node->index;
431: node = node->parent;
432: }
433: }
434:
435: int
436: rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key,
437: void *ptr, void ***slotp)
438: {
439: struct rdxtree_node *node, *prev;
440: unsigned int height, shift, index = index;
441: int error;
442:
443: assert(ptr != NULL);
444: assert(rdxtree_check_alignment(ptr));
445:
446: if (unlikely(key > rdxtree_max_key(tree->height))) {
447: error = rdxtree_grow(tree, key);
448:
449: if (error)
450: return error;
451: }
452:
453: height = tree->height;
454:
455: if (unlikely(height == 0)) {
456: if (tree->root != NULL)
457: return ERR_BUSY;
458:
459: llsync_assign_ptr(tree->root, ptr);
460:
461: if (slotp != NULL)
462: *slotp = &tree->root;
463:
464: return ERR_SUCCESS;
465: }
466:
467: node = rdxtree_entry_addr(tree->root);
468: shift = (height - 1) * RDXTREE_RADIX;
469: prev = NULL;
470:
471: do {
472: if (node == NULL) {
473: error = rdxtree_node_create(&node, height - 1);
474:
475: if (error) {
476: if (prev == NULL)
477: tree->height = 0;
478: else
479: rdxtree_cleanup(tree, prev);
480:
481: return error;
482: }
483:
484: if (prev == NULL)
485: llsync_assign_ptr(tree->root, rdxtree_node_to_entry(node));
486: else {
487: rdxtree_node_link(node, prev, index);
488: rdxtree_node_insert_node(prev, index, node);
489: }
490: }
491:
492: prev = node;
493: index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK;
494: node = rdxtree_entry_addr(prev->entries[index]);
495: shift -= RDXTREE_RADIX;
496: height--;
497: } while (height > 0);
498:
499: if (unlikely(node != NULL))
500: return ERR_BUSY;
501:
502: rdxtree_node_insert(prev, index, ptr);
503: rdxtree_insert_bm_clear(prev, index);
504:
505: if (slotp != NULL)
506: *slotp = &prev->entries[index];
507:
508: return ERR_SUCCESS;
509: }
510:
511: int
512: rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
513: rdxtree_key_t *keyp, void ***slotp)
514: {
515: struct rdxtree_node *node, *prev;
516: unsigned int height, shift, index = index;
517: rdxtree_key_t key;
518: int error;
519:
520: assert(ptr != NULL);
521: assert(rdxtree_check_alignment(ptr));
522:
523: height = tree->height;
524:
525: if (unlikely(height == 0)) {
526: if (tree->root == NULL) {
527: llsync_assign_ptr(tree->root, ptr);
528: *keyp = 0;
529:
530: if (slotp != NULL)
531: *slotp = &tree->root;
532:
533: return ERR_SUCCESS;
534: }
535:
536: goto grow;
537: }
538:
539: node = rdxtree_entry_addr(tree->root);
540: key = 0;
541: shift = (height - 1) * RDXTREE_RADIX;
542: prev = NULL;
543:
544: do {
545: if (node == NULL) {
546: error = rdxtree_node_create(&node, height - 1);
547:
548: if (error) {
549: rdxtree_cleanup(tree, prev);
550: return error;
551: }
552:
553: rdxtree_node_link(node, prev, index);
554: rdxtree_node_insert_node(prev, index, node);
555: }
556:
557: prev = node;
558: index = rdxtree_node_bm_first(node);
559:
560: if (index == (unsigned int)-1)
561: goto grow;
562:
563: key |= (rdxtree_key_t)index << shift;
564: node = rdxtree_entry_addr(node->entries[index]);
565: shift -= RDXTREE_RADIX;
566: height--;
567: } while (height > 0);
568:
569: rdxtree_node_insert(prev, index, ptr);
570: rdxtree_insert_bm_clear(prev, index);
571:
572: if (slotp != NULL)
573: *slotp = &prev->entries[index];
574:
575: goto out;
576:
577: grow:
578: key = rdxtree_max_key(height) + 1;
579: error = rdxtree_insert_common(tree, key, ptr, slotp);
580:
581: if (error)
582: return error;
583:
584: out:
585: *keyp = key;
586: return ERR_SUCCESS;
587: }
588:
589: static void
590: rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned int index)
591: {
592: do {
593: rdxtree_node_bm_set(node, index);
594:
595: if (node->parent == NULL)
596: break;
597:
598: index = node->index;
599: node = node->parent;
600: } while (!rdxtree_node_bm_is_set(node, index));
601: }
602:
603: void *
604: rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key)
605: {
606: struct rdxtree_node *node, *prev;
607: unsigned int height, shift, index;
608:
609: height = tree->height;
610:
611: if (unlikely(key > rdxtree_max_key(height)))
612: return NULL;
613:
614: node = rdxtree_entry_addr(tree->root);
615:
616: if (unlikely(height == 0)) {
617: llsync_assign_ptr(tree->root, NULL);
618: return node;
619: }
620:
621: shift = (height - 1) * RDXTREE_RADIX;
622:
623: do {
624: if (node == NULL)
625: return NULL;
626:
627: prev = node;
628: index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK;
629: node = rdxtree_entry_addr(node->entries[index]);
630: shift -= RDXTREE_RADIX;
631: height--;
632: } while (height > 0);
633:
634: if (node == NULL)
635: return NULL;
636:
637: rdxtree_node_remove(prev, index);
638: rdxtree_remove_bm_set(prev, index);
639: rdxtree_cleanup(tree, prev);
640: return node;
641: }
642:
643: void *
644: rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key,
645: int get_slot)
646: {
647: struct rdxtree_node *node, *prev;
648: unsigned int height, shift, index;
649: void *entry;
650:
651: entry = llsync_read_ptr(tree->root);
652:
653: if (entry == NULL) {
654: node = NULL;
655: height = 0;
656: } else {
657: node = rdxtree_entry_addr(entry);
658: height = rdxtree_entry_is_node(entry) ? node->height + 1 : 0;
659: }
660:
661: if (key > rdxtree_max_key(height))
662: return NULL;
663:
664: if (height == 0) {
665: if (node == NULL)
666: return NULL;
667:
668: return get_slot ? (void *)&tree->root : node;
669: }
670:
671: shift = (height - 1) * RDXTREE_RADIX;
672:
673: do {
674: if (node == NULL)
675: return NULL;
676:
677: prev = node;
678: index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK;
679: entry = llsync_read_ptr(node->entries[index]);
680: node = rdxtree_entry_addr(entry);
681: shift -= RDXTREE_RADIX;
682: height--;
683: } while (height > 0);
684:
685: if (node == NULL)
686: return NULL;
687:
688: return get_slot ? (void *)&prev->entries[index] : node;
689: }
690:
691: void *
692: rdxtree_replace_slot(void **slot, void *ptr)
693: {
694: void *old;
695:
696: assert(ptr != NULL);
697: assert(rdxtree_check_alignment(ptr));
698:
699: old = *slot;
700: assert(old != NULL);
701: assert(rdxtree_check_alignment(old));
702: llsync_assign_ptr(*slot, ptr);
703: return old;
704: }
705:
706: static void *
707: rdxtree_walk_next(struct rdxtree *tree, struct rdxtree_iter *iter)
708: {
709: struct rdxtree_node *root, *node, *prev;
710: unsigned int height, shift, index, orig_index;
711: rdxtree_key_t key;
712: void *entry;
713:
714: entry = llsync_read_ptr(tree->root);
715:
716: if (entry == NULL)
717: return NULL;
718:
719: if (!rdxtree_entry_is_node(entry)) {
720: if (iter->key != (rdxtree_key_t)-1)
721: return NULL;
722: else {
723: iter->key = 0;
724: return rdxtree_entry_addr(entry);
725: }
726: }
727:
728: key = iter->key + 1;
729:
730: if ((key == 0) && (iter->node != NULL))
731: return NULL;
732:
733: root = rdxtree_entry_addr(entry);
734:
735: restart:
736: node = root;
737: height = root->height + 1;
738:
739: if (key > rdxtree_max_key(height))
740: return NULL;
741:
742: shift = (height - 1) * RDXTREE_RADIX;
743:
744: do {
745: prev = node;
746: index = (key >> shift) & RDXTREE_RADIX_MASK;
747: orig_index = index;
748: node = rdxtree_node_find(node, &index);
749:
750: if (node == NULL) {
751: shift += RDXTREE_RADIX;
752: key = ((key >> shift) + 1) << shift;
753:
754: if (key == 0)
755: return NULL;
756:
757: goto restart;
758: }
759:
760: if (orig_index != index)
761: key = ((key >> shift) + (index - orig_index)) << shift;
762:
763: shift -= RDXTREE_RADIX;
764: height--;
765: } while (height > 0);
766:
767: iter->node = prev;
768: iter->key = key;
769: return node;
770: }
771:
772: void *
773: rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter)
774: {
775: unsigned int index, orig_index;
776: void *ptr;
777:
778: if (iter->node == NULL)
779: return rdxtree_walk_next(tree, iter);
780:
781: index = (iter->key + 1) & RDXTREE_RADIX_MASK;
782:
783: if (index != 0) {
784: orig_index = index;
785: ptr = rdxtree_node_find(iter->node, &index);
786:
787: if (ptr != NULL) {
788: iter->key += (index - orig_index) + 1;
789: return ptr;
790: }
791: }
792:
793: return rdxtree_walk_next(tree, iter);
794: }
795:
796: void
797: rdxtree_remove_all(struct rdxtree *tree)
798: {
799: struct rdxtree_node *node, *parent;
800: struct rdxtree_iter iter;
801:
802: if (tree->height == 0) {
803: if (tree->root != NULL)
804: llsync_assign_ptr(tree->root, NULL);
805:
806: return;
807: }
808:
809: for (;;) {
810: rdxtree_iter_init(&iter);
811: rdxtree_walk_next(tree, &iter);
812:
813: if (iter.node == NULL)
814: break;
815:
816: node = iter.node;
817: parent = node->parent;
818:
819: if (parent == NULL)
820: rdxtree_init(tree);
821: else {
822: rdxtree_node_remove(parent, node->index);
823: rdxtree_remove_bm_set(parent, node->index);
824: rdxtree_cleanup(tree, parent);
825: node->parent = NULL;
826: }
827:
828: rdxtree_node_schedule_destruction(node);
829: }
830: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.