runtime/hashtable2.h

   1 /*
   2  * Copyright (c) 1999-2006 Apple Inc.  All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*
  24     hashtable2.h
  25     Scalable hash table.
  26     Copyright 1989-1996 NeXT Software, Inc.
  27 */
  28
  29 #ifndef _OBJC_LITTLE_HASHTABLE_H_
  30 #define _OBJC_LITTLE_HASHTABLE_H_
  31
  32 #ifndef _OBJC_PRIVATE_H_
  33 #   define OBJC_HASH_AVAILABILITY __OSX_AVAILABLE_BUT_DEPRECATED(__MAC_10_0,__MAC_10_1, __IPHONE_NA,__IPHONE_NA);
  34 #else
  35 #   define OBJC_HASH_AVAILABILITY
  36 #endif
  37
  38 #include <objc/objc.h>
  39 #include <stdint.h>
  40 #include <TargetConditionals.h>
  41
  42 __BEGIN_DECLS
  43
  44 /*************************************************************************
  45  *      Hash tables of arbitrary data
  46  *************************************************************************/
  47
  48 /* This module allows hashing of arbitrary data.  Such data must be pointers or integers, and client is responsible for allocating/deallocating this data.  A deallocation call-back is provided.
  49 The objective C class HashTable is preferred when dealing with (key, values) associations because it is easier to use in that situation.
  50 As well-behaved scalable data structures, hash tables double in size when they start becoming full, thus guaranteeing both average constant time access and linear size. */
  51
  52 typedef struct {
  53     uintptr_t   (*hash)(const void *info, const void *data);
  54     int         (*isEqual)(const void *info, const void *data1, const void *data2);
  55     void        (*free)(const void *info, void *data);
  56     int         style; /* reserved for future expansion; currently 0 */
  57     } NXHashTablePrototype;
  58
  59 /* the info argument allows a certain generality, such as freeing according to some owner information */
  60 /* invariants assumed by the implementation:
  61         1 - data1 = data2 => hash(data1) = hash(data2)
  62             when data varies over time, hash(data) must remain invariant
  63                     e.g. if data hashes over a string key, the string must not be changed
  64         2- isEqual (data1, data2) => data1= data2
  65  */
  66
  67 typedef struct {
  68     const NXHashTablePrototype  *prototype OBJC_HASH_AVAILABILITY;
  69     unsigned                    count OBJC_HASH_AVAILABILITY;
  70     unsigned                    nbBuckets OBJC_HASH_AVAILABILITY;
  71     void                        *buckets OBJC_HASH_AVAILABILITY;
  72     const void                  *info OBJC_HASH_AVAILABILITY;
  73    } NXHashTable OBJC_HASH_AVAILABILITY;
  74     /* private data structure; may change */
  75
  76 OBJC_EXPORT NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity, const void *info, void *z) OBJC_HASH_AVAILABILITY;
  77 OBJC_EXPORT NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info) OBJC_HASH_AVAILABILITY;
  78     /* if hash is 0, pointer hash is assumed */
  79     /* if isEqual is 0, pointer equality is assumed */
  80     /* if free is 0, elements are not freed */
  81     /* capacity is only a hint; 0 creates a small table */
  82     /* info allows call backs to be very general */
  83
  84 OBJC_EXPORT void NXFreeHashTable (NXHashTable *table) OBJC_HASH_AVAILABILITY;
  85     /* calls free for each data, and recovers table */
  86
  87 OBJC_EXPORT void NXEmptyHashTable (NXHashTable *table) OBJC_HASH_AVAILABILITY;
  88     /* does not deallocate table nor data; keeps current capacity */
  89
  90 OBJC_EXPORT void NXResetHashTable (NXHashTable *table) OBJC_HASH_AVAILABILITY;
  91     /* frees each entry; keeps current capacity */
  92
  93 OBJC_EXPORT BOOL NXCompareHashTables (NXHashTable *table1, NXHashTable *table2) OBJC_HASH_AVAILABILITY;
  94     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
  95
  96 OBJC_EXPORT NXHashTable *NXCopyHashTable (NXHashTable *table) OBJC_HASH_AVAILABILITY;
  97     /* makes a fresh table, copying data pointers, not data itself.  */
  98
  99 OBJC_EXPORT unsigned NXCountHashTable (NXHashTable *table) OBJC_HASH_AVAILABILITY;
 100     /* current number of data in table */
 101
 102 OBJC_EXPORT int NXHashMember (NXHashTable *table, const void *data) OBJC_HASH_AVAILABILITY;
 103     /* returns non-0 iff data is present in table.
 104     Example of use when the hashed data is a struct containing the key,
 105     and when the callee only has a key:
 106         MyStruct        pseudo;
 107         pseudo.key = myKey;
 108         return NXHashMember (myTable, &pseudo)
 109     */
 110
 111 OBJC_EXPORT void *NXHashGet (NXHashTable *table, const void *data) OBJC_HASH_AVAILABILITY;
 112     /* return original table data or NULL.
 113     Example of use when the hashed data is a struct containing the key,
 114     and when the callee only has a key:
 115         MyStruct        pseudo;
 116         MyStruct        *original;
 117         pseudo.key = myKey;
 118         original = NXHashGet (myTable, &pseudo)
 119     */
 120
 121 OBJC_EXPORT void *NXHashInsert (NXHashTable *table, const void *data) OBJC_HASH_AVAILABILITY;
 122     /* previous data or NULL is returned. */
 123
 124 OBJC_EXPORT void *NXHashInsertIfAbsent (NXHashTable *table, const void *data) OBJC_HASH_AVAILABILITY;
 125     /* If data already in table, returns the one in table
 126     else adds argument to table and returns argument. */
 127
 128 OBJC_EXPORT void *NXHashRemove (NXHashTable *table, const void *data) OBJC_HASH_AVAILABILITY;
 129     /* previous data or NULL is returned */
 130
 131 /* Iteration over all elements of a table consists in setting up an iteration state and then to progress until all entries have been visited.  An example of use for counting elements in a table is:
 132     unsigned    count = 0;
 133     MyData      *data;
 134     NXHashState state = NXInitHashState(table);
 135     while (NXNextHashState(table, &state, &data)) {
 136         count++;
 137     }
 138 */
 139
 140 typedef struct {int i; int j;} NXHashState OBJC_HASH_AVAILABILITY;
 141     /* callers should not rely on actual contents of the struct */
 142
 143 OBJC_EXPORT NXHashState NXInitHashState(NXHashTable *table) OBJC_HASH_AVAILABILITY;
 144
 145 OBJC_EXPORT int NXNextHashState(NXHashTable *table, NXHashState *state, void **data) OBJC_HASH_AVAILABILITY;
 146     /* returns 0 when all elements have been visited */
 147
 148 /*************************************************************************
 149  *      Conveniences for writing hash, isEqual and free functions
 150  *      and common prototypes
 151  *************************************************************************/
 152
 153 OBJC_EXPORT uintptr_t NXPtrHash(const void *info, const void *data) OBJC_HASH_AVAILABILITY;
 154     /* scrambles the address bits; info unused */
 155 OBJC_EXPORT uintptr_t NXStrHash(const void *info, const void *data) OBJC_HASH_AVAILABILITY;
 156     /* string hashing; info unused */
 157 OBJC_EXPORT int NXPtrIsEqual(const void *info, const void *data1, const void *data2) OBJC_HASH_AVAILABILITY;
 158     /* pointer comparison; info unused */
 159 OBJC_EXPORT int NXStrIsEqual(const void *info, const void *data1, const void *data2) OBJC_HASH_AVAILABILITY;
 160     /* string comparison; NULL ok; info unused */
 161 OBJC_EXPORT void NXNoEffectFree(const void *info, void *data) OBJC_HASH_AVAILABILITY;
 162     /* no effect; info unused */
 163 OBJC_EXPORT void NXReallyFree(const void *info, void *data) OBJC_HASH_AVAILABILITY;
 164     /* frees it; info unused */
 165
 166 /* The two following prototypes are useful for manipulating set of pointers or set of strings; For them free is defined as NXNoEffectFree */
 167 OBJC_EXPORT const NXHashTablePrototype NXPtrPrototype OBJC_HASH_AVAILABILITY;
 168     /* prototype when data is a pointer (void *) */
 169 OBJC_EXPORT const NXHashTablePrototype NXStrPrototype OBJC_HASH_AVAILABILITY;
 170     /* prototype when data is a string (char *) */
 171
 172 /* following prototypes help describe mappings where the key is the first element of a struct and is either a pointer or a string.
 173 For example NXStrStructKeyPrototype can be used to hash pointers to Example, where Example is:
 174         typedef struct {
 175             char        *key;
 176             int         data1;
 177             ...
 178             } Example
 179
 180 For the following prototypes, free is defined as NXReallyFree.
 181  */
 182 OBJC_EXPORT const NXHashTablePrototype NXPtrStructKeyPrototype OBJC_HASH_AVAILABILITY;
 183 OBJC_EXPORT const NXHashTablePrototype NXStrStructKeyPrototype OBJC_HASH_AVAILABILITY;
 184
 185
 186 #if !__OBJC2__  &&  !TARGET_OS_WIN32
 187
 188 /*************************************************************************
 189  *      Unique strings and buffers
 190  *************************************************************************/
 191
 192 /* Unique strings allows C users to enjoy the benefits of Lisp's atoms:
 193 A unique string is a string that is allocated once for all (never de-allocated) and that has only one representant (thus allowing comparison with == instead of strcmp).  A unique string should never be modified (and in fact some memory protection is done to ensure that).  In order to more explicitly insist on the fact that the string has been uniqued, a synonym of (const char *) has been added, NXAtom. */
 194
 195 typedef const char *NXAtom OBJC_HASH_AVAILABILITY;
 196
 197 OBJC_EXPORT NXAtom NXUniqueString(const char *buffer) OBJC_HASH_AVAILABILITY;
 198     /* assumes that buffer is \0 terminated, and returns
 199      a previously created string or a new string that is a copy of buffer.
 200     If NULL is passed returns NULL.
 201     Returned string should never be modified.  To ensure this invariant,
 202     allocations are made in a special read only zone. */
 203
 204 OBJC_EXPORT NXAtom NXUniqueStringWithLength(const char *buffer, int length) OBJC_HASH_AVAILABILITY;
 205     /* assumes that buffer is a non NULL buffer of at least
 206     length characters.  Returns a previously created string or
 207     a new string that is a copy of buffer.
 208     If buffer contains \0, string will be truncated.
 209     As for NXUniqueString, returned string should never be modified.  */
 210
 211 OBJC_EXPORT NXAtom NXUniqueStringNoCopy(const char *string) OBJC_HASH_AVAILABILITY;
 212     /* If there is already a unique string equal to string, returns the original.
 213     Otherwise, string is entered in the table, without making a copy.  Argument should then never be modified.  */
 214
 215 OBJC_EXPORT char *NXCopyStringBuffer(const char *buffer) OBJC_HASH_AVAILABILITY;
 216     /* given a buffer, allocates a new string copy of buffer.
 217     Buffer should be \0 terminated; returned string is \0 terminated. */
 218
 219 OBJC_EXPORT char *NXCopyStringBufferFromZone(const char *buffer, void *z) OBJC_HASH_AVAILABILITY;
 220     /* given a buffer, allocates a new string copy of buffer.
 221     Buffer should be \0 terminated; returned string is \0 terminated. */
 222
 223 #endif
 224
 225 __END_DECLS
 226
 227 #endif /* _OBJC_LITTLE_HASHTABLE_H_ */