uu_avl.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*
    2  * CDDL HEADER START
    3  *
    4  * The contents of this file are subject to the terms of the
    5  * Common Development and Distribution License (the "License").
    6  * You may not use this file except in compliance with the License.
    7  *
    8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
    9  * or https://opensource.org/licenses/CDDL-1.0.
   10  * See the License for the specific language governing permissions
   11  * and limitations under the License.
   12  *
   13  * When distributing Covered Code, include this CDDL HEADER in each
   14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
   15  * If applicable, add the following below this CDDL HEADER, with the
   16  * fields enclosed by brackets "[]" replaced with your own identifying
   17  * information: Portions Copyright [yyyy] [name of copyright owner]
   18  *
   19  * CDDL HEADER END
   20  */
   21 /*
   22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
   23  * Use is subject to license terms.
   24  */
   25 
   26 
   27 
   28 #include "libuutil_common.h"
   29 
   30 #include <stdlib.h>
   31 #include <string.h>
   32 #include <unistd.h>
   33 #include <sys/avl.h>
   34 
   35 static uu_avl_pool_t    uu_null_apool = { &uu_null_apool, &uu_null_apool };
   36 static pthread_mutex_t  uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER;
   37 
   38 /*
   39  * The index mark change on every insert and delete, to catch stale
   40  * references.
   41  *
   42  * We leave the low bit alone, since the avl code uses it.
   43  */
   44 #define INDEX_MAX               (sizeof (uintptr_t) - 2)
   45 #define INDEX_NEXT(m)           (((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX)
   46 
   47 #define INDEX_DECODE(i)         ((i) & ~INDEX_MAX)
   48 #define INDEX_ENCODE(p, n)      (((n) & ~INDEX_MAX) | (p)->ua_index)
   49 #define INDEX_VALID(p, i)       (((i) & INDEX_MAX) == (p)->ua_index)
   50 #define INDEX_CHECK(i)          (((i) & INDEX_MAX) != 0)
   51 
   52 /*
   53  * When an element is inactive (not in a tree), we keep a marked pointer to
   54  * its containing pool in its first word, and a NULL pointer in its second.
   55  *
   56  * On insert, we use these to verify that it comes from the correct pool.
   57  */
   58 #define NODE_ARRAY(p, n)        ((uintptr_t *)((uintptr_t)(n) + \
   59                                     (pp)->uap_nodeoffset))
   60 
   61 #define POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1))
   62 
   63 #define DEAD_MARKER             0xc4
   64 
   65 uu_avl_pool_t *
   66 uu_avl_pool_create(const char *name, size_t objsize, size_t nodeoffset,
   67     uu_compare_fn_t *compare_func, uint32_t flags)
   68 {
   69         uu_avl_pool_t *pp, *next, *prev;
   70 
   71         if (name == NULL ||
   72             uu_check_name(name, UU_NAME_DOMAIN) == -1 ||
   73             nodeoffset + sizeof (uu_avl_node_t) > objsize ||
   74             compare_func == NULL) {
   75                 uu_set_error(UU_ERROR_INVALID_ARGUMENT);
   76                 return (NULL);
   77         }
   78 
   79         if (flags & ~UU_AVL_POOL_DEBUG) {
   80                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
   81                 return (NULL);
   82         }
   83 
   84         pp = uu_zalloc(sizeof (uu_avl_pool_t));
   85         if (pp == NULL) {
   86                 uu_set_error(UU_ERROR_NO_MEMORY);
   87                 return (NULL);
   88         }
   89 
   90         (void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name));
   91         pp->uap_nodeoffset = nodeoffset;
   92         pp->uap_objsize = objsize;
   93         pp->uap_cmp = compare_func;
   94         if (flags & UU_AVL_POOL_DEBUG)
   95                 pp->uap_debug = 1;
   96         pp->uap_last_index = 0;
   97 
   98         (void) pthread_mutex_init(&pp->uap_lock, NULL);
   99 
  100         pp->uap_null_avl.ua_next = &pp->uap_null_avl;
  101         pp->uap_null_avl.ua_prev = &pp->uap_null_avl;
  102 
  103         (void) pthread_mutex_lock(&uu_apool_list_lock);
  104         pp->uap_next = next = &uu_null_apool;
  105         pp->uap_prev = prev = next->uap_prev;
  106         next->uap_prev = pp;
  107         prev->uap_next = pp;
  108         (void) pthread_mutex_unlock(&uu_apool_list_lock);
  109 
  110         return (pp);
  111 }
  112 
  113 void
  114 uu_avl_pool_destroy(uu_avl_pool_t *pp)
  115 {
  116         if (pp->uap_debug) {
  117                 if (pp->uap_null_avl.ua_next != &pp->uap_null_avl ||
  118                     pp->uap_null_avl.ua_prev != &pp->uap_null_avl) {
  119                         uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has "
  120                             "outstanding avls, or is corrupt.\n",
  121                             (int)sizeof (pp->uap_name), pp->uap_name,
  122                             (void *)pp);
  123                 }
  124         }
  125         (void) pthread_mutex_lock(&uu_apool_list_lock);
  126         pp->uap_next->uap_prev = pp->uap_prev;
  127         pp->uap_prev->uap_next = pp->uap_next;
  128         (void) pthread_mutex_unlock(&uu_apool_list_lock);
  129         (void) pthread_mutex_destroy(&pp->uap_lock);
  130         pp->uap_prev = NULL;
  131         pp->uap_next = NULL;
  132         uu_free(pp);
  133 }
  134 
  135 void
  136 uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
  137 {
  138         uintptr_t *na = (uintptr_t *)np;
  139 
  140         if (pp->uap_debug) {
  141                 uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
  142                 if (offset + sizeof (*np) > pp->uap_objsize) {
  143                         uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
  144                             "offset %ld doesn't fit in object (size %ld)\n",
  145                             base, (void *)np, (void *)pp, pp->uap_name,
  146                             (long)offset, (long)pp->uap_objsize);
  147                 }
  148                 if (offset != pp->uap_nodeoffset) {
  149                         uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
  150                             "offset %ld doesn't match pool's offset (%ld)\n",
  151                             base, (void *)np, (void *)pp, pp->uap_name,
  152                             (long)offset, (long)pp->uap_objsize);
  153                 }
  154         }
  155 
  156         na[0] = POOL_TO_MARKER(pp);
  157         na[1] = 0;
  158 }
  159 
  160 void
  161 uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
  162 {
  163         uintptr_t *na = (uintptr_t *)np;
  164 
  165         if (pp->uap_debug) {
  166                 if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) {
  167                         uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
  168                             "node already finied\n",
  169                             base, (void *)np, (void *)pp, pp->uap_name);
  170                 }
  171                 if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) {
  172                         uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
  173                             "node corrupt, in tree, or in different pool\n",
  174                             base, (void *)np, (void *)pp, pp->uap_name);
  175                 }
  176         }
  177 
  178         na[0] = DEAD_MARKER;
  179         na[1] = DEAD_MARKER;
  180         na[2] = DEAD_MARKER;
  181 }
  182 
  183 struct uu_avl_node_compare_info {
  184         uu_compare_fn_t *ac_compare;
  185         void            *ac_private;
  186         void            *ac_right;
  187         void            *ac_found;
  188 };
  189 
  190 static int
  191 uu_avl_node_compare(const void *l, const void *r)
  192 {
  193         struct uu_avl_node_compare_info *info =
  194             (struct uu_avl_node_compare_info *)l;
  195 
  196         int res = info->ac_compare(r, info->ac_right, info->ac_private);
  197 
  198         if (res == 0) {
  199                 if (info->ac_found == NULL)
  200                         info->ac_found = (void *)r;
  201                 return (-1);
  202         }
  203         if (res < 0)
  204                 return (1);
  205         return (-1);
  206 }
  207 
  208 uu_avl_t *
  209 uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags)
  210 {
  211         uu_avl_t *ap, *next, *prev;
  212 
  213         if (flags & ~UU_AVL_DEBUG) {
  214                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
  215                 return (NULL);
  216         }
  217 
  218         ap = uu_zalloc(sizeof (*ap));
  219         if (ap == NULL) {
  220                 uu_set_error(UU_ERROR_NO_MEMORY);
  221                 return (NULL);
  222         }
  223 
  224         ap->ua_pool = pp;
  225         ap->ua_parent = parent;
  226         ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG);
  227         ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index));
  228 
  229         avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize,
  230             pp->uap_nodeoffset);
  231 
  232         ap->ua_null_walk.uaw_next = &ap->ua_null_walk;
  233         ap->ua_null_walk.uaw_prev = &ap->ua_null_walk;
  234 
  235         (void) pthread_mutex_lock(&pp->uap_lock);
  236         next = &pp->uap_null_avl;
  237         prev = next->ua_prev;
  238         ap->ua_next = next;
  239         ap->ua_prev = prev;
  240         next->ua_prev = ap;
  241         prev->ua_next = ap;
  242         (void) pthread_mutex_unlock(&pp->uap_lock);
  243 
  244         return (ap);
  245 }
  246 
  247 void
  248 uu_avl_destroy(uu_avl_t *ap)
  249 {
  250         uu_avl_pool_t *pp = ap->ua_pool;
  251 
  252         if (ap->ua_debug) {
  253                 if (avl_numnodes(&ap->ua_tree) != 0) {
  254                         uu_panic("uu_avl_destroy(%p): tree not empty\n",
  255                             (void *)ap);
  256                 }
  257                 if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
  258                     ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
  259                         uu_panic("uu_avl_destroy(%p):  outstanding walkers\n",
  260                             (void *)ap);
  261                 }
  262         }
  263         (void) pthread_mutex_lock(&pp->uap_lock);
  264         ap->ua_next->ua_prev = ap->ua_prev;
  265         ap->ua_prev->ua_next = ap->ua_next;
  266         (void) pthread_mutex_unlock(&pp->uap_lock);
  267         ap->ua_prev = NULL;
  268         ap->ua_next = NULL;
  269 
  270         ap->ua_pool = NULL;
  271         avl_destroy(&ap->ua_tree);
  272 
  273         uu_free(ap);
  274 }
  275 
  276 size_t
  277 uu_avl_numnodes(uu_avl_t *ap)
  278 {
  279         return (avl_numnodes(&ap->ua_tree));
  280 }
  281 
  282 void *
  283 uu_avl_first(uu_avl_t *ap)
  284 {
  285         return (avl_first(&ap->ua_tree));
  286 }
  287 
  288 void *
  289 uu_avl_last(uu_avl_t *ap)
  290 {
  291         return (avl_last(&ap->ua_tree));
  292 }
  293 
  294 void *
  295 uu_avl_next(uu_avl_t *ap, void *node)
  296 {
  297         return (AVL_NEXT(&ap->ua_tree, node));
  298 }
  299 
  300 void *
  301 uu_avl_prev(uu_avl_t *ap, void *node)
  302 {
  303         return (AVL_PREV(&ap->ua_tree, node));
  304 }
  305 
  306 static void
  307 _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags)
  308 {
  309         uu_avl_walk_t *next, *prev;
  310 
  311         int robust = (flags & UU_WALK_ROBUST);
  312         int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
  313 
  314         (void) memset(wp, 0, sizeof (*wp));
  315         wp->uaw_avl = ap;
  316         wp->uaw_robust = robust;
  317         wp->uaw_dir = direction;
  318 
  319         if (direction > 0)
  320                 wp->uaw_next_result = avl_first(&ap->ua_tree);
  321         else
  322                 wp->uaw_next_result = avl_last(&ap->ua_tree);
  323 
  324         if (ap->ua_debug || robust) {
  325                 wp->uaw_next = next = &ap->ua_null_walk;
  326                 wp->uaw_prev = prev = next->uaw_prev;
  327                 next->uaw_prev = wp;
  328                 prev->uaw_next = wp;
  329         }
  330 }
  331 
  332 static void *
  333 _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap)
  334 {
  335         void *np = wp->uaw_next_result;
  336 
  337         avl_tree_t *t = &ap->ua_tree;
  338 
  339         if (np == NULL)
  340                 return (NULL);
  341 
  342         wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) :
  343             AVL_PREV(t, np);
  344 
  345         return (np);
  346 }
  347 
  348 static void
  349 _avl_walk_fini(uu_avl_walk_t *wp)
  350 {
  351         if (wp->uaw_next != NULL) {
  352                 wp->uaw_next->uaw_prev = wp->uaw_prev;
  353                 wp->uaw_prev->uaw_next = wp->uaw_next;
  354                 wp->uaw_next = NULL;
  355                 wp->uaw_prev = NULL;
  356         }
  357         wp->uaw_avl = NULL;
  358         wp->uaw_next_result = NULL;
  359 }
  360 
  361 uu_avl_walk_t *
  362 uu_avl_walk_start(uu_avl_t *ap, uint32_t flags)
  363 {
  364         uu_avl_walk_t *wp;
  365 
  366         if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
  367                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
  368                 return (NULL);
  369         }
  370 
  371         wp = uu_zalloc(sizeof (*wp));
  372         if (wp == NULL) {
  373                 uu_set_error(UU_ERROR_NO_MEMORY);
  374                 return (NULL);
  375         }
  376 
  377         _avl_walk_init(wp, ap, flags);
  378         return (wp);
  379 }
  380 
  381 void *
  382 uu_avl_walk_next(uu_avl_walk_t *wp)
  383 {
  384         return (_avl_walk_advance(wp, wp->uaw_avl));
  385 }
  386 
  387 void
  388 uu_avl_walk_end(uu_avl_walk_t *wp)
  389 {
  390         _avl_walk_fini(wp);
  391         uu_free(wp);
  392 }
  393 
  394 int
  395 uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags)
  396 {
  397         void *e;
  398         uu_avl_walk_t my_walk;
  399 
  400         int status = UU_WALK_NEXT;
  401 
  402         if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
  403                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
  404                 return (-1);
  405         }
  406 
  407         _avl_walk_init(&my_walk, ap, flags);
  408         while (status == UU_WALK_NEXT &&
  409             (e = _avl_walk_advance(&my_walk, ap)) != NULL)
  410                 status = (*func)(e, private);
  411         _avl_walk_fini(&my_walk);
  412 
  413         if (status >= 0)
  414                 return (0);
  415         uu_set_error(UU_ERROR_CALLBACK_FAILED);
  416         return (-1);
  417 }
  418 
  419 void
  420 uu_avl_remove(uu_avl_t *ap, void *elem)
  421 {
  422         uu_avl_walk_t *wp;
  423         uu_avl_pool_t *pp = ap->ua_pool;
  424         uintptr_t *na = NODE_ARRAY(pp, elem);
  425 
  426         if (ap->ua_debug) {
  427                 /*
  428                  * invalidate outstanding uu_avl_index_ts.
  429                  */
  430                 ap->ua_index = INDEX_NEXT(ap->ua_index);
  431         }
  432 
  433         /*
  434          * Robust walkers most be advanced, if we are removing the node
  435          * they are currently using.  In debug mode, non-robust walkers
  436          * are also on the walker list.
  437          */
  438         for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk;
  439             wp = wp->uaw_next) {
  440                 if (wp->uaw_robust) {
  441                         if (elem == wp->uaw_next_result)
  442                                 (void) _avl_walk_advance(wp, ap);
  443                 } else if (wp->uaw_next_result != NULL) {
  444                         uu_panic("uu_avl_remove(%p, %p): active non-robust "
  445                             "walker\n", (void *)ap, elem);
  446                 }
  447         }
  448 
  449         avl_remove(&ap->ua_tree, elem);
  450 
  451         na[0] = POOL_TO_MARKER(pp);
  452         na[1] = 0;
  453 }
  454 
  455 void *
  456 uu_avl_teardown(uu_avl_t *ap, void **cookie)
  457 {
  458         void *elem = avl_destroy_nodes(&ap->ua_tree, cookie);
  459 
  460         if (elem != NULL) {
  461                 uu_avl_pool_t *pp = ap->ua_pool;
  462                 uintptr_t *na = NODE_ARRAY(pp, elem);
  463 
  464                 na[0] = POOL_TO_MARKER(pp);
  465                 na[1] = 0;
  466         }
  467         return (elem);
  468 }
  469 
  470 void *
  471 uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out)
  472 {
  473         struct uu_avl_node_compare_info info;
  474         void *result;
  475 
  476         info.ac_compare = ap->ua_pool->uap_cmp;
  477         info.ac_private = private;
  478         info.ac_right = elem;
  479         info.ac_found = NULL;
  480 
  481         result = avl_find(&ap->ua_tree, &info, out);
  482         if (out != NULL)
  483                 *out = INDEX_ENCODE(ap, *out);
  484 
  485         if (ap->ua_debug && result != NULL)
  486                 uu_panic("uu_avl_find: internal error: avl_find succeeded\n");
  487 
  488         return (info.ac_found);
  489 }
  490 
  491 void
  492 uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx)
  493 {
  494         if (ap->ua_debug) {
  495                 uu_avl_pool_t *pp = ap->ua_pool;
  496                 uintptr_t *na = NODE_ARRAY(pp, elem);
  497 
  498                 if (na[1] != 0)
  499                         uu_panic("uu_avl_insert(%p, %p, %p): node already "
  500                             "in tree, or corrupt\n",
  501                             (void *)ap, elem, (void *)idx);
  502                 if (na[0] == 0)
  503                         uu_panic("uu_avl_insert(%p, %p, %p): node not "
  504                             "initialized\n",
  505                             (void *)ap, elem, (void *)idx);
  506                 if (na[0] != POOL_TO_MARKER(pp))
  507                         uu_panic("uu_avl_insert(%p, %p, %p): node from "
  508                             "other pool, or corrupt\n",
  509                             (void *)ap, elem, (void *)idx);
  510 
  511                 if (!INDEX_VALID(ap, idx))
  512                         uu_panic("uu_avl_insert(%p, %p, %p): %s\n",
  513                             (void *)ap, elem, (void *)idx,
  514                             INDEX_CHECK(idx)? "outdated index" :
  515                             "invalid index");
  516 
  517                 /*
  518                  * invalidate outstanding uu_avl_index_ts.
  519                  */
  520                 ap->ua_index = INDEX_NEXT(ap->ua_index);
  521         }
  522         avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx));
  523 }
  524 
  525 void *
  526 uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx)
  527 {
  528         if (ap->ua_debug && !INDEX_VALID(ap, idx))
  529                 uu_panic("uu_avl_nearest_next(%p, %p): %s\n",
  530                     (void *)ap, (void *)idx, INDEX_CHECK(idx)?
  531                     "outdated index" : "invalid index");
  532         return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER));
  533 }
  534 
  535 void *
  536 uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx)
  537 {
  538         if (ap->ua_debug && !INDEX_VALID(ap, idx))
  539                 uu_panic("uu_avl_nearest_prev(%p, %p): %s\n",
  540                     (void *)ap, (void *)idx, INDEX_CHECK(idx)?
  541                     "outdated index" : "invalid index");
  542         return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE));
  543 }
  544 
  545 /*
  546  * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
  547  */
  548 void
  549 uu_avl_lockup(void)
  550 {
  551         uu_avl_pool_t *pp;
  552 
  553         (void) pthread_mutex_lock(&uu_apool_list_lock);
  554         for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
  555             pp = pp->uap_next)
  556                 (void) pthread_mutex_lock(&pp->uap_lock);
  557 }
  558 
  559 void
  560 uu_avl_release(void)
  561 {
  562         uu_avl_pool_t *pp;
  563 
  564         for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
  565             pp = pp->uap_next)
  566                 (void) pthread_mutex_unlock(&pp->uap_lock);
  567         (void) pthread_mutex_unlock(&uu_apool_list_lock);
  568 }
Cache object: 0d8a550609267138304b7dba0ecd0a75
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/contrib/openzfs/lib/libuutil/uu_avl.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/openzfs/lib/libuutil/uu_avl.c
