2N/A * The contents of this file are subject to the terms of the 2N/A * Common Development and Distribution License (the "License"). 2N/A * You may not use this file except in compliance with the License. 2N/A * See the License for the specific language governing permissions 2N/A * and limitations under the License. 2N/A * When distributing Covered Code, include this CDDL HEADER in each 2N/A * If applicable, add the following below this CDDL HEADER, with the 2N/A * fields enclosed by brackets "[]" replaced with your own identifying 2N/A * information: Portions Copyright [yyyy] [name of copyright owner] 2N/A * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 2N/A * Use is subject to license terms. 2N/A/* Copyright (c) 1988 AT&T */ 2N/A/* All Rights Reserved */ 2N/A * Compile time switches: 2N/A * MULT - use a multiplicative hashing function. 2N/A * DIV - use the remainder mod table size as a hashing function. 2N/A * CHAINED - use a linked list to resolve collisions. 2N/A * OPEN - use open addressing to resolve collisions. 2N/A * BRENT - use Brent's modification to improve the OPEN algorithm. 2N/A * SORTUP - CHAINED list is sorted in increasing order. 2N/A * SORTDOWN - CHAINED list is sorted in decreasing order. 2N/A * START - CHAINED list with entries appended at front. 2N/A * DRIVER - compile in a main program to drive the tests. 2N/A * DEBUG - compile some debugging printout statements. 2N/A * USCR - user supplied comparison routine. 2N/A#
define FACTOR 0
35761254233 /* Magic multiplication factor */ 2N/A#
define HASH2(A)
1 /* Secondary hash function */ 2N/Atypedef struct node {
/* Part of the linked list of entries */ 2N/Astatic unsigned int count = 0;
/* Number of entries in hash table */ 2N/Astatic unsigned int length;
/* Size of the hash table */ 2N/Astatic unsigned int m;
/* Log base 2 of length */ 2N/Astatic unsigned int prcnt;
/* Number of probes this item */ 2N/A * forward declarations 2N/A char line[
80];
/* Room for the input line */ 2N/A int i = 0;
/* Data generator */ 2N/A /* Minimum "size" for hash table */ 2N/Ahdestroy(
void)
/* Reset the module to its initial state */ 2N/A * This is a locking vs malloc() violation. 2N/A * Fortunately, it is not actually compiled. 2N/A * Hash search of a fixed-capacity table. Open addressing used to 2N/A * resolve collisions. Algorithm modified from Knuth, Volume 3, 2N/A * section 6.4, algorithm D. Labels flag corresponding actions. 2N/A/* Find or insert the item into the table */ 2N/A /* "item" to be inserted or found */ 2N/A /* action: FIND or ENTER */ 2N/A unsigned int i;
/* Insertion index */ 2N/A unsigned int c;
/* Secondary probe displacement */ 2N/A i = (i + c) %
length;
/* Advance to next slot */ 2N/A * Brent's variation of the open addressing algorithm. Do extra 2N/A * work during insertion to speed retrieval. May require switching 2N/A * of previously placed items. Adapted from Knuth, Volume 3, section 2N/A * 4.6 and Brent's article in CACM, volume 10, #2, February 1973. 2N/A unsigned int r =
prcnt -
1;
/* Current minimum distance */ 2N/A unsigned int j;
/* Counts along main branch */ 2N/A unsigned int k;
/* Counts along secondary branch */ 2N/A unsigned int curj;
/* Current best main branch site */ 2N/A unsigned int curpos;
/* Current best table index */ 2N/A unsigned int pj;
/* Main branch indices */ 2N/A unsigned int cj;
/* Secondary branch increment distance */ 2N/A unsigned int pjk;
/* Secondary branch probe indices */ 2N/A for (j = 0; j <
prcnt; j++) {
/* Count along main branch */ 2N/A for (k =
1; j+k <= r; k++) {
2N/A /* Count on secondary branch */ 2N/A /* Secondary probe */ 2N/A /* Improvement found */ 2N/A r = j + k;
/* Decrement upper bound */ 2N/A /* Save secondeary index */ 2N/A if (r !=
prcnt -
1) {
/* If an improvement occurred */ 2N/A printf(
"Switch curpos = %o, curj = %o, oldi = %o\n",
2N/A count++;
/* Increment table occupancy count */ 2N/A return (&
table[i]);
/* Address of item is returned */ 2N/A NODE *p;
/* Searches through the linked list */ 2N/A NODE **q;
/* Where to store the pointer to a new NODE */ 2N/A unsigned int i;
/* Result of hash */ 2N/A int res;
/* Result of string comparison */ 2N/A }
else {
/* List is not empty */ 2N/A if (p !=
NULL &&
res == 0)
/* Item has been found */ 2N/A else {
/* Item is not yet on list */ 2N/A * This is a locking vs malloc() violation. 2N/A * Fortunately, it is not actually compiled. 2N/A * NOTE: The following algorithm only works on machines where 2N/A * the results of multiplying two integers is the least 2N/A * significant part of the double word integer required to hold 2N/A * the result. It is adapted from Knuth, Volume 3, section 6.4. 2N/A /* "key" to be hashed */ 2N/A * Secondary hashing, for use with multiplicitive hashing scheme. 2N/A * Adapted from Knuth, Volume 3, section 6.4. 2N/A /* "key" is the string to be hashed */ 2N/A/* PJ Weinberger's hash function */ 2N/A unsigned char *p = (
unsigned char *)
key;
2N/Ahdump()
/* Dumps loc, data, probe count, key */ 2N/A unsigned int i;
/* Counts table slots */ 2N/A unsigned int sum = 0;
/* Counts probes */ 2N/A NODE *a;
/* Current Node on list */ 2N/A /* Save current probe count */