1 |
|
|
/* $OpenBSD: hash.c,v 1.3 2016/10/12 15:51:44 millert Exp $ */ |
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 |
|
|
|
18 |
|
|
#include <sys/types.h> |
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 |
✗✓ |
164 |
if (hsize < MIN_HASH_SIZE) |
36 |
|
|
hsize = MIN_HASH_SIZE; |
37 |
|
|
|
38 |
✗✓ |
82 |
if (hsize > MAX_HASH_SIZE) |
39 |
|
|
hsize = MAX_HASH_SIZE; |
40 |
|
|
|
41 |
✓✗ |
82 |
if ((hsize & (hsize - 1)) != 0) { |
42 |
✓✓ |
1312 |
for (power = 0; hsize != 0; power++) |
43 |
|
574 |
hsize >>= 1; |
44 |
|
82 |
hsize = 1 << power; |
45 |
|
82 |
} |
46 |
|
|
|
47 |
|
82 |
htable->h_table = xcalloc(hsize, sizeof(struct hash_head)); |
48 |
|
82 |
htable->h_size = hsize; |
49 |
|
|
|
50 |
✓✓ |
21156 |
for (i = 0; i < htable->h_size; i++) |
51 |
|
10496 |
SLIST_INIT(&(htable->h_table[i])); |
52 |
|
82 |
} |
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 |
|
70 |
hashv = hash4(e->h_key, strlen(e->h_key)); |
62 |
|
35 |
tableh = &(htable->h_table[(hashv & (htable->h_size - 1))]); |
63 |
|
|
|
64 |
|
35 |
entry = xmalloc(sizeof(*entry)); |
65 |
|
35 |
entry->h_data.h_key = e->h_key; |
66 |
|
35 |
entry->h_data.h_data = e->h_data; |
67 |
|
35 |
SLIST_INSERT_HEAD(tableh, entry, h_list); |
68 |
|
35 |
} |
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 |
|
80 |
hashv = hash4(key, len); |
78 |
|
40 |
tableh = &(htable->h_table[(hashv & (htable->h_size - 1))]); |
79 |
|
|
|
80 |
✓✓ |
80 |
SLIST_FOREACH(entry, tableh, h_list) { |
81 |
✓✗ |
5 |
if (!strcmp(entry->h_data.h_key, key)) |
82 |
|
5 |
return (&(entry->h_data)); |
83 |
|
|
} |
84 |
|
|
|
85 |
|
35 |
return (NULL); |
86 |
|
40 |
} |