1 #ifndef MP_TREE_H 2 #define MP_TREE_H 3 4 5 /* 6 * mpatrol 7 * A library for controlling and tracing dynamic memory allocations. 8 * Copyright (C) 1997-2002 Graeme S. Roy <graeme.roy@analog.com> 9 * 10 * This library is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU Library General Public 12 * License as published by the Free Software Foundation; either 13 * version 2 of the License, or (at your option) any later version. 14 * 15 * This library is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 * Library General Public License for more details. 19 * 20 * You should have received a copy of the GNU Library General Public 21 * License along with this library; if not, write to the Free 22 * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, 23 * MA 02111-1307, USA. 24 */ 25 26 27 /* 28 * Binary search trees. All tree structures used within the mpatrol 29 * library are based on the following data structures and use the same 30 * interface for building and traversing them. Only the linkage between 31 * tree nodes is dealt with by this module - dynamically allocating 32 * memory for nodes is done elsewhere. 33 */ 34 35 36 /* 37 * $Id: tree.h,v 1.6 2002/01/08 20:13:59 graeme Exp $ 38 */ 39 40 41 #include "config.h" 42 #include <stddef.h> 43 44 45 /* A tree node simply contains linkage information and is intended to be 46 * used as a member for any datatypes that need to belong to a tree. 47 */ 48 49 typedef struct treenode 50 { 51 struct treenode *parent; /* parent node in tree */ 52 struct treenode *left; /* left child node in tree */ 53 struct treenode *right; /* right child node in tree */ 54 unsigned long key; /* search key */ 55 char flag; /* node flags */ 56 } 57 treenode; 58 59 60 /* A tree root contains a pointer to the topmost node of the tree and 61 * also contains a sentinel leaf node in order to make tree manipulation 62 * simpler. 63 */ 64 65 typedef struct treeroot 66 { 67 struct treenode *root; /* topmost node of tree */ 68 struct treenode null; /* leaf node for tree */ 69 size_t size; /* number of nodes in tree */ 70 } 71 treeroot; 72 73 74 #ifdef __cplusplus 75 extern "C" 76 { 77 #endif /* __cplusplus */ 78 79 80 MP_EXPORT void __mp_newtree(treeroot *); 81 MP_EXPORT void __mp_treeinsert(treeroot *, treenode *, unsigned long); 82 MP_EXPORT void __mp_treeremove(treeroot *, treenode *); 83 MP_EXPORT treenode *__mp_search(treenode *, unsigned long); 84 MP_EXPORT treenode *__mp_searchlower(treenode *, unsigned long); 85 MP_EXPORT treenode *__mp_searchhigher(treenode *, unsigned long); 86 MP_EXPORT treenode *__mp_minimum(treenode *); 87 MP_EXPORT treenode *__mp_maximum(treenode *); 88 MP_EXPORT treenode *__mp_predecessor(treenode *); 89 MP_EXPORT treenode *__mp_successor(treenode *); 90 91 92 #ifdef __cplusplus 93 } 94 #endif /* __cplusplus */ 95 96 97 #endif /* MP_TREE_H */ 98