Print this page
6222 libuutil could provide a way to re-create an AVL tree


   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 http://www.opensolaris.org/os/licensing.
  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 #pragma ident   "%Z%%M% %I%     %E% SMI"
  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)


 255                         uu_panic("uu_avl_destroy(%p): tree not empty\n",
 256                             (void *)ap);
 257                 }
 258                 if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
 259                     ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
 260                         uu_panic("uu_avl_destroy(%p):  outstanding walkers\n",
 261                             (void *)ap);
 262                 }
 263         }
 264         (void) pthread_mutex_lock(&pp->uap_lock);
 265         UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc;
 266         UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc;
 267         (void) pthread_mutex_unlock(&pp->uap_lock);
 268         ap->ua_prev_enc = UU_PTR_ENCODE(NULL);
 269         ap->ua_next_enc = UU_PTR_ENCODE(NULL);
 270 
 271         ap->ua_pool = NULL;
 272         avl_destroy(&ap->ua_tree);
 273 
 274         uu_free(ap);










 275 }
 276 
 277 size_t
 278 uu_avl_numnodes(uu_avl_t *ap)
 279 {
 280         return (avl_numnodes(&ap->ua_tree));
 281 }
 282 
 283 void *
 284 uu_avl_first(uu_avl_t *ap)
 285 {
 286         return (avl_first(&ap->ua_tree));
 287 }
 288 
 289 void *
 290 uu_avl_last(uu_avl_t *ap)
 291 {
 292         return (avl_last(&ap->ua_tree));
 293 }
 294 




   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 http://www.opensolaris.org/os/licensing.
  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  * Copyright 2015 Nexenta Systems, Inc.  All rights reserved.
  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)


 255                         uu_panic("uu_avl_destroy(%p): tree not empty\n",
 256                             (void *)ap);
 257                 }
 258                 if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
 259                     ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
 260                         uu_panic("uu_avl_destroy(%p):  outstanding walkers\n",
 261                             (void *)ap);
 262                 }
 263         }
 264         (void) pthread_mutex_lock(&pp->uap_lock);
 265         UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc;
 266         UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc;
 267         (void) pthread_mutex_unlock(&pp->uap_lock);
 268         ap->ua_prev_enc = UU_PTR_ENCODE(NULL);
 269         ap->ua_next_enc = UU_PTR_ENCODE(NULL);
 270 
 271         ap->ua_pool = NULL;
 272         avl_destroy(&ap->ua_tree);
 273 
 274         uu_free(ap);
 275 }
 276 
 277 void
 278 uu_avl_recreate(uu_avl_t *ap)
 279 {
 280         uu_avl_pool_t *pp = ap->ua_pool;
 281 
 282         avl_destroy(&ap->ua_tree);
 283         avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize,
 284             pp->uap_nodeoffset);
 285 }
 286 
 287 size_t
 288 uu_avl_numnodes(uu_avl_t *ap)
 289 {
 290         return (avl_numnodes(&ap->ua_tree));
 291 }
 292 
 293 void *
 294 uu_avl_first(uu_avl_t *ap)
 295 {
 296         return (avl_first(&ap->ua_tree));
 297 }
 298 
 299 void *
 300 uu_avl_last(uu_avl_t *ap)
 301 {
 302         return (avl_last(&ap->ua_tree));
 303 }
 304