+++ /dev/null
-/*\r
- * tree234.h: header defining functions in tree234.c.\r
- * \r
- * This file is copyright 1999-2001 Simon Tatham.\r
- * \r
- * Permission is hereby granted, free of charge, to any person\r
- * obtaining a copy of this software and associated documentation\r
- * files (the "Software"), to deal in the Software without\r
- * restriction, including without limitation the rights to use,\r
- * copy, modify, merge, publish, distribute, sublicense, and/or\r
- * sell copies of the Software, and to permit persons to whom the\r
- * Software is furnished to do so, subject to the following\r
- * conditions:\r
- * \r
- * The above copyright notice and this permission notice shall be\r
- * included in all copies or substantial portions of the Software.\r
- * \r
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES\r
- * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
- * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR\r
- * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF\r
- * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
- * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
- * SOFTWARE.\r
- */\r
-\r
-#ifndef TREE234_H\r
-#define TREE234_H\r
-\r
-/*\r
- * This typedef is opaque outside tree234.c itself.\r
- */\r
-typedef struct tree234_Tag tree234;\r
-\r
-typedef int (*cmpfn234) (void *, void *);\r
-\r
-/*\r
- * Create a 2-3-4 tree. If `cmp' is NULL, the tree is unsorted, and\r
- * lookups by key will fail: you can only look things up by numeric\r
- * index, and you have to use addpos234() and delpos234().\r
- */\r
-tree234 *newtree234(cmpfn234 cmp);\r
-\r
-/*\r
- * Free a 2-3-4 tree (not including freeing the elements).\r
- */\r
-void freetree234(tree234 * t);\r
-\r
-/*\r
- * Add an element e to a sorted 2-3-4 tree t. Returns e on success,\r
- * or if an existing element compares equal, returns that.\r
- */\r
-void *add234(tree234 * t, void *e);\r
-\r
-/*\r
- * Add an element e to an unsorted 2-3-4 tree t. Returns e on\r
- * success, NULL on failure. (Failure should only occur if the\r
- * index is out of range or the tree is sorted.)\r
- * \r
- * Index range can be from 0 to the tree's current element count,\r
- * inclusive.\r
- */\r
-void *addpos234(tree234 * t, void *e, int index);\r
-\r
-/*\r
- * Look up the element at a given numeric index in a 2-3-4 tree.\r
- * Returns NULL if the index is out of range.\r
- * \r
- * One obvious use for this function is in iterating over the whole\r
- * of a tree (sorted or unsorted):\r
- * \r
- * for (i = 0; (p = index234(tree, i)) != NULL; i++) consume(p);\r
- * \r
- * or\r
- * \r
- * int maxcount = count234(tree);\r
- * for (i = 0; i < maxcount; i++) {\r
- * p = index234(tree, i);\r
- * assert(p != NULL);\r
- * consume(p);\r
- * }\r
- */\r
-void *index234(tree234 * t, int index);\r
-\r
-/*\r
- * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not\r
- * found. e is always passed as the first argument to cmp, so cmp\r
- * can be an asymmetric function if desired. cmp can also be passed\r
- * as NULL, in which case the compare function from the tree proper\r
- * will be used.\r
- * \r
- * Three of these functions are special cases of findrelpos234. The\r
- * non-`pos' variants lack the `index' parameter: if the parameter\r
- * is present and non-NULL, it must point to an integer variable\r
- * which will be filled with the numeric index of the returned\r
- * element.\r
- * \r
- * The non-`rel' variants lack the `relation' parameter. This\r
- * parameter allows you to specify what relation the element you\r
- * provide has to the element you're looking for. This parameter\r
- * can be:\r
- * \r
- * REL234_EQ - find only an element that compares equal to e\r
- * REL234_LT - find the greatest element that compares < e\r
- * REL234_LE - find the greatest element that compares <= e\r
- * REL234_GT - find the smallest element that compares > e\r
- * REL234_GE - find the smallest element that compares >= e\r
- * \r
- * Non-`rel' variants assume REL234_EQ.\r
- * \r
- * If `rel' is REL234_GT or REL234_LT, the `e' parameter may be\r
- * NULL. In this case, REL234_GT will return the smallest element\r
- * in the tree, and REL234_LT will return the greatest. This gives\r
- * an alternative means of iterating over a sorted tree, instead of\r
- * using index234:\r
- * \r
- * // to loop forwards\r
- * for (p = NULL; (p = findrel234(tree, p, NULL, REL234_GT)) != NULL ;)\r
- * consume(p);\r
- * \r
- * // to loop backwards\r
- * for (p = NULL; (p = findrel234(tree, p, NULL, REL234_LT)) != NULL ;)\r
- * consume(p);\r
- */\r
-enum {\r
- REL234_EQ, REL234_LT, REL234_LE, REL234_GT, REL234_GE\r
-};\r
-void *find234(tree234 * t, void *e, cmpfn234 cmp);\r
-void *findrel234(tree234 * t, void *e, cmpfn234 cmp, int relation);\r
-void *findpos234(tree234 * t, void *e, cmpfn234 cmp, int *index);\r
-void *findrelpos234(tree234 * t, void *e, cmpfn234 cmp, int relation,\r
- int *index);\r
-\r
-/*\r
- * Delete an element e in a 2-3-4 tree. Does not free the element,\r
- * merely removes all links to it from the tree nodes.\r
- * \r
- * delpos234 deletes the element at a particular tree index: it\r
- * works on both sorted and unsorted trees.\r
- * \r
- * del234 deletes the element passed to it, so it only works on\r
- * sorted trees. (It's equivalent to using findpos234 to determine\r
- * the index of an element, and then passing that index to\r
- * delpos234.)\r
- * \r
- * Both functions return a pointer to the element they delete, for\r
- * the user to free or pass on elsewhere or whatever. If the index\r
- * is out of range (delpos234) or the element is already not in the\r
- * tree (del234) then they return NULL.\r
- */\r
-void *del234(tree234 * t, void *e);\r
-void *delpos234(tree234 * t, int index);\r
-\r
-/*\r
- * Return the total element count of a tree234.\r
- */\r
-int count234(tree234 * t);\r
-\r
-#endif /* TREE234_H */\r
OSDN Git Service
