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

Annotation of mandoc/compat_ohash.c, Revision 1.3

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

CVSweb