git.sur5r.net Git - openldap/blob - include/avl.h

   1 /* avl.h - avl tree definitions */
   2 /*
   3  * Copyright (c) 1993 Regents of the University of Michigan.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms are permitted
   7  * provided that this notice is preserved and that due credit is given
   8  * to the University of Michigan at Ann Arbor. The name of the University
   9  * may not be used to endorse or promote products derived from this
  10  * software without specific prior written permission. This software
  11  * is provided ``as is'' without express or implied warranty.
  12  */
  13
  14
  15 #ifndef _AVL
  16 #define _AVL
  17
  18 #include <ldap_cdefs.h>
  19
  20 /*
  21  * this structure represents a generic avl tree node.
  22  */
  23
  24 LDAP_BEGIN_DECL
  25
  26 typedef struct avlnode {
  27         caddr_t         avl_data;
  28         signed char             avl_bf;
  29         struct avlnode  *avl_left;
  30         struct avlnode  *avl_right;
  31 } Avlnode;
  32
  33 #define NULLAVL ((Avlnode *) NULL)
  34
  35 /* balance factor values */
  36 #define LH      -1
  37 #define EH      0
  38 #define RH      1
  39
  40 /* avl routines */
  41 #define avl_getone(x)   ((x) == 0 ? 0 : (x)->avl_data)
  42 #define avl_onenode(x)  ((x) == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0))
  43
  44 /* looks like this function pointer is not used consistently */
  45 /* typedef int  (*IFP)LDAP_P((caddr_t, caddr_t)); */
  46 typedef int     (*IFP)();
  47
  48 LDAP_F int
  49 avl_free LDAP_P(( Avlnode *root, IFP dfree ));
  50
  51 LDAP_F int
  52 avl_insert LDAP_P((Avlnode **, caddr_t, IFP, IFP));
  53
  54 LDAP_F caddr_t
  55 avl_delete LDAP_P((Avlnode **, caddr_t, IFP));
  56
  57 LDAP_F caddr_t
  58 avl_find LDAP_P((Avlnode *, caddr_t, IFP));
  59
  60 LDAP_F caddr_t
  61 avl_getfirst LDAP_P((Avlnode *));
  62
  63 #ifdef AVL_REENTRANT
  64 LDAP_F caddr_t
  65 avl_getnext LDAP_P((Avlnode *, caddr_t ));
  66 #else
  67 LDAP_F caddr_t
  68 avl_getnext LDAP_P((void));
  69 #endif
  70
  71 LDAP_F int
  72 avl_dup_error LDAP_P((void));
  73
  74 LDAP_F int
  75 avl_apply LDAP_P((Avlnode *, IFP, caddr_t, int, int));
  76
  77 /* apply traversal types */
  78 #define AVL_PREORDER    1
  79 #define AVL_INORDER     2
  80 #define AVL_POSTORDER   3
  81 /* what apply returns if it ran out of nodes */
  82 #define AVL_NOMORE      -6
  83
  84 LDAP_END_DECL
  85
  86 #endif /* _AVL */