Return to rdxtree.c CVS log

Up to [GnuMach] / Gnu-Mach / kern

Annotation of Gnu-Mach/kern/rdxtree.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.