1 /* $OpenBSD: ohash_lookup_interval.c,v 1.3 2006/01/16 15:52:25 espie Exp $ */ 2 /* ex:ts=8 sw=4: 3 */ 4 5 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20 #include "ohash_int.h" 21 22 unsigned int 23 ohash_lookup_interval(struct ohash *h, const char *start, const char *end, 24 uint32_t hv) 25 { 26 unsigned int i, incr; 27 unsigned int empty; 28 29 #ifdef STATS_HASH 30 STAT_HASH_LOOKUP++; 31 #endif 32 empty = NONE; 33 i = hv % h->size; 34 incr = ((hv % (h->size-2)) & ~1) + 1; 35 while (h->t[i].p != NULL) { 36 #ifdef STATS_HASH 37 STAT_HASH_LENGTH++; 38 #endif 39 if (h->t[i].p == DELETED) { 40 if (empty == NONE) 41 empty = i; 42 } else if (h->t[i].hv == hv && 43 strncmp(h->t[i].p+h->info.key_offset, start, 44 end - start) == 0 && 45 (h->t[i].p+h->info.key_offset)[end-start] == '\0') { 46 if (empty != NONE) { 47 h->t[empty].hv = hv; 48 h->t[empty].p = h->t[i].p; 49 h->t[i].p = DELETED; 50 return empty; 51 } else { 52 #ifdef STATS_HASH 53 STAT_HASH_POSITIVE++; 54 #endif 55 return i; 56 } 57 } 58 i += incr; 59 if (i >= h->size) 60 i -= h->size; 61 } 62 63 /* Found an empty position. */ 64 if (empty != NONE) 65 i = empty; 66 h->t[i].hv = hv; 67 return i; 68 } 69