BRL-CAD
hash.h
Go to the documentation of this file.
1 /* H A S H . H
2  * BRL-CAD
3  *
4  * Copyright (c) 2004-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 /** @file hash.h
22  *
23  */
24 #ifndef BU_HASH_H
25 #define BU_HASH_H
26 
27 #include "common.h"
28 
29 #include "bu/defines.h"
30 
32 
33 /** @addtogroup hash */
34 /** @{ */
35 /** @file libbu/hash.c
36  *
37  * @brief
38  * An implementation of hash tables.
39  */
40 
41 /**
42  * A hash entry
43  */
44 struct bu_hash_entry {
45  uint32_t magic;
46  unsigned char *key;
47  unsigned char *value;
48  int key_len;
50 };
52 #define BU_HASH_ENTRY_NULL ((struct bu_hash_entry *)0)
53 
54 /**
55  * asserts the integrity of a non-head node bu_hash_entry struct.
56  */
57 #define BU_CK_HASH_ENTRY(_ep) BU_CKMAG(_ep, BU_HASH_ENTRY_MAGIC, "bu_hash_entry")
58 
59 /**
60  * initializes a bu_hash_entry struct without allocating any memory.
61  */
62 #define BU_HASH_ENTRY_INIT(_h) { \
63  (_h)->magic = BU_HASH_ENTRY_MAGIC; \
64  (_h)->key = (_h)->value = NULL; \
65  (_h)->key_len = 0; \
66  (_h)->next = NULL; \
67  }
68 
69 /**
70  * macro suitable for declaration statement initialization of a
71  * bu_hash_entry struct. does not allocate memory.
72  */
73 #define BU_HASH_ENTRY_INIT_ZERO { BU_HASH_ENTRY_MAGIC, NULL, NULL, 0, NULL }
74 
75 /**
76  * returns truthfully whether a bu_hash_entry has been initialized.
77  */
78 #define BU_HASH_ENTRY_IS_INITIALIZED(_h) (((struct bu_hash_entry *)(_h) != BU_HASH_ENTRY_NULL) && LIKELY((_h)->magic == BU_HASH_ENTRY_MAGIC))
79 
80 
81 /**
82  * A table of hash entries
83  */
84 struct bu_hash_tbl {
85  uint32_t magic;
86  unsigned long mask;
87  unsigned long num_lists;
88  unsigned long num_entries;
89  struct bu_hash_entry **lists;
90 };
91 typedef struct bu_hash_tbl bu_hash_tbl_t;
92 #define BU_HASH_TBL_NULL ((struct bu_hash_tbl *)0)
93 
94 /**
95  * asserts the integrity of a non-head node bu_hash_tbl struct.
96  */
97 #define BU_CK_HASH_TBL(_hp) BU_CKMAG(_hp, BU_HASH_TBL_MAGIC, "bu_hash_tbl")
98 
99 /**
100  * initializes a bu_hash_tbl struct without allocating any memory.
101  */
102 #define BU_HASH_TBL_INIT(_h) { \
103  (_h)->magic = BU_HASH_TBL_MAGIC; \
104  (_h)->mask = (_h)->num_lists = (_h)->num_entries = 0; \
105  (_h)->lists = NULL; \
106  }
107 
108 /**
109  * macro suitable for declaration statement initialization of a
110  * bu_hash_tbl struct. does not allocate memory.
111  */
112 #define BU_HASH_TBL_INIT_ZERO { BU_HASH_TBL_MAGIC, 0, 0, 0, NULL }
113 
114 /**
115  * returns truthfully whether a bu_hash_tbl has been initialized.
116  */
117 #define BU_HASH_TBL_IS_INITIALIZED(_h) (((struct bu_hash_tbl *)(_h) != BU_HASH_TBL_NULL) && LIKELY((_h)->magic == BU_HASH_TBL_MAGIC))
118 
119 
120 /**
121  * A hash table entry record
122  */
124  uint32_t magic;
125  const struct bu_hash_tbl *tbl;
126  unsigned long index;
128 };
130 #define BU_HASH_RECORD_NULL ((struct bu_hash_record *)0)
131 
132 /**
133  * asserts the integrity of a non-head node bu_hash_record struct.
134  */
135 #define BU_CK_HASH_RECORD(_rp) BU_CKMAG(_rp, BU_HASH_RECORD_MAGIC, "bu_hash_record")
136 
137 /**
138  * initializes a bu_hash_record struct without allocating any memory.
139  */
140 #define BU_HASH_RECORD_INIT(_h) { \
141  (_h)->magic = BU_HASH_RECORD_MAGIC; \
142  (_h)->tbl = NULL; \
143  (_h)->index = 0; \
144  (_h)->hsh_entry = NULL; \
145  }
146 
147 /**
148  * macro suitable for declaration statement initialization of a
149  * bu_hash_record struct. does not allocate memory.
150  */
151 #define BU_HASH_RECORD_INIT_ZERO { BU_HASH_RECORD_MAGIC, NULL, 0, NULL }
152 
153 /**
154  * returns truthfully whether a bu_hash_record has been initialized.
155  */
156 #define BU_HASH_RECORD_IS_INITIALIZED(_h) (((struct bu_hash_record *)(_h) != BU_HASH_RECORD_NULL) && LIKELY((_h)->magic == BU_HASH_RECORD_MAGIC))
157 
158 
159 /**
160  * the hashing function
161  */
162 BU_EXPORT extern unsigned long bu_hash(const unsigned char *str,
163  int len);
164 
165 /**
166  * Create an empty hash table
167  *
168  * The input is the number of desired hash bins. This number will be
169  * rounded up to the nearest power of two.
170  */
171 BU_EXPORT extern struct bu_hash_tbl *bu_hash_tbl_create(unsigned long tbl_size);
172 
173 /**
174  * Find the hash table entry corresponding to the provided key
175  *
176  * @param[in] hsh_tbl - The hash table to look in
177  * @param[in] key - the key to look for
178  * @param[in] key_len - the length of the key in bytes
179  *
180  * Output:
181  * @param[out] prev - the previous hash table entry (non-null for entries that not the first in hash bin)
182  * @param[out] idx - the index of the hash bin for this key
183  *
184  * @return
185  * the hash table entry corresponding to the provided key, or NULL if
186  * not found.
187  */
188 BU_EXPORT extern struct bu_hash_entry *bu_hash_tbl_find(const struct bu_hash_tbl *hsh_tbl,
189  const unsigned char *key,
190  int key_len,
191  struct bu_hash_entry **prev,
192  unsigned long *idx);
193 
194 /**
195  * Set the value for a hash table entry
196  *
197  * Note that this is just a pointer copy, the hash table does not
198  * maintain its own copy of this value.
199  */
200 BU_EXPORT extern void bu_set_hash_value(struct bu_hash_entry *hsh_entry,
201  unsigned char *value);
202 
203 /**
204  * get the value pointer stored for the specified hash table entry
205  */
206 BU_EXPORT extern unsigned char *bu_get_hash_value(const struct bu_hash_entry *hsh_entry);
207 
208 /**
209  * get the key pointer stored for the specified hash table entry
210  */
211 BU_EXPORT extern unsigned char *bu_get_hash_key(const struct bu_hash_entry *hsh_entry);
212 
213 /**
214  * Add an new entry to a hash table
215  *
216  * @param[in] hsh_tbl - the hash table to accept the new entry
217  * @param[in] key - the key (any byte string)
218  * @param[in] key_len - the number of bytes in the key
219  *
220  * @param[out] new_entry - a flag, non-zero indicates that a new entry
221  * was created. zero indicates that an entry already exists with the
222  * specified key and key length
223  *
224  * @return
225  * a hash table entry. If "new" is non-zero, a new, empty entry is
226  * returned. if "new" is zero, the returned entry is the one matching
227  * the specified key and key_len.
228  */
229 BU_EXPORT extern struct bu_hash_entry *bu_hash_tbl_add(struct bu_hash_tbl *hsh_tbl,
230  const unsigned char *key,
231  int key_len,
232  int *new_entry);
233 
234 /**
235  * Print the specified hash table to stderr.
236  *
237  * (Note that the keys and values are printed as pointers)
238  */
239 BU_EXPORT extern void bu_hash_tbl_print(const struct bu_hash_tbl *hsh_tbl,
240  const char *str);
241 
242 /**
243  * Free all the memory associated with the specified hash table.
244  *
245  * Note that the keys are freed (they are copies), but the "values"
246  * are not freed. (The values are merely pointers)
247  */
248 BU_EXPORT extern void bu_hash_tbl_free(struct bu_hash_tbl *hsh_tbl);
249 
250 /**
251  * get the "first" entry in a hash table
252  *
253  * @param[in] hsh_tbl - the hash table of interest
254  * @param[in] rec - an empty "bu_hash_record" structure for use by this routine and "bu_hash_tbl_next"
255  *
256  * @return
257  * the first non-null entry in the hash table, or NULL if there are no
258  * entries (Note that the order of entries is not likely to have any
259  * significance)
260  */
261 BU_EXPORT extern struct bu_hash_entry *bu_hash_tbl_first(const struct bu_hash_tbl *hsh_tbl,
262  struct bu_hash_record *rec);
263 
264 /**
265  * get the "next" entry in a hash table
266  *
267  * input:
268  * rec - the "bu_hash_record" structure that was passed to
269  * "bu_hash_tbl_first"
270  *
271  * return:
272  * the "next" non-null hash entry in this hash table
273  */
274 BU_EXPORT extern struct bu_hash_entry *bu_hash_tbl_next(struct bu_hash_record *rec);
275 
276 /**
277  * Pass each table entry to a supplied function, along with an
278  * additional argument (which may be NULL).
279  *
280  * Returns when func returns !0 or every entry has been visited.
281  *
282  * Example, freeing all memory associated with a table whose values
283  * are dynamically allocated ints:
284  @code
285  static int
286  free_entry(struct bu_hash_entry *entry, void *UNUSED(arg))
287  {
288  bu_free(bu_get_hash_value(entry), "table value");
289  return 0;
290  }
291 
292  bu_hash_table_traverse(table, free_entry, NULL);
293  bu_hash_table_free(table);
294  @endcode
295  *
296  * @return
297  * If func returns !0 for an entry, that entry is returned.
298  * Otherwise NULL is returned.
299  */
300 BU_EXPORT extern struct bu_hash_entry *bu_hash_tbl_traverse(struct bu_hash_tbl *hsh_tbl, int (*func)(struct bu_hash_entry *, void *), void *func_arg);
301 
302 
303 /** @} */
304 
306 
307 #endif /* BU_HASH_H */
308 
309 /*
310  * Local Variables:
311  * mode: C
312  * tab-width: 8
313  * indent-tabs-mode: t
314  * c-file-style: "stroustrup"
315  * End:
316  * ex: shiftwidth=4 tabstop=8
317  */
unsigned char * bu_get_hash_value(const struct bu_hash_entry *hsh_entry)
Definition: hash.c:170
uint32_t magic
Definition: hash.h:85
void bu_hash_tbl_free(struct bu_hash_tbl *hsh_tbl)
Definition: hash.c:263
void bu_set_hash_value(struct bu_hash_entry *hsh_entry, unsigned char *value)
Definition: hash.c:160
struct bu_hash_entry * bu_hash_tbl_first(const struct bu_hash_tbl *hsh_tbl, struct bu_hash_record *rec)
Definition: hash.c:296
unsigned char * bu_get_hash_key(const struct bu_hash_entry *hsh_entry)
Definition: hash.c:179
Header file for the BRL-CAD common definitions.
unsigned char * value
Definition: hash.h:47
Definition: hash.h:44
void bu_hash_tbl_print(const struct bu_hash_tbl *hsh_tbl, const char *str)
Definition: hash.c:240
unsigned long index
Definition: hash.h:126
struct bu_hash_entry * hsh_entry
Definition: hash.h:127
unsigned long mask
Definition: hash.h:86
#define __BEGIN_DECLS
Definition: common.h:73
int key_len
Definition: hash.h:48
const struct bu_hash_tbl * tbl
Definition: hash.h:125
struct bu_hash_entry * bu_hash_tbl_add(struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, int *new_entry)
Definition: hash.c:188
unsigned long num_lists
Definition: hash.h:87
unsigned char * key
Definition: hash.h:46
struct bu_hash_entry * bu_hash_tbl_next(struct bu_hash_record *rec)
Definition: hash.c:327
unsigned long bu_hash(const unsigned char *str, int len)
Definition: hash.c:32
unsigned long num_entries
Definition: hash.h:88
#define __END_DECLS
Definition: common.h:74
struct bu_hash_tbl * bu_hash_tbl_create(unsigned long tbl_size)
Definition: hash.c:48
struct bu_hash_entry ** lists
Definition: hash.h:89
struct bu_hash_entry * bu_hash_tbl_find(const struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, struct bu_hash_entry **prev, unsigned long *idx)
Definition: hash.c:95
struct bu_hash_entry * next
Definition: hash.h:49
uint32_t magic
Definition: hash.h:45
struct bu_hash_entry * bu_hash_tbl_traverse(struct bu_hash_tbl *hsh_tbl, int(*func)(struct bu_hash_entry *, void *), void *func_arg)
Definition: hash.c:358
uint32_t magic
Definition: hash.h:124