[BACK]Return to compat_ohash.c CVS log [TXT][DIR] Up to [cvsweb.bsd.lv] / mandoc

Annotation of mandoc/compat_ohash.c, Revision 1.6

1.1       kristaps    1: #include "config.h"
                      2:
1.6     ! schwarze    3: #if HAVE_OHASH
1.1       kristaps    4:
                      5: int dummy;
                      6:
                      7: #else
                      8:
1.3       schwarze    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:  */
1.5       schwarze   25:
                     26: #include <sys/types.h>
1.1       kristaps   27:
                     28: #include <stddef.h>
                     29: #include <stdint.h>
                     30: #include <stdlib.h>
                     31: #include <string.h>
1.4       schwarze   32: #include <limits.h>
1.1       kristaps   33: #include "compat_ohash.h"
                     34:
                     35: struct _ohash_record {
1.2       schwarze   36:        uint32_t        hv;
1.3       schwarze   37:        const char      *p;
1.1       kristaps   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:
1.3       schwarze   47: static void ohash_resize(struct ohash *);
                     48:
1.1       kristaps   49:
1.3       schwarze   50: /* This handles the common case of variable length keys, where the
1.1       kristaps   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) {
1.3       schwarze   62:                memcpy(p+i->key_offset, start, *end-start);
                     63:                p[i->key_offset + (*end - start)] = '\0';
1.1       kristaps   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.  */
1.3       schwarze   70: void
1.1       kristaps   71: ohash_delete(struct ohash *h)
                     72: {
1.4       schwarze   73:        (h->info.free)(h->t, h->info.data);
1.1       kristaps   74: #ifndef NDEBUG
                     75:        h->t = NULL;
                     76: #endif
                     77: }
                     78:
1.3       schwarze   79: static void
1.1       kristaps   80: ohash_resize(struct ohash *h)
                     81: {
                     82:        struct _ohash_record *n;
1.4       schwarze   83:        size_t ns;
                     84:        unsigned int    j;
1.1       kristaps   85:        unsigned int    i, incr;
                     86:
1.4       schwarze   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;
1.1       kristaps   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
1.4       schwarze  102:
                    103:        n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
1.1       kristaps  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;
1.3       schwarze  115:                        }
1.1       kristaps  116:                        n[i].hv = h->t[j].hv;
                    117:                        n[i].p = h->t[j].p;
                    118:                }
                    119:        }
1.4       schwarze  120:        (h->info.free)(h->t, h->info.data);
1.1       kristaps  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: {
1.3       schwarze  130:        void            *result = (void *)h->t[i].p;
1.1       kristaps  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;
1.3       schwarze  165:                /* Arbitrary resize boundary.  Tweak if not efficient enough.  */
1.1       kristaps  166:                if (++h->total * 4 > h->size * 3)
                    167:                        ohash_resize(h);
                    168:        }
1.3       schwarze  169:        return p;
1.1       kristaps  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: }
1.3       schwarze  184:
1.1       kristaps  185: void *
                    186: ohash_next(struct ohash *h, unsigned int *pos)
                    187: {
1.3       schwarze  188:        for (; *pos < h->size; (*pos)++)
                    189:                if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
1.1       kristaps  190:                        return (void *)h->t[(*pos)++].p;
                    191:        return NULL;
                    192: }
                    193:
1.3       schwarze  194: void
1.1       kristaps  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;
1.4       schwarze  206:        h->info.calloc = info->calloc;
                    207:        h->info.free = info->free;
1.1       kristaps  208:        h->info.alloc = info->alloc;
                    209:        h->info.data = info->data;
1.4       schwarze  210:        h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
                    211:                    h->info.data);
1.1       kristaps  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
1.3       schwarze  232: ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
1.1       kristaps  233:     uint32_t hv)
                    234: {
1.3       schwarze  235:        unsigned int    i, incr;
1.1       kristaps  236:        unsigned int    empty;
1.3       schwarze  237:
1.1       kristaps  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;
1.3       schwarze  251:                } else if (h->t[i].hv == hv &&
                    252:                    strncmp(h->t[i].p+h->info.key_offset, start,
                    253:                        end - start) == 0 &&
1.1       kristaps  254:                    (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
1.3       schwarze  255:                        if (empty != NONE) {
1.1       kristaps  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;
1.3       schwarze  268:                if (i >= h->size)
1.1       kristaps  269:                        i -= h->size;
                    270:        }
                    271:
                    272:        /* Found an empty position.  */
1.3       schwarze  273:        if (empty != NONE)
1.1       kristaps  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;
1.3       schwarze  284:
1.1       kristaps  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;
1.3       schwarze  298:                } else if (h->t[i].hv == hv &&
1.1       kristaps  299:                    memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
1.3       schwarze  300:                        if (empty != NONE) {
1.1       kristaps  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;
1.3       schwarze  312:                if (i >= h->size)
1.1       kristaps  313:                        i -= h->size;
                    314:        }
                    315:
                    316:        /* Found an empty position.  */
1.3       schwarze  317:        if (empty != NONE)
1.1       kristaps  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: {
1.2       schwarze  333:        uint32_t hv;
1.1       kristaps  334:
                    335:        hv = ohash_interval(s, e);
                    336:        return ohash_lookup_interval(h, s, *e, hv);
                    337: }
                    338:
                    339: #endif /*!HAVE_OHASH*/

CVSweb