home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / nsprpub / lib / ds / plhash.h < prev   
Encoding:
C/C++ Source or Header  |  1998-04-08  |  5.0 KB  |  132 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /*
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  * 
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  * 
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. #ifndef plhash_h___
  20. #define plhash_h___
  21. /*
  22.  * API to portable hash table code.
  23.  */
  24. #include <stddef.h>
  25. #include <stdio.h>
  26. #include "prtypes.h"
  27.  
  28. PR_BEGIN_EXTERN_C
  29.  
  30. typedef struct PLHashEntry  PLHashEntry;
  31. typedef struct PLHashTable  PLHashTable;
  32. typedef PRUint32 PLHashNumber;
  33. #define PL_HASH_BITS 32
  34. typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key);
  35. typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2);
  36. typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg);
  37.  
  38. /* Flag bits in PLHashEnumerator's return value */
  39. #define HT_ENUMERATE_NEXT       0       /* continue enumerating entries */
  40. #define HT_ENUMERATE_STOP       1       /* stop enumerating entries */
  41. #define HT_ENUMERATE_REMOVE     2       /* remove and free the current entry */
  42. #define HT_ENUMERATE_UNHASH     4       /* just unhash the current entry */
  43.  
  44. typedef struct PLHashAllocOps {
  45.     void *              (PR_CALLBACK *allocTable)(void *pool, PRSize size);
  46.     void                (PR_CALLBACK *freeTable)(void *pool, void *item);
  47.     PLHashEntry *       (PR_CALLBACK *allocEntry)(void *pool, const void *key);
  48.     void                (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag);
  49. } PLHashAllocOps;
  50.  
  51. #define HT_FREE_VALUE   0               /* just free the entry's value */
  52. #define HT_FREE_ENTRY   1               /* free value and entire entry */
  53.  
  54. struct PLHashEntry {
  55.     PLHashEntry         *next;          /* hash chain linkage */
  56.     PLHashNumber        keyHash;        /* key hash function result */
  57.     const void          *key;           /* ptr to opaque key */
  58.     void                *value;         /* ptr to opaque value */
  59. };
  60.  
  61. struct PLHashTable {
  62.     PLHashEntry         **buckets;      /* vector of hash buckets */
  63.     PRUint32              nentries;       /* number of entries in table */
  64.     PRUint32              shift;          /* multiplicative hash shift */
  65.     PLHashFunction      keyHash;        /* key hash function */
  66.     PLHashComparator    keyCompare;     /* key comparison function */
  67.     PLHashComparator    valueCompare;   /* value comparison function */
  68.     PLHashAllocOps      *allocOps;      /* allocation operations */
  69.     void                *allocPriv;     /* allocation private data */
  70. #ifdef HASHMETER
  71.     PRUint32              nlookups;       /* total number of lookups */
  72.     PRUint32              nsteps;         /* number of hash chains traversed */
  73.     PRUint32              ngrows;         /* number of table expansions */
  74.     PRUint32              nshrinks;       /* number of table contractions */
  75. #endif
  76. };
  77.  
  78. /*
  79.  * Create a new hash table.
  80.  * If allocOps is null, use default allocator ops built on top of malloc().
  81.  */
  82. PR_EXTERN(PLHashTable *)
  83. PL_NewHashTable(PRUint32 n, PLHashFunction keyHash,
  84.                 PLHashComparator keyCompare, PLHashComparator valueCompare,
  85.                 PLHashAllocOps *allocOps, void *allocPriv);
  86.  
  87. PR_EXTERN(void)
  88. PL_HashTableDestroy(PLHashTable *ht);
  89.  
  90. /* Low level access methods */
  91. PR_EXTERN(PLHashEntry **)
  92. PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key);
  93.  
  94. PR_EXTERN(PLHashEntry *)
  95. PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash,
  96.                    const void *key, void *value);
  97.  
  98. PR_EXTERN(void)
  99. PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he);
  100.  
  101. /* Higher level access methods */
  102. PR_EXTERN(PLHashEntry *)
  103. PL_HashTableAdd(PLHashTable *ht, const void *key, void *value);
  104.  
  105. PR_EXTERN(PRBool)
  106. PL_HashTableRemove(PLHashTable *ht, const void *key);
  107.  
  108. PR_EXTERN(PRIntn)
  109. PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg);
  110.  
  111. PR_EXTERN(void *)
  112. PL_HashTableLookup(PLHashTable *ht, const void *key);
  113.  
  114. PR_EXTERN(PRIntn)
  115. PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp);
  116.  
  117. /* General-purpose C string hash function. */
  118. PR_EXTERN(PLHashNumber)
  119. PL_HashString(const void *key);
  120.  
  121. /* Compare strings using strcmp(), return true if equal. */
  122. PR_EXTERN(int)
  123. PL_CompareStrings(const void *v1, const void *v2);
  124.  
  125. /* Stub function just returns v1 == v2 */
  126. PR_EXTERN(PRIntn)
  127. PL_CompareValues(const void *v1, const void *v2);
  128.  
  129. PR_END_EXTERN_C
  130.  
  131. #endif /* plhash_h___ */
  132.