xref: /illumos-gate/usr/src/lib/libc/port/gen/hsearch.c (revision 18c77f76)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (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
 * or http://www.opensolaris.org/os/licensing.
 * 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 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1988 AT&T	*/
/*	  All Rights Reserved	*/

/*
 * 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.
 *  HSEARCH_DEBUG - compile some debugging printout statements.
 *  USCR - user supplied comparison routine.
 */

#pragma weak _hcreate = hcreate
#pragma weak _hdestroy = hdestroy
#pragma weak _hsearch = hsearch

#include "lint.h"
#include <mtlib.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <thread.h>
#include <synch.h>
#include <search.h>

typedef char *POINTER;

#define	SUCCEED		0
#define	FAIL		1
#define	TRUE		1
#define	FALSE		0
#define	repeat		for (;;)
#define	until(A)	if (A) break;

#ifdef OPEN
#undef CHAINED
#else
#ifndef CHAINED
#define	OPEN
#endif
#endif

#ifdef MULT
#undef DIV
#else
#ifndef DIV
#define	MULT
#endif
#endif

#ifdef START
#undef SORTUP
#undef SORTDOWN
#else
#ifdef SORTUP
#undef SORTDOWN
#endif
#endif

#ifdef USCR
#define	COMPARE(A, B) (* hcompar)((A), (B))
extern int (* hcompar)();
#else
#define	COMPARE(A, B) strcmp((A), (B))
#endif

#ifdef MULT
#define	SHIFT ((CHAR_BIT * sizeof (int)) - m) /* Shift factor */
#define	FACTOR 035761254233	/* Magic multiplication factor */
#define	HASH hashm		/* Multiplicative hash function */
#define	HASH2 hash2m	/* Secondary hash function */
static unsigned int hashm(POINTER);
static unsigned int hash2m(POINTER);
#else
#ifdef DIV
#define	HASH hashd		/* Division hashing routine */
#define	HASH2(A) 1		/* Secondary hash function */
static unsigned int hashd();
#endif
#endif

#ifdef CHAINED
typedef struct node {	/* Part of the linked list of entries */
	ENTRY item;
	struct node *next;
} NODE;
typedef NODE *TABELEM;
static NODE **table;	/* The address of the hash table */
static ENTRY *build();
#else
#ifdef OPEN
typedef ENTRY TABELEM;	/* What the table contains (TABle ELEMents) */
static TABELEM *table;	/* The address of the hash table */
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 */
static mutex_t table_lock = DEFAULTMUTEX;
#define	RETURN(n)    { lmutex_unlock(&table_lock); return (n); }

/*
 * forward declarations
 */

static unsigned int crunch(POINTER);

#ifdef DRIVER
static void hdump();

main()
{
	char line[80];	/* Room for the input line */
	int i = 0;		/* Data generator */
	ENTRY *res;		/* Result of hsearch */
	ENTRY *new;		/* Test entry */

start:
	if (hcreate(5))
		printf("Length = %u, m = %u\n", length, m);
	else {
		fprintf(stderr, "Out of core\n");
		exit(FAIL);
	}
	repeat {
	hdump();
	printf("Enter a probe: ");
	until(EOF == scanf("%s", line) || strcmp(line, "quit") == 0);
#ifdef HSEARCH_DEBUG
	printf("%s, ", line);
	printf("division: %d, ", hashd(line));
	printf("multiplication: %d\n", hashm(line));
#endif
	new = (ENTRY *) malloc(sizeof (ENTRY));
	if (new == NULL) {
		fprintf(stderr, "Out of core \n");
		exit(FAIL);
	} else {
		new->key = malloc((unsigned)strlen(line) + 1);
		if (new->key == NULL) {
			fprintf(stderr, "Out of core \n");
			exit(FAIL);
		}
		(void) strcpy(new->key, line);
		new->data = malloc(sizeof (int));
		if (new->data == NULL) {
			fprintf(stderr, "Out of core \n");
			exit(FAIL);
		}
		*new->data = i++;
	}
	res = hsearch(*new, ENTER);
	printf("The number of probes required was %d\n", prcnt);
	if (res == (ENTRY *) 0)
		printf("Table is full\n");
	else {
		printf("Success: ");
		printf("Key = %s, Value = %d\n", res->key, *res->data);
	}
	}
	printf("Do you wish to start another hash table (yes/no?)");
	if (EOF == scanf("%s", line) || strcmp(line, "no") == 0)
		exit(SUCCEED);
	hdestroy();
	goto start;
}
#endif

int
hcreate(size_t size)	/* Create a hash table no smaller than size */
	/* Minimum "size" for hash table */
{
	size_t unsize;	/* Holds the shifted size */
	TABELEM *local_table;
	TABELEM *old_table;
	unsigned int local_length;
	unsigned int local_m;

	if (size == 0)
		return (FALSE);

	unsize = size;	/* +1 for empty table slot; -1 for ceiling */
	local_length = 1;	/* Maximum entries in table */
	local_m = 0;		/* Log2 length */
	while (unsize) {
		unsize >>= 1;
		local_length <<= 1;
		local_m++;
	}

	local_table = (TABELEM *) calloc(local_length, sizeof (TABELEM));

	lmutex_lock(&table_lock);
	old_table = table;
	table = local_table;
	length = local_length;
	m = local_m;
	lmutex_unlock(&table_lock);
	if (old_table != NULL)
		free(old_table);
	return (local_table != NULL);
}

void
hdestroy(void)	/* Reset the module to its initial state */
{
	POINTER local_table;

	lmutex_lock(&table_lock);
#ifdef CHAINED
	int i;
	NODE *p, *oldp;
	for (i = 0; i < length; i++) {
		if (table[i] != (NODE *)NULL) {
			p = table[i];
			while (p != (NODE *)NULL) {
				oldp = p;
				p = p -> next;
				/*
				 * This is a locking vs malloc() violation.
				 * Fortunately, it is not actually compiled.
				 */
				free(oldp);
			}
		}
	}
#endif
	local_table = (POINTER)table;
	table = 0;
#ifdef OPEN
	count = 0;
#endif
	lmutex_unlock(&table_lock);
	free(local_table);
}

#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.
 */

/* Find or insert the item into the table */
ENTRY
*hsearch(ENTRY item, ACTION action)
	/* "item" to be inserted or found */
	/* action: FIND or ENTER */
{
	unsigned int i;	/* Insertion index */
	unsigned int c;	/* Secondary probe displacement */

	lmutex_lock(&table_lock);
	prcnt = 1;

/* D1: */
	i = HASH(item.key);	/* Primary hash on key */
#ifdef HSEARCH_DEBUG
	if (action == ENTER)
		printf("hash = %o\n", i);
#endif

/* D2: */
	if (table[i].key == NULL)	/* Empty slot? */
		goto D6;
	else if (COMPARE(table[i].key, item.key) == 0)	/* Match? */
		RETURN(&table[i]);

/* D3: */
	c = HASH2(item.key);	/* No match => compute secondary hash */
#ifdef HSEARCH_DEBUG
	if (action == ENTER)
		printf("hash2 = %o\n", c);
#endif

D4:
	i = (i + c) % length;	/* Advance to next slot */
	prcnt++;

/* D5: */
	if (table[i].key == NULL)	/* Empty slot? */
		goto D6;
	else if (COMPARE(table[i].key, item.key) == 0)	/* Match? */
		RETURN(&table[i])
	else
		goto D4;

D6:	if (action == FIND)		/* Insert if requested */
		RETURN((ENTRY *) NULL);
	if (count == (length - 1))	/* Table full? */
		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 p0 = HASH(item.key);   /* First probe index */
	unsigned int c0 = HASH2(item.key);  /* Main branch increment */
	unsigned int r = prcnt - 1; /* Current minimum distance */
	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 */
			pj = (p0 + j * c0) % length; /* New main branch index */
			cj = HASH2(table[pj].key); /* Secondary branch incr. */
			for (k = 1; j+k <= r; k++) {
					/* Count on secondary branch */
				pjk = (pj + k * cj) % length;
					/* Secondary probe */
				if (table[pjk].key == NULL) {
					/* Improvement found */
					r = j + k; /* Decrement upper bound */
					curj = pj; /* Save main probe index */
					curpos = pjk;
						/* Save secondeary index */
				}
			}
		}
		if (r != prcnt - 1) {	/* If an improvement occurred */
			table[curpos] = table[curj]; /* Old key to new site */
#ifdef HSEARCH_DEBUG
			printf("Switch curpos = %o, curj = %o, oldi = %o\n",
				curj, curpos, i);
#endif
			i = curj;
		}
	}
	}
