ohash_lookup_interval.c revision 256281
1133359Sobrien/* $OpenBSD: ohash_lookup_interval.c,v 1.3 2006/01/16 15:52:25 espie Exp $ */ 268349Sobrien/* ex:ts=8 sw=4: 3133359Sobrien */ 4133359Sobrien 5133359Sobrien/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org> 6133359Sobrien * 7133359Sobrien * Permission to use, copy, modify, and distribute this software for any 868349Sobrien * purpose with or without fee is hereby granted, provided that the above 9133359Sobrien * copyright notice and this permission notice appear in all copies. 10133359Sobrien * 11133359Sobrien * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12133359Sobrien * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 1368349Sobrien * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 1468349Sobrien * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15103373Sobrien * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 1668349Sobrien * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 1768349Sobrien * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 1868349Sobrien */ 1968349Sobrien#include <sys/cdefs.h> 2068349Sobrien__FBSDID("$FreeBSD: stable/10/usr.bin/m4/lib/ohash_lookup_interval.c 228063 2011-11-28 13:32:39Z bapt $"); 2168349Sobrien 2268349Sobrien#include "ohash_int.h" 2368349Sobrien 2468349Sobrienunsigned int 2568349Sobrienohash_lookup_interval(struct ohash *h, const char *start, const char *end, 2668349Sobrien uint32_t hv) 2768349Sobrien{ 2868349Sobrien unsigned int i, incr; 2968349Sobrien unsigned int empty; 3084685Sobrien 3184685Sobrien#ifdef STATS_HASH 32103373Sobrien STAT_HASH_LOOKUP++; 3384685Sobrien#endif 3484685Sobrien empty = NONE; 3584685Sobrien i = hv % h->size; 3684685Sobrien incr = ((hv % (h->size-2)) & ~1) + 1; 3784685Sobrien while (h->t[i].p != NULL) { 3884685Sobrien#ifdef STATS_HASH 39103373Sobrien STAT_HASH_LENGTH++; 4084685Sobrien#endif 4184685Sobrien if (h->t[i].p == DELETED) { 4284685Sobrien if (empty == NONE) 4384685Sobrien empty = i; 4484685Sobrien } else if (h->t[i].hv == hv && 4584685Sobrien strncmp(h->t[i].p+h->info.key_offset, start, 4684685Sobrien end - start) == 0 && 4784685Sobrien (h->t[i].p+h->info.key_offset)[end-start] == '\0') { 4884685Sobrien if (empty != NONE) { 4984685Sobrien h->t[empty].hv = hv; 5084685Sobrien h->t[empty].p = h->t[i].p; 51103373Sobrien h->t[i].p = DELETED; 5284685Sobrien return empty; 5384685Sobrien } else { 5484685Sobrien#ifdef STATS_HASH 5584685Sobrien STAT_HASH_POSITIVE++; 5684685Sobrien#endif 5784685Sobrien return i; 5884685Sobrien } 5984685Sobrien } 6084685Sobrien i += incr; 6184685Sobrien if (i >= h->size) 6284685Sobrien i -= h->size; 6384685Sobrien } 6484685Sobrien 6584685Sobrien /* Found an empty position. */ 6684685Sobrien if (empty != NONE) 6784685Sobrien i = empty; 6884685Sobrien h->t[i].hv = hv; 6984685Sobrien return i; 7084685Sobrien} 7184685Sobrien