1 #ifndef DWARF_TSEARCH_H 2 #define DWARF_TSEARCH_H 3 /* Copyright (c) 2013-2019, 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 https://www.prevanders.net/tsearch.html 42 and https://www.prevanders.net/dwarf.html#tsearch 43 for information about tsearch. 44 45 We are matching the standard functional 46 interface here, but to avoid interfering with 47 libc implementations or code using libc 48 implementations, we change all the names. 49 50 */ 51 52 /* configure/cmake ensure uintptr_t defined, but if not, 53 possibly "-Duintptr_t=unsigned long" might help */ 54 #ifndef DW_TSHASHTYPE 55 #define DW_TSHASHTYPE uintptr_t 56 #endif 57 58 /* The DW_VISIT values passed back to you through 59 the callback function in dwarf_twalk(); 60 */ 61 typedef enum 62 { 63 dwarf_preorder, 64 dwarf_postorder, 65 dwarf_endorder, 66 dwarf_leaf 67 } 68 DW_VISIT; 69 70 /* void * return values are actually 71 void **key so you must dereference these 72 once to get a key you passed in. 73 */ 74 75 /* We rename these so there is no conflict with another version 76 of the tsearch sources, such as is used in dwarfdump. */ 77 #define dwarf_tsearch _dwarf_tsearch 78 #define dwarf_tfind _dwarf_tfind 79 #define dwarf_tdelete _dwarf_tdelete 80 #define dwarf_twalk _dwarf_twalk 81 #define dwarf_tdestroy _dwarf_tdestroy 82 #define dwarf_tdump _dwarf_tdump 83 #define dwarf_initialize_search_hash _dwarf_initialize_search_hash 84 85 void *dwarf_tsearch(const void * /*key*/, void ** /*rootp*/, 86 int (* /*compar*/)(const void *, const void *)); 87 88 void *dwarf_tfind(const void * /*key*/, void *const * /*rootp*/, 89 int (* /*compar*/)(const void *, const void *)); 90 91 /* 92 dwarf_tdelete() returns NULL if it cannot delete anything 93 or if the tree is now empty (if empty, *rootp 94 is set NULL by dwarf_tdelete()). 95 If the delete succeeds and the tree is non-empty returns 96 a pointer to the parent node of the deleted item, 97 unless the deleted item was at the root, in which 98 case the returned pointer relates to the new root. 99 */ 100 void *dwarf_tdelete(const void * /*key*/, void ** /*rootp*/, 101 int (* /*compar*/)(const void *, const void *)); 102 103 void dwarf_twalk(const void * /*root*/, 104 void (* /*action*/)(const void * /*nodep*/, 105 const DW_VISIT /*which*/, 106 const int /*depth*/)); 107 108 /* dwarf_tdestroy() cannot set the root pointer NULL, you must do 109 so on return from dwarf_tdestroy(). */ 110 void dwarf_tdestroy(void * /*root*/, 111 void (* /*free_node*/)(void * /*nodep*/)); 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_H */ 125