Return to jsdhash.h CVS log

Up to [Synchronet] / sbbs / javascript / include / mozilla / js

Annotation of sbbs/javascript/include/mozilla/js/jsdhash.h, revision 1.1

1.1     ! root        1: /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
        !             2: /* ***** BEGIN LICENSE BLOCK *****
        !             3:  * Version: NPL 1.1/GPL 2.0/LGPL 2.1
        !             4:  *
        !             5:  * The contents of this file are subject to the Netscape Public License
        !             6:  * Version 1.1 (the "License"); you may not use this file except in
        !             7:  * compliance with the License. You may obtain a copy of the License at
        !             8:  * http://www.mozilla.org/NPL/
        !             9:  *
        !            10:  * Software distributed under the License is distributed on an "AS IS" basis,
        !            11:  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
        !            12:  * for the specific language governing rights and limitations under the
        !            13:  * License.
        !            14:  *
        !            15:  * The Original Code is Mozilla JavaScript code.
        !            16:  *
        !            17:  * The Initial Developer of the Original Code is 
        !            18:  * Netscape Communications Corporation.
        !            19:  * Portions created by the Initial Developer are Copyright (C) 1999-2001
        !            20:  * the Initial Developer. All Rights Reserved.
        !            21:  *
        !            22:  * Contributor(s):
        !            23:  *   Brendan Eich <[email protected]> (Original Author)
        !            24:  *
        !            25:  * Alternatively, the contents of this file may be used under the terms of
        !            26:  * either the GNU General Public License Version 2 or later (the "GPL"), or 
        !            27:  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
        !            28:  * in which case the provisions of the GPL or the LGPL are applicable instead
        !            29:  * of those above. If you wish to allow use of your version of this file only
        !            30:  * under the terms of either the GPL or the LGPL, and not to allow others to
        !            31:  * use your version of this file under the terms of the NPL, indicate your
        !            32:  * decision by deleting the provisions above and replace them with the notice
        !            33:  * and other provisions required by the GPL or the LGPL. If you do not delete
        !            34:  * the provisions above, a recipient may use your version of this file under
        !            35:  * the terms of any one of the NPL, the GPL or the LGPL.
        !            36:  *
        !            37:  * ***** END LICENSE BLOCK ***** */
        !            38: 
        !            39: #ifndef jsdhash_h___
        !            40: #define jsdhash_h___
        !            41: /*
        !            42:  * Double hashing, a la Knuth 6.
        !            43:  */
        !            44: #include "jstypes.h"
        !            45: 
        !            46: JS_BEGIN_EXTERN_C
        !            47: 
        !            48: #ifdef DEBUG_XXXbrendan
        !            49: #define JS_DHASHMETER 1
        !            50: #endif
        !            51: 
        !            52: /* Table size limit, do not equal or exceed (see min&maxAlphaFrac, below). */
        !            53: #undef JS_DHASH_SIZE_LIMIT
        !            54: #define JS_DHASH_SIZE_LIMIT     JS_BIT(24)
        !            55: 
        !            56: /* Minimum table size, or gross entry count (net is at most .75 loaded). */
        !            57: #ifndef JS_DHASH_MIN_SIZE
        !            58: #define JS_DHASH_MIN_SIZE 16
        !            59: #elif (JS_DHASH_MIN_SIZE & (JS_DHASH_MIN_SIZE - 1)) != 0
        !            60: #error "JS_DHASH_MIN_SIZE must be a power of two!"
        !            61: #endif
        !            62: 
        !            63: /*
        !            64:  * Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
        !            65:  * expressed as a fixed-point 32-bit fraction.
        !            66:  */
        !            67: #define JS_DHASH_BITS           32
        !            68: #define JS_DHASH_GOLDEN_RATIO   0x9E3779B9U
        !            69: 
        !            70: /* Primitive and forward-struct typedefs. */
        !            71: typedef uint32                  JSDHashNumber;
        !            72: typedef struct JSDHashEntryHdr  JSDHashEntryHdr;
        !            73: typedef struct JSDHashEntryStub JSDHashEntryStub;
        !            74: typedef struct JSDHashTable     JSDHashTable;
        !            75: typedef struct JSDHashTableOps  JSDHashTableOps;
        !            76: 
        !            77: /*
        !            78:  * Table entry header structure.
        !            79:  *
        !            80:  * In order to allow in-line allocation of key and value, we do not declare
        !            81:  * either here.  Instead, the API uses const void *key as a formal parameter,
        !            82:  * and asks each entry for its key when necessary via a getKey callback, used
        !            83:  * when growing or shrinking the table.  Other callback types are defined
        !            84:  * below and grouped into the JSDHashTableOps structure, for single static
        !            85:  * initialization per hash table sub-type.
        !            86:  *
        !            87:  * Each hash table sub-type should nest the JSDHashEntryHdr structure at the
        !            88:  * front of its particular entry type.  The keyHash member contains the result
        !            89:  * of multiplying the hash code returned from the hashKey callback (see below)
        !            90:  * by JS_DHASH_GOLDEN_RATIO, then constraining the result to avoid the magic 0
        !            91:  * and 1 values.  The stored keyHash value is table size invariant, and it is
        !            92:  * maintained automatically by JS_DHashTableOperate -- users should never set
        !            93:  * it, and its only uses should be via the entry macros below.
        !            94:  *
        !            95:  * The JS_DHASH_ENTRY_IS_LIVE macro tests whether entry is neither free nor
        !            96:  * removed.  An entry may be either busy or free; if busy, it may be live or
        !            97:  * removed.  Consumers of this API should not access members of entries that
        !            98:  * are not live.
        !            99:  *
        !           100:  * However, use JS_DHASH_ENTRY_IS_BUSY for faster liveness testing of entries
        !           101:  * returned by JS_DHashTableOperate, as JS_DHashTableOperate never returns a
        !           102:  * non-live, busy (i.e., removed) entry pointer to its caller.  See below for
        !           103:  * more details on JS_DHashTableOperate's calling rules.
        !           104:  */
        !           105: struct JSDHashEntryHdr {
        !           106:     JSDHashNumber       keyHash;        /* every entry must begin like this */
        !           107: };
        !           108: 
        !           109: #define JS_DHASH_ENTRY_IS_FREE(entry)   ((entry)->keyHash == 0)
        !           110: #define JS_DHASH_ENTRY_IS_BUSY(entry)   (!JS_DHASH_ENTRY_IS_FREE(entry))
        !           111: #define JS_DHASH_ENTRY_IS_LIVE(entry)   ((entry)->keyHash >= 2)
        !           112: 
        !           113: /*
        !           114:  * A JSDHashTable is currently 8 words (without the JS_DHASHMETER overhead)
        !           115:  * on most architectures, and may be allocated on the stack or within another
        !           116:  * structure or class (see below for the Init and Finish functions to use).
        !           117:  *
        !           118:  * To decide whether to use double hashing vs. chaining, we need to develop a
        !           119:  * trade-off relation, as follows:
        !           120:  *
        !           121:  * Let alpha be the load factor, esize the entry size in words, count the
        !           122:  * entry count, and pow2 the power-of-two table size in entries.
        !           123:  *
        !           124:  *   (JSDHashTable overhead)    > (JSHashTable overhead)
        !           125:  *   (unused table entry space) > (malloc and .next overhead per entry) +
        !           126:  *                                (buckets overhead)
        !           127:  *   (1 - alpha) * esize * pow2 > 2 * count + pow2
        !           128:  *
        !           129:  * Notice that alpha is by definition (count / pow2):
        !           130:  *
        !           131:  *   (1 - alpha) * esize * pow2 > 2 * alpha * pow2 + pow2
        !           132:  *   (1 - alpha) * esize        > 2 * alpha + 1
        !           133:  *
        !           134:  *   esize > (1 + 2 * alpha) / (1 - alpha)
        !           135:  *
        !           136:  * This assumes both tables must keep keyHash, key, and value for each entry,
        !           137:  * where key and value point to separately allocated strings or structures.
        !           138:  * If key and value can be combined into one pointer, then the trade-off is:
        !           139:  *
        !           140:  *   esize > (1 + 3 * alpha) / (1 - alpha)
        !           141:  *
        !           142:  * If the entry value can be a subtype of JSDHashEntryHdr, rather than a type
        !           143:  * that must be allocated separately and referenced by an entry.value pointer
        !           144:  * member, and provided key's allocation can be fused with its entry's, then
        !           145:  * k (the words wasted per entry with chaining) is 4.
        !           146:  *
        !           147:  * To see these curves, feed gnuplot input like so:
        !           148:  *
        !           149:  *   gnuplot> f(x,k) = (1 + k * x) / (1 - x)
        !           150:  *   gnuplot> plot [0:.75] f(x,2), f(x,3), f(x,4)
        !           151:  *
        !           152:  * For k of 2 and a well-loaded table (alpha > .5), esize must be more than 4
        !           153:  * words for chaining to be more space-efficient than double hashing.
        !           154:  *
        !           155:  * Solving for alpha helps us decide when to shrink an underloaded table:
        !           156:  *
        !           157:  *   esize                     > (1 + k * alpha) / (1 - alpha)
        !           158:  *   esize - alpha * esize     > 1 + k * alpha
        !           159:  *   esize - 1                 > (k + esize) * alpha
        !           160:  *   (esize - 1) / (k + esize) > alpha
        !           161:  *
        !           162:  *   alpha < (esize - 1) / (esize + k)
        !           163:  *
        !           164:  * Therefore double hashing should keep alpha >= (esize - 1) / (esize + k),
        !           165:  * assuming esize is not too large (in which case, chaining should probably be
        !           166:  * used for any alpha).  For esize=2 and k=3, we want alpha >= .2; for esize=3
        !           167:  * and k=2, we want alpha >= .4.  For k=4, esize could be 6, and alpha >= .5
        !           168:  * would still obtain.  See the JS_DHASH_MIN_ALPHA macro further below.
        !           169:  *
        !           170:  * The current implementation uses a configurable lower bound on alpha, which
        !           171:  * defaults to .25, when deciding to shrink the table (while still respecting
        !           172:  * JS_DHASH_MIN_SIZE).
        !           173:  *
        !           174:  * Note a qualitative difference between chaining and double hashing: under
        !           175:  * chaining, entry addresses are stable across table shrinks and grows.  With
        !           176:  * double hashing, you can't safely hold an entry pointer and use it after an
        !           177:  * ADD or REMOVE operation, unless you sample table->generation before adding
        !           178:  * or removing, and compare the sample after, dereferencing the entry pointer
        !           179:  * only if table->generation has not changed.
        !           180:  *
        !           181:  * The moral of this story: there is no one-size-fits-all hash table scheme,
        !           182:  * but for small table entry size, and assuming entry address stability is not
        !           183:  * required, double hashing wins.
        !           184:  */
        !           185: struct JSDHashTable {
        !           186:     const JSDHashTableOps *ops;         /* virtual operations, see below */
        !           187:     void                *data;          /* ops- and instance-specific data */
        !           188:     int16               hashShift;      /* multiplicative hash shift */
        !           189:     uint8               maxAlphaFrac;   /* 8-bit fixed point max alpha */
        !           190:     uint8               minAlphaFrac;   /* 8-bit fixed point min alpha */
        !           191:     uint32              entrySize;      /* number of bytes in an entry */
        !           192:     uint32              entryCount;     /* number of entries in table */
        !           193:     uint32              removedCount;   /* removed entry sentinels in table */
        !           194:     uint32              generation;     /* entry storage generation number */
        !           195:     char                *entryStore;    /* entry storage */
        !           196: #ifdef JS_DHASHMETER
        !           197:     struct JSDHashStats {
        !           198:         uint32          searches;       /* total number of table searches */
        !           199:         uint32          steps;          /* hash chain links traversed */
        !           200:         uint32          hits;           /* searches that found key */
        !           201:         uint32          misses;         /* searches that didn't find key */
        !           202:         uint32          lookups;        /* number of JS_DHASH_LOOKUPs */
        !           203:         uint32          addMisses;      /* adds that miss, and do work */
        !           204:         uint32          addOverRemoved; /* adds that recycled a removed entry */
        !           205:         uint32          addHits;        /* adds that hit an existing entry */
        !           206:         uint32          addFailures;    /* out-of-memory during add growth */
        !           207:         uint32          removeHits;     /* removes that hit, and do work */
        !           208:         uint32          removeMisses;   /* useless removes that miss */
        !           209:         uint32          removeFrees;    /* removes that freed entry directly */
        !           210:         uint32          removeEnums;    /* removes done by Enumerate */
        !           211:         uint32          grows;          /* table expansions */
        !           212:         uint32          shrinks;        /* table contractions */
        !           213:         uint32          compresses;     /* table compressions */
        !           214:         uint32          enumShrinks;    /* contractions after Enumerate */
        !           215:     } stats;
        !           216: #endif
        !           217: };
        !           218: 
        !           219: /*
        !           220:  * Size in entries (gross, not net of free and removed sentinels) for table.
        !           221:  * We store hashShift rather than sizeLog2 to optimize the collision-free case
        !           222:  * in SearchTable.
        !           223:  */
        !           224: #define JS_DHASH_TABLE_SIZE(table)  JS_BIT(JS_DHASH_BITS - (table)->hashShift)
        !           225: 
        !           226: /*
        !           227:  * Table space at entryStore is allocated and freed using these callbacks.
        !           228:  * The allocator should return null on error only (not if called with nbytes
        !           229:  * equal to 0; but note that jsdhash.c code will never call with 0 nbytes).
        !           230:  */
        !           231: typedef void *
        !           232: (* JS_DLL_CALLBACK JSDHashAllocTable)(JSDHashTable *table, uint32 nbytes);
        !           233: 
        !           234: typedef void
        !           235: (* JS_DLL_CALLBACK JSDHashFreeTable) (JSDHashTable *table, void *ptr);
        !           236: 
        !           237: /*
        !           238:  * When a table grows or shrinks, each entry is queried for its key using this
        !           239:  * callback.  NB: in that event, entry is not in table any longer; it's in the
        !           240:  * old entryStore vector, which is due to be freed once all entries have been
        !           241:  * moved via moveEntry callbacks.
        !           242:  */
        !           243: typedef const void *
        !           244: (* JS_DLL_CALLBACK JSDHashGetKey)    (JSDHashTable *table,
        !           245:                                       JSDHashEntryHdr *entry);
        !           246: 
        !           247: /*
        !           248:  * Compute the hash code for a given key to be looked up, added, or removed
        !           249:  * from table.  A hash code may have any JSDHashNumber value.
        !           250:  */
        !           251: typedef JSDHashNumber
        !           252: (* JS_DLL_CALLBACK JSDHashHashKey)   (JSDHashTable *table, const void *key);
        !           253: 
        !           254: /*
        !           255:  * Compare the key identifying entry in table with the provided key parameter.
        !           256:  * Return JS_TRUE if keys match, JS_FALSE otherwise.
        !           257:  */
        !           258: typedef JSBool
        !           259: (* JS_DLL_CALLBACK JSDHashMatchEntry)(JSDHashTable *table,
        !           260:                                       const JSDHashEntryHdr *entry,
        !           261:                                       const void *key);
        !           262: 
        !           263: /*
        !           264:  * Copy the data starting at from to the new entry storage at to.  Do not add
        !           265:  * reference counts for any strong references in the entry, however, as this
        !           266:  * is a "move" operation: the old entry storage at from will be freed without
        !           267:  * any reference-decrementing callback shortly.
        !           268:  */
        !           269: typedef void
        !           270: (* JS_DLL_CALLBACK JSDHashMoveEntry)(JSDHashTable *table,
        !           271:                                      const JSDHashEntryHdr *from,
        !           272:                                      JSDHashEntryHdr *to);
        !           273: 
        !           274: /*
        !           275:  * Clear the entry and drop any strong references it holds.  This callback is
        !           276:  * invoked during a JS_DHASH_REMOVE operation (see below for operation codes),
        !           277:  * but only if the given key is found in the table.
        !           278:  */
        !           279: typedef void
        !           280: (* JS_DLL_CALLBACK JSDHashClearEntry)(JSDHashTable *table,
        !           281:                                       JSDHashEntryHdr *entry);
        !           282: 
        !           283: /*
        !           284:  * Called when a table (whether allocated dynamically by itself, or nested in
        !           285:  * a larger structure, or allocated on the stack) is finished.  This callback
        !           286:  * allows table->ops-specific code to finalize table->data.
        !           287:  */
        !           288: typedef void
        !           289: (* JS_DLL_CALLBACK JSDHashFinalize)  (JSDHashTable *table);
        !           290: 
        !           291: /*
        !           292:  * Initialize a new entry, apart from keyHash.  This function is called when
        !           293:  * JS_DHashTableOperate's JS_DHASH_ADD case finds no existing entry for the
        !           294:  * given key, and must add a new one.  At that point, entry->keyHash is not
        !           295:  * set yet, to avoid claiming the last free entry in a severely overloaded
        !           296:  * table.
        !           297:  */
        !           298: typedef JSBool
        !           299: (* JS_DLL_CALLBACK JSDHashInitEntry)(JSDHashTable *table,
        !           300:                                      JSDHashEntryHdr *entry,
        !           301:                                      const void *key);
        !           302: 
        !           303: /*
        !           304:  * Finally, the "vtable" structure for JSDHashTable.  The first eight hooks
        !           305:  * must be provided by implementations; they're called unconditionally by the
        !           306:  * generic jsdhash.c code.  Hooks after these may be null.
        !           307:  *
        !           308:  * Summary of allocation-related hook usage with C++ placement new emphasis:
        !           309:  *  allocTable          Allocate raw bytes with malloc, no ctors run.
        !           310:  *  freeTable           Free raw bytes with free, no dtors run.
        !           311:  *  initEntry           Call placement new using default key-based ctor.
        !           312:  *                      Return JS_TRUE on success, JS_FALSE on error.
        !           313:  *  moveEntry           Call placement new using copy ctor, run dtor on old
        !           314:  *                      entry storage.
        !           315:  *  clearEntry          Run dtor on entry.
        !           316:  *  finalize            Stub unless table->data was initialized and needs to
        !           317:  *                      be finalized.
        !           318:  *
        !           319:  * Note the reason why initEntry is optional: the default hooks (stubs) clear
        !           320:  * entry storage:  On successful JS_DHashTableOperate(tbl, key, JS_DHASH_ADD),
        !           321:  * the returned entry pointer addresses an entry struct whose keyHash member
        !           322:  * has been set non-zero, but all other entry members are still clear (null).
        !           323:  * JS_DHASH_ADD callers can test such members to see whether the entry was
        !           324:  * newly created by the JS_DHASH_ADD call that just succeeded.  If placement
        !           325:  * new or similar initialization is required, define an initEntry hook.  Of
        !           326:  * course, the clearEntry hook must zero or null appropriately.
        !           327:  *
        !           328:  * XXX assumes 0 is null for pointer types.
        !           329:  */
        !           330: struct JSDHashTableOps {
        !           331:     /* Mandatory hooks.  All implementations must provide these. */
        !           332:     JSDHashAllocTable   allocTable;
        !           333:     JSDHashFreeTable    freeTable;
        !           334:     JSDHashGetKey       getKey;
        !           335:     JSDHashHashKey      hashKey;
        !           336:     JSDHashMatchEntry   matchEntry;
        !           337:     JSDHashMoveEntry    moveEntry;
        !           338:     JSDHashClearEntry   clearEntry;
        !           339:     JSDHashFinalize     finalize;
        !           340: 
        !           341:     /* Optional hooks start here.  If null, these are not called. */
        !           342:     JSDHashInitEntry    initEntry;
        !           343: };
        !           344: 
        !           345: /*
        !           346:  * Default implementations for the above ops.
        !           347:  */
        !           348: extern JS_PUBLIC_API(void *)
        !           349: JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes);
        !           350: 
        !           351: extern JS_PUBLIC_API(void)
        !           352: JS_DHashFreeTable(JSDHashTable *table, void *ptr);
        !           353: 
        !           354: extern JS_PUBLIC_API(JSDHashNumber)
        !           355: JS_DHashStringKey(JSDHashTable *table, const void *key);
        !           356: 
        !           357: /* A minimal entry contains a keyHash header and a void key pointer. */
        !           358: struct JSDHashEntryStub {
        !           359:     JSDHashEntryHdr hdr;
        !           360:     const void      *key;
        !           361: };
        !           362: 
        !           363: extern JS_PUBLIC_API(const void *)
        !           364: JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry);
        !           365: 
        !           366: extern JS_PUBLIC_API(JSDHashNumber)
        !           367: JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key);
        !           368: 
        !           369: extern JS_PUBLIC_API(JSBool)
        !           370: JS_DHashMatchEntryStub(JSDHashTable *table,
        !           371:                        const JSDHashEntryHdr *entry,
        !           372:                        const void *key);
        !           373: 
        !           374: extern JS_PUBLIC_API(JSBool)
        !           375: JS_DHashMatchStringKey(JSDHashTable *table,
        !           376:                        const JSDHashEntryHdr *entry,
        !           377:                        const void *key);
        !           378: 
        !           379: extern JS_PUBLIC_API(void)
        !           380: JS_DHashMoveEntryStub(JSDHashTable *table,
        !           381:                       const JSDHashEntryHdr *from,
        !           382:                       JSDHashEntryHdr *to);
        !           383: 
        !           384: extern JS_PUBLIC_API(void)
        !           385: JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry);
        !           386: 
        !           387: extern JS_PUBLIC_API(void)
        !           388: JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry);
        !           389: 
        !           390: extern JS_PUBLIC_API(void)
        !           391: JS_DHashFinalizeStub(JSDHashTable *table);
        !           392: 
        !           393: /*
        !           394:  * If you use JSDHashEntryStub or a subclass of it as your entry struct, and
        !           395:  * if your entries move via memcpy and clear via memset(0), you can use these
        !           396:  * stub operations.
        !           397:  */
        !           398: extern JS_PUBLIC_API(const JSDHashTableOps *)
        !           399: JS_DHashGetStubOps(void);
        !           400: 
        !           401: /*
        !           402:  * Dynamically allocate a new JSDHashTable using malloc, initialize it using
        !           403:  * JS_DHashTableInit, and return its address.  Return null on malloc failure.
        !           404:  * Note that the entry storage at table->entryStore will be allocated using
        !           405:  * the ops->allocTable callback.
        !           406:  */
        !           407: extern JS_PUBLIC_API(JSDHashTable *)
        !           408: JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
        !           409:                  uint32 capacity);
        !           410: 
        !           411: /*
        !           412:  * Finalize table's data, free its entry storage (via table->ops->freeTable),
        !           413:  * and return the memory starting at table to the malloc heap.
        !           414:  */
        !           415: extern JS_PUBLIC_API(void)
        !           416: JS_DHashTableDestroy(JSDHashTable *table);
        !           417: 
        !           418: /*
        !           419:  * Initialize table with ops, data, entrySize, and capacity.  Capacity is a
        !           420:  * guess for the smallest table size at which the table will usually be less
        !           421:  * than 75% loaded (the table will grow or shrink as needed; capacity serves
        !           422:  * only to avoid inevitable early growth from JS_DHASH_MIN_SIZE).
        !           423:  */
        !           424: extern JS_PUBLIC_API(JSBool)
        !           425: JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
        !           426:                   uint32 entrySize, uint32 capacity);
        !           427: 
        !           428: /*
        !           429:  * Set maximum and minimum alpha for table.  The defaults are 0.75 and .25.
        !           430:  * maxAlpha must be in [0.5, 0.9375] for the default JS_DHASH_MIN_SIZE; or if
        !           431:  * MinSize=JS_DHASH_MIN_SIZE <= 256, in [0.5, (float)(MinSize-1)/MinSize]; or
        !           432:  * else in [0.5, 255.0/256].  minAlpha must be in [0, maxAlpha / 2), so that
        !           433:  * we don't shrink on the very next remove after growing a table upon adding
        !           434:  * an entry that brings entryCount past maxAlpha * tableSize.
        !           435:  */
        !           436: JS_PUBLIC_API(void)
        !           437: JS_DHashTableSetAlphaBounds(JSDHashTable *table,
        !           438:                             float maxAlpha,
        !           439:                             float minAlpha);
        !           440: 
        !           441: /*
        !           442:  * Call this macro with k, the number of pointer-sized words wasted per entry
        !           443:  * under chaining, to compute the minimum alpha at which double hashing still
        !           444:  * beats chaining.
        !           445:  */
        !           446: #define JS_DHASH_MIN_ALPHA(table, k)                                          \
        !           447:     ((float)((table)->entrySize / sizeof(void *) - 1)                         \
        !           448:      / ((table)->entrySize / sizeof(void *) + (k)))
        !           449: 
        !           450: /*
        !           451:  * Finalize table's data, free its entry storage using table->ops->freeTable,
        !           452:  * and leave its members unchanged from their last live values (which leaves
        !           453:  * pointers dangling).  If you want to burn cycles clearing table, it's up to
        !           454:  * your code to call memset.
        !           455:  */
        !           456: extern JS_PUBLIC_API(void)
        !           457: JS_DHashTableFinish(JSDHashTable *table);
        !           458: 
        !           459: /*
        !           460:  * To consolidate keyHash computation and table grow/shrink code, we use a
        !           461:  * single entry point for lookup, add, and remove operations.  The operation
        !           462:  * codes are declared here, along with codes returned by JSDHashEnumerator
        !           463:  * functions, which control JS_DHashTableEnumerate's behavior.
        !           464:  */
        !           465: typedef enum JSDHashOperator {
        !           466:     JS_DHASH_LOOKUP = 0,        /* lookup entry */
        !           467:     JS_DHASH_ADD = 1,           /* add entry */
        !           468:     JS_DHASH_REMOVE = 2,        /* remove entry, or enumerator says remove */
        !           469:     JS_DHASH_NEXT = 0,          /* enumerator says continue */
        !           470:     JS_DHASH_STOP = 1           /* enumerator says stop */
        !           471: } JSDHashOperator;
        !           472: 
        !           473: /*
        !           474:  * To lookup a key in table, call:
        !           475:  *
        !           476:  *  entry = JS_DHashTableOperate(table, key, JS_DHASH_LOOKUP);
        !           477:  *
        !           478:  * If JS_DHASH_ENTRY_IS_BUSY(entry) is true, key was found and it identifies
        !           479:  * entry.  If JS_DHASH_ENTRY_IS_FREE(entry) is true, key was not found.
        !           480:  *
        !           481:  * To add an entry identified by key to table, call:
        !           482:  *
        !           483:  *  entry = JS_DHashTableOperate(table, key, JS_DHASH_ADD);
        !           484:  *
        !           485:  * If entry is null upon return, then either the table is severely overloaded,
        !           486:  * and memory can't be allocated for entry storage via table->ops->allocTable;
        !           487:  * Or if table->ops->initEntry is non-null, the table->ops->initEntry op may
        !           488:  * have returned false.
        !           489:  *
        !           490:  * Otherwise, entry->keyHash has been set so that JS_DHASH_ENTRY_IS_BUSY(entry)
        !           491:  * is true, and it is up to the caller to initialize the key and value parts
        !           492:  * of the entry sub-type, if they have not been set already (i.e. if entry was
        !           493:  * not already in the table, and if the optional initEntry hook was not used).
        !           494:  *
        !           495:  * To remove an entry identified by key from table, call:
        !           496:  *
        !           497:  *  (void) JS_DHashTableOperate(table, key, JS_DHASH_REMOVE);
        !           498:  *
        !           499:  * If key's entry is found, it is cleared (via table->ops->clearEntry) and
        !           500:  * the entry is marked so that JS_DHASH_ENTRY_IS_FREE(entry).  This operation
        !           501:  * returns null unconditionally; you should ignore its return value.
        !           502:  */
        !           503: extern JS_PUBLIC_API(JSDHashEntryHdr *)
        !           504: JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op);
        !           505: 
        !           506: /*
        !           507:  * Remove an entry already accessed via LOOKUP or ADD.
        !           508:  *
        !           509:  * NB: this is a "raw" or low-level routine, intended to be used only where
        !           510:  * the inefficiency of a full JS_DHashTableOperate (which rehashes in order
        !           511:  * to find the entry given its key) is not tolerable.  This function does not
        !           512:  * shrink the table if it is underloaded.  It does not update stats #ifdef
        !           513:  * JS_DHASHMETER, either.
        !           514:  */
        !           515: extern JS_PUBLIC_API(void)
        !           516: JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry);
        !           517: 
        !           518: /*
        !           519:  * Enumerate entries in table using etor:
        !           520:  *
        !           521:  *   count = JS_DHashTableEnumerate(table, etor, arg);
        !           522:  *
        !           523:  * JS_DHashTableEnumerate calls etor like so:
        !           524:  *
        !           525:  *   op = etor(table, entry, number, arg);
        !           526:  *
        !           527:  * where number is a zero-based ordinal assigned to live entries according to
        !           528:  * their order in table->entryStore.
        !           529:  *
        !           530:  * The return value, op, is treated as a set of flags.  If op is JS_DHASH_NEXT,
        !           531:  * then continue enumerating.  If op contains JS_DHASH_REMOVE, then clear (via
        !           532:  * table->ops->clearEntry) and free entry.  Then we check whether op contains
        !           533:  * JS_DHASH_STOP; if so, stop enumerating and return the number of live entries
        !           534:  * that were enumerated so far.  Return the total number of live entries when
        !           535:  * enumeration completes normally.
        !           536:  *
        !           537:  * If etor calls JS_DHashTableOperate on table with op != JS_DHASH_LOOKUP, it
        !           538:  * must return JS_DHASH_STOP; otherwise undefined behavior results.
        !           539:  *
        !           540:  * If any enumerator returns JS_DHASH_REMOVE, table->entryStore may be shrunk
        !           541:  * or compressed after enumeration, but before JS_DHashTableEnumerate returns.
        !           542:  * Such an enumerator therefore can't safely set aside entry pointers, but an
        !           543:  * enumerator that never returns JS_DHASH_REMOVE can set pointers to entries
        !           544:  * aside, e.g., to avoid copying live entries into an array of the entry type.
        !           545:  * Copying entry pointers is cheaper, and safe so long as the caller of such a
        !           546:  * "stable" Enumerate doesn't use the set-aside pointers after any call either
        !           547:  * to PL_DHashTableOperate, or to an "unstable" form of Enumerate, which might
        !           548:  * grow or shrink entryStore.
        !           549:  *
        !           550:  * If your enumerator wants to remove certain entries, but set aside pointers
        !           551:  * to other entries that it retains, it can use JS_DHashTableRawRemove on the
        !           552:  * entries to be removed, returning JS_DHASH_NEXT to skip them.  Likewise, if
        !           553:  * you want to remove entries, but for some reason you do not want entryStore
        !           554:  * to be shrunk or compressed, you can call JS_DHashTableRawRemove safely on
        !           555:  * the entry being enumerated, rather than returning JS_DHASH_REMOVE.
        !           556:  */
        !           557: typedef JSDHashOperator
        !           558: (* JS_DLL_CALLBACK JSDHashEnumerator)(JSDHashTable *table, JSDHashEntryHdr *hdr,
        !           559:                                       uint32 number, void *arg);
        !           560: 
        !           561: extern JS_PUBLIC_API(uint32)
        !           562: JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg);
        !           563: 
        !           564: #ifdef JS_DHASHMETER
        !           565: #include <stdio.h>
        !           566: 
        !           567: extern JS_PUBLIC_API(void)
        !           568: JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp);
        !           569: #endif
        !           570: 
        !           571: JS_END_EXTERN_C
        !           572: 
        !           573: #endif /* jsdhash_h___ */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.