1 // ************************************************************************
2 //
3 // Copyright (c) 1995-2002 Juniper Networks, Inc. All rights reserved.
4 //
5 // Permission is hereby granted, without written agreement and without
6 // license or royalty fees, to use, copy, modify, and distribute this
7 // software and its documentation for any purpose, provided that the
8 // above copyright notice and the following three paragraphs appear in
9 // all copies of this software.
10 //
11 // IN NO EVENT SHALL JUNIPER NETWORKS, INC. BE LIABLE TO ANY PARTY FOR
12 // DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
13 // ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
14 // JUNIPER NETWORKS, INC. HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
15 // DAMAGE.
16 //
17 // JUNIPER NETWORKS, INC. SPECIFICALLY DISCLAIMS ANY WARRANTIES,
18 // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
20 // NON-INFRINGEMENT.
21 //
22 // THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND JUNIPER
23 // NETWORKS, INC. HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
24 // UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
25 //
26 // ************************************************************************
27
28
29
30 /* ihash.h --
31 *
32 * "Internal" hash routines.
33 * Allows hashing of existing structs without creating parallel structs
34 * to hold keys etc.
35 *
36 * The structs to be hashed must have "key" and "next" fields. The offsets
37 * of these fields are passed to HashInit.
38 */
39
40 /* rcsid "$Header$" */
41
42 #ifndef _IHASH_H
43 #define _IHASH_H
44
45 /* returns total memory required for malloc of given size, for */
46 /* routine IHashStat2() only. */
47
IHashAlignedSize(int size)48 static __inline__ int IHashAlignedSize(int size)
49 {
50 int result;
51 /* Expand size to be double-word (64 bit) aligned */
52 result = ((size + 7) / 8) * 8;
53 return result;
54 }
55
56 /* The IHashTable struct should not be manipulated directly by clients */
57
58 typedef struct ihashtable
59 {
60 void **iht_table; /* Pointer to array of pointers. */
61 int iht_nBucketsInit; /* Initial size of array. */
62 int iht_nBuckets; /* Size of array. */
63 int iht_nEntries; /* Number of hashed items */
64 int iht_keyOffset; /* offset of keys in client strucs */
65 int iht_nextOffset; /* offset of next fields in client strucs */
66 int (*iht_hashFn)(void *key); /* Hash function */
67 int (*iht_sameKeyFn)(void *key1, void *key2); /* returns 1 if keys match */
68
69 } IHashTable;
70
71 /* create a new hash table */
72 extern IHashTable *IHashInit(
73 int nBuckets,
74 int keyOffset,
75 int nextOffset,
76 int (*hashFn)(void *key),
77 int (*sameKeyFn)(void *key1, void *key2)
78 );
79
80 /* lookup an entry in table (returns first match) */
81 extern void *IHashLookUp(IHashTable *table, void *key);
82
83 /* lookup NEXT matching entry in table */
84 extern void *IHashLookUpNext(IHashTable *table, void *prevEntry);
85
86 /* add an entry to the table */
87 extern void IHashAdd(IHashTable *table, void *entry);
88
89 /* delete an entry from the table */
90 extern void IHashDelete(IHashTable *table, void *entry);
91
92 /* delete all entrys (and restore initial hash table size) */
93 extern void IHashClear(IHashTable *table);
94
95 /* callback supplied func for each entry in table */
96 extern void IHashEnum(IHashTable *table, void (*clientFunc)(void *entry));
97
98 /* return number of entries in table */
99 extern int IHashEntries(IHashTable *table);
100
101 /* print hash table statistics */
102 extern void IHashStats(IHashTable *table);
103
104 /* return hashtable memory usage and stats */
105 extern int IHashStats2(IHashTable *table, int *nBuckets, int *nEntries);
106
107 /* free hash table (does not free client strucs!) */
108 extern void IHashFree(IHashTable *table);
109
110 /* A hash function suitable for hash key fields that are pointers to strings */
111 extern int IHashStringPKeyHash(void *key);
112
113 /* key comparison function for key fields that are pointers to strings */
114 extern int IHashStringPKeyEq(void *key1, void *key2);
115
116 /* A hash function suitable for hash key fields that are strings */
117 extern int IHashStringKeyHash(void *key);
118
119 /* key comparison function for key fields that are strings */
120 extern int IHashStringKeyEq(void *key1, void *key2);
121
122 /* A hash function suitable for keys that are pointers */
123 extern int IHashWordKeyHash(void *key);
124
125 /* key comparison function for key fields that are pointers */
126 extern int IHashWordKeyEq(void *key1, void *key2);
127
128 /* A hash function suitable for 4 word keys */
129 extern int IHash4WordKeyHash(void *key);
130
131 /* key comparison function for four word keys */
132 extern int IHash4WordKeyEq(void *key1, void *key2);
133 #endif /* _IHASH_H */
134