#endif
	count++;			/* Increment table occupancy count */
	table[i] = item;		/* Save item */

	lmutex_unlock(&table_lock);
	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));
}

int (* hcompar)() = compare;
#endif
#endif

#ifdef CHAINED
#ifdef SORTUP
#define	STRCMP(A, B) (COMPARE((A), (B)) > 0)
#else
#ifdef SORTDOWN
#define	STRCMP(A, B) (COMPARE((A), (B)) < 0)
#else
#define	STRCMP(A, B) (COMPARE((A), (B)) != 0)
#endif
#endif

ENTRY
*hsearch(item, action)	/* Chained search with sorted lists */
ENTRY item;		/* Item to be inserted or found */
ACTION action;		/* FIND or ENTER */
{
	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 */

	lmutex_lock(&table_lock);
	prcnt = 1;

	i = HASH(item.key);	/* Table[i] contains list head */

	if (table[i] == (NODE*)NULL) { /* List has not yet been begun */
		if (action == FIND)
			RETURN((ENTRY *) NULL);
		else
			RETURN(build(&table[i], (NODE *) NULL, item));
	} else {		/* List is not empty */
		q = &table[i];
		p = table[i];
		while (p != NULL && (res = STRCMP(item.key, p->item.key))) {
			prcnt++;
			q = &(p->next);
			p = p->next;
		}

		if (p != NULL && res == 0)	/* Item has been found */
			RETURN(&(p->item));
		else {			/* Item is not yet on list */
			if (action == FIND)
				RETURN((ENTRY *) NULL);
			else
#ifdef START
				RETURN(build(&table[i], table[i], item));
#else
				RETURN(build(q, p, item));
#endif
		}
	}
}

