| 1 |
#ifndef OHASH_H |
| 2 |
#define OHASH_H |
| 3 |
/* $MidnightBSD: src/include/ohash.h,v 1.1 2007/03/24 07:56:45 archite Exp $ */ |
| 4 |
/* $OpenBSD: ohash.h,v 1.7 2004/06/22 20:00:16 espie Exp $ */ |
| 5 |
/* ex:ts=8 sw=4: |
| 6 |
*/ |
| 7 |
|
| 8 |
/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org> |
| 9 |
* |
| 10 |
* Permission to use, copy, modify, and distribute this software for any |
| 11 |
* purpose with or without fee is hereby granted, provided that the above |
| 12 |
* copyright notice and this permission notice appear in all copies. |
| 13 |
* |
| 14 |
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| 15 |
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| 16 |
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR |
| 17 |
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| 18 |
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN |
| 19 |
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF |
| 20 |
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| 21 |
*/ |
| 22 |
|
| 23 |
/* Open hashing support. |
| 24 |
* Open hashing was chosen because it is much lighter than other hash |
| 25 |
* techniques, and more efficient in most cases. |
| 26 |
*/ |
| 27 |
|
| 28 |
struct ohash_info { |
| 29 |
ptrdiff_t key_offset; |
| 30 |
void *data; /* user data */ |
| 31 |
void *(*halloc)(size_t, void *); |
| 32 |
void (*hfree)(void *, size_t, void *); |
| 33 |
void *(*alloc)(size_t, void *); |
| 34 |
}; |
| 35 |
|
| 36 |
struct _ohash_record; |
| 37 |
|
| 38 |
struct ohash { |
| 39 |
struct _ohash_record *t; |
| 40 |
struct ohash_info info; |
| 41 |
unsigned int size; |
| 42 |
unsigned int total; |
| 43 |
unsigned int deleted; |
| 44 |
}; |
| 45 |
|
| 46 |
/* For this to be tweakable, we use small primitives, and leave part of the |
| 47 |
* logic to the client application. e.g., hashing is left to the client |
| 48 |
* application. We also provide a simple table entry lookup that yields |
| 49 |
* a hashing table index (opaque) to be used in find/insert/remove. |
| 50 |
* The keys are stored at a known position in the client data. |
| 51 |
*/ |
| 52 |
__BEGIN_DECLS |
| 53 |
void ohash_init(struct ohash *, unsigned, struct ohash_info *); |
| 54 |
void ohash_delete(struct ohash *); |
| 55 |
|
| 56 |
unsigned int ohash_lookup_string(struct ohash *, const char *, uint32_t); |
| 57 |
unsigned int ohash_lookup_interval(struct ohash *, const char *, |
| 58 |
const char *, uint32_t); |
| 59 |
unsigned int ohash_lookup_memory(struct ohash *, const char *, |
| 60 |
size_t, uint32_t) |
| 61 |
__attribute__ ((__bounded__(__string__,2,3))); |
| 62 |
void *ohash_find(struct ohash *, unsigned int); |
| 63 |
void *ohash_remove(struct ohash *, unsigned int); |
| 64 |
void *ohash_insert(struct ohash *, unsigned int, void *); |
| 65 |
void *ohash_first(struct ohash *, unsigned int *); |
| 66 |
void *ohash_next(struct ohash *, unsigned int *); |
| 67 |
unsigned int ohash_entries(struct ohash *); |
| 68 |
|
| 69 |
void *ohash_create_entry(struct ohash_info *, const char *, const char **); |
| 70 |
uint32_t ohash_interval(const char *, const char **); |
| 71 |
|
| 72 |
unsigned int ohash_qlookupi(struct ohash *, const char *, const char **); |
| 73 |
unsigned int ohash_qlookup(struct ohash *, const char *); |
| 74 |
__END_DECLS |
| 75 |
#endif |
