hsearch.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 1996 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/* All Rights Reserved */
#pragma ident "%Z%%M% %I% %E% SMI"
/*LINTLIBRARY*/
/* Compile time switches:
MULT - use a multiplicative hashing function.
DIV - use the remainder mod table size as a hashing function.
CHAINED - use a linked list to resolve collisions.
OPEN - use open addressing to resolve collisions.
BRENT - use Brent's modification to improve the OPEN algorithm.
SORTUP - CHAINED list is sorted in increasing order.
SORTDOWN - CHAINED list is sorted in decreasing order.
START - CHAINED list with entries appended at front.
DRIVER - compile in a main program to drive the tests.
DEBUG - compile some debugging printout statements.
USCR - user supplied comparison routine.
*/
#include <stdio.h>
#include <limits.h>
#define SUCCEED 0
#define FAIL 1
#define TRUE 1
#define FALSE 0
#define repeat for(;;)
#define until(A) if(A) break;
#ifdef OPEN
#else
#ifndef CHAINED
# define OPEN
#endif
#endif
#ifdef MULT
#else
#ifndef DIV
# define MULT
#endif
#endif
#ifdef START
#else
#ifdef SORTUP
#endif
#endif
#ifdef USCR
extern int (* hcompar)();
#else
#endif
#ifdef MULT
static unsigned int bitsper; /* Bits per byte */
static unsigned int hashm();
static unsigned int hash2m();
#else
#ifdef DIV
static unsigned int hashd();
#endif
#endif
typedef enum {
FIND, /* Find, if present */
ENTER /* Find; enter if not present */
} ACTION;
typedef char *POINTER;
typedef struct entry { /* Hash table entry */
} ENTRY;
#ifdef CHAINED
typedef struct node { /* Part of the linked list of entries */
} NODE;
#else
#ifdef OPEN
static unsigned int count = 0; /* Number of entries in hash table */
#endif
#endif
static unsigned int length; /* Size of the hash table */
static unsigned int m; /* Log base 2 of length */
static unsigned int prcnt; /* Number of probes this item */
extern void free();
int hcreate();
void hdestroy();
static unsigned int crunch();
#ifdef DRIVER
static void hdump();
main()
{
int i = 0; /* Data generator */
if(hcreate(5))
else {
}
repeat {
hdump();
printf("Enter a probe: ");
#ifdef DEBUG
#endif
}
else {
}
}
}
printf("Table is full\n");
else {
printf("Success: ");
}
}
}
#endif
int
int size; /* Minimum size for hash table */
{
unsigned int unsize; /* Holds the shifted size */
if(size <= 0)
return(FALSE);
m = 0; /* Log2 length */
while(unsize) {
unsize >>= 1;
length <<= 1;
m++;
}
}
void
hdestroy() /* Reset the module to its initial state */
{
#ifdef OPEN
count = 0;
#endif
}
#ifdef OPEN
/* Hash search of a fixed-capacity table. Open addressing used to
resolve collisions. Algorithm modified from Knuth, Volume 3,
section 6.4, algorithm D. Labels flag corresponding actions.
*/
{
unsigned int i; /* Insertion index */
unsigned int c; /* Secondary probe displacement */
prcnt = 1;
/* D1: */
#ifdef DEBUG
printf("hash = %o\n", i);
#endif
/* D2: */
goto D6;
return(&table[i]);
/* D3: */
#ifdef DEBUG
printf("hash2 = %o\n", c);
#endif
D4:
i = (i + c) % length; /* Advance to next slot */
prcnt++;
/* D5: */
goto D6;
return(&table[i]);
else
goto D4;
return((ENTRY *) 0);
#ifdef BRENT
/* Brent's variation of the open addressing algorithm. Do extra
work during insertion to speed retrieval. May require switching
of previously placed items. Adapted from Knuth, Volume 3, section
4.6 and Brent's article in CACM, volume 10, #2, February 1973.
*/
unsigned int j; /* Counts along main branch */
unsigned int k; /* Counts along secondary branch */
unsigned int curj; /* Current best main branch site */
unsigned int curpos; /* Current best table index */
unsigned int pj; /* Main branch indices */
unsigned int cj; /* Secondary branch increment distance*/
unsigned int pjk; /* Secondary branch probe indices */
if(prcnt >= 3) {
for(j = 0; j < prcnt; j++) { /* Count along main branch */
for(k=1; j+k <= r; k++) { /* Count on secondary branch*/
r = j + k; /* Decrement upper bound */
}
}
}
#ifdef DEBUG
printf("Switch curpos = %o, curj = %o, oldi = %o\n",
#endif
i = curj;
}
}
}
#endif
count++; /* Increment table occupancy count */
return(&table[i]); /* Address of item is returned */
}
#endif
#ifdef USCR
# ifdef DRIVER
static int
compare(a, b)
POINTER a;
POINTER b;
{
return(strcmp(a, b));
}
# endif
#endif
#ifdef CHAINED
# ifdef SORTUP
# else
# ifdef SORTDOWN
# else
# endif
# endif
{
NODE *p; /* Searches through the linked list */
NODE **q; /* Where to store the pointer to a new NODE */
unsigned int i; /* Result of hash */
int res; /* Result of string comparison */
prcnt = 1;
else
}
else { /* List is not empty */
q = &table[i];
p = table[i];
prcnt++;
q = &(p->next);
p = p->next;
}
return(&(p->item));
else { /* Item is not yet on list */
else
#ifdef START
#else
#endif
}
}
}
static ENTRY
{
if(p != NULL) {
*last = p;
return(&(p->item));
}
else
return(NULL);
}
#endif
#ifdef DIV
static unsigned int
{
}
#else
#ifdef MULT
/*
NOTE: The following algorithm only works on machines where
the results of multiplying two integers is the least
significant part of the double word integer required to hold
the result. It is adapted from Knuth, Volume 3, section 6.4.
*/
static unsigned int
{
if(first) { /* Compute the number of bits in a byte */
unsigned char c = UCHAR_MAX; /* A byte full of 1's */
bitsper = 0;
while(c) { /* Shift until no more 1's */
c >>= 1;
bitsper++; /* Count number of shifts */
}
}
}
/*
* Secondary hashing, for use with multiplicitive hashing scheme.
* Adapted from Knuth, Volume 3, section 6.4.
*/
static unsigned int
{
}
#endif
#endif
static unsigned int
{
unsigned int sum = 0; /* Results */
int s; /* Length of the key */
for(s = 0; *key; s++) /* Simply add up the bytes */
return(sum + s);
}
#ifdef DRIVER
static void
hdump() /* Dumps loc, data, probe count, key */
{
unsigned int i; /* Counts table slots */
#ifdef OPEN
unsigned int sum = 0; /* Counts probes */
#else
#ifdef CHAINED
NODE *a; /* Current Node on list */
#endif
#endif
for(i = 0; i < length; i++)
#ifdef OPEN
printf("%o.\t-,\t-,\t(NULL)\n", i);
else {
printf("%o.\t%d,\t%d,\t%s\n", i,
}
#else
#ifdef CHAINED
printf("%o.\t-,\t-,\t(NULL)\n", i);
else {
printf("%o.", i);
printf("\t%d,\t%#0.4x,\t%s\n",
}
#endif
#endif
}
#endif