static ENTRY
*build(last, next, item)
NODE **last;		/* Where to store in last list item */
NODE *next;		/* Link to next list item */
ENTRY item;		/* Item to be kept in node */
{
	/*
	 * This is a locking vs malloc() violation.
	 * Fortunately, it is not actually compiled.
	 */
	NODE *p = (NODE *) malloc(sizeof (NODE));

	if (p != NULL) {
		p->item = item;
		*last = p;
		p->next = next;
		return (&(p->item));
	} else
		return (NULL);
}
#endif

#ifdef DIV
static unsigned int
hashd(key)		/* Division hashing scheme */
POINTER key;		/* Key to be hashed */
{
    return (crunch(key) % length);
}
#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
hashm(POINTER key)	/* Multiplication hashing scheme */
	/* "key" to be hashed */
{
	return ((int)(((unsigned)(crunch(key) * FACTOR)) >> SHIFT));
}

/*
 * Secondary hashing, for use with multiplicitive hashing scheme.
 * Adapted from Knuth, Volume 3, section 6.4.
 */

static unsigned int
hash2m(POINTER key)	/* Secondary hashing routine */
	/* "key" is the string to be hashed */
{
    return (((unsigned int)((crunch(key) * FACTOR) << m) >> SHIFT) | 1);
}
#endif
#endif

/* PJ Weinberger's hash function */
static unsigned int
crunch(POINTER key)	/* Convert multicharacter key to unsigned int */
{
	unsigned int h = 0;
	unsigned int g;
	unsigned char *p = (unsigned char *)key;

	for (; *p; p++) {
		h = (h << 4) + *p;
		g = h & 0xf0000000;
		if (g != 0) {
			h ^= (g >> 24);
			h ^= g;
		}
	}
	return (h);
}

#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
		if (table[i].key == NULL)
			printf("%o.\t-,\t-,\t(NULL)\n", i);
		else {
			unsigned int oldpr = prcnt;
				/* Save current probe count */

			hsearch(table[i], FIND);
			sum += prcnt;
			printf("%o.\t%d,\t%d,\t%s\n", i,
			    *table[i].data, prcnt, table[i].key);
			prcnt = oldpr;
		}
	printf("Total probes = %d\n", sum);
#else
#ifdef CHAINED
	if (table[i] == NULL)
		printf("%o.\t-,\t-,\t(NULL)\n", i);
	else {
		printf("%o.", i);
		for (a = table[i]; a != NULL; a = a->next)
			printf("\t%d,\t%#0.4x,\t%s\n",
			    *a->item.data, a, a->item.key);
	}
#endif
#endif
}
#endif