1 /* $OpenBSD: hash.c,v 1.1 2008/06/21 15:39:15 joris 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/param.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 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 47 htable->h_table = xcalloc(hsize, sizeof(struct hash_head *)); 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 } 87