[BACK]Return to radixtree.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / common / lib / libc / gen

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>