File: hash.h

package info (click to toggle)
magic 7.5.220-1
  • links: PTS
  • area: main
  • in suites: wheezy
  • size: 17,860 kB
file content (135 lines) | stat: -rw-r--r-- 4,749 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/* hash.h --
 *
 *     ********************************************************************* 
 *     * Copyright (C) 1985, 1990 Regents of the University of California. * 
 *     * Permission to use, copy, modify, and distribute this              * 
 *     * software and its documentation for any purpose and without        * 
 *     * fee is hereby granted, provided that the above copyright          * 
 *     * notice appear in all copies.  The University of California        * 
 *     * makes no representations about the suitability of this            * 
 *     * software for any purpose.  It is provided "as is" without         * 
 *     * express or implied warranty.  Export of this software outside     * 
 *     * of the United States of America may require an export license.    * 
 *     *********************************************************************
 *
 * This file contains definitions used by the hash module,
 * which maintains hash tables.
 */

/* rcsid "$Header: /usr/cvsroot/magic-7.5/utils/hash.h,v 1.1.1.1 2006/04/10 22:03:14 tim Exp $" */

#ifndef	_HASH_H
#define	_HASH_H

/*---------------------------------------------------------
 *	This first stuff should only be used internally
 *	in the hash routines.
 *---------------------------------------------------------
 */

/* The following defines one entry in the hash table. */

typedef struct h1
{
    char *h_pointer;		/* Pointer to anything. */
    struct h1 *h_next;		/* Next element, zero for end. */
    union
    {
	char *h_ptr;		/* One-word key value to identify entry. */
	unsigned h_words[1];	/* N-word key value.  Note: the actual
				 * size may be longer if necessary to hold
				 * the entire key.
				 */
	char h_name[4];		/* Text name of this entry.  Note: the
				 * actual size may be longer if necessary
				 * to hold the whole string. This MUST be
				 * the last entry in the structure!!!
				 */
    } h_key;
} HashEntry;

/* A hash table consists of an array of pointers to hash
 * lists:
 */

typedef struct h3
{
    HashEntry **ht_table;	/* Pointer to array of pointers. */
    int ht_size;		/* Actual size of array. */
    int ht_nEntries;		/* Number of entries in the table. */
    int ht_downShift;		/* Shift count, used in hashing function. */
    int ht_mask;		/* Used to select bits for hashing. */
    int ht_ptrKeys;		/* See below */

    /* Used if ht_ptrKeys == HT_CLIENTKEYS */
    char *(*ht_copyFn)();	/* Used for copying a key value */
    int (*ht_compareFn)();	/* Used for comparing two keys for equality */
    int (*ht_hashFn)();		/* Hash function */
    int (*ht_killFn)();		/* Used to kill an entry */
} HashTable;

/*
 * Values for ht_ptrKeys.
 *
 * HT_STRINGKEYS means that keys are NULL-terminated strings stored
 * in the variable-sized array h_key.h_name at the end of a HashEntry.
 *
 * HT_WORDKEYS and HT_CLIENTKEYS both mean that the value is stored
 * in h_key.h_ptr; with HT_WORDKEYS it is treated as a one-word value,
 * while with HT_CLIENTKEYS it is interpreted by user-supplied procedures
 * (and hence it can be a pointer).
 *
 * Finally, values of ht_ptrKeys of HT_STRUCTKEYS or greater mean
 * that the key consists of ht_ptrKeys 32-bit words of data, stored
 * in the variable-sized array h_key.h_words.
 */
#define	HT_CLIENTKEYS	-1
#define	HT_STRINGKEYS	0
#define	HT_WORDKEYS	1
#define	HT_STRUCTKEYS	2

/*
 * Default initial size (number of buckets) in a hash table.
 * May be passed to HashInit() or HashInitClient().
 */
#define	HT_DEFAULTSIZE	32

/* The following structure is used by the searching routines
 * to record where we are in the search.
 */

typedef struct h2
{
    int hs_nextIndex;		/* Next bucket to check (after current). */
    HashEntry * hs_h;		/* Next entry to check in current bucket. */
} HashSearch;

/*---------------------------------------------------------
 *	The following procedure declarations and macros
 *	are the only things that should be needed outside
 *	the implementation code.
 *---------------------------------------------------------
 */

extern void HashInit(), HashInitClient(), HashStats(), HashKill(), 
	    HashFreeKill();
extern HashEntry *HashFind();
extern HashEntry *HashLookOnly();
extern void HashStartSearch();
extern HashEntry *HashNext();

/* char * HashGetValue(h); HashEntry *h; */

#define HashGetValue(h) ((h)->h_pointer)

/* HashSetValue(h, val); HashEntry *h; char *val; */

#define HashSetValue(h, val) ((h)->h_pointer = (char *) (val))

/* HashSize(n) returns the number of words in an object of n bytes */
#define	HashSize(n)	(((n) + sizeof (unsigned) - 1) / sizeof (unsigned))

/* HashGetNumEntries(ht); HashTable *ht ; returns number of entries in table */
#define	HashGetNumEntries(ht)	((ht)->ht_nEntries)

#endif	/* _HASH_H */