diff options
| -rw-r--r-- | include/Makefile | 5 | ||||
| -rw-r--r-- | include/ohash.h | 85 | ||||
| -rw-r--r-- | lib/libc/Makefile.inc | 3 | ||||
| -rw-r--r-- | lib/libc/ohash/Makefile.inc | 25 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_create_entry.c | 53 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_delete.c | 45 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_do.c | 132 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_entries.c | 40 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_enum.c | 52 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_init.3 | 242 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_init.c | 58 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_int.h | 20 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_interval.3 | 98 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_interval.c | 50 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_lookup_interval.c | 84 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_lookup_memory.c | 81 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_qlookup.c | 42 | ||||
| -rw-r--r-- | lib/libc/ohash/ohash_qlookupi.c | 44 | ||||
| -rw-r--r-- | lib/libc/shlib_version | 2 |
19 files changed, 1157 insertions, 4 deletions
diff --git a/include/Makefile b/include/Makefile index 87257d02f9d..f3142a26573 100644 --- a/include/Makefile +++ b/include/Makefile @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile,v 1.88 2000/12/18 16:51:49 brad Exp $ +# $OpenBSD: Makefile,v 1.89 2001/03/02 13:27:04 espie Exp $ # $NetBSD: Makefile,v 1.59 1996/05/15 21:36:43 jtc Exp $ # @(#)Makefile 5.45.1.1 (Berkeley) 5/6/91 @@ -13,7 +13,8 @@ FILES= a.out.h ar.h assert.h bitstring.h blf.h bm.h bsd_auth.h cast.h cpio.h \ fnmatch.h fstab.h fts.h glob.h grp.h ifaddrs.h inttypes.h \ iso646.h kvm.h langinfo.h libgen.h limits.h locale.h login_cap.h \ malloc.h math.h md4.h md5.h memory.h mpool.h ndbm.h netdb.h netgroup.h \ - nlist.h nl_types.h olf_abi.h paths.h poll.h pwd.h ranlib.h re_comp.h \ + nlist.h nl_types.h ohash.h olf_abi.h paths.h poll.h pwd.h \ + ranlib.h re_comp.h \ readpassphrase.h regex.h resolv.h rmd160.h search.h setjmp.h sgtty.h \ sha1.h skipjack.h signal.h stab.h stdbool.h stddef.h stdio.h stdlib.h \ string.h strings.h struct.h sysexits.h tar.h time.h ttyent.h tzfile.h \ diff --git a/include/ohash.h b/include/ohash.h new file mode 100644 index 00000000000..2c6f3aed034 --- /dev/null +++ b/include/ohash.h @@ -0,0 +1,85 @@ +#ifndef OHASH_H +#define OHASH_H +/* $OpenBSD: ohash.h,v 1.1 2001/03/02 13:27:05 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* Open hashing support. + * Open hashing was chosen because it is much lighter than other hash + * techniques, and more efficient in most cases. + */ + +struct ohash_info { + ptrdiff_t key_offset; + void *data; /* user data */ + void *(*halloc) __P((size_t, void *)); + void (*hfree) __P((void *, size_t, void *)); + void *(*alloc) __P((size_t, void *)); +}; + +struct _ohash_record; + +struct ohash { + struct _ohash_record *t; + struct ohash_info info; + unsigned int size; + unsigned int total; + unsigned int deleted; +}; + +/* 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 ohash_init __P((struct ohash *, unsigned, struct ohash_info *)); +void ohash_delete __P((struct ohash *)); + +unsigned int ohash_lookup_string __P((struct ohash *, const char *, u_int32_t)); +unsigned int ohash_lookup_interval __P((struct ohash *, const char *, \ + const char *, u_int32_t)); +unsigned int ohash_lookup_memory __P((struct ohash *, const char *, \ + size_t, u_int32_t)); +void *ohash_find __P((struct ohash *, unsigned int)); +void *ohash_remove __P((struct ohash *, unsigned int)); +void *ohash_insert __P((struct ohash *, unsigned int, void *)); +void *ohash_first __P((struct ohash *, unsigned int *)); +void *ohash_next __P((struct ohash *, unsigned int *)); +unsigned int ohash_entries __P((struct ohash *)); + +void *ohash_create_entry __P((struct ohash_info *, const char *, const char **)); +u_int32_t ohash_interval __P((const char *, const char **)); + +unsigned int ohash_qlookupi __P((struct ohash *, const char *, const char **)); +unsigned int ohash_qlookup __P((struct ohash *, const char *)); +__END_DECLS +#endif diff --git a/lib/libc/Makefile.inc b/lib/libc/Makefile.inc index 72ecb7fa6d1..c9f6ddef254 100644 --- a/lib/libc/Makefile.inc +++ b/lib/libc/Makefile.inc @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile.inc,v 1.3 2000/09/03 18:41:13 espie Exp $ +# $OpenBSD: Makefile.inc,v 1.4 2001/03/02 13:27:05 espie Exp $ # # This file contains make rules that are shared by libc and libc_r. # @@ -35,6 +35,7 @@ AINC+= -nostdinc -idirafter ${DESTDIR}/usr/include .include "${LIBCSRCDIR}/md/Makefile.inc" .include "${LIBCSRCDIR}/net/Makefile.inc" .include "${LIBCSRCDIR}/nls/Makefile.inc" +.include "${LIBCSRCDIR}/ohash/Makefile.inc" .if (${MACHINE_ARCH} != "alpha") .include "${LIBCSRCDIR}/quad/Makefile.inc" .endif diff --git a/lib/libc/ohash/Makefile.inc b/lib/libc/ohash/Makefile.inc new file mode 100644 index 00000000000..91babfa3671 --- /dev/null +++ b/lib/libc/ohash/Makefile.inc @@ -0,0 +1,25 @@ +# $OpenBSD: Makefile.inc,v 1.1 2001/03/02 13:27:06 espie Exp $ + + +# open hashing functions +.PATH: ${LIBCSRCDIR}/ohash + +SRCS+= ohash_create_entry.c ohash_delete.c ohash_do.c ohash_entries.c \ + ohash_enum.c ohash_init.c ohash_interval.c \ + ohash_lookup_interval.c ohash_lookup_memory.c \ + ohash_qlookup.c ohash_qlookupi.c + +MAN+= ohash_init.3 ohash_interval.3 +MLINKS+=ohash_init.3 ohash_delete.3 \ + ohash_init.3 ohash_lookup_string.3 \ + ohash_init.3 ohash_lookup_interval.3 \ + ohash_init.3 ohash_lookup_memory.3 \ + ohash_init.3 ohash_find.3 \ + ohash_init.3 ohash_remove.3 \ + ohash_init.3 ohash_insert.3 \ + ohash_init.3 ohash_first.3 \ + ohash_init.3 ohash_next.3 \ + ohash_init.3 ohash_entries.3 \ + ohash_interval.3 ohash_create_entry.3 \ + ohash_interval.3 ohash_qlookupi.3 \ + ohash_interval.3 ohash_qlookup.3 diff --git a/lib/libc/ohash/ohash_create_entry.c b/lib/libc/ohash/ohash_create_entry.c new file mode 100644 index 00000000000..6f8d1a01077 --- /dev/null +++ b/lib/libc/ohash/ohash_create_entry.c @@ -0,0 +1,53 @@ +/* $OpenBSD: ohash_create_entry.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +/* This handles the common case of variable length keys, where the + * key is stored at the end of the record. + */ +void * +ohash_create_entry(i, start, end) + struct ohash_info *i; + const char *start; + const char **end; +{ + char *p; + + if (!*end) + *end = start + strlen(start); + p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data); + if (p) { + memcpy(p+i->key_offset, start, *end-start); + p[i->key_offset + (*end - start)] = '\0'; + } + return (void *)p; +} diff --git a/lib/libc/ohash/ohash_delete.c b/lib/libc/ohash/ohash_delete.c new file mode 100644 index 00000000000..55067558861 --- /dev/null +++ b/lib/libc/ohash/ohash_delete.c @@ -0,0 +1,45 @@ +/* $OpenBSD: ohash_delete.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" +/* hash_delete only frees the hash structure. Use hash_first/hash_next + * to free entries as well. */ +void +ohash_delete(h) + struct ohash *h; +{ + (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size, + h->info.data); +#ifndef NDEBUG + h->t = NULL; +#endif +} + diff --git a/lib/libc/ohash/ohash_do.c b/lib/libc/ohash/ohash_do.c new file mode 100644 index 00000000000..c5fc551d763 --- /dev/null +++ b/lib/libc/ohash/ohash_do.c @@ -0,0 +1,132 @@ +/* $OpenBSD: ohash_do.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +static void ohash_resize __P((struct ohash *)); + +static void +ohash_resize(h) + struct ohash *h; +{ + struct _ohash_record *n; + unsigned int ns, j; + unsigned int i, incr; + + if (4 * h->deleted < h->total) + ns = h->size << 1; + else if (3 * h->deleted > 2 * h->total) + ns = h->size >> 1; + else + ns = h->size; + if (ns < MINSIZE) + ns = MINSIZE; +#ifdef STATS_HASH + STAT_HASH_EXPAND++; + STAT_HASH_SIZE += ns - h->size; +#endif + n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data); + if (!n) + return; + + for (j = 0; j < h->size; j++) { + if (h->t[j].p != NULL && h->t[j].p != DELETED) { + i = h->t[j].hv % ns; + incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; + while (n[i].p != NULL) { + i += incr; + if (i >= ns) + i -= ns; + } + n[i].hv = h->t[j].hv; + n[i].p = h->t[j].p; + } + } + (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size, + h->info.data); + h->t = n; + h->size = ns; + h->total -= h->deleted; + h->deleted = 0; +} + +void * +ohash_remove(h, i) + struct ohash *h; + unsigned int i; +{ + void *result = (void *)h->t[i].p; + + if (result == NULL || result == DELETED) + return NULL; + +#ifdef STATS_HASH + STAT_HASH_ENTRIES--; +#endif + h->t[i].p = DELETED; + h->deleted++; + if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) + hash_resize(h); + return result; +} + +void * +ohash_find(h, i) + struct ohash *h; + unsigned int i; +{ + if (h->t[i].p == DELETED) + return NULL; + else + return (void *)h->t[i].p; +} + +void * +ohash_insert(h, i, p) + struct ohash *h; + unsigned int i; + void *p; +{ +#ifdef STATS_HASH + STAT_HASH_ENTRIES++; +#endif + if (h->t[i].p == DELETED) { + h->deleted--; + h->t[i].p = p; + } else { + h->t[i].p = p; + /* Arbitrary resize boundary. Tweak if not efficient enough. */ + if (++h->total * 4 > h->size * 3) + hash_resize(h); + } + return p; +} + diff --git a/lib/libc/ohash/ohash_entries.c b/lib/libc/ohash/ohash_entries.c new file mode 100644 index 00000000000..9668eb4282d --- /dev/null +++ b/lib/libc/ohash/ohash_entries.c @@ -0,0 +1,40 @@ +/* $OpenBSD: ohash_entries.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +unsigned int +ohash_entries(h) + struct ohash *h; +{ + return h->total - h->deleted; +} + diff --git a/lib/libc/ohash/ohash_enum.c b/lib/libc/ohash/ohash_enum.c new file mode 100644 index 00000000000..6c43e5e0263 --- /dev/null +++ b/lib/libc/ohash/ohash_enum.c @@ -0,0 +1,52 @@ +/* $OpenBSD: ohash_enum.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +void * +ohash_first(h, pos) + struct ohash *h; + unsigned int *pos; +{ + *pos = 0; + return ohash_next(h, pos); +} + +void * +hash_next(h, pos) + struct ohash *h; + unsigned int *pos; +{ + for (; *pos < h->size; (*pos)++) + if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) + return (void *)h->t[(*pos)++].p; + return NULL; +} diff --git a/lib/libc/ohash/ohash_init.3 b/lib/libc/ohash/ohash_init.3 new file mode 100644 index 00000000000..204d4519004 --- /dev/null +++ b/lib/libc/ohash/ohash_init.3 @@ -0,0 +1,242 @@ +.\" $OpenBSD: ohash_init.3,v 1.1 2001/03/02 13:27:07 espie Exp $ +.\" +.\" Copyright (c) 1999 Marc Espie. +.\" +.\" Code written for the OpenBSD project. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS +.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +.\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD +.\" PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +.\" LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +.\" OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +.\" +.Dd November 3, 1999 +.Dt OPEN_HASH 3 +.Os +.Sh NAME +.Nm ohash_init , +.Nm ohash_delete , +.Nm ohash_lookup_interval , +.Nm ohash_lookup_memory , +.Nm ohash_find , +.Nm ohash_remove , +.Nm ohash_insert , +.Nm ohash_first , +.Nm ohash_next , +.Nm ohash_entries +.Nd light-weight open hashing +.Sh SYNOPSIS +.Fd #include <sys/types.h> +.Fd #include <stddef.h> +.Fd #include <ohash.h> +.Ft void +.Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info" +.Ft void +.Fn ohash_delete "struct oohash *h" +.Ft "unsigned int" +.Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "u_int32_t hv" +.Ft "unsigned int" +.Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "u_int32_t hv" +.Ft void * +.Fn ohash_find "struct ohash *h" "unsigned int i" +.Ft void * +.Fn ohash_remove "struct ohash *h" "unsigned int i" +.Ft void * +.Fn ohash_insert "struct ohash *h" "unsigned int i" "void *p" +.Ft void * +.Fn ohash_first "struct ohash *h" "unsigned int *i" +.Ft void * +.Fn ohash_next "struct ohash *h" "unsigned int *i" +.Ft "unsigned int" +.Fn ohash_entries "struct ohash *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 ohash structure as the +.Fa h +function argument. +Storage for this structure should be provided by user code. +.Pp +.Fn ohash_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 ohash_delete +frees storage internal to +.Fa h . +Elements themselves should be freed by the user first, using for instance +.Fn ohash_first +and +.Fn ohash_next . +.Pp +.Fn ohash_lookup_interval +and +.Fn ohash_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 ohash table +.Fa h , +to be used with +.Fn ohash_find , +.Fn ohash_insert , +or +.Fn ohash_remove . +This slot is only valid up to the next call to +.Fn ohash_insert +or +.Fn ohash_remove . +.Pp +.Fn ohash_lookup_interval +handles string-like keys. +.Fn ohash_lookup_interval +assumes the key is the interval between +.Fa start +and +.Fa end , +exclusive, +though the actual elements stored in the ohash should contain +null-terminated keys. +.Pp +.Fn ohash_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 ohash_find +retrieves an element from a slot +.Fa i +returned by the +.Fn ohash_lookup* +functions. +It returns +.Va NULL +if the slot is empty. +.Pp +.Fn ohash_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 ohash_lookup* +call. +.Pp +.Fn ohash_remove +removes element of ohash 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 ohash_first +and +.Fn ohash_next +can be used to access all elements in a ohash table, like this: +.Pp +.Bd -literal + for (n = ohash_first(h, &i); n != NULL; n = ohash_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 ohash 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 ohash_entries +returns the number of elements in the ohash table. +.Sh STORAGE HANDLING +Only +.Fn ohash_init , +.Fn ohash_insert , +.Fn ohash_remove +and +.Fn ohash_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 ohash_init +returns a useless ohash table. +.Fn ohash_insert +and +.Fn ohash_remove +still perform the requested operation, but the returned table should be +considered read-only. +It can still be accessed by +.Fn ohash_lookup* , +.Fn ohash_find , +.Fn ohash_first +and +.Fn ohash_next +to dump relevant information to disk before aborting. +.Sh THREAD SAFETY +The open ohashing 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 ohash_lookup* +and a +.Fn ohash_find , +.Fn ohash_insert +or +.Fn ohash_remove +call. +.Pp +Multi-threaded applications should explicitly protect ohash 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 +.Xr ohash_interval 3 +.Sh STANDARDS +Those functions are completely non-standard and should be avoided in +portable programs. +.Sh HISTORY +Those functions were designed and written for +.Ox +make +by Marc Espie in 1999. diff --git a/lib/libc/ohash/ohash_init.c b/lib/libc/ohash/ohash_init.c new file mode 100644 index 00000000000..b563525e97f --- /dev/null +++ b/lib/libc/ohash/ohash_init.c @@ -0,0 +1,58 @@ +/* $OpenBSD: ohash_init.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + + +#include "ohash_int.h" + +void +ohash_init(h, size, info) + struct ohash *h; + unsigned int size; + struct ohash_info*info; +{ + h->size = 1UL << size; + if (h->size < MINSIZE) + h->size = MINSIZE; +#ifdef STATS_HASH + STAT_HASH_CREATION++; + STAT_HASH_SIZE += h->size; +#endif + /* Copy info so that caller may free it. */ + h->info.key_offset = info->key_offset; + h->info.halloc = info->halloc; + h->info.hfree = info->hfree; + h->info.alloc = info->alloc; + h->info.data = info->data; + h->t = (h->info.halloc)(sizeof(struct _ohash_record) * h->size, + h->info.data); + h->total = h->deleted = 0; +} + diff --git a/lib/libc/ohash/ohash_int.h b/lib/libc/ohash/ohash_int.h new file mode 100644 index 00000000000..5984e024bb6 --- /dev/null +++ b/lib/libc/ohash/ohash_int.h @@ -0,0 +1,20 @@ +/* $OpenBSD: ohash_int.h,v 1.1 2001/03/02 13:27:07 espie Exp $ */ + +#include <sys/types.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> +#include "ohash.h" + +struct _ohash_record { + u_int32_t hv; + const char *p; +}; + +#define DELETED ((const char *)h) +#define NONE (h->size) + +/* Don't bother changing the hash table if the change is small enough. */ +#define MINSIZE (1UL << 4) +#define MINDELETED 4 + diff --git a/lib/libc/ohash/ohash_interval.3 b/lib/libc/ohash/ohash_interval.3 new file mode 100644 index 00000000000..97de05de98b --- /dev/null +++ b/lib/libc/ohash/ohash_interval.3 @@ -0,0 +1,98 @@ +.\" $OpenBSD: ohash_interval.3,v 1.1 2001/03/02 13:27:07 espie Exp $ +.\" +.\" Copyright (c) 2001 Marc Espie. +.\" +.\" Code written for the OpenBSD project. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS +.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +.\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD +.\" PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +.\" LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +.\" OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +.\" +.Dd February 23, 2001 +.Dt OPEN_HASH_HELPER 3 +.Nm ohash_interval , +.Nm ohash_create_entry , +.Nm ohash_qlookup , +.Nm ohash_qlookupi +.Nm helper functions for open hashing +.Sh SYNOPSIS +.Fd #include <sys/types.h> +.Fd #include <stddef.h> +.Fd #include <ohash.h> +.Ft u_int32_t +.Fn ohash_interval "const char *start" "const char **pend" +.Ft "void *" +.Fn ohash_create_entry "struct ohash_info *info" "const char *start" "const char **pend" +.Ft "unsigned int" +.Fn ohash_qlookupi "struct ohash *h" "const char *start" "const char **pend" +.Ft "unsigned int" +.Fn ohash_qlookup "struct ohash *h" "const char *start" +.Sh DESCRIPTION +These functions are commonly used to simplify open hashing usage, and use +similar conventions. They operate indifferently on null-terminated strings +.Po +by setting +.Fa *pend += +.Dv NULL +.Pc +or memory ranges +.Po +deliminated by +.Fa start +and +.Fa *pend +.Pc . +For null-terminated strings, as a side effect, those functions +set +.Fa *pend +to the terminating null byte. +.Pp +.Fn ohash_interval +is a simple hashing function that yields good results on many data sets. +.Pp +.Fn ohash_create_entry +can be used to create a new record with a given key. In that case, +the alloc field of +.Fa info +should point to a +.Xr malloc 3 +-like function to allocate the storage. +.Pp +.Fn ohash_qlookupi +is a wrapper function that simply calls +.Fn ohash_interval +and +.Fn ohash_lookup_interval . +.Pp +.Fn ohash_qlookup +is a variation on +.Fn ohash_qlookupi +designed for null-terminated strings. +.Sh SEE ALSO +.Xr ohash_init 3 +.Sh STANDARDS +Those functions are completely non-standard and should be avoided in +portable programs. +.Sh HISTORY +Those functions were designed and written for +.Ox +make +by Marc Espie in 1999. diff --git a/lib/libc/ohash/ohash_interval.c b/lib/libc/ohash/ohash_interval.c new file mode 100644 index 00000000000..1c907f576a6 --- /dev/null +++ b/lib/libc/ohash/ohash_interval.c @@ -0,0 +1,50 @@ +/* $OpenBSD: ohash_interval.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +u_int32_t +ohash_interval(s, e) + const char *s; + const char **e; +{ + u_int32_t k; + + if (!*e) + *e = s + strlen(s); + if (s == *e) + k = 0; + else + k = *s++; + while (s != *e) + k = ((k << 2) | (k >> 30)) ^ *s++; + return k; +} diff --git a/lib/libc/ohash/ohash_lookup_interval.c b/lib/libc/ohash/ohash_lookup_interval.c new file mode 100644 index 00000000000..0eaf9643005 --- /dev/null +++ b/lib/libc/ohash/ohash_lookup_interval.c @@ -0,0 +1,84 @@ +/* $OpenBSD: ohash_lookup_interval.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +unsigned int +ohash_lookup_interval(h, start, end, hv) + struct ohash *h; + const char *start; + const char *end; + u_int32_t hv; +{ + unsigned int i, incr; + unsigned int empty; + +#ifdef STATS_HASH + STAT_HASH_LOOKUP++; +#endif + empty = NONE; + i = hv % h->size; + incr = ((hv % (h->size-2)) & ~1) + 1; + while (h->t[i].p != NULL) { +#ifdef STATS_HASH + STAT_HASH_LENGTH++; +#endif + if (h->t[i].p == DELETED) { + if (empty == NONE) + empty = i; + } else if (h->t[i].hv == hv && + strncmp(h->t[i].p+h->info.key_offset, start, + end - start) == 0 && + (h->t[i].p+h->info.key_offset)[end-start] == '\0') { + if (empty != NONE) { + h->t[empty].hv = hv; + h->t[empty].p = h->t[i].p; + h->t[i].p = DELETED; + return empty; + } else { +#ifdef STATS_HASH + STAT_HASH_POSITIVE++; +#endif + return i; + } + } + i += incr; + if (i >= h->size) + i -= h->size; + } + + /* Found an empty position. */ + if (empty != NONE) + i = empty; + h->t[i].hv = hv; + return i; +} + diff --git a/lib/libc/ohash/ohash_lookup_memory.c b/lib/libc/ohash/ohash_lookup_memory.c new file mode 100644 index 00000000000..eb4ab16eed1 --- /dev/null +++ b/lib/libc/ohash/ohash_lookup_memory.c @@ -0,0 +1,81 @@ +/* $OpenBSD: ohash_lookup_memory.c,v 1.1 2001/03/02 13:27:08 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +unsigned int +ohash_lookup_memory(h, k, size, hv) + struct ohash *h; + const char *k; + size_t size; + u_int32_t hv; +{ + unsigned int i, incr; + unsigned int empty; + +#ifdef STATS_HASH + STAT_HASH_LOOKUP++; +#endif + empty = NONE; + i = hv % h->size; + incr = ((hv % (h->size-2)) & ~1) + 1; + while (h->t[i].p != NULL) { +#ifdef STATS_HASH + STAT_HASH_LENGTH++; +#endif + if (h->t[i].p == DELETED) { + if (empty == NONE) + empty = i; + } else if (h->t[i].hv == hv && + memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) { + if (empty != NONE) { + h->t[empty].hv = hv; + h->t[empty].p = h->t[i].p; + h->t[i].p = DELETED; + return empty; + } else { +#ifdef STATS_HASH + STAT_HASH_POSITIVE++; +#endif + } return i; + } + i += incr; + if (i >= h->size) + i -= h->size; + } + + /* Found an empty position. */ + if (empty != NONE) + i = empty; + h->t[i].hv = hv; + return i; +} + diff --git a/lib/libc/ohash/ohash_qlookup.c b/lib/libc/ohash/ohash_qlookup.c new file mode 100644 index 00000000000..89f0318221a --- /dev/null +++ b/lib/libc/ohash/ohash_qlookup.c @@ -0,0 +1,42 @@ +/* $OpenBSD: ohash_qlookup.c,v 1.1 2001/03/02 13:27:08 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +unsigned int +ohash_qlookup(h, s) + struct ohash *h; + const char *s; +{ + const char *e = NULL; + return ohash_qlookupi(h, s, &e); +} + diff --git a/lib/libc/ohash/ohash_qlookupi.c b/lib/libc/ohash/ohash_qlookupi.c new file mode 100644 index 00000000000..1b1e6383257 --- /dev/null +++ b/lib/libc/ohash/ohash_qlookupi.c @@ -0,0 +1,44 @@ +/* $OpenBSD: ohash_qlookupi.c,v 1.1 2001/03/02 13:27:08 espie Exp $ */ +/* ex:ts=8 sw=4: + */ + +/* + * Copyright (c) 1999 Marc Espie. + * + * Code written for the OpenBSD project. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD + * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ohash_int.h" + +unsigned int +ohash_qlookupi(h, s, e) + struct ohash *h; + const char *s; + const char **e; +{ + u_int32_t hv; + + hv = ohash_interval(s, e); + return ohash_lookup_interval(h, s, *e, hv); +} diff --git a/lib/libc/shlib_version b/lib/libc/shlib_version index c622cb8cdf3..72168dfd16a 100644 --- a/lib/libc/shlib_version +++ b/lib/libc/shlib_version @@ -1,2 +1,2 @@ major=26 -minor=0 +minor=1 |