Annotation of src/common/lib/libc/gen/radixtree.c, Revision 1.4
1.4 ! yamt 1: /* $NetBSD: radixtree.c,v 1.3 2011/04/26 20:53:53 yamt Exp $ */
1.1 yamt 2:
3: /*-
4: * Copyright (c)2011 YAMAMOTO Takashi,
5: * All rights reserved.
6: *
7: * Redistribution and use in source and binary forms, with or without
8: * modification, are permitted provided that the following conditions
9: * are met:
10: * 1. Redistributions of source code must retain the above copyright
11: * notice, this list of conditions and the following disclaimer.
12: * 2. Redistributions in binary form must reproduce the above copyright
13: * notice, this list of conditions and the following disclaimer in the
14: * documentation and/or other materials provided with the distribution.
15: *
16: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19: * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26: * SUCH DAMAGE.
27: */
28:
29: /*
30: * radix tree
31: *
32: * it's designed to work efficiently with dense index distribution.
33: * the memory consumption (number of necessary intermediate nodes)
34: * heavily depends on index distribution. basically, more dense index
35: * distribution consumes less nodes per item.
36: * approximately,
37: * the best case: about RADIX_TREE_PTR_PER_NODE items per node.
38: * the worst case: RADIX_TREE_MAX_HEIGHT nodes per item.
39: */
40:
41: #include <sys/cdefs.h>
42:
1.2 yamt 43: #if defined(_KERNEL) || defined(_STANDALONE)
1.4 ! yamt 44: __KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.3 2011/04/26 20:53:53 yamt Exp $");
1.1 yamt 45: #include <sys/param.h>
1.3 yamt 46: #include <sys/errno.h>
1.1 yamt 47: #include <sys/pool.h>
48: #include <sys/radixtree.h>
1.3 yamt 49: #include <lib/libkern/libkern.h>
50: #if defined(_STANDALONE)
51: #include <lib/libsa/stand.h>
52: #endif /* defined(_STANDALONE) */
1.2 yamt 53: #else /* defined(_KERNEL) || defined(_STANDALONE) */
1.4 ! yamt 54: __RCSID("$NetBSD: radixtree.c,v 1.3 2011/04/26 20:53:53 yamt Exp $");
1.1 yamt 55: #include <assert.h>
56: #include <errno.h>
57: #include <stdbool.h>
58: #include <stdlib.h>
59: #if 1
60: #define KASSERT assert
61: #else
62: #define KASSERT(a) /* nothing */
63: #endif
1.2 yamt 64: #endif /* defined(_KERNEL) || defined(_STANDALONE) */
1.1 yamt 65:
66: #include <sys/radixtree.h>
67:
68: #define RADIX_TREE_BITS_PER_HEIGHT 4 /* XXX tune */
69: #define RADIX_TREE_PTR_PER_NODE (1 << RADIX_TREE_BITS_PER_HEIGHT)
70: #define RADIX_TREE_MAX_HEIGHT (64 / RADIX_TREE_BITS_PER_HEIGHT)
1.2 yamt 71: __CTASSERT((64 % RADIX_TREE_BITS_PER_HEIGHT) == 0);
1.1 yamt 72:
1.2 yamt 73: __CTASSERT(((1 << RADIX_TREE_TAG_ID_MAX) & (sizeof(int) - 1)) == 0);
1.1 yamt 74: #define RADIX_TREE_TAG_MASK ((1 << RADIX_TREE_TAG_ID_MAX) - 1)
75:
76: static inline void *
77: entry_ptr(void *p)
78: {
79:
80: return (void *)((uintptr_t)p & ~RADIX_TREE_TAG_MASK);
81: }
82:
83: static inline unsigned int
84: entry_tagmask(void *p)
85: {
86:
87: return (uintptr_t)p & RADIX_TREE_TAG_MASK;
88: }
89:
90: static inline void *
91: entry_compose(void *p, unsigned int tagmask)
92: {
93:
94: return (void *)((uintptr_t)p | tagmask);
95: }
96:
97: static inline bool
98: entry_match_p(void *p, unsigned int tagmask)
99: {
100:
101: KASSERT(entry_ptr(p) != NULL || entry_tagmask(p) == 0);
102: if (p == NULL) {
103: return false;
104: }
105: if (tagmask == 0) {
106: return true;
107: }
108: return (entry_tagmask(p) & tagmask) != 0;
109: }
110:
111: static inline unsigned int
112: tagid_to_mask(radix_tree_tagid_t id)
113: {
114:
115: return 1U << id;
116: }
117:
118: /*
119: * radix_tree_node: an intermediate node
120: *
121: * we don't care the type of leaf nodes. they are just void *.
122: */
123:
124: struct radix_tree_node {
125: void *n_ptrs[RADIX_TREE_PTR_PER_NODE];
126: unsigned int n_nptrs; /* # of non-NULL pointers in n_ptrs */
127: };
128:
129: static unsigned int
130: any_children_tagmask(struct radix_tree_node *n)
131: {
132: unsigned int mask;
133: int i;
134:
135: mask = 0;
136: for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
137: mask |= (unsigned int)(uintptr_t)n->n_ptrs[i];
138: }
139: return mask & RADIX_TREE_TAG_MASK;
140: }
141:
142: /*
143: * p_refs[0].pptr == &t->t_root
144: * :
145: * p_refs[n].pptr == &(*p_refs[n-1])->n_ptrs[x]
146: * :
147: * :
148: * p_refs[t->t_height].pptr == &leaf_pointer
149: */
150:
151: struct radix_tree_path {
152: struct radix_tree_node_ref {
153: void **pptr;
154: } p_refs[RADIX_TREE_MAX_HEIGHT + 1]; /* +1 for the root ptr */
155: int p_lastidx;
156: };
157:
158: static inline void **
159: path_pptr(struct radix_tree *t, struct radix_tree_path *p,
160: unsigned int height)
161: {
162:
163: KASSERT(height <= t->t_height);
164: return p->p_refs[height].pptr;
165: }
166:
167: static inline struct radix_tree_node *
168: path_node(struct radix_tree * t, struct radix_tree_path *p, unsigned int height)
169: {
170:
171: KASSERT(height <= t->t_height);
172: return entry_ptr(*path_pptr(t, p, height));
173: }
174:
175: static inline unsigned int
176: path_idx(struct radix_tree * t, struct radix_tree_path *p, unsigned int height)
177: {
178:
179: KASSERT(height <= t->t_height);
180: return path_pptr(t, p, height + 1) - path_node(t, p, height)->n_ptrs;
181: }
182:
183: /*
184: * radix_tree_init_tree:
185: *
186: * initialize a tree.
187: */
188:
189: void
190: radix_tree_init_tree(struct radix_tree *t)
191: {
192:
193: t->t_height = 0;
194: t->t_root = NULL;
195: }
196:
197: /*
198: * radix_tree_init_tree:
199: *
200: * clean up a tree.
201: */
202:
203: void
204: radix_tree_fini_tree(struct radix_tree *t)
205: {
206:
207: KASSERT(t->t_root == NULL);
208: KASSERT(t->t_height == 0);
209: }
210:
1.3 yamt 211: static void
212: radix_tree_node_init(struct radix_tree_node *n)
213: {
214:
215: memset(n, 0, sizeof(*n));
216: }
217:
1.1 yamt 218: #if defined(_KERNEL)
1.2 yamt 219: pool_cache_t radix_tree_node_cache __read_mostly;
1.1 yamt 220:
221: static int
222: radix_tree_node_ctor(void *dummy, void *item, int flags)
223: {
224: struct radix_tree_node *n = item;
225:
226: KASSERT(dummy == NULL);
1.3 yamt 227: radix_tree_node_init(n);
1.1 yamt 228: return 0;
229: }
230:
231: /*
232: * radix_tree_init:
233: *
234: * initialize the subsystem.
235: */
236:
237: void
238: radix_tree_init(void)
239: {
240:
241: radix_tree_node_cache = pool_cache_init(sizeof(struct radix_tree_node),
242: 0, 0, 0, "radix_tree_node", NULL, IPL_NONE, radix_tree_node_ctor,
243: NULL, NULL);
244: KASSERT(radix_tree_node_cache != NULL);
245: }
246: #endif /* defined(_KERNEL) */
247:
248: static bool __unused
249: radix_tree_node_clean_p(const struct radix_tree_node *n)
250: {
251: unsigned int i;
252:
253: if (n->n_nptrs != 0) {
254: return false;
255: }
256: for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
257: if (n->n_ptrs[i] != NULL) {
258: return false;
259: }
260: }
261: return true;
262: }
263:
264: static struct radix_tree_node *
265: radix_tree_alloc_node(void)
266: {
267: struct radix_tree_node *n;
268:
269: #if defined(_KERNEL)
270: n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT);
271: #else /* defined(_KERNEL) */
1.3 yamt 272: #if defined(_STANDALONE)
273: n = alloc(sizeof(*n));
274: #else /* defined(_STANDALONE) */
275: n = malloc(sizeof(*n));
276: #endif /* defined(_STANDALONE) */
277: if (n != NULL) {
278: radix_tree_node_init(n);
279: }
1.1 yamt 280: #endif /* defined(_KERNEL) */
281: KASSERT(n == NULL || radix_tree_node_clean_p(n));
282: return n;
283: }
284:
285: static void
286: radix_tree_free_node(struct radix_tree_node *n)
287: {
288:
289: KASSERT(radix_tree_node_clean_p(n));
290: #if defined(_KERNEL)
291: pool_cache_put(radix_tree_node_cache, n);
1.3 yamt 292: #elif defined(_STANDALONE)
293: dealloc(n, sizeof(*n));
294: #else
1.1 yamt 295: free(n);
1.3 yamt 296: #endif
1.1 yamt 297: }
298:
299: static int
300: radix_tree_grow(struct radix_tree *t, unsigned int newheight)
301: {
302: const unsigned int tagmask = entry_tagmask(t->t_root);
303:
304: KASSERT(newheight <= 64 / RADIX_TREE_BITS_PER_HEIGHT);
305: if (t->t_root == NULL) {
306: t->t_height = newheight;
307: return 0;
308: }
309: while (t->t_height < newheight) {
310: struct radix_tree_node *n;
311:
312: n = radix_tree_alloc_node();
313: if (n == NULL) {
314: /*
315: * don't bother to revert our changes.
316: * the caller will likely retry.
317: */
318: return ENOMEM;
319: }
320: n->n_nptrs = 1;
321: n->n_ptrs[0] = t->t_root;
322: t->t_root = entry_compose(n, tagmask);
323: t->t_height++;
324: }
325: return 0;
326: }
327:
328: static inline void **
329: radix_tree_lookup_ptr(struct radix_tree *t, uint64_t idx,
330: struct radix_tree_path *path, bool alloc, const unsigned int tagmask)
331: {
332: struct radix_tree_node *n;
333: int hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height;
334: int shift;
335: void **vpp;
336: const uint64_t mask = (UINT64_C(1) << RADIX_TREE_BITS_PER_HEIGHT) - 1;
337: struct radix_tree_node_ref *refs = NULL;
338:
339: KASSERT(tagmask == 0 || !alloc);
340: KASSERT(path == NULL || !alloc);
341: vpp = &t->t_root;
342: if (path != NULL) {
343: refs = path->p_refs;
344: refs->pptr = vpp;
345: }
346: n = NULL;
347: for (shift = 64 - RADIX_TREE_BITS_PER_HEIGHT; shift >= 0;) {
348: struct radix_tree_node *c;
349: void *entry;
350: const uint64_t i = (idx >> shift) & mask;
351:
352: if (shift >= hshift) {
353: unsigned int newheight;
354:
355: KASSERT(vpp == &t->t_root);
356: if (i == 0) {
357: shift -= RADIX_TREE_BITS_PER_HEIGHT;
358: continue;
359: }
360: if (!alloc) {
361: if (path != NULL) {
362: KASSERT((refs - path->p_refs) == 0);
363: path->p_lastidx = 0;
364: }
365: return NULL;
366: }
367: newheight = shift / RADIX_TREE_BITS_PER_HEIGHT + 1;
368: if (radix_tree_grow(t, newheight)) {
369: return NULL;
370: }
371: hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height;
372: }
373: entry = *vpp;
374: c = entry_ptr(entry);
375: if (c == NULL ||
376: (tagmask != 0 &&
377: (entry_tagmask(entry) & tagmask) == 0)) {
378: if (!alloc) {
379: if (path != NULL) {
380: path->p_lastidx = refs - path->p_refs;
381: }
382: return NULL;
383: }
384: c = radix_tree_alloc_node();
385: if (c == NULL) {
386: return NULL;
387: }
388: *vpp = c;
389: if (n != NULL) {
390: KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE);
391: n->n_nptrs++;
392: }
393: }
394: n = c;
395: vpp = &n->n_ptrs[i];
396: if (path != NULL) {
397: refs++;
398: refs->pptr = vpp;
399: }
400: shift -= RADIX_TREE_BITS_PER_HEIGHT;
401: }
402: if (alloc) {
403: KASSERT(*vpp == NULL);
404: if (n != NULL) {
405: KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE);
406: n->n_nptrs++;
407: }
408: }
409: if (path != NULL) {
410: path->p_lastidx = refs - path->p_refs;
411: }
412: return vpp;
413: }
414:
415: /*
416: * radix_tree_insert_node:
417: *
418: * insert the node at idx.
419: * it's illegal to insert NULL.
420: * it's illegal to insert a non-aligned pointer.
421: *
422: * this function returns ENOMEM if necessary memory allocation failed.
423: * otherwise, this function returns 0.
424: *
425: * note that inserting a node can involves memory allocation for intermediate
426: * nodes. if _KERNEL, it's done with non-blocking IPL_NONE memory allocation.
1.4 ! yamt 427: *
! 428: * for the newly inserted node, all tags are cleared.
1.1 yamt 429: */
430:
431: int
432: radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p)
433: {
434: void **vpp;
435:
436: KASSERT(p != NULL);
437: KASSERT(entry_compose(p, 0) == p);
438: vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0);
439: if (vpp == NULL) {
440: return ENOMEM;
441: }
442: KASSERT(*vpp == NULL);
443: *vpp = p;
444: return 0;
445: }
446:
1.4 ! yamt 447: /*
! 448: * radix_tree_replace_node:
! 449: *
! 450: * replace a node at the given index with the given node.
! 451: * return the old node.
! 452: * it's illegal to try to replace a node which has not been inserted.
! 453: *
! 454: * this function doesn't change tags.
! 455: */
! 456:
1.1 yamt 457: void *
458: radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p)
459: {
460: void **vpp;
461: void *oldp;
462:
463: KASSERT(p != NULL);
464: KASSERT(entry_compose(p, 0) == p);
465: vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
466: KASSERT(vpp != NULL);
467: oldp = *vpp;
468: KASSERT(oldp != NULL);
469: *vpp = entry_compose(p, entry_tagmask(*vpp));
470: return entry_ptr(oldp);
471: }
472:
473: /*
474: * radix_tree_remove_node:
475: *
476: * remove the node at idx.
477: * it's illegal to try to remove a node which has not been inserted.
478: */
479:
480: void *
481: radix_tree_remove_node(struct radix_tree *t, uint64_t idx)
482: {
483: struct radix_tree_path path;
484: void **vpp;
485: void *oldp;
486: int i;
487:
488: vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
489: KASSERT(vpp != NULL);
490: oldp = *vpp;
491: KASSERT(oldp != NULL);
492: KASSERT(path.p_lastidx == t->t_height);
493: KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
494: *vpp = NULL;
495: for (i = t->t_height - 1; i >= 0; i--) {
496: void *entry;
497: struct radix_tree_node ** const pptr =
498: (struct radix_tree_node **)path_pptr(t, &path, i);
499: struct radix_tree_node *n;
500:
501: KASSERT(pptr != NULL);
502: entry = *pptr;
503: n = entry_ptr(entry);
504: KASSERT(n != NULL);
505: KASSERT(n->n_nptrs > 0);
506: n->n_nptrs--;
507: if (n->n_nptrs > 0) {
508: break;
509: }
510: radix_tree_free_node(n);
511: *pptr = NULL;
512: }
513: /*
514: * fix up height
515: */
516: if (i < 0) {
517: KASSERT(t->t_root == NULL);
518: t->t_height = 0;
519: }
520: /*
521: * update tags
522: */
523: for (; i >= 0; i--) {
524: void *entry;
525: struct radix_tree_node ** const pptr =
526: (struct radix_tree_node **)path_pptr(t, &path, i);
527: struct radix_tree_node *n;
528: unsigned int newmask;
529:
530: KASSERT(pptr != NULL);
531: entry = *pptr;
532: n = entry_ptr(entry);
533: KASSERT(n != NULL);
534: KASSERT(n->n_nptrs > 0);
535: newmask = any_children_tagmask(n);
536: if (newmask == entry_tagmask(entry)) {
537: break;
538: }
539: *pptr = entry_compose(n, newmask);
540: }
541: /*
542: * XXX is it worth to try to reduce height?
543: * if we do that, make radix_tree_grow rollback its change as well.
544: */
545: return entry_ptr(oldp);
546: }
547:
548: /*
549: * radix_tree_lookup_node:
550: *
551: * returns the node at idx.
552: * returns NULL if nothing is found at idx.
553: */
554:
555: void *
556: radix_tree_lookup_node(struct radix_tree *t, uint64_t idx)
557: {
558: void **vpp;
559:
560: vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
561: if (vpp == NULL) {
562: return NULL;
563: }
564: return entry_ptr(*vpp);
565: }
566:
567: static inline void
568: gang_lookup_init(struct radix_tree *t, uint64_t idx,
569: struct radix_tree_path *path, const unsigned int tagmask)
570: {
571: void **vpp;
572:
573: vpp = radix_tree_lookup_ptr(t, idx, path, false, tagmask);
574: KASSERT(vpp == NULL ||
575: vpp == path_pptr(t, path, path->p_lastidx));
576: KASSERT(&t->t_root == path_pptr(t, path, 0));
577: }
578:
579: static inline unsigned int
580: gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path,
581: void **results, unsigned int maxresults, const unsigned int tagmask)
582: {
583: void **vpp;
584: int nfound;
585: unsigned int lastidx;
586:
587: KASSERT(maxresults > 0);
588: lastidx = path->p_lastidx;
589: if (lastidx == 0) {
590: return 0;
591: }
592: nfound = 0;
593: vpp = path_pptr(t, path, lastidx);
594: while (/*CONSTCOND*/true) {
595: struct radix_tree_node *n;
596: int i;
597:
598: if (entry_match_p(*vpp, tagmask)) {
599: KASSERT(lastidx == t->t_height);
600: /*
601: * record the non-NULL leaf.
602: */
603: results[nfound] = entry_ptr(*vpp);
604: nfound++;
605: if (nfound == maxresults) {
606: return nfound;
607: }
608: }
609: scan_siblings:
610: /*
611: * try to find the next non-NULL sibling.
612: */
613: n = path_node(t, path, lastidx - 1);
614: if (*vpp != NULL && n->n_nptrs == 1) {
615: /*
616: * optimization
617: */
618: goto no_siblings;
619: }
620: for (i = path_idx(t, path, lastidx - 1) + 1;
621: i < RADIX_TREE_PTR_PER_NODE;
622: i++) {
623: if (entry_match_p(n->n_ptrs[i], tagmask)) {
624: vpp = &n->n_ptrs[i];
625: path->p_refs[lastidx].pptr = vpp;
626: KASSERT(path_idx(t, path, lastidx - 1)
627: == i);
628: break;
629: }
630: }
631: if (i == RADIX_TREE_PTR_PER_NODE) {
632: no_siblings:
633: /*
634: * not found. go to parent.
635: */
636: lastidx--;
637: if (lastidx == 0) {
638: return nfound;
639: }
640: vpp = path_pptr(t, path, lastidx);
641: goto scan_siblings;
642: }
643: /*
644: * descending the left-most child node, upto the leaf or NULL.
645: */
646: while (entry_match_p(*vpp, tagmask) && lastidx < t->t_height) {
647: n = entry_ptr(*vpp);
648: vpp = &n->n_ptrs[0];
649: lastidx++;
650: path->p_refs[lastidx].pptr = vpp;
651: }
652: }
653: }
654:
655: /*
656: * radix_tree_gang_lookup_node:
657: *
658: * search nodes starting from idx in the ascending order.
659: * results should be an array large enough to hold maxresults pointers.
660: * returns the number of nodes found, up to maxresults.
661: * returning less than maxresults means there are no more nodes.
662: *
663: * the result of this function is semantically equivalent to what could be
664: * obtained by repeated calls of radix_tree_lookup_node with increasing index.
665: * but this function is much faster when node indexes are distributed sparsely.
666: *
667: * note that this function doesn't return exact values of node indexes of
668: * found nodes. if they are important for a caller, it's the caller's
669: * responsibility to check them, typically by examinining the returned nodes
670: * using some caller-specific knowledge about them.
671: */
672:
673: unsigned int
674: radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx,
675: void **results, unsigned int maxresults)
676: {
677: struct radix_tree_path path;
678:
679: gang_lookup_init(t, idx, &path, 0);
680: return gang_lookup_scan(t, &path, results, maxresults, 0);
681: }
682:
683: /*
684: * radix_tree_gang_lookup_tagged_node:
685: *
686: * same as radix_tree_gang_lookup_node except that this one only returns
687: * nodes tagged with tagid.
688: */
689:
690: unsigned int
691: radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx,
692: void **results, unsigned int maxresults, radix_tree_tagid_t tagid)
693: {
694: struct radix_tree_path path;
695: const unsigned int tagmask = tagid_to_mask(tagid);
696:
697: gang_lookup_init(t, idx, &path, tagmask);
698: return gang_lookup_scan(t, &path, results, maxresults, tagmask);
699: }
700:
1.4 ! yamt 701: /*
! 702: * radix_tree_get_tag:
! 703: *
! 704: * return if the tag is set for the node at the given index. (true if set)
! 705: * it's illegal to call this function for a node which has not been inserted.
! 706: */
! 707:
1.1 yamt 708: bool
709: radix_tree_get_tag(struct radix_tree *t, uint64_t idx,
710: radix_tree_tagid_t tagid)
711: {
712: #if 1
713: const unsigned int tagmask = tagid_to_mask(tagid);
714: void **vpp;
715:
716: vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask);
717: if (vpp == NULL) {
718: return false;
719: }
720: KASSERT(*vpp != NULL);
721: return (entry_tagmask(*vpp) & tagmask) != 0;
722: #else
723: const unsigned int tagmask = tagid_to_mask(tagid);
724: void **vpp;
725:
726: vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
727: KASSERT(vpp != NULL);
728: return (entry_tagmask(*vpp) & tagmask) != 0;
729: #endif
730: }
731:
1.4 ! yamt 732: /*
! 733: * radix_tree_set_tag:
! 734: *
! 735: * set the tag for the node at the given index.
! 736: * it's illegal to call this function for a node which has not been inserted.
! 737: */
! 738:
1.1 yamt 739: void
740: radix_tree_set_tag(struct radix_tree *t, uint64_t idx,
741: radix_tree_tagid_t tagid)
742: {
743: struct radix_tree_path path;
744: const unsigned int tagmask = tagid_to_mask(tagid);
745: void **vpp;
746: int i;
747:
748: vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
749: KASSERT(vpp != NULL);
750: KASSERT(*vpp != NULL);
751: KASSERT(path.p_lastidx == t->t_height);
752: KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
753: for (i = t->t_height; i >= 0; i--) {
754: void ** const pptr = (void **)path_pptr(t, &path, i);
755: void *entry;
756:
757: KASSERT(pptr != NULL);
758: entry = *pptr;
759: if ((entry_tagmask(entry) & tagmask) != 0) {
760: break;
761: }
762: *pptr = (void *)((uintptr_t)entry | tagmask);
763: }
764: }
765:
1.4 ! yamt 766: /*
! 767: * radix_tree_clear_tag:
! 768: *
! 769: * clear the tag for the node at the given index.
! 770: * it's illegal to call this function for a node which has not been inserted.
! 771: */
! 772:
1.1 yamt 773: void
774: radix_tree_clear_tag(struct radix_tree *t, uint64_t idx,
775: radix_tree_tagid_t tagid)
776: {
777: struct radix_tree_path path;
778: const unsigned int tagmask = tagid_to_mask(tagid);
779: void **vpp;
780: int i;
781:
782: vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
783: KASSERT(vpp != NULL);
784: KASSERT(*vpp != NULL);
785: KASSERT(path.p_lastidx == t->t_height);
786: KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
787: if ((entry_tagmask(*vpp) & tagmask) == 0) {
788: return;
789: }
790: for (i = t->t_height; i >= 0; i--) {
791: void ** const pptr = (void **)path_pptr(t, &path, i);
792: void *entry;
793:
794: KASSERT(pptr != NULL);
795: entry = *pptr;
796: KASSERT((entry_tagmask(entry) & tagmask) != 0);
797: *pptr = entry_compose(entry_ptr(entry),
798: entry_tagmask(entry) & ~tagmask);
799: if (0 < i && i < t->t_height - 1) {
800: struct radix_tree_node *n = path_node(t, &path, i - 1);
801:
802: if ((any_children_tagmask(n) & tagmask) != 0) {
803: break;
804: }
805: }
806: }
807: }
808:
809: #if defined(UNITTEST)
810:
811: #include <inttypes.h>
812: #include <stdio.h>
813:
814: static void
815: radix_tree_dump_node(const struct radix_tree *t, void *vp,
816: uint64_t offset, unsigned int height)
817: {
818: struct radix_tree_node *n;
819: unsigned int i;
820:
821: for (i = 0; i < t->t_height - height; i++) {
822: printf(" ");
823: }
824: if (entry_tagmask(vp) == 0) {
825: printf("[%" PRIu64 "] %p", offset, entry_ptr(vp));
826: } else {
827: printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp),
828: entry_tagmask(vp));
829: }
830: if (height == 0) {
831: printf(" (leaf)\n");
832: return;
833: }
834: n = entry_ptr(vp);
835: assert(any_children_tagmask(n) == entry_tagmask(vp));
836: printf(" (%u children)\n", n->n_nptrs);
837: for (i = 0; i < __arraycount(n->n_ptrs); i++) {
838: void *c;
839:
840: c = n->n_ptrs[i];
841: if (c == NULL) {
842: continue;
843: }
844: radix_tree_dump_node(t, c,
845: offset + i * (UINT64_C(1) <<
846: (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1);
847: }
848: }
849:
850: void radix_tree_dump(const struct radix_tree *);
851:
852: void
853: radix_tree_dump(const struct radix_tree *t)
854: {
855:
856: printf("tree %p height=%u\n", t, t->t_height);
857: radix_tree_dump_node(t, t->t_root, 0, t->t_height);
858: }
859:
860: static void
861: test1(void)
862: {
863: struct radix_tree s;
864: struct radix_tree *t = &s;
865: void *results[3];
866:
867: radix_tree_init_tree(t);
868: radix_tree_dump(t);
869: assert(radix_tree_lookup_node(t, 0) == NULL);
870: assert(radix_tree_lookup_node(t, 1000) == NULL);
871: assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0);
872: radix_tree_dump(t);
873: assert(!radix_tree_get_tag(t, 1000, 0));
874: assert(!radix_tree_get_tag(t, 1000, 1));
875: radix_tree_set_tag(t, 1000, 1);
876: assert(!radix_tree_get_tag(t, 1000, 0));
877: assert(radix_tree_get_tag(t, 1000, 1));
878: radix_tree_dump(t);
879: assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
880: assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0);
881: radix_tree_dump(t);
882: assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0);
883: assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
884: assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0)
885: == 0);
886: radix_tree_dump(t);
887: assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0);
888: assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
889: assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) ==
890: (void *)0xdea0);
891: radix_tree_dump(t);
892: assert(!radix_tree_get_tag(t, 0, 1));
893: assert(radix_tree_get_tag(t, 1000, 1));
894: assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1));
895: radix_tree_set_tag(t, 0, 1);;
896: radix_tree_set_tag(t, UINT64_C(10000000000), 1);
897: radix_tree_dump(t);
898: assert(radix_tree_get_tag(t, 0, 1));
899: assert(radix_tree_get_tag(t, 1000, 1));
900: assert(radix_tree_get_tag(t, UINT64_C(10000000000), 1));
901: radix_tree_clear_tag(t, 0, 1);;
902: radix_tree_clear_tag(t, UINT64_C(10000000000), 1);
903: radix_tree_dump(t);
904: assert(!radix_tree_get_tag(t, 0, 1));
905: assert(radix_tree_get_tag(t, 1000, 1));
906: assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1));
907: radix_tree_dump(t);
908: assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) ==
909: (void *)0xdeadbea0);
910: assert(!radix_tree_get_tag(t, 1000, 0));
911: assert(radix_tree_get_tag(t, 1000, 1));
912: assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 3);
913: assert(results[0] == (void *)0xbea0);
914: assert(results[1] == (void *)0x12345678);
915: assert(results[2] == (void *)0xdea0);
916: assert(radix_tree_gang_lookup_node(t, 1, results, 3) == 2);
917: assert(results[0] == (void *)0x12345678);
918: assert(results[1] == (void *)0xdea0);
919: assert(radix_tree_gang_lookup_node(t, 1001, results, 3) == 1);
920: assert(results[0] == (void *)0xdea0);
921: assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3)
922: == 0);
923: assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results,
924: 3) == 0);
925: assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, 1) == 1);
926: assert(results[0] == (void *)0x12345678);
927: assert(entry_tagmask(t->t_root) != 0);
928: assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678);
929: assert(entry_tagmask(t->t_root) == 0);
930: radix_tree_dump(t);
931: assert(radix_tree_remove_node(t, UINT64_C(10000000000)) ==
932: (void *)0xdea0);
933: radix_tree_dump(t);
934: assert(radix_tree_remove_node(t, 0) == (void *)0xbea0);
935: radix_tree_dump(t);
936: radix_tree_fini_tree(t);
937: }
938:
939: #include <sys/time.h>
940:
941: struct testnode {
942: uint64_t idx;
943: };
944:
945: static void
946: printops(const char *name, unsigned int n, const struct timeval *stv,
947: const struct timeval *etv)
948: {
949: uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec;
950: uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec;
951:
952: printf("%lf %s/s\n", (double)n / (e - s) * 1000000, name);
953: }
954:
955: #define TEST2_GANG_LOOKUP_NODES 16
956:
957: static bool
958: test2_should_tag(unsigned int i, radix_tree_tagid_t tagid)
959: {
960:
961: if (tagid == 0) {
962: return (i & 0x3) == 0;
963: } else {
964: return (i % 7) == 0;
965: }
966: }
967:
968: static void
969: test2(bool dense)
970: {
971: struct radix_tree s;
972: struct radix_tree *t = &s;
973: struct testnode *n;
974: unsigned int i;
975: unsigned int nnodes = 100000;
976: unsigned int removed;
977: radix_tree_tagid_t tag;
978: unsigned int ntagged[RADIX_TREE_TAG_ID_MAX];
979: struct testnode *nodes;
980: struct timeval stv;
981: struct timeval etv;
982:
983: nodes = malloc(nnodes * sizeof(*nodes));
984: for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
985: ntagged[tag] = 0;
986: }
987: radix_tree_init_tree(t);
988: for (i = 0; i < nnodes; i++) {
989: n = &nodes[i];
990: n->idx = random();
991: if (sizeof(long) == 4) {
992: n->idx <<= 32;
993: n->idx |= (uint32_t)random();
994: }
995: if (dense) {
996: n->idx %= nnodes * 2;
997: }
998: while (radix_tree_lookup_node(t, n->idx) != NULL) {
999: n->idx++;
1000: }
1001: radix_tree_insert_node(t, n->idx, n);
1002: for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1003: if (test2_should_tag(i, tag)) {
1004: radix_tree_set_tag(t, n->idx, tag);
1005: ntagged[tag]++;
1006: }
1007: assert(test2_should_tag(i, tag) ==
1008: radix_tree_get_tag(t, n->idx, tag));
1009: }
1010: }
1011:
1012: gettimeofday(&stv, NULL);
1013: for (i = 0; i < nnodes; i++) {
1014: n = &nodes[i];
1015: assert(radix_tree_lookup_node(t, n->idx) == n);
1016: }
1017: gettimeofday(&etv, NULL);
1018: printops("lookup", nnodes, &stv, &etv);
1019:
1020: for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1021: gettimeofday(&stv, NULL);
1022: for (i = 0; i < nnodes; i++) {
1023: n = &nodes[i];
1024: assert(test2_should_tag(i, tag) ==
1025: radix_tree_get_tag(t, n->idx, tag));
1026: }
1027: gettimeofday(&etv, NULL);
1028: printops("get_tag", ntagged[tag], &stv, &etv);
1029: }
1030:
1031: gettimeofday(&stv, NULL);
1032: for (i = 0; i < nnodes; i++) {
1033: n = &nodes[i];
1034: radix_tree_remove_node(t, n->idx);
1035: }
1036: gettimeofday(&etv, NULL);
1037: printops("remove", nnodes, &stv, &etv);
1038:
1039: gettimeofday(&stv, NULL);
1040: for (i = 0; i < nnodes; i++) {
1041: n = &nodes[i];
1042: radix_tree_insert_node(t, n->idx, n);
1043: }
1044: gettimeofday(&etv, NULL);
1045: printops("insert", nnodes, &stv, &etv);
1046:
1047: for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1048: ntagged[tag] = 0;
1049: gettimeofday(&stv, NULL);
1050: for (i = 0; i < nnodes; i++) {
1051: n = &nodes[i];
1052: if (test2_should_tag(i, tag)) {
1053: radix_tree_set_tag(t, n->idx, tag);
1054: ntagged[tag]++;
1055: }
1056: }
1057: gettimeofday(&etv, NULL);
1058: printops("set_tag", ntagged[tag], &stv, &etv);
1059: }
1060:
1061: gettimeofday(&stv, NULL);
1062: {
1063: struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1064: uint64_t nextidx;
1065: unsigned int nfound;
1066: unsigned int total;
1067:
1068: nextidx = 0;
1069: total = 0;
1070: while ((nfound = radix_tree_gang_lookup_node(t, nextidx,
1071: (void *)results, __arraycount(results))) > 0) {
1072: nextidx = results[nfound - 1]->idx + 1;
1073: total += nfound;
1074: }
1075: assert(total == nnodes);
1076: }
1077: gettimeofday(&etv, NULL);
1078: printops("ganglookup", nnodes, &stv, &etv);
1079:
1080: for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1081: gettimeofday(&stv, NULL);
1082: {
1083: struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1084: uint64_t nextidx;
1085: unsigned int nfound;
1086: unsigned int total;
1087:
1088: nextidx = 0;
1089: total = 0;
1090: while ((nfound = radix_tree_gang_lookup_tagged_node(t,
1091: nextidx, (void *)results, __arraycount(results),
1092: tag)) > 0) {
1093: nextidx = results[nfound - 1]->idx + 1;
1094: total += nfound;
1095: }
1096: assert(total == ntagged[tag]);
1097: }
1098: gettimeofday(&etv, NULL);
1099: printops("ganglookup_tag", ntagged[tag], &stv, &etv);
1100: }
1101:
1102: removed = 0;
1103: for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1104: unsigned int total;
1105:
1106: total = 0;
1107: gettimeofday(&stv, NULL);
1108: {
1109: struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1110: uint64_t nextidx;
1111: unsigned int nfound;
1112:
1113: nextidx = 0;
1114: while ((nfound = radix_tree_gang_lookup_tagged_node(t,
1115: nextidx, (void *)results, __arraycount(results),
1116: tag)) > 0) {
1117: for (i = 0; i < nfound; i++) {
1118: radix_tree_remove_node(t,
1119: results[i]->idx);
1120: }
1121: nextidx = results[nfound - 1]->idx + 1;
1122: total += nfound;
1123: }
1124: assert(tag != 0 || total == ntagged[tag]);
1125: assert(total <= ntagged[tag]);
1126: }
1127: gettimeofday(&etv, NULL);
1128: printops("ganglookup_tag+remove", total, &stv, &etv);
1129: removed += total;
1130: }
1131:
1132: gettimeofday(&stv, NULL);
1133: {
1134: struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1135: uint64_t nextidx;
1136: unsigned int nfound;
1137: unsigned int total;
1138:
1139: nextidx = 0;
1140: total = 0;
1141: while ((nfound = radix_tree_gang_lookup_node(t, nextidx,
1142: (void *)results, __arraycount(results))) > 0) {
1143: for (i = 0; i < nfound; i++) {
1144: assert(results[i] == radix_tree_remove_node(t,
1145: results[i]->idx));
1146: }
1147: nextidx = results[nfound - 1]->idx + 1;
1148: total += nfound;
1149: }
1150: assert(total == nnodes - removed);
1151: }
1152: gettimeofday(&etv, NULL);
1153: printops("ganglookup+remove", nnodes - removed, &stv, &etv);
1154:
1155: radix_tree_fini_tree(t);
1156: free(nodes);
1157: }
1158:
1159: int
1160: main(int argc, char *argv[])
1161: {
1162:
1163: test1();
1164: printf("dense distribution:\n");
1165: test2(true);
1166: printf("sparse distribution:\n");
1167: test2(false);
1168: return 0;
1169: }
1170:
1171: #endif /* defined(UNITTEST) */
CVSweb <webmaster@jp.NetBSD.org>