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: }