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 /*
  19  * this structure represents a generic avl tree node.
  20  */
  21
  22 typedef struct avlnode {
  23         caddr_t         avl_data;
  24         char            avl_bf;
  25         struct avlnode  *avl_left;
  26         struct avlnode  *avl_right;
  27 } Avlnode;
  28
  29 #define NULLAVL ((Avlnode *) NULL)
  30
  31 /* balance factor values */
  32 #define LH      -1
  33 #define EH      0
  34 #define RH      1
  35
  36 /* avl routines */
  37 #define avl_getone(x)   (x == 0 ? 0 : (x)->avl_data)
  38 #define avl_onenode(x)  (x == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0))
  39 extern int              avl_insert();
  40 extern caddr_t          avl_delete();
  41 extern caddr_t          avl_find();
  42 extern caddr_t          avl_getfirst();
  43 extern caddr_t          avl_getnext();
  44 extern int              avl_dup_error();
  45 extern int              avl_apply();
  46
  47 /* apply traversal types */
  48 #define AVL_PREORDER    1
  49 #define AVL_INORDER     2
  50 #define AVL_POSTORDER   3
  51 /* what apply returns if it ran out of nodes */
  52 #define AVL_NOMORE      -6
  53
  54 typedef int     (*IFP)();
  55
  56 #endif /* _AVL */