diff options
| -rw-r--r-- | usr.bin/make/ohash/hash_do.c | 12 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_entries.c | 4 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_enum.c | 6 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_init.c | 4 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_lookup_interval.c | 8 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_lookup_memory.c | 8 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_lookup_string.c | 8 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_qlookup.c | 4 | ||||
| -rw-r--r-- | usr.bin/make/ohash/hash_qlookupi.c | 4 | ||||
| -rw-r--r-- | usr.bin/make/ohash/ohash.3 | 222 | ||||
| -rw-r--r-- | usr.bin/make/ohash/ohash.h | 44 |
11 files changed, 272 insertions, 52 deletions
diff --git a/usr.bin/make/ohash/hash_do.c b/usr.bin/make/ohash/hash_do.c index d1abe9b807d..8c9af5d6ff8 100644 --- a/usr.bin/make/ohash/hash_do.c +++ b/usr.bin/make/ohash/hash_do.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_do.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_do.c,v 1.2 2000/06/28 10:12:46 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -38,8 +38,8 @@ hash_resize(h) struct hash *h; { struct hash_record *n; - unsigned ns, j; - unsigned i, incr; + unsigned int ns, j; + unsigned int i, incr; if (4 * h->deleted < h->total) ns = h->size << 1; @@ -81,7 +81,7 @@ hash_resize(h) void * hash_remove(h, i) struct hash *h; - unsigned i; + unsigned int i; { void *result = (void *)h->t[i].p; @@ -101,7 +101,7 @@ hash_remove(h, i) void * hash_find(h, i) struct hash *h; - unsigned i; + unsigned int i; { if (h->t[i].p == DELETED) return NULL; @@ -112,7 +112,7 @@ hash_find(h, i) void * hash_insert(h, i, p) struct hash *h; - unsigned i; + unsigned int i; void *p; { #ifdef STATS_HASH diff --git a/usr.bin/make/ohash/hash_entries.c b/usr.bin/make/ohash/hash_entries.c index d8b9bcfb32d..4dfe55ad14b 100644 --- a/usr.bin/make/ohash/hash_entries.c +++ b/usr.bin/make/ohash/hash_entries.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_entries.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_entries.c,v 1.2 2000/06/28 10:12:46 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -31,7 +31,7 @@ #include "ohash_int.h" -unsigned +unsigned int hash_entries(h) struct hash *h; { diff --git a/usr.bin/make/ohash/hash_enum.c b/usr.bin/make/ohash/hash_enum.c index 57daaa0eb65..b370f404f10 100644 --- a/usr.bin/make/ohash/hash_enum.c +++ b/usr.bin/make/ohash/hash_enum.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_enum.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_enum.c,v 1.2 2000/06/28 10:12:47 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -34,7 +34,7 @@ void * hash_first(h, pos) struct hash *h; - unsigned *pos; + unsigned int *pos; { *pos = 0; return hash_next(h, pos); @@ -43,7 +43,7 @@ hash_first(h, pos) void * hash_next(h, pos) struct hash *h; - unsigned *pos; + unsigned int *pos; { for (; *pos < h->size; (*pos)++) if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) diff --git a/usr.bin/make/ohash/hash_init.c b/usr.bin/make/ohash/hash_init.c index 35d1af354c3..54096692d92 100644 --- a/usr.bin/make/ohash/hash_init.c +++ b/usr.bin/make/ohash/hash_init.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_init.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_init.c,v 1.2 2000/06/28 10:12:47 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -35,7 +35,7 @@ void hash_init(h, size, info) struct hash *h; - unsigned size; + unsigned int size; struct hash_info*info; { h->size = 1UL << size; diff --git a/usr.bin/make/ohash/hash_lookup_interval.c b/usr.bin/make/ohash/hash_lookup_interval.c index a68ffd628c3..dcf94022b8e 100644 --- a/usr.bin/make/ohash/hash_lookup_interval.c +++ b/usr.bin/make/ohash/hash_lookup_interval.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_lookup_interval.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_lookup_interval.c,v 1.2 2000/06/28 10:12:47 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -31,15 +31,15 @@ #include "ohash_int.h" -unsigned +unsigned int hash_lookup_interval(h, start, end, hv) struct hash *h; const char *start; const char *end; u_int32_t hv; { - unsigned i, incr; - unsigned empty; + unsigned int i, incr; + unsigned int empty; #ifdef STATS_HASH STAT_HASH_LOOKUP++; diff --git a/usr.bin/make/ohash/hash_lookup_memory.c b/usr.bin/make/ohash/hash_lookup_memory.c index 80750e39ac0..e4c6755de21 100644 --- a/usr.bin/make/ohash/hash_lookup_memory.c +++ b/usr.bin/make/ohash/hash_lookup_memory.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_lookup_memory.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_lookup_memory.c,v 1.2 2000/06/28 10:12:48 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -31,15 +31,15 @@ #include "ohash_int.h" -unsigned +unsigned int hash_lookup_memory(h, k, size, hv) struct hash *h; const char *k; size_t size; u_int32_t hv; { - unsigned i, incr; - unsigned empty; + unsigned int i, incr; + unsigned int empty; #ifdef STATS_HASH STAT_HASH_LOOKUP++; diff --git a/usr.bin/make/ohash/hash_lookup_string.c b/usr.bin/make/ohash/hash_lookup_string.c index f9efcac57b0..3cd115ed3ed 100644 --- a/usr.bin/make/ohash/hash_lookup_string.c +++ b/usr.bin/make/ohash/hash_lookup_string.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_lookup_string.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_lookup_string.c,v 1.2 2000/06/28 10:12:48 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -31,14 +31,14 @@ #include "ohash_int.h" -unsigned +unsigned int hash_lookup_string(h, k, hv) struct hash *h; const char *k; u_int32_t hv; { - unsigned i, incr; - unsigned empty; + unsigned int i, incr; + unsigned int empty; #ifdef STATS_HASH STAT_HASH_LOOKUP++; diff --git a/usr.bin/make/ohash/hash_qlookup.c b/usr.bin/make/ohash/hash_qlookup.c index 0f7ff8f49d0..3d38189b845 100644 --- a/usr.bin/make/ohash/hash_qlookup.c +++ b/usr.bin/make/ohash/hash_qlookup.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_qlookup.c,v 1.1 2000/06/23 16:24:50 espie Exp $ */ +/* $OpenBSD: hash_qlookup.c,v 1.2 2000/06/28 10:12:48 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -31,7 +31,7 @@ #include "ohash_int.h" -unsigned +unsigned int hash_qlookup(h, s) struct hash *h; const char *s; diff --git a/usr.bin/make/ohash/hash_qlookupi.c b/usr.bin/make/ohash/hash_qlookupi.c index 4e1985b4f8f..74b48cedc0d 100644 --- a/usr.bin/make/ohash/hash_qlookupi.c +++ b/usr.bin/make/ohash/hash_qlookupi.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hash_qlookupi.c,v 1.1 2000/06/23 16:24:51 espie Exp $ */ +/* $OpenBSD: hash_qlookupi.c,v 1.2 2000/06/28 10:12:48 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -31,7 +31,7 @@ #include "ohash_int.h" -unsigned +unsigned int hash_qlookupi(h, s, e) struct hash *h; const char *s; diff --git a/usr.bin/make/ohash/ohash.3 b/usr.bin/make/ohash/ohash.3 new file mode 100644 index 00000000000..138c11285e2 --- /dev/null +++ b/usr.bin/make/ohash/ohash.3 @@ -0,0 +1,222 @@ +.Dd November 3, 1999 +.Dt OPEN_HASH 3 +.Os +.Sh NAME +.Nm hash_init , +.Nm hash_delete , +.Nm hash_lookup_string , +.Nm hash_lookup_interval , +.Nm hash_lookup_memory , +.Nm hash_find , +.Nm hash_remove , +.Nm hash_insert , +.Nm hash_first , +.Nm hash_next , +.Nm hash_entries +.Nd light-weight open hashing +.Sh SYNOPSIS +.Fd #include <sys/types.h> +.Fd #include <stddef.h> +.Fd #include <ohash.h> +.Ft void +.Fn hash_init "struct hash *h" "unsigned int size" "struct hash_info *info" +.Ft void +.Fn hash_delete "struct hash *h" +.Ft "unsigned int" +.Fn hash_lookup_string "struct hash *h" "const char *k" "u_int32_t v" +.Ft "unsigned int" +.Fn hash_lookup_interval "struct hash *h" "const char *start" "const char *end" "u_int32_t hv" +.Ft "unsigned int" +.Fn hash_lookup_memory "struct hash *h" "const char *k" "size_t s" "u_int32_t hv" +.Ft void * +.Fn hash_find "struct hash *h" "unsigned int i" +.Ft void * +.Fn hash_remove "struct hash *h" "unsigned int i" +.Ft void * +.Fn hash_insert "struct hash *h" "unsigned int i" "void *p" +.Ft void * +.Fn hash_first "struct hash *h" "unsigned int *i" +.Ft void * +.Fn hash_next "struct hash *h" "unsigned int *i" +.Ft "unsigned int" +.Fn hash_entries "struct hash *h" +.Sh DESCRIPTION +Those functions have been designed as a fast, extensible alternative to +the usual hash table functions. +These provide storing and retrieval of records indexed by keys, +where a key is a contiguous sequence of bytes at a fixed position in +each record. +Keys can either be null-terminated strings, or fixed-size memory areas. +All functions take a pointer to a hash structure as the +.Fa h +function argument. +Storage for this structure should be provided by user code. +.Pp +.Fn hash_init +initializes the table to store roughly 2 to the power +.Fa size +elements. +.Fa info +holds the position of the key in each record, and two pointers to +.Xr calloc 3 +and +.Xr free 3 +-like functions, to use for managing the table internal storage. +.Pp +.Fn hash_delete +frees storage internal to +.Fa h . +Elements themselves should be freed by the user first, using for instance +.Fn hash_first +and +.Fn hash_next . +.Pp +.Fn hash_lookup_string , +.Fn hash_lookup_interval +and +.Fn hash_lookup_memory +are the basic look-up element functions. +The hashing function result is provided by the user as +.Fa hv . +These return a +.Qq slot +in the hash table +.Fa h , +to be used with +.Fn hash_find , +.Fn hash_insert , +or +.Fn hash_remove . +This slot is only valid up to the next call to +.Fn hash_insert +or +.Fn hash_remove . +.Pp +.Fn hash_lookup_string +and +.Fn hash_lookup_interval +handle string-like keys. +.Fn hash_lookup_string +assumes a null-terminated +.Ft char * +.Fa k , +whereas +.Fn hash_lookup_interval +assumes the key is the interval between +.Fa start +and +.Fa end , +exclusive. +In both cases, the actual elements stored in the hash should contain +null-terminated keys. +.Pp +.Fn hash_lookup_memory +assumes the key is the memory area starting at +.Fa k +of size +.Fa s . +All bytes are significant in key comparison. +.Pp +.Fn hash_find +retrieves an element from a slot +.Fa i +returned by the +.Fn hash_lookup* +functions. +It returns +.Va NULL +if the slot is empty. +.Pp +.Fn hash_insert +inserts a new element +.Fa p +at slot +.Fa i . +Slot +.Fa i +must be empty and element +.Fa p +must have a key corresponding to the +.Fn hash_lookup* +call. +.Pp +.Fn hash_remove +removes element of hash table at slot +.Fa i . +It returns the removed element, for user code to dispose of, or +.Va NULL +if the slot was empty. +.Pp +.Fn hash_first +and +.Fn hash_next +can be used to access all elements in a hash table, like this: +.Pp +.Bd -literal + for (n = hash_first(h, &i); n != NULL; n = hash_next(h, &i)) + do_something_with(n); +.Ed +.Pp +.Fa i +points to an auxiliary unsigned integer used to record the current position +in the hash table. +Those functions are safe to use even while entries are added to/removed +from the table, but in such a case they don't guarantee that new entries +will be returned. +As a special case, they can safely be used to free elements in the table. +.Pp +.Fn hash_entries +returns the number of elements in the hash table. +.Sh STORAGE HANDLING +Only +.Fn hash_init , +.Fn hash_insert , +.Fn hash_remove +and +.Fn hash_delete +may call the user-supplied memory functions. +It is the responsability of the user memory allocation code to verify +that those calls did not fail. +.Pp +In case memory allocation fails, +.Fn hash_init +returns a useless hash table. +.Fn hash_insert +and +.Fn hash_remove +still perform the requested operation, but the returned table should be +considered read-only. +It can still be accessed by +.Fn hash_lookup* , +.Fn hash_find , +.Fn hash_first +and +.Fn hash_next +to dump relevant information to disk before aborting. +.Sh THREAD SAFETY +The open hashing functions are not thread-safe by design. +In particular, it cannot be guaranteed that a +.Qq slot +will not move in a threaded environment between a +.Fn hash_lookup* +and a +.Fn hash_find , +.Fn hash_insert +or +.Fn hash_remove +call. +.Pp +Multi-threaded applications should explicitly protect hash table access. +.Sh SEE ALSO +.Rs +.%A Donald E. Knuth +.%B The Art of Computer Programming +.%V Vol. 3 +.%P pp 506-550 +.%D 1973 +.Re +.Sh HISTORY +Those functions were designed and written for +.Ox +make +by Marc Espie in 1999. diff --git a/usr.bin/make/ohash/ohash.h b/usr.bin/make/ohash/ohash.h index 73ca0039301..58c0c5914fa 100644 --- a/usr.bin/make/ohash/ohash.h +++ b/usr.bin/make/ohash/ohash.h @@ -1,6 +1,6 @@ #ifndef OHASH_H #define OHASH_H -/* $OpenBSD: ohash.h,v 1.1 2000/06/23 16:24:51 espie Exp $ */ +/* $OpenBSD: ohash.h,v 1.2 2000/06/28 10:12:49 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -45,46 +45,44 @@ struct hash_info { }; struct hash { - struct hash_record *t; - struct hash_info info; - unsigned size; - unsigned total; - unsigned deleted; + struct hash_record *t; + struct hash_info info; + unsigned int size; + unsigned int total; + unsigned int deleted; }; struct hash_record { - unsigned hv; - const char *p; + u_int32_t hv; + const char *p; }; -#define hash_to_info(h) (&(h)->info) - /* For this to be tweakable, we use small primitives, and leave part of the * logic to the client application. e.g., hashing is left to the client * application. We also provide a simple table entry lookup that yields * a hashing table index (opaque) to be used in find/insert/remove. * The keys are stored at a known position in the client data. */ +__BEGIN_DECLS void hash_init __P((struct hash *, unsigned, struct hash_info *)); void hash_delete __P((struct hash *)); -unsigned hash_lookup_string __P((struct hash *, const char *, u_int32_t)); -unsigned hash_lookup_interval __P((struct hash *, const char *, \ +unsigned int hash_lookup_string __P((struct hash *, const char *, u_int32_t)); +unsigned int hash_lookup_interval __P((struct hash *, const char *, \ const char *, u_int32_t)); -unsigned hash_lookup_memory __P((struct hash *, const char *, \ +unsigned int hash_lookup_memory __P((struct hash *, const char *, \ size_t, u_int32_t)); -void *hash_find __P((struct hash *, unsigned)); -void *hash_remove __P((struct hash *, unsigned)); -void *hash_insert __P((struct hash *, unsigned, void *)); -void *hash_first __P((struct hash *, unsigned *)); -void *hash_next __P((struct hash *, unsigned *)); -unsigned hash_entries __P((struct hash *)); +void *hash_find __P((struct hash *, unsigned int)); +void *hash_remove __P((struct hash *, unsigned int)); +void *hash_insert __P((struct hash *, unsigned int, void *)); +void *hash_first __P((struct hash *, unsigned int *)); +void *hash_next __P((struct hash *, unsigned int *)); +unsigned int hash_entries __P((struct hash *)); void *hash_create_entry __P((struct hash_info *, const char *, const char **)); u_int32_t hash_interval __P((const char *, const char **)); -unsigned hash_qlookupi __P((struct hash *, const char *, const char **)); -unsigned hash_qlookup __P((struct hash *, const char *)); - +unsigned int hash_qlookupi __P((struct hash *, const char *, const char **)); +unsigned int hash_qlookup __P((struct hash *, const char *)); +__END_DECLS #endif - |