Coverage Report

Created: 2024-11-21 07:03

/src/nss-nspr/nspr/lib/ds/plhash.c
Line
Count
Source (jump to first uncovered line)
1
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2
/* This Source Code Form is subject to the terms of the Mozilla Public
3
 * License, v. 2.0. If a copy of the MPL was not distributed with this
4
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6
/*
7
 * PL hash table package.
8
 */
9
#include "plhash.h"
10
#include "prbit.h"
11
#include "prlog.h"
12
#include "prmem.h"
13
#include "prtypes.h"
14
#include <stdlib.h>
15
#include <string.h>
16
17
/* Compute the number of buckets in ht */
18
876
#define NBUCKETS(ht) (1 << (PL_HASH_BITS - (ht)->shift))
19
20
/* The smallest table has 16 buckets */
21
54
#define MINBUCKETSLOG2 4
22
34
#define MINBUCKETS (1 << MINBUCKETSLOG2)
23
24
/* Compute the maximum entries given n buckets that we will tolerate, ~90% */
25
876
#define OVERLOADED(n) ((n) - ((n) >> 3))
26
27
/* Compute the number of entries below which we shrink the table by half */
28
0
#define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
29
30
/*
31
** Stubs for default hash allocator ops.
32
*/
33
52
static void* PR_CALLBACK DefaultAllocTable(void* pool, PRSize size) {
34
52
  return PR_MALLOC(size);
35
52
}
36
37
16
static void PR_CALLBACK DefaultFreeTable(void* pool, void* item) {
38
16
  PR_Free(item);
39
16
}
40
41
876
static PLHashEntry* PR_CALLBACK DefaultAllocEntry(void* pool, const void* key) {
42
876
  return PR_NEW(PLHashEntry);
43
876
}
44
45
static void PR_CALLBACK DefaultFreeEntry(void* pool, PLHashEntry* he,
46
140
                                         PRUintn flag) {
47
140
  if (flag == HT_FREE_ENTRY) {
48
0
    PR_Free(he);
49
0
  }
50
140
}
51
52
static PLHashAllocOps defaultHashAllocOps = {
53
    DefaultAllocTable, DefaultFreeTable, DefaultAllocEntry, DefaultFreeEntry};
54
55
PR_IMPLEMENT(PLHashTable*)
56
PL_NewHashTable(PRUint32 n, PLHashFunction keyHash, PLHashComparator keyCompare,
57
                PLHashComparator valueCompare, const PLHashAllocOps* allocOps,
58
34
                void* allocPriv) {
59
34
  PLHashTable* ht;
60
34
  PRSize nb;
61
62
34
  if (n <= MINBUCKETS) {
63
20
    n = MINBUCKETSLOG2;
64
20
  } else {
65
14
    n = PR_CeilingLog2(n);
66
14
    if ((PRInt32)n < 0) {
67
0
      return 0;
68
0
    }
69
14
  }
70
71
34
  if (!allocOps) {
72
18
    allocOps = &defaultHashAllocOps;
73
18
  }
74
75
34
  ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht));
76
34
  if (!ht) {
77
0
    return 0;
78
0
  }
79
34
  memset(ht, 0, sizeof *ht);
80
34
  ht->shift = PL_HASH_BITS - n;
81
34
  n = 1 << n;
82
34
  nb = n * sizeof(PLHashEntry*);
83
34
  ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb));
84
34
  if (!ht->buckets) {
85
0
    (*allocOps->freeTable)(allocPriv, ht);
86
0
    return 0;
87
0
  }
88
34
  memset(ht->buckets, 0, nb);
89
90
34
  ht->keyHash = keyHash;
91
34
  ht->keyCompare = keyCompare;
92
34
  ht->valueCompare = valueCompare;
93
34
  ht->allocOps = allocOps;
94
34
  ht->allocPriv = allocPriv;
95
34
  return ht;
