1 #ifndef DWARF_TSEARCH 2 #define DWARF_TSEARCH 3 /* Copyright (c) 2013, David Anderson 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with 7 or without modification, are permitted provided that the 8 following conditions are met: 9 10 Redistributions of source code must retain the above 11 copyright notice, this list of conditions and the following 12 disclaimer. 13 14 Redistributions in binary form must reproduce the above 15 copyright notice, this list of conditions and the following 16 disclaimer in the documentation and/or other materials 17 provided with the distribution. 18 19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 20 CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 21 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 22 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 24 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 25 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 27 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 29 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 30 OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 31 EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 33 */ 34 35 /* The following interfaces follow tsearch (See the Single 36 Unix Specification) but the implementation is 37 written without reference to the source code 38 of any version of tsearch. Only uses 39 of tsearch were examined, not tsearch source code. 40 41 See http://reality.sgiweb.org/davea/tsearch.html 42 for information about tsearch. 43 44 We are matching the standard functional 45 interface here, but to avoid interfering with 46 libc implementations or code using libc 47 implementations, we change all the names. 48 49 */ 50 51 /* The hashfunc return is now easily changed with 52 cc -Duintptr_t or something. */ 53 #ifndef DW_TSHASHTYPE 54 #define DW_TSHASHTYPE unsigned long 55 #endif 56 57 /* The DW_VISIT values passed back to you through 58 the callback function in dwarf_twalk(); 59 */ 60 typedef enum 61 { 62 dwarf_preorder, 63 dwarf_postorder, 64 dwarf_endorder, 65 dwarf_leaf 66 } 67 DW_VISIT; 68 69 /* void * return values are actually 70 void **key so you must dereference these 71 once to get a key you passed in. 72 */ 73 74 /* We rename these so there is no conflict with another version 75 of the tsearch sources, such as is used in dwarfdump. */ 76 #define dwarf_tsearch _dwarf_tsearch 77 #define dwarf_tfind _dwarf_tfind 78 #define dwarf_tdelete _dwarf_tdelete 79 #define dwarf_twalk _dwarf_twalk 80 #define dwarf_tdestroy _dwarf_tdestroy 81 #define dwarf_tdump _dwarf_tdump 82 #define dwarf_initialize_search_hash _dwarf_initialize_search_hash 83 84 void *dwarf_tsearch(const void * /*key*/, void ** /*rootp*/, 85 int (* /*compar*/)(const void *, const void *)); 86 87 void *dwarf_tfind(const void * /*key*/, void *const * /*rootp*/, 88 int (* /*compar*/)(const void *, const void *)); 89 90 /* 91 dwarf_tdelete() returns NULL if it cannot delete anything 92 or if the tree is now empty (if empty, *rootp 93 is set NULL by dwarf_tdelete()). 94 If the delete succeeds and the tree is non-empty returns 95 a pointer to the parent node of the deleted item, 96 unless the deleted item was at the root, in which 97 case the returned pointer relates to the new root. 98 */ 99 void *dwarf_tdelete(const void * /*key*/, void ** /*rootp*/, 100 int (* /*compar*/)(const void *, const void *)); 101 102 void dwarf_twalk(const void * /*root*/, 103 void (* /*action*/)(const void * /*nodep*/, 104 const DW_VISIT /*which*/, 105 const int /*depth*/)); 106 107 /* dwarf_tdestroy() cannot set the root pointer NULL, you must do 108 so on return from dwarf_tdestroy(). */ 109 void dwarf_tdestroy(void * /*root*/, 110 void (* /*free_node*/)(void * /*nodep*/)); 111 112 113 /* Prints a simple tree representation to stdout. For debugging. 114 */ 115 void dwarf_tdump(const void*root, 116 char *(* /*keyprint*/)(const void *), 117 const char *msg); 118 119 /* Returns NULL and does nothing 120 unless the implemenation used uses a hash tree. */ 121 void * dwarf_initialize_search_hash( void **treeptr, 122 DW_TSHASHTYPE (*hashfunc)(const void *key), 123 unsigned long size_estimate); 124 #endif /* DWARF_TSEARCH */ 125 126 127 128