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_find_lin LDAP_P((Avlnode *, caddr_t, IFP));
  62
  63 LDAP_F caddr_t
  64 avl_getfirst LDAP_P((Avlnode *));
  65
  66 #ifdef AVL_REENTRANT
  67 /* ??? avl.c does not provide this version ??? */
  68 LDAP_F caddr_t
  69 avl_getnext LDAP_P((Avlnode *, caddr_t ));
  70 #else
  71 LDAP_F caddr_t
  72 avl_getnext LDAP_P((void));
  73 #endif
  74
  75 LDAP_F int
  76 avl_dup_error LDAP_P((void));
  77
  78 LDAP_F int
  79 avl_dup_ok LDAP_P((void));
  80
  81 LDAP_F int
  82 avl_apply LDAP_P((Avlnode *, IFP, caddr_t, int, int));
  83
  84 LDAP_F int
  85 avl_prefixapply LDAP_P((Avlnode *, caddr_t, IFP, caddr_t, IFP, caddr_t, int));
  86
  87 /* apply traversal types */
  88 #define AVL_PREORDER    1
  89 #define AVL_INORDER     2
  90 #define AVL_POSTORDER   3
  91 /* what apply returns if it ran out of nodes */
  92 #define AVL_NOMORE      (-6)
  93
  94 LDAP_END_DECL
  95
  96 #endif /* _AVL */