Back to index

openldap  2.4.31
avl.h
Go to the documentation of this file.
00001 /* avl.h - avl tree definitions */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 1998-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 /* Portions Copyright (c) 1993 Regents of the University of Michigan.
00017  * All rights reserved.
00018  *
00019  * Redistribution and use in source and binary forms are permitted
00020  * provided that this notice is preserved and that due credit is given
00021  * to the University of Michigan at Ann Arbor. The name of the University
00022  * may not be used to endorse or promote products derived from this
00023  * software without specific prior written permission. This software
00024  * is provided ``as is'' without express or implied warranty.
00025  */
00026 
00027 
00028 #ifndef _AVL
00029 #define _AVL
00030 
00031 #include <ldap_cdefs.h>
00032 
00033 /*
00034  * this structure represents a generic avl tree node.
00035  */
00036 
00037 LDAP_BEGIN_DECL
00038 
00039 typedef struct avlnode Avlnode;
00040 
00041 struct avlnode {
00042        void*         avl_data;
00043        struct avlnode       *avl_link[2];
00044        char          avl_bits[2];
00045        signed char          avl_bf;
00046 };
00047 
00048 #define avl_left     avl_link[0]
00049 #define avl_right    avl_link[1]
00050 #define avl_lbit     avl_bits[0]
00051 #define avl_rbit     avl_bits[1]
00052 
00053 #ifdef AVL_INTERNAL
00054 
00055 #define NULLAVL      ((Avlnode *) NULL)
00056 
00057 /* balance factor values */
00058 #define LH    (-1)
00059 #define EH    0
00060 #define RH    1
00061 
00062 #define avl_bf2str(bf)      ((bf) == -1 ? "LH" : (bf) == 0 ? "EH" : (bf) == 1 ? "RH" : "(unknown)" )
00063 
00064 /* thread bits */
00065 #define       AVL_THREAD    0
00066 #define       AVL_CHILD     1
00067 
00068 /* avl routines */
00069 #define avl_getone(x)       ((x) == 0 ? 0 : (x)->avl_data)
00070 #define avl_onenode(x)      ((x) == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0))
00071 
00072 #endif /* AVL_INTERNALS */
00073 
00074 #define       avl_child(x,dir)     ((x)->avl_bits[dir]) == AVL_CHILD ? \
00075        (x)->avl_link[dir] : NULL
00076 #define       avl_lchild(x) avl_child(x,0)
00077 #define       avl_rchild(x) avl_child(x,1)
00078 
00079 typedef int          (*AVL_APPLY) LDAP_P((void *, void*));
00080 typedef int          (*AVL_CMP) LDAP_P((const void*, const void*));
00081 typedef int          (*AVL_DUP) LDAP_P((void*, void*));
00082 typedef void  (*AVL_FREE) LDAP_P((void*));
00083 
00084 LDAP_AVL_F( int )
00085 avl_free LDAP_P(( Avlnode *root, AVL_FREE dfree ));
00086 
00087 LDAP_AVL_F( int )
00088 avl_insert LDAP_P((Avlnode **, void*, AVL_CMP, AVL_DUP));
00089 
00090 LDAP_AVL_F( void* )
00091 avl_delete LDAP_P((Avlnode **, void*, AVL_CMP));
00092 
00093 LDAP_AVL_F( void* )
00094 avl_find LDAP_P((Avlnode *, const void*, AVL_CMP));
00095 
00096 LDAP_AVL_F( Avlnode* )
00097 avl_find2 LDAP_P((Avlnode *, const void*, AVL_CMP));
00098 
00099 LDAP_AVL_F( void* )
00100 avl_find_lin LDAP_P((Avlnode *, const void*, AVL_CMP));
00101 
00102 #ifdef AVL_NONREENTRANT
00103 LDAP_AVL_F( void* )
00104 avl_getfirst LDAP_P((Avlnode *));
00105 
00106 LDAP_AVL_F( void* )
00107 avl_getnext LDAP_P((void));
00108 #endif
00109 
00110 LDAP_AVL_F( int )
00111 avl_dup_error LDAP_P((void*, void*));
00112 
00113 LDAP_AVL_F( int )
00114 avl_dup_ok LDAP_P((void*, void*));
00115 
00116 LDAP_AVL_F( int )
00117 avl_apply LDAP_P((Avlnode *, AVL_APPLY, void*, int, int));
00118 
00119 LDAP_AVL_F( int )
00120 avl_prefixapply LDAP_P((Avlnode *, void*, AVL_CMP, void*, AVL_CMP, void*, int));
00121 
00122 LDAP_AVL_F( int )
00123 tavl_free LDAP_P(( Avlnode *root, AVL_FREE dfree ));
00124 
00125 LDAP_AVL_F( int )
00126 tavl_insert LDAP_P((Avlnode **, void*, AVL_CMP, AVL_DUP));
00127 
00128 LDAP_AVL_F( void* )
00129 tavl_delete LDAP_P((Avlnode **, void*, AVL_CMP));
00130 
00131 LDAP_AVL_F( void* )
00132 tavl_find LDAP_P((Avlnode *, const void*, AVL_CMP));
00133 
00134 LDAP_AVL_F( Avlnode* )
00135 tavl_find2 LDAP_P((Avlnode *, const void*, AVL_CMP));
00136 
00137 LDAP_AVL_F( Avlnode* )
00138 tavl_find3 LDAP_P((Avlnode *, const void*, AVL_CMP, int *ret));
00139 
00140 #define       TAVL_DIR_LEFT 0
00141 #define       TAVL_DIR_RIGHT       1
00142 
00143 LDAP_AVL_F( Avlnode* )
00144 tavl_end LDAP_P((Avlnode *, int direction ));
00145 
00146 LDAP_AVL_F( Avlnode* )
00147 tavl_next LDAP_P((Avlnode *, int direction ));
00148 
00149 /* apply traversal types */
00150 #define AVL_PREORDER 1
00151 #define AVL_INORDER  2
00152 #define AVL_POSTORDER       3
00153 /* what apply returns if it ran out of nodes */
00154 #define AVL_NOMORE   (-6)
00155 
00156 LDAP_END_DECL
00157 
00158 #endif /* _AVL */