Return to hash.c CVS log

Up to [local] / src / usr.bin / cvs

Annotation of src/usr.bin/cvs/hash.c, Revision 1.3

1.3     ! millert     1: /*     $OpenBSD: hash.c,v 1.2 2015/01/16 06:40:07 deraadt Exp $        */
1.1       joris       2: /*
                      3:  * Copyright (c) 2008 Joris Vink <joris@openbsd.org>
                      4:  *
                      5:  * Permission to use, copy, modify, and distribute this software for any
                      6:  * purpose with or without fee is hereby granted, provided that the above
                      7:  * copyright notice and this permission notice appear in all copies.
                      8:  *
                      9:  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
                     10:  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
                     11:  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
                     12:  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
                     13:  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
                     14:  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
                     15:  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
                     16:  */
                     17:
1.2       deraadt    18: #include <sys/types.h>
1.1       joris      19: #include <sys/queue.h>
                     20:
                     21: #include <stdio.h>
                     22: #include <stdlib.h>
                     23: #include <string.h>
                     24:
                     25: #include "cvs.h"
                     26: #include "hash.h"
                     27: #include "xmalloc.h"
                     28:
                     29: void
                     30: hash_table_init(struct hash_table *htable, size_t hsize)
                     31: {
                     32:        size_t i;
                     33:        u_int power;
                     34:
                     35:        if (hsize < MIN_HASH_SIZE)
                     36:                hsize = MIN_HASH_SIZE;
                     37:
                     38:        if (hsize > MAX_HASH_SIZE)
                     39:                hsize = MAX_HASH_SIZE;
                     40:
                     41:        if ((hsize & (hsize - 1)) != 0) {
                     42:                for (power = 0; hsize != 0; power++)
                     43:                        hsize >>= 1;
                     44:                hsize = 1 << power;
                     45:        }
                     46:
1.3     ! millert    47:        htable->h_table = xcalloc(hsize, sizeof(struct hash_head));
1.1       joris      48:        htable->h_size = hsize;
                     49:
                     50:        for (i = 0; i < htable->h_size; i++)
                     51:                SLIST_INIT(&(htable->h_table[i]));
                     52: }
                     53:
                     54: void
                     55: hash_table_enter(struct hash_table *htable, struct hash_data *e)
                     56: {
                     57:        uint32_t hashv;
                     58:        struct hash_head *tableh;
                     59:        struct hash_table_entry *entry;
                     60:
                     61:        hashv = hash4(e->h_key, strlen(e->h_key));
                     62:        tableh = &(htable->h_table[(hashv & (htable->h_size - 1))]);
                     63:
                     64:        entry = xmalloc(sizeof(*entry));
                     65:        entry->h_data.h_key = e->h_key;
                     66:        entry->h_data.h_data = e->h_data;
                     67:        SLIST_INSERT_HEAD(tableh, entry, h_list);
                     68: }
                     69:
                     70: struct hash_data *
                     71: hash_table_find(struct hash_table *htable, const char *key, size_t len)
                     72: {
                     73:        uint32_t hashv;
                     74:        struct hash_head *tableh;
                     75:        struct hash_table_entry *entry;
                     76:
                     77:        hashv = hash4(key, len);
                     78:        tableh = &(htable->h_table[(hashv & (htable->h_size - 1))]);
                     79:
                     80:        SLIST_FOREACH(entry, tableh, h_list) {
                     81:                if (!strcmp(entry->h_data.h_key, key))
                     82:                        return (&(entry->h_data));
                     83:        }
                     84:
                     85:        return (NULL);
                     86: }