96
34
}
97
98
PR_IMPLEMENT(void)
99
0
PL_HashTableDestroy(PLHashTable* ht) {
100
0
  PRUint32 i, n;
101
0
  PLHashEntry *he, *next;
102
0
  const PLHashAllocOps* allocOps = ht->allocOps;
103
0
  void* allocPriv = ht->allocPriv;
104
105
0
  n = NBUCKETS(ht);
106
0
  for (i = 0; i < n; i++) {
107
0
    for (he = ht->buckets[i]; he; he = next) {
108
0
      next = he->next;
109
0
      (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
110
0
    }
111
0
  }
112
0
#ifdef DEBUG
113
0
  memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
114
0
#endif
115
0
  (*allocOps->freeTable)(allocPriv, ht->buckets);
116
0
#ifdef DEBUG
117
0
  memset(ht, 0xDB, sizeof *ht);
118
0
#endif
119
0
  (*allocOps->freeTable)(allocPriv, ht);
120
0
}
121
122
/*
123
** Multiplicative hash, from Knuth 6.4.
124
*/
125
7.02k
#define GOLDEN_RATIO 0x9E3779B9U /* 2/(1+sqrt(5))*(2^32) */
126
127
PR_IMPLEMENT(PLHashEntry**)
128
2.11k
PL_HashTableRawLookup(PLHashTable* ht, PLHashNumber keyHash, const void* key) {
129
2.11k
  PLHashEntry *he, **hep, **hep0;
130
2.11k
  PLHashNumber h;
131
132
#ifdef HASHMETER
133
  ht->nlookups++;
134
#endif
135
2.11k
  h = keyHash * GOLDEN_RATIO;
136
2.11k
  h >>= ht->shift;
137
2.11k
  hep = hep0 = &ht->buckets[h];
138
2.77k
  while ((he = *hep) != 0) {
139
804
    if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
140
      /* Move to front of chain if not already there */
141
140
      if (hep != hep0) {
142
6
        *hep = he->next;
143
6
        he->next = *hep0;
144
6
        *hep0 = he;
145
6
      }
146
140
      return hep0;
147
140
    }
148
664
    hep = &he->next;
149
#ifdef HASHMETER
150
    ht->nsteps++;
151
#endif
152
664
  }
153
1.97k
  return hep;
154
2.11k
}
155
156
/*
157
** Same as PL_HashTableRawLookup but doesn't reorder the hash entries.
158
*/
159
PR_IMPLEMENT(PLHashEntry**)
160
PL_HashTableRawLookupConst(PLHashTable* ht, PLHashNumber keyHash,
161
4.91k
                           const void* key) {
162
4.91k
  PLHashEntry *he, **hep;
163
4.91k
  PLHashNumber h;
164
165
#ifdef HASHMETER
166
  ht->nlookups++;
167
#endif
168
4.91k
  h = keyHash * GOLDEN_RATIO;
169
4.91k
  h >>= ht->shift;
170
4.91k
  hep = &ht->buckets[h];
171
5.06k
  while ((he = *hep) != 0) {
172
5.06k
    if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
173
4.91k
      break;
174
4.91k
    }
175
148
    hep = &he->next;
176
#ifdef HASHMETER
177
    ht->nsteps++;
178
#endif
179
148
  }
180
4.91k
  return hep;
181
4.91k
}
182
183
PR_IMPLEMENT(PLHashEntry*)
184
PL_HashTableRawAdd(PLHashTable* ht, PLHashEntry** hep, PLHashNumber keyHash,
185
876
                   const void* key, void* value) {
186
876
  PRUint32 i, n;
187
876
  PLHashEntry *he, *next, **oldbuckets;
188
876
  PRSize nb;
189
190
  /* Grow the table if it is overloaded */
191
876
  n = NBUCKETS(ht);
192
876
  if (ht->nentries >= OVERLOADED(n)) {
193
16
    oldbuckets = ht->buckets;
194
16
    nb = 2 * n * sizeof(PLHashEntry*);
195
16
    ht->buckets =
196
16
        (PLHashEntry**)((*ht->allocOps->allocTable)(ht->allocPriv, nb));
197
16
    if (!ht->buckets) {
198
0
      ht->buckets = oldbuckets;
199
0
      return 0;
200
0
    }
201
16
    memset(ht->buckets, 0, nb);
202
#ifdef HASHMETER
203
    ht->ngrows++;
204
#endif
205
16
    ht->shift--;
206
207
1.23k
    for (i = 0; i < n; i++) {
208
2.28k
      for (he = oldbuckets[i]; he; he = next) {
209
1.06k
        next = he->next;
210
1.06k
        hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
211
1.06k
        PR_ASSERT(*hep == 0);
212
1.06k
        he->next = 0;
213
1.06k
        *hep = he;
214
1.06k
      }
215
1.21k
    }
216
16
#ifdef DEBUG
217
16
    memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
218
16
#endif
219
16
    (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
220
16
    hep = PL_HashTableRawLookup(ht, keyHash, key);
221
16
  }
222
223
  /* Make a new key value entry */
224
876
  he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
225
876
  if (!he) {
226
0
    return 0;
227
0
  }
228
876
  he->keyHash = keyHash;
229
876
  he->key = key;
230
876
  he->value = value;
231
876
  he->next = *hep;
232
876
  *hep = he;
233
876
  ht->nentries++;
234
876
  return he;
235
876
}
236
237
PR_IMPLEMENT(PLHashEntry*)
238
1.01k
PL_HashTableAdd(PLHashTable* ht, const void* key, void* value) {
239
1.01k
  PLHashNumber keyHash;
240
1.01k
  PLHashEntry *he, **hep;
241
242
1.01k
  keyHash = (*ht->keyHash)(key);
243
1.01k
  hep = PL_HashTableRawLookup(ht, keyHash, key);
244
1.01k
  if ((he = *hep) != 0) {
245
    /* Hit; see if values match */
246
140
    if ((*ht->valueCompare)(he->value, value)) {
247
      /* key,value pair is already present in table */
248
0
      return he;
249
0
    }
250
140
    if (he->value) {
251
140
      (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
252
140
    }
253
140
    he->value = value;
254
140
    return he;
255
140
  }
256
876
  return PL_HashTableRawAdd(ht, hep, keyHash, key, value);
257
1.01k
}
258
259
PR_IMPLEMENT(void)
260
0
PL_HashTableRawRemove(PLHashTable* ht, PLHashEntry** hep, PLHashEntry* he) {
261
0
  PRUint32 i, n;
262
0
  PLHashEntry *next, **oldbuckets;
263
0
  PRSize nb;
264
265
0
  *hep = he->next;
266
0
  (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);
267
268
  /* Shrink table if it's underloaded */
269
0
  n = NBUCKETS(ht);
270
0
  if (--ht->nentries < UNDERLOADED(n)) {
271
0
    oldbuckets = ht->buckets;
272
0
    nb = n * sizeof(PLHashEntry*) / 2;
273
0
    ht->buckets =
274
0
        (PLHashEntry**)((*ht->allocOps->allocTable)(ht->allocPriv, nb));
275
0
    if (!ht->buckets) {
276
0
      ht->buckets = oldbuckets;
277
0
      return;
278
0
    }
279
0
    memset(ht->buckets, 0, nb);
280
#ifdef HASHMETER
281
    ht->nshrinks++;
282
#endif
283
0
    ht->shift++;
284
285
0
    for (i = 0; i < n; i++) {
286
0
      for (he = oldbuckets[i]; he; he = next) {
287
0
        next = he->next;
288
0
        hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
289
0
        PR_ASSERT(*hep == 0);
290
0
        he->next = 0;
291
0
        *hep = he;
292
0
      }
293
0
    }
294
0
#ifdef DEBUG
295
0
    memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
296
0
#endif
297
0
    (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
298
0
  }
299
0
}
300
301
PR_IMPLEMENT(PRBool)
302
0
PL_HashTableRemove(PLHashTable* ht, const void* key) {
303
0
  PLHashNumber keyHash;
304
0
  PLHashEntry *he, **hep;
305
306
0
  keyHash = (*ht->keyHash)(key);
307
0
  hep = PL_HashTableRawLookup(ht, keyHash, key);
308
0
  if ((he = *hep) == 0) {
309
0
    return PR_FALSE;
310
0
  }
311
312
  /* Hit; remove element */
313
0
  PL_HashTableRawRemove(ht, hep, he);
314
0
  return PR_TRUE;
315
0
}
316
317
PR_IMPLEMENT(void*)
318
16
PL_HashTableLookup(PLHashTable* ht, const void* key) {
319
16
  PLHashNumber keyHash;
320
16
  PLHashEntry *he, **hep;
321
322
16
  keyHash = (*ht->keyHash)(key);
323
16
  hep = PL_HashTableRawLookup(ht, keyHash, key);
324
16
  if ((he = *hep) != 0) {
325
0
    return he->value;
326
0
  }
327
16
  return 0;
328
16
}
329
330
/*
331
** Same as PL_HashTableLookup but doesn't reorder the hash entries.
332
*/
333
PR_IMPLEMENT(void*)
334
4.91k
PL_HashTableLookupConst(PLHashTable* ht, const void* key) {
335
4.91k
  PLHashNumber keyHash;
336
4.91k
  PLHashEntry *he, **hep;
337
338
4.91k
  keyHash = (*ht->keyHash)(key);
339
4.91k
  hep = PL_HashTableRawLookupConst(ht, keyHash, key);
340
4.91k
  if ((he = *hep) != 0) {
341
4.91k
    return he->value;
342
4.91k
  }
343
0
  return 0;
344
4.91k
}
345
346
/*
347
** Iterate over the entries in the hash table calling func for each
348
** entry found. Stop if "f" says to (return value & PR_ENUMERATE_STOP).
349
** Return a count of the number of elements scanned.
350
*/
351
PR_IMPLEMENT(int)
352
0
PL_HashTableEnumerateEntries(PLHashTable* ht, PLHashEnumerator f, void* arg) {
353
0
  PLHashEntry *he, **hep;
354
0
  PRUint32 i, nbuckets;
355
0
  int rv, n = 0;
356
0
  PLHashEntry* todo = 0;
357
358
0
  nbuckets = NBUCKETS(ht);
359
0
  for (i = 0; i < nbuckets; i++) {
360
0
    hep = &ht->buckets[i];
361
0
    while ((he = *hep) != 0) {
362
0
      rv = (*f)(he, n, arg);
363
0
      n++;
364
0
      if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
365
0
        *hep = he->next;
366
0
        if (rv & HT_ENUMERATE_REMOVE) {
367
0
          he->next = todo;
368
0
          todo = he;
369
0
        }
370
0
      } else {
371
0
        hep = &he->next;
372
0
      }
373
0
      if (rv & HT_ENUMERATE_STOP) {
374
0
        goto out;
375
0
      }
376
0
    }
377
0
  }
378
379
0
out:
380
0
  hep = &todo;
381
0
  while ((he = *hep) != 0) {
382
0
    PL_HashTableRawRemove(ht, hep, he);
383
0
  }
384
0
  return n;
385
0
}
386
387
#ifdef HASHMETER
388
#  include <math.h>
389
#  include <stdio.h>
390
391
PR_IMPLEMENT(void)
392
PL_HashTableDumpMeter(PLHashTable* ht, PLHashEnumerator dump, FILE* fp) {
393
  double mean, variance;
394
  PRUint32 nchains, nbuckets;
395
  PRUint32 i, n, maxChain, maxChainLen;
396
  PLHashEntry* he;
397
398
  variance = 0;
399
  nchains = 0;
400
  maxChainLen = 0;
401
  nbuckets = NBUCKETS(ht);
402
  for (i = 0; i < nbuckets; i++) {
403
    he = ht->buckets[i];
404
    if (!he) {
405
      continue;
406
    }
407
    nchains++;
408
    for (n = 0; he; he = he->next) {
409
      n++;
410
    }
411
    variance += n * n;
412
    if (n > maxChainLen) {
413
      maxChainLen = n;
414
      maxChain = i;
415
    }
416
  }
417
  mean = (double)ht->nentries / nchains;
418
  variance = fabs(variance / nchains - mean * mean);
419
420
  fprintf(fp, "\nHash table statistics:\n");
421
  fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
422
  fprintf(fp, "     number of entries: %u\n", ht->nentries);
423
  fprintf(fp, "       number of grows: %u\n", ht->ngrows);
424
  fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
425
  fprintf(fp, "   mean steps per hash: %g\n",
426
          (double)ht->nsteps / ht->nlookups);
427
  fprintf(fp, "mean hash chain length: %g\n", mean);
428
  fprintf(fp, "    standard deviation: %g\n", sqrt(variance));
429
  fprintf(fp, " max hash chain length: %u\n", maxChainLen);
430
  fprintf(fp, "        max hash chain: [%u]\n", maxChain);
431
432
  for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
433
    if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT) {
434
      break;
435
    }
436
}
437
#endif /* HASHMETER */
438
439
PR_IMPLEMENT(int)
440
0
PL_HashTableDump(PLHashTable* ht, PLHashEnumerator dump, FILE* fp) {
441
0
  int count;
442
443
0
  count = PL_HashTableEnumerateEntries(ht, dump, fp);
444
#ifdef HASHMETER
445
  PL_HashTableDumpMeter(ht, dump, fp);
446
#endif
447
0
  return count;
448
0
}
449
450
PR_IMPLEMENT(PLHashNumber)
451
0
PL_HashString(const void* key) {
452
0
  PLHashNumber h;
453
0
  const PRUint8* s;
454
455
0
  h = 0;
456
0
  for (s = (const PRUint8*)key; *s; s++) {
457
0
    h = PR_ROTATE_LEFT32(h, 4) ^ *s;
458
0
  }
459
0
  return h;
460
0
}
461
462
PR_IMPLEMENT(int)
463
0
PL_CompareStrings(const void* v1, const void* v2) {
464
0
  return strcmp((const char*)v1, (const char*)v2) == 0;
465
0
}
466
467
PR_IMPLEMENT(int)
468
4.12k
PL_CompareValues(const void* v1, const void* v2) { return v1 == v2; }