Home | History | Annotate | Line # | Download | only in include 
      1 /*	$NetBSD: ldap_avl.h,v 1.3 2025/09/05 21:16:19 christos Exp $	*/
      2 
      3 /* ldap_avl.h - avl tree definitions */
      4 /* $OpenLDAP$ */
      5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
      6  *
      7  * Copyright 1998-2024 The OpenLDAP Foundation.
      8  * All rights reserved.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted only as authorized by the OpenLDAP
     12  * Public License.
     13  *
     14  * A copy of this license is available in file LICENSE in the
     15  * top-level directory of the distribution or, alternatively, at
     16  * <http://www.OpenLDAP.org/license.html>.
     17  */
     18 /* Portions Copyright (c) 1993 Regents of the University of Michigan.
     19  * All rights reserved.
     20  *
     21  * Redistribution and use in source and binary forms are permitted
     22  * provided that this notice is preserved and that due credit is given
     23  * to the University of Michigan at Ann Arbor. The name of the University
     24  * may not be used to endorse or promote products derived from this
     25  * software without specific prior written permission. This software
     26  * is provided ``as is'' without express or implied warranty.
     27  */
     28 
     29 
     30 #ifndef _AVL
     31 #define _AVL
     32 
     33 #include <ldap_cdefs.h>
     34 
     35 /*
     36  * this structure represents a generic avl tree node.
     37  */
     38 
     39 LDAP_BEGIN_DECL
     40 
     41 typedef struct avlnode Avlnode;
     42 
     43 struct avlnode {
     44 	void*		avl_data;
     45 	struct avlnode	*avl_link[2];
     46 	char		avl_bits[2];
     47 	signed char		avl_bf;
     48 };
     49 
     50 #define avl_left	avl_link[0]
     51 #define avl_right	avl_link[1]
     52 #define avl_lbit	avl_bits[0]
     53 #define avl_rbit	avl_bits[1]
     54 
     55 typedef struct tavlnode TAvlnode;
     56 
     57 struct tavlnode {
     58 	void*		avl_data;
     59 	struct tavlnode	*avl_link[2];
     60 	char		avl_bits[2];
     61 	signed char		avl_bf;
     62 };
     63 
     64 #ifdef AVL_INTERNAL
     65 
     66 /* balance factor values */
     67 #define LH 	(-1)
     68 #define EH 	0
     69 #define RH 	1
     70 
     71 #define avl_bf2str(bf)	((bf) == -1 ? "LH" : (bf) == 0 ? "EH" : (bf) == 1 ? "RH" : "(unknown)" )
     72 
     73 /* thread bits */
     74 #define	AVL_CHILD	0
     75 #define	AVL_THREAD	1
     76 
     77 /* avl routines */
     78 #define ldap_avl_getone(x)	((x) == 0 ? 0 : (x)->avl_data)
     79 #define ldap_avl_onenode(x)	((x) == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0))
     80 
     81 #endif /* AVL_INTERNALS */
     82 
     83 #define	ldap_avl_child(x,dir)	((x)->avl_bits[dir]) == AVL_CHILD ? \
     84 	(x)->avl_link[dir] : NULL
     85 #define	ldap_avl_lchild(x)	ldap_avl_child(x,0)
     86 #define	ldap_avl_rchild(x)	ldap_avl_child(x,1)
     87 
     88 typedef int		(*AVL_APPLY) LDAP_P((void *, void*));
     89 typedef int		(*AVL_CMP) LDAP_P((const void*, const void*));
     90 typedef int		(*AVL_DUP) LDAP_P((void*, void*));
     91 typedef void	(*AVL_FREE) LDAP_P((void*));
     92 
     93 LDAP_AVL_F( int )
     94 ldap_avl_free LDAP_P(( Avlnode *root, AVL_FREE dfree ));
     95 
     96 LDAP_AVL_F( int )
     97 ldap_avl_insert LDAP_P((Avlnode **, void*, AVL_CMP, AVL_DUP));
     98 
     99 LDAP_AVL_F( void* )
    100 ldap_avl_delete LDAP_P((Avlnode **, void*, AVL_CMP));
    101 
    102 LDAP_AVL_F( void* )
    103 ldap_avl_find LDAP_P((Avlnode *, const void*, AVL_CMP));
    104 
    105 LDAP_AVL_F( Avlnode* )
    106 ldap_avl_find2 LDAP_P((Avlnode *, const void*, AVL_CMP));
    107 
    108 LDAP_AVL_F( void* )
    109 ldap_avl_find_lin LDAP_P((Avlnode *, const void*, AVL_CMP));
    110 
    111 #ifdef AVL_NONREENTRANT
    112 LDAP_AVL_F( void* )
    113 ldap_avl_getfirst LDAP_P((Avlnode *));
    114 
    115 LDAP_AVL_F( void* )
    116 ldap_avl_getnext LDAP_P((void));
    117 #endif
    118 
    119 LDAP_AVL_F( int )
    120 ldap_avl_dup_error LDAP_P((void*, void*));
    121 
    122 LDAP_AVL_F( int )
    123 ldap_avl_dup_ok LDAP_P((void*, void*));
    124 
    125 LDAP_AVL_F( int )
    126 ldap_avl_apply LDAP_P((Avlnode *, AVL_APPLY, void*, int, int));
    127 
    128 LDAP_AVL_F( int )
    129 ldap_avl_prefixapply LDAP_P((Avlnode *, void*, AVL_CMP, void*, AVL_CMP, void*, int));
    130 
    131 LDAP_AVL_F( int )
    132 ldap_tavl_free LDAP_P(( TAvlnode *root, AVL_FREE dfree ));
    133 
    134 LDAP_AVL_F( int )
    135 ldap_tavl_insert LDAP_P((TAvlnode **, void*, AVL_CMP, AVL_DUP));
    136 
    137 LDAP_AVL_F( void* )
    138 ldap_tavl_delete LDAP_P((TAvlnode **, void*, AVL_CMP));
    139 
    140 LDAP_AVL_F( void* )
    141 ldap_tavl_find LDAP_P((TAvlnode *, const void*, AVL_CMP));
    142 
    143 LDAP_AVL_F( TAvlnode* )
    144 ldap_tavl_find2 LDAP_P((TAvlnode *, const void*, AVL_CMP));
    145 
    146 LDAP_AVL_F( TAvlnode* )
    147 ldap_tavl_find3 LDAP_P((TAvlnode *, const void*, AVL_CMP, int *ret));
    148 
    149 #define	TAVL_DIR_LEFT	0
    150 #define	TAVL_DIR_RIGHT	1
    151 
    152 LDAP_AVL_F( TAvlnode* )
    153 ldap_tavl_end LDAP_P((TAvlnode *, int direction));
    154 
    155 LDAP_AVL_F( TAvlnode* )
    156 ldap_tavl_next LDAP_P((TAvlnode *, int direction));
    157 
    158 /* apply traversal types */
    159 #define AVL_PREORDER	1
    160 #define AVL_INORDER	2
    161 #define AVL_POSTORDER	3
    162 /* what apply returns if it ran out of nodes */
    163 #define AVL_NOMORE	(-6)
    164 
    165 LDAP_END_DECL
    166 
    167 #endif /* _AVL */
    168