1 /* 2 Copyright (C) 1993-2018 Free Software Foundation, Inc. 3 This file is based on the GNU C Library and contains: 4 5 * Declarations for System V style searching functions 6 * Declarations for hash hash table management functions 7 8 The GNU C Library is free software; you can redistribute it and/or 9 modify it under the terms of the GNU Lesser General Public 10 License as published by the Free Software Foundation; either 11 version 2.1 of the License, or (at your option) any later version. 12 13 The GNU C Library is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 Lesser General Public License for more details. 17 18 You should have received a copy of the GNU Lesser General Public 19 License along with the GNU C Library; if not, see 20 <http://www.gnu.org/licenses/>. 21 */ 22 #ifndef PMSEARCH_H 23 #define PMSEARCH_H 24 25 /* includes */ 26 #include <stddef.h> 27 #include <stdint.h> 28 29 /* definitions */ 30 typedef struct pm_node_t 31 { 32 /* Callers expect this to be the first element in the structure - do not 33 move! */ 34 const void *key; 35 uintptr_t left_node; /* Includes whether the node is red in low-bit. */ 36 uintptr_t right_node; 37 } *pm_node; 38 39 #define RED(N) (pm_node)((N)->left_node & ((uintptr_t) 0x1)) 40 #define SETRED(N) (N)->left_node |= ((uintptr_t) 0x1) 41 #define SETBLACK(N) (N)->left_node &= ~((uintptr_t) 0x1) 42 #define SETNODEPTR(NP,P) (*NP) = (pm_node)((((uintptr_t)(*NP)) \ 43 & (uintptr_t) 0x1) | (uintptr_t)(P)) 44 #define LEFT(N) (pm_node)((N)->left_node & ~((uintptr_t) 0x1)) 45 #define LEFTPTR(N) (pm_node *)(&(N)->left_node) 46 #define SETLEFT(N,L) (N)->left_node = (((N)->left_node & (uintptr_t) 0x1) \ 47 | (uintptr_t)(L)) 48 #define RIGHT(N) (pm_node)((N)->right_node) 49 #define RIGHTPTR(N) (pm_node *)(&(N)->right_node) 50 #define SETRIGHT(N,R) (N)->right_node = (uintptr_t)(R) 51 #define DEREFNODEPTR(NP) (pm_node)((uintptr_t)(*(NP)) & ~((uintptr_t) 0x1)) 52 53 typedef const struct pm_node_t *pm_const_node; 54 55 /* The tsearch routines are very interesting. They make many 56 assumptions about the compiler. It assumes that the first field 57 in node must be the "key" field, which points to the datum. 58 Everything depends on that. */ 59 typedef enum 60 { 61 preorder, 62 postorder, 63 endorder, 64 leaf 65 } pm_VISIT; 66 67 typedef int (*pm_compar_fn_t) (const void *, const void *); 68 typedef int (*pm_action_fn_t) (const void *, pm_VISIT, int, void *); 69 typedef void (*pm_free_fn_t) (void *); 70 71 typedef enum { 72 FIND, 73 INSERT, 74 DELETE 75 } pm_ACTION; 76 77 typedef struct pm_hentry_t { 78 void *key; 79 unsigned int keylen; 80 void *data; 81 } pm_HENTRY; 82 83 typedef struct _pm_hentry_t { 84 unsigned int used; 85 pm_HENTRY entry; 86 } _pm_HENTRY; 87 88 struct pm_htable { 89 _pm_HENTRY *table; 90 unsigned int size; 91 unsigned int filled; 92 }; 93 94 /* prototypes */ 95 /* Search for an entry matching the given KEY in the tree pointed to 96 by *ROOTP and insert a new element if not found. */ 97 extern void *__pm_tsearch (const void *, void **, pm_compar_fn_t); 98 99 /* Search for an entry matching the given KEY in the tree pointed to 100 by *ROOTP. If no matching entry is available return NULL. */ 101 extern void *pm_tfind (const void *, void **, pm_compar_fn_t); 102 103 /* Remove the element matching KEY from the tree pointed to by *ROOTP. */ 104 extern void *pm_tdelete (const void *, void **, pm_compar_fn_t); 105 106 /* Walk through the whole tree and call the ACTION callback for every node or leaf. */ 107 extern void pm_twalk (const void *, pm_action_fn_t, void *); 108 109 /* Destroy the whole tree, call FREEFCT for each node or leaf. */ 110 extern void __pm_tdestroy (void *, pm_free_fn_t); 111 112 extern int pm_hcreate(size_t, struct pm_htable *); 113 extern void pm_hdestroy(struct pm_htable *); 114 extern int pm_hsearch(pm_HENTRY, pm_ACTION, pm_HENTRY **, struct pm_htable *); 115 extern void pm_hmove(struct pm_htable *, struct pm_htable *, struct pm_htable *); 116 extern void __pm_hdelete(_pm_HENTRY *); 117 118 #endif //PMSEARCH_H 119