VirtualBox

source: kBuild/trunk/src/fastdep/avl.h@ 936

Last change on this file since 936 was 7, checked in by bird, 22 years ago

Initial version from odin32.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 2.8 KB
Line 
1/* $Id: avl.h 7 2002-10-15 21:00:40Z bird $
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
22extern "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 */
45typedef const char *AVLKEY;
46
47
48/**
49 * AVL Core node.
50 */
51typedef 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 */
63typedef 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 */
75typedef unsigned ( _PAVLCALLBACK)(PAVLNODECORE, void*);
76typedef _PAVLCALLBACK *PAVLCALLBACK;
77
78
79BOOL AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode);
80PAVLNODECORE AVLRemove(PPAVLNODECORE ppTree, AVLKEY Key);
81PAVLNODECORE AVLGet(PPAVLNODECORE ppTree, AVLKEY Key);
82PAVLNODECORE AVLGetWithParent(PPAVLNODECORE ppTree, PPAVLNODECORE ppParent, AVLKEY Key);
83PAVLNODECORE AVLGetWithAdjecentNodes(PPAVLNODECORE ppTree, AVLKEY Key, PPAVLNODECORE ppLeft, PPAVLNODECORE ppRight);
84unsigned AVLDoWithAll(PPAVLNODECORE ppTree, int fFromLeft, PAVLCALLBACK pfnCallBack, void *pvParam);
85PAVLNODECORE AVLBeginEnumTree(PPAVLNODECORE ppTree, PAVLENUMDATA pEnumData, int fFromLeft);
86PAVLNODECORE AVLGetNextNode(PAVLENUMDATA pEnumData);
87PAVLNODECORE 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
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette