src/fastdep/avl.h

   1 /* $Id$
   2  *
   3  * AVL-Tree (lookalike) declaration.
   4  *
   5  * This AVL implementation is configurable from this headerfile. By
   6  * for example alterning the AVLKEY typedefinition an the AVL_<L|G|E|N>[E]
   7  * macros you are able to create different trees. Currently you may only have
   8  * one type of trees within one program (module).
   9  *
  10  * TREETYPE: Case Sensitive Strings (Key is pointer).
  11  *
  12  *
  13  * Copyright (c) 1999-2000 knut st. osmundsen
  14  *
  15  * Project Odin Software License can be found in LICENSE.TXT
  16  *
  17  */
  18 #ifndef _AVL_H_
  19 #define _AVL_H_
  20
  21 #ifdef __cplusplus
  22 extern "C" {
  23 #endif
  24
  25 /*
  26  * AVL configuration. PRIVATE!
  27  */
  28 #define AVL_MAX_HEIGHT              19          /* Up to 2^16 nodes. */
  29 #define AVL_MAY_TRY_INSERT_EQUAL    1           /* Ignore attempts to insert existing nodes. */
  30
  31 /*
  32  * AVL Compare macros
  33  */
  34 #define AVL_L(key1, key2)  (strcmp(key1, key2) <  0)
  35 #define AVL_LE(key1, key2) (strcmp(key1, key2) <= 0)
  36 #define AVL_G(key1, key2)  (strcmp(key1, key2) >  0)
  37 #define AVL_GE(key1, key2) (strcmp(key1, key2) >= 0)
  38 #define AVL_E(key1, key2)  (strcmp(key1, key2) == 0)
  39 #define AVL_NE(key1, key2) (strcmp(key1, key2) != 0)
  40 #define AVL_CMP(key1, key2) strcmp(key1, key2)
  41
  42 /**
  43  * AVL key type
  44  */
  45 typedef const char *AVLKEY;
  46
  47
  48 /**
  49  * AVL Core node.
  50  */
  51 typedef struct _AVLNodeCore
  52 {
  53     AVLKEY                  Key;       /* Key value. */
  54     struct  _AVLNodeCore *  pLeft;     /* Pointer to left leaf node. */
  55     struct  _AVLNodeCore *  pRight;    /* Pointer to right leaf node. */
  56     unsigned char           uchHeight; /* Height of this tree: max(heigth(left), heigth(right)) + 1 */
  57 } AVLNODECORE, *PAVLNODECORE, **PPAVLNODECORE;
  58
  59
  60 /**
  61  * AVL Enum data - All members are PRIVATE! Don't touch!
  62  */
  63 typedef struct _AVLEnumData
  64 {
  65     char         fFromLeft;
  66     char         cEntries;
  67     char         achFlags[AVL_MAX_HEIGHT];
  68     PAVLNODECORE aEntries[AVL_MAX_HEIGHT];
  69 } AVLENUMDATA, *PAVLENUMDATA;
  70
  71
  72 /*
  73  * callback type
  74  */
  75 typedef unsigned ( _PAVLCALLBACK)(PAVLNODECORE, void*);
  76 typedef _PAVLCALLBACK *PAVLCALLBACK;
  77
  78
  79 BOOL            AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode);
  80 PAVLNODECORE    AVLRemove(PPAVLNODECORE ppTree, AVLKEY Key);
  81 PAVLNODECORE    AVLGet(PPAVLNODECORE ppTree, AVLKEY Key);
  82 PAVLNODECORE    AVLGetWithParent(PPAVLNODECORE ppTree, PPAVLNODECORE ppParent, AVLKEY Key);
  83 PAVLNODECORE    AVLGetWithAdjecentNodes(PPAVLNODECORE ppTree, AVLKEY Key, PPAVLNODECORE ppLeft, PPAVLNODECORE ppRight);
  84 unsigned        AVLDoWithAll(PPAVLNODECORE ppTree, int fFromLeft, PAVLCALLBACK pfnCallBack, void *pvParam);
  85 PAVLNODECORE    AVLBeginEnumTree(PPAVLNODECORE ppTree, PAVLENUMDATA pEnumData, int fFromLeft);
  86 PAVLNODECORE    AVLGetNextNode(PAVLENUMDATA pEnumData);
  87 PAVLNODECORE    AVLGetBestFit(PPAVLNODECORE ppTree, AVLKEY Key, int fAbove);
  88
  89
  90
  91 /*
  92  * Just in case NULL is undefined.
  93  */
  94 #ifndef NULL
  95     #define NULL ((void*)0)
  96 #endif
  97
  98 #ifdef __cplusplus
  99 }
 100 #endif
 101
 102 #endif