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