00001 /* 00002 * tree234.h: header defining functions in tree234.c. 00003 * 00004 * This file is copyright 1999-2001 Simon Tatham. 00005 * 00006 * Permission is hereby granted, free of charge, to any person 00007 * obtaining a copy of this software and associated documentation 00008 * files (the "Software"), to deal in the Software without 00009 * restriction, including without limitation the rights to use, 00010 * copy, modify, merge, publish, distribute, sublicense, and/or 00011 * sell copies of the Software, and to permit persons to whom the 00012 * Software is furnished to do so, subject to the following 00013 * conditions: 00014 * 00015 * The above copyright notice and this permission notice shall be 00016 * included in all copies or substantial portions of the Software. 00017 * 00018 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00019 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 00020 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00021 * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR 00022 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 00023 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 00024 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 00025 * SOFTWARE. 00026 */ 00027 00028 #ifndef TREE234_H 00029 #define TREE234_H 00030 00031 /* 00032 * This typedef is opaque outside tree234.c itself. 00033 */ 00034 typedef struct tree234_Tag tree234; 00035 00036 typedef int (*cmpfn234) (void *, void *); 00037 00038 /* 00039 * Create a 2-3-4 tree. If `cmp' is NULL, the tree is unsorted, and 00040 * lookups by key will fail: you can only look things up by numeric 00041 * index, and you have to use addpos234() and delpos234(). 00042 */ 00043 tree234 *newtree234(cmpfn234 cmp); 00044 00045 /* 00046 * Free a 2-3-4 tree (not including freeing the elements). 00047 */ 00048 void freetree234(tree234 * t); 00049 00050 /* 00051 * Add an element e to a sorted 2-3-4 tree t. Returns e on success, 00052 * or if an existing element compares equal, returns that. 00053 */ 00054 void *add234(tree234 * t, void *e); 00055 00056 /* 00057 * Add an element e to an unsorted 2-3-4 tree t. Returns e on 00058 * success, NULL on failure. (Failure should only occur if the 00059 * index is out of range or the tree is sorted.) 00060 * 00061 * Index range can be from 0 to the tree's current element count, 00062 * inclusive. 00063 */ 00064 void *addpos234(tree234 * t, void *e, int index); 00065 00066 /* 00067 * Look up the element at a given numeric index in a 2-3-4 tree. 00068 * Returns NULL if the index is out of range. 00069 * 00070 * One obvious use for this function is in iterating over the whole 00071 * of a tree (sorted or unsorted): 00072 * 00073 * for (i = 0; (p = index234(tree, i)) != NULL; i++) consume(p); 00074 * 00075 * or 00076 * 00077 * int maxcount = count234(tree); 00078 * for (i = 0; i < maxcount; i++) { 00079 * p = index234(tree, i); 00080 * assert(p != NULL); 00081 * consume(p); 00082 * } 00083 */ 00084 void *index234(tree234 * t, int index); 00085 00086 /* 00087 * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not 00088 * found. e is always passed as the first argument to cmp, so cmp 00089 * can be an asymmetric function if desired. cmp can also be passed 00090 * as NULL, in which case the compare function from the tree proper 00091 * will be used. 00092 * 00093 * Three of these functions are special cases of findrelpos234. The 00094 * non-`pos' variants lack the `index' parameter: if the parameter 00095 * is present and non-NULL, it must point to an integer variable 00096 * which will be filled with the numeric index of the returned 00097 * element. 00098 * 00099 * The non-`rel' variants lack the `relation' parameter. This 00100 * parameter allows you to specify what relation the element you 00101 * provide has to the element you're looking for. This parameter 00102 * can be: 00103 * 00104 * REL234_EQ - find only an element that compares equal to e 00105 * REL234_LT - find the greatest element that compares < e 00106 * REL234_LE - find the greatest element that compares <= e 00107 * REL234_GT - find the smallest element that compares > e 00108 * REL234_GE - find the smallest element that compares >= e 00109 * 00110 * Non-`rel' variants assume REL234_EQ. 00111 * 00112 * If `rel' is REL234_GT or REL234_LT, the `e' parameter may be 00113 * NULL. In this case, REL234_GT will return the smallest element 00114 * in the tree, and REL234_LT will return the greatest. This gives 00115 * an alternative means of iterating over a sorted tree, instead of 00116 * using index234: 00117 * 00118 * // to loop forwards 00119 * for (p = NULL; (p = findrel234(tree, p, NULL, REL234_GT)) != NULL ;) 00120 * consume(p); 00121 * 00122 * // to loop backwards 00123 * for (p = NULL; (p = findrel234(tree, p, NULL, REL234_LT)) != NULL ;) 00124 * consume(p); 00125 */ 00126 enum { 00127 REL234_EQ, REL234_LT, REL234_LE, REL234_GT, REL234_GE 00128 }; 00129 void *find234(tree234 * t, void *e, cmpfn234 cmp); 00130 void *findrel234(tree234 * t, void *e, cmpfn234 cmp, int relation); 00131 void *findpos234(tree234 * t, void *e, cmpfn234 cmp, int *index); 00132 void *findrelpos234(tree234 * t, void *e, cmpfn234 cmp, int relation, 00133 int *index); 00134 00135 /* 00136 * Delete an element e in a 2-3-4 tree. Does not free the element, 00137 * merely removes all links to it from the tree nodes. 00138 * 00139 * delpos234 deletes the element at a particular tree index: it 00140 * works on both sorted and unsorted trees. 00141 * 00142 * del234 deletes the element passed to it, so it only works on 00143 * sorted trees. (It's equivalent to using findpos234 to determine 00144 * the index of an element, and then passing that index to 00145 * delpos234.) 00146 * 00147 * Both functions return a pointer to the element they delete, for 00148 * the user to free or pass on elsewhere or whatever. If the index 00149 * is out of range (delpos234) or the element is already not in the 00150 * tree (del234) then they return NULL. 00151 */ 00152 void *del234(tree234 * t, void *e); 00153 void *delpos234(tree234 * t, int index); 00154 00155 /* 00156 * Return the total element count of a tree234. 00157 */ 00158 int count234(tree234 * t); 00159 00160 #endif /* TREE234_H */