Annotation of mandoc/compat_ohash.c, Revision 1.1
1.1 ! kristaps 1: #ifdef HAVE_CONFIG_H
! 2: #include "config.h"
! 3: #endif
! 4:
! 5: #ifdef HAVE_OHASH
! 6:
! 7: int dummy;
! 8:
! 9: #else
! 10:
! 11: /* $OpenBSD: ohash_int.h,v 1.3 2006/01/16 15:52:25 espie Exp $ */
! 12:
! 13: #include <stddef.h>
! 14: #include <stdint.h>
! 15: #include <stdlib.h>
! 16: #include <string.h>
! 17: #include "compat_ohash.h"
! 18:
! 19: struct _ohash_record {
! 20: u_int32_t hv;
! 21: const char *p;
! 22: };
! 23:
! 24: #define DELETED ((const char *)h)
! 25: #define NONE (h->size)
! 26:
! 27: /* Don't bother changing the hash table if the change is small enough. */
! 28: #define MINSIZE (1UL << 4)
! 29: #define MINDELETED 4
! 30: /* $OpenBSD: ohash_create_entry.c,v 1.2 2004/06/22 20:00:16 espie Exp $ */
! 31: /* ex:ts=8 sw=4:
! 32: */
! 33:
! 34: /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
! 35: *
! 36: * Permission to use, copy, modify, and distribute this software for any
! 37: * purpose with or without fee is hereby granted, provided that the above
! 38: * copyright notice and this permission notice appear in all copies.
! 39: *
! 40: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
! 41: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
! 42: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
! 43: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
! 44: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
! 45: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
! 46: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
! 47: */
! 48:
! 49: /* This handles the common case of variable length keys, where the
! 50: * key is stored at the end of the record.
! 51: */
! 52: void *
! 53: ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
! 54: {
! 55: char *p;
! 56:
! 57: if (!*end)
! 58: *end = start + strlen(start);
! 59: p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
! 60: if (p) {
! 61: memcpy(p+i->key_offset, start, *end-start);
! 62: p[i->key_offset + (*end - start)] = '\0';
! 63: }
! 64: return (void *)p;
! 65: }
! 66:
! 67: /* hash_delete only frees the hash structure. Use hash_first/hash_next
! 68: * to free entries as well. */
! 69: void
! 70: ohash_delete(struct ohash *h)
! 71: {
! 72: (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
! 73: h->info.data);
! 74: #ifndef NDEBUG
! 75: h->t = NULL;
! 76: #endif
! 77: }
! 78:
! 79: static void ohash_resize(struct ohash *);
! 80:
! 81: static void
! 82: ohash_resize(struct ohash *h)
! 83: {
! 84: struct _ohash_record *n;
! 85: unsigned int ns, j;
! 86: unsigned int i, incr;
! 87:
! 88: if (4 * h->deleted < h->total)
! 89: ns = h->size << 1;
! 90: else if (3 * h->deleted > 2 * h->total)
! 91: ns = h->size >> 1;
! 92: else
! 93: ns = h->size;
! 94: if (ns < MINSIZE)
! 95: ns = MINSIZE;
! 96: #ifdef STATS_HASH
! 97: STAT_HASH_EXPAND++;
! 98: STAT_HASH_SIZE += ns - h->size;
! 99: #endif
! 100: n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data);
! 101: if (!n)
! 102: return;
! 103:
! 104: for (j = 0; j < h->size; j++) {
! 105: if (h->t[j].p != NULL && h->t[j].p != DELETED) {
! 106: i = h->t[j].hv % ns;
! 107: incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
! 108: while (n[i].p != NULL) {
! 109: i += incr;
! 110: if (i >= ns)
! 111: i -= ns;
! 112: }
! 113: n[i].hv = h->t[j].hv;
! 114: n[i].p = h->t[j].p;
! 115: }
! 116: }
! 117: (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
! 118: h->info.data);
! 119: h->t = n;
! 120: h->size = ns;
! 121: h->total -= h->deleted;
! 122: h->deleted = 0;
! 123: }
! 124:
! 125: void *
! 126: ohash_remove(struct ohash *h, unsigned int i)
! 127: {
! 128: void *result = (void *)h->t[i].p;
! 129:
! 130: if (result == NULL || result == DELETED)
! 131: return NULL;
! 132:
! 133: #ifdef STATS_HASH
! 134: STAT_HASH_ENTRIES--;
! 135: #endif
! 136: h->t[i].p = DELETED;
! 137: h->deleted++;
! 138: if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
! 139: ohash_resize(h);
! 140: return result;
! 141: }
! 142:
! 143: void *
! 144: ohash_find(struct ohash *h, unsigned int i)
! 145: {
! 146: if (h->t[i].p == DELETED)
! 147: return NULL;
! 148: else
! 149: return (void *)h->t[i].p;
! 150: }
! 151:
! 152: void *
! 153: ohash_insert(struct ohash *h, unsigned int i, void *p)
! 154: {
! 155: #ifdef STATS_HASH
! 156: STAT_HASH_ENTRIES++;
! 157: #endif
! 158: if (h->t[i].p == DELETED) {
! 159: h->deleted--;
! 160: h->t[i].p = p;
! 161: } else {
! 162: h->t[i].p = p;
! 163: /* Arbitrary resize boundary. Tweak if not efficient enough. */
! 164: if (++h->total * 4 > h->size * 3)
! 165: ohash_resize(h);
! 166: }
! 167: return p;
! 168: }
! 169:
! 170: unsigned int
! 171: ohash_entries(struct ohash *h)
! 172: {
! 173: return h->total - h->deleted;
! 174: }
! 175:
! 176: void *
! 177: ohash_first(struct ohash *h, unsigned int *pos)
! 178: {
! 179: *pos = 0;
! 180: return ohash_next(h, pos);
! 181: }
! 182:
! 183: void *
! 184: ohash_next(struct ohash *h, unsigned int *pos)
! 185: {
! 186: for (; *pos < h->size; (*pos)++)
! 187: if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
! 188: return (void *)h->t[(*pos)++].p;
! 189: return NULL;
! 190: }
! 191:
! 192: void
! 193: ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
! 194: {
! 195: h->size = 1UL << size;
! 196: if (h->size < MINSIZE)
! 197: h->size = MINSIZE;
! 198: #ifdef STATS_HASH
! 199: STAT_HASH_CREATION++;
! 200: STAT_HASH_SIZE += h->size;
! 201: #endif
! 202: /* Copy info so that caller may free it. */
! 203: h->info.key_offset = info->key_offset;
! 204: h->info.halloc = info->halloc;
! 205: h->info.hfree = info->hfree;
! 206: h->info.alloc = info->alloc;
! 207: h->info.data = info->data;
! 208: h->t = (h->info.halloc)(sizeof(struct _ohash_record) * h->size,
! 209: h->info.data);
! 210: h->total = h->deleted = 0;
! 211: }
! 212:
! 213: uint32_t
! 214: ohash_interval(const char *s, const char **e)
! 215: {
! 216: uint32_t k;
! 217:
! 218: if (!*e)
! 219: *e = s + strlen(s);
! 220: if (s == *e)
! 221: k = 0;
! 222: else
! 223: k = *s++;
! 224: while (s != *e)
! 225: k = ((k << 2) | (k >> 30)) ^ *s++;
! 226: return k;
! 227: }
! 228:
! 229: unsigned int
! 230: ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
! 231: uint32_t hv)
! 232: {
! 233: unsigned int i, incr;
! 234: unsigned int empty;
! 235:
! 236: #ifdef STATS_HASH
! 237: STAT_HASH_LOOKUP++;
! 238: #endif
! 239: empty = NONE;
! 240: i = hv % h->size;
! 241: incr = ((hv % (h->size-2)) & ~1) + 1;
! 242: while (h->t[i].p != NULL) {
! 243: #ifdef STATS_HASH
! 244: STAT_HASH_LENGTH++;
! 245: #endif
! 246: if (h->t[i].p == DELETED) {
! 247: if (empty == NONE)
! 248: empty = i;
! 249: } else if (h->t[i].hv == hv &&
! 250: strncmp(h->t[i].p+h->info.key_offset, start,
! 251: end - start) == 0 &&
! 252: (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
! 253: if (empty != NONE) {
! 254: h->t[empty].hv = hv;
! 255: h->t[empty].p = h->t[i].p;
! 256: h->t[i].p = DELETED;
! 257: return empty;
! 258: } else {
! 259: #ifdef STATS_HASH
! 260: STAT_HASH_POSITIVE++;
! 261: #endif
! 262: return i;
! 263: }
! 264: }
! 265: i += incr;
! 266: if (i >= h->size)
! 267: i -= h->size;
! 268: }
! 269:
! 270: /* Found an empty position. */
! 271: if (empty != NONE)
! 272: i = empty;
! 273: h->t[i].hv = hv;
! 274: return i;
! 275: }
! 276:
! 277: unsigned int
! 278: ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
! 279: {
! 280: unsigned int i, incr;
! 281: unsigned int empty;
! 282:
! 283: #ifdef STATS_HASH
! 284: STAT_HASH_LOOKUP++;
! 285: #endif
! 286: empty = NONE;
! 287: i = hv % h->size;
! 288: incr = ((hv % (h->size-2)) & ~1) + 1;
! 289: while (h->t[i].p != NULL) {
! 290: #ifdef STATS_HASH
! 291: STAT_HASH_LENGTH++;
! 292: #endif
! 293: if (h->t[i].p == DELETED) {
! 294: if (empty == NONE)
! 295: empty = i;
! 296: } else if (h->t[i].hv == hv &&
! 297: memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
! 298: if (empty != NONE) {
! 299: h->t[empty].hv = hv;
! 300: h->t[empty].p = h->t[i].p;
! 301: h->t[i].p = DELETED;
! 302: return empty;
! 303: } else {
! 304: #ifdef STATS_HASH
! 305: STAT_HASH_POSITIVE++;
! 306: #endif
! 307: } return i;
! 308: }
! 309: i += incr;
! 310: if (i >= h->size)
! 311: i -= h->size;
! 312: }
! 313:
! 314: /* Found an empty position. */
! 315: if (empty != NONE)
! 316: i = empty;
! 317: h->t[i].hv = hv;
! 318: return i;
! 319: }
! 320:
! 321: unsigned int
! 322: ohash_qlookup(struct ohash *h, const char *s)
! 323: {
! 324: const char *e = NULL;
! 325: return ohash_qlookupi(h, s, &e);
! 326: }
! 327:
! 328: unsigned int
! 329: ohash_qlookupi(struct ohash *h, const char *s, const char **e)
! 330: {
! 331: u_int32_t hv;
! 332:
! 333: hv = ohash_interval(s, e);
! 334: return ohash_lookup_interval(h, s, *e, hv);
! 335: }
! 336:
! 337: #endif /*!HAVE_OHASH*/
CVSweb
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to compat_ohash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [cvsweb.bsd.lv] / mandoc