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 \
  34     OBJC_OSX_DEPRECATED_OTHERS_UNAVAILABLE(10.0, 10.1, "NXHashTable is deprecated")
  35 #else
  36 #   define OBJC_HASH_AVAILABILITY
  37 #endif
  38
  39 #include <objc/objc.h>
  40 #include <stdint.h>
  41 #include <TargetConditionals.h>
  42
  43 __BEGIN_DECLS
  44
  45 /*************************************************************************
  46  *      Hash tables of arbitrary data
  47  *************************************************************************/
  48
  49 /* 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.
  50 The objective C class HashTable is preferred when dealing with (key, values) associations because it is easier to use in that situation.
  51 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. */
  52
  53 typedef struct {
  54     uintptr_t   (* _Nonnull hash)(const void * _Nullable info,
  55                                   const void * _Nullable data);
  56     int         (* _Nonnull isEqual)(const void * _Nullable info,
  57                                      const void * _Nullable data1,
  58                                      const void * _Nullable data2);
  59     void        (* _Nonnull free)(const void * _Nullable info,
  60                                   void * _Nullable data);
  61     int         style; /* reserved for future expansion; currently 0 */
  62     } NXHashTablePrototype;
  63
  64 /* the info argument allows a certain generality, such as freeing according to some owner information */
  65 /* invariants assumed by the implementation:
  66         1 - data1 = data2 => hash(data1) = hash(data2)
  67             when data varies over time, hash(data) must remain invariant
  68                     e.g. if data hashes over a string key, the string must not be changed
  69         2- isEqual (data1, data2) => data1= data2
  70  */
  71
  72 typedef struct {
  73     const NXHashTablePrototype  * _Nonnull prototype OBJC_HASH_AVAILABILITY;
  74     unsigned                    count OBJC_HASH_AVAILABILITY;
  75     unsigned                    nbBuckets OBJC_HASH_AVAILABILITY;
  76     void                        * _Nullable buckets OBJC_HASH_AVAILABILITY;
  77     const void                  * _Nullable info OBJC_HASH_AVAILABILITY;
  78    } NXHashTable OBJC_HASH_AVAILABILITY;
  79     /* private data structure; may change */
  80
  81 OBJC_EXPORT NXHashTable * _Nonnull
  82 NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity,
  83                            const void * _Nullable info, void * _Nullable z)
  84     OBJC_HASH_AVAILABILITY;
  85
  86 OBJC_EXPORT NXHashTable * _Nonnull
  87 NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity,
  88                    const void * _Nullable info)
  89     OBJC_HASH_AVAILABILITY;
  90     /* if hash is 0, pointer hash is assumed */
  91     /* if isEqual is 0, pointer equality is assumed */
  92     /* if free is 0, elements are not freed */
  93     /* capacity is only a hint; 0 creates a small table */
  94     /* info allows call backs to be very general */
  95
  96 OBJC_EXPORT void
  97 NXFreeHashTable (NXHashTable * _Nonnull table)
  98     OBJC_HASH_AVAILABILITY;
  99     /* calls free for each data, and recovers table */
 100
 101 OBJC_EXPORT void
 102 NXEmptyHashTable (NXHashTable * _Nonnull table)
 103     OBJC_HASH_AVAILABILITY;
 104     /* does not deallocate table nor data; keeps current capacity */
 105
 106 OBJC_EXPORT void
 107 NXResetHashTable (NXHashTable * _Nonnull table)
 108     OBJC_HASH_AVAILABILITY;
 109     /* frees each entry; keeps current capacity */
 110
 111 OBJC_EXPORT BOOL
 112 NXCompareHashTables (NXHashTable * _Nonnull table1,
 113                      NXHashTable * _Nonnull table2)
 114     OBJC_HASH_AVAILABILITY;
 115     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
 116
 117 OBJC_EXPORT NXHashTable * _Nonnull
 118 NXCopyHashTable (NXHashTable * _Nonnull table)
 119     OBJC_HASH_AVAILABILITY;
 120     /* makes a fresh table, copying data pointers, not data itself.  */
 121
 122 OBJC_EXPORT unsigned
 123 NXCountHashTable (NXHashTable * _Nonnull table)
 124     OBJC_HASH_AVAILABILITY;
 125     /* current number of data in table */
 126
 127 OBJC_EXPORT int
 128 NXHashMember (NXHashTable * _Nonnull table, const void * _Nullable data)
 129     OBJC_HASH_AVAILABILITY;
 130     /* returns non-0 iff data is present in table.
 131     Example of use when the hashed data is a struct containing the key,
 132     and when the callee only has a key:
 133         MyStruct        pseudo;
 134         pseudo.key = myKey;
 135         return NXHashMember (myTable, &pseudo)
 136     */
 137
 138 OBJC_EXPORT void * _Nullable
 139 NXHashGet (NXHashTable * _Nonnull table, const void * _Nullable data)
 140     OBJC_HASH_AVAILABILITY;
 141     /* return original table data or NULL.
 142     Example of use when the hashed data is a struct containing the key,
 143     and when the callee only has a key:
 144         MyStruct        pseudo;
 145         MyStruct        *original;
 146         pseudo.key = myKey;
 147         original = NXHashGet (myTable, &pseudo)
 148     */
 149
 150 OBJC_EXPORT void * _Nullable
 151 NXHashInsert (NXHashTable * _Nonnull table, const void * _Nullable data)
 152     OBJC_HASH_AVAILABILITY;
 153     /* previous data or NULL is returned. */
 154
 155 OBJC_EXPORT void * _Nullable
 156 NXHashInsertIfAbsent (NXHashTable * _Nonnull table, const void * _Nullable data)
 157     OBJC_HASH_AVAILABILITY;
 158     /* If data already in table, returns the one in table
 159     else adds argument to table and returns argument. */
 160
 161 OBJC_EXPORT void * _Nullable
 162 NXHashRemove (NXHashTable * _Nonnull table, const void * _Nullable data)
 163     OBJC_HASH_AVAILABILITY;
 164     /* previous data or NULL is returned */
 165
 166 /* 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:
 167     unsigned    count = 0;
 168     MyData      *data;
 169     NXHashState state = NXInitHashState(table);
 170     while (NXNextHashState(table, &state, &data)) {
 171         count++;
 172     }
 173 */
 174
 175 typedef struct {int i; int j;} NXHashState OBJC_HASH_AVAILABILITY;
 176     /* callers should not rely on actual contents of the struct */
 177
 178 OBJC_EXPORT NXHashState
 179 NXInitHashState(NXHashTable * _Nonnull table)
 180     OBJC_HASH_AVAILABILITY;
 181
 182 OBJC_EXPORT int
 183 NXNextHashState(NXHashTable * _Nonnull table, NXHashState * _Nonnull state,
 184                 void * _Nullable * _Nonnull data) OBJC_HASH_AVAILABILITY;
 185     /* returns 0 when all elements have been visited */
 186
 187 /*************************************************************************
 188  *      Conveniences for writing hash, isEqual and free functions
 189  *      and common prototypes
 190  *************************************************************************/
 191
 192 OBJC_EXPORT uintptr_t
 193 NXPtrHash(const void * _Nullable info, const void * _Nullable data)
 194     OBJC_HASH_AVAILABILITY;
 195     /* scrambles the address bits; info unused */
 196
 197 OBJC_EXPORT uintptr_t
 198 NXStrHash(const void * _Nullable info, const void * _Nullable data)
 199     OBJC_HASH_AVAILABILITY;
 200     /* string hashing; info unused */
 201
 202 OBJC_EXPORT int
 203 NXPtrIsEqual(const void * _Nullable info, const void * _Nullable data1,
 204              const void * _Nullable data2)
 205     OBJC_HASH_AVAILABILITY;
 206     /* pointer comparison; info unused */
 207
 208 OBJC_EXPORT int
 209 NXStrIsEqual(const void * _Nullable info, const void * _Nullable data1,
 210              const void * _Nullable data2)
 211     OBJC_HASH_AVAILABILITY;
 212     /* string comparison; NULL ok; info unused */
 213
 214 OBJC_EXPORT void
 215 NXNoEffectFree(const void * _Nullable info, void * _Nullable data)
 216     OBJC_HASH_AVAILABILITY;
 217     /* no effect; info unused */
 218
 219 OBJC_EXPORT void
 220 NXReallyFree(const void * _Nullable info, void * _Nullable data)
 221     OBJC_HASH_AVAILABILITY;
 222     /* frees it; info unused */
 223
 224 /* The two following prototypes are useful for manipulating set of pointers or set of strings; For them free is defined as NXNoEffectFree */
 225 OBJC_EXPORT const NXHashTablePrototype NXPtrPrototype
 226     OBJC_HASH_AVAILABILITY;
 227     /* prototype when data is a pointer (void *) */
 228
 229 OBJC_EXPORT const NXHashTablePrototype NXStrPrototype
 230     OBJC_HASH_AVAILABILITY;
 231     /* prototype when data is a string (char *) */
 232
 233 /* following prototypes help describe mappings where the key is the first element of a struct and is either a pointer or a string.
 234 For example NXStrStructKeyPrototype can be used to hash pointers to Example, where Example is:
 235         typedef struct {
 236             char        *key;
 237             int         data1;
 238             ...
 239             } Example
 240
 241 For the following prototypes, free is defined as NXReallyFree.
 242  */
 243 OBJC_EXPORT const NXHashTablePrototype NXPtrStructKeyPrototype
 244     OBJC_HASH_AVAILABILITY;
 245 OBJC_EXPORT const NXHashTablePrototype NXStrStructKeyPrototype
 246     OBJC_HASH_AVAILABILITY;
 247
 248
 249 #if !__OBJC2__  &&  !TARGET_OS_WIN32
 250
 251 /*************************************************************************
 252  *      Unique strings and buffers
 253  *************************************************************************/
 254
 255 /* Unique strings allows C users to enjoy the benefits of Lisp's atoms:
 256 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. */
 257
 258 typedef const char *NXAtom OBJC_HASH_AVAILABILITY;
 259
 260 OBJC_EXPORT NXAtom _Nullable
 261 NXUniqueString(const char * _Nullable buffer)
 262     OBJC_HASH_AVAILABILITY;
 263     /* assumes that buffer is \0 terminated, and returns
 264      a previously created string or a new string that is a copy of buffer.
 265     If NULL is passed returns NULL.
 266     Returned string should never be modified.  To ensure this invariant,
 267     allocations are made in a special read only zone. */
 268
 269 OBJC_EXPORT NXAtom _Nonnull
 270 NXUniqueStringWithLength(const char * _Nullable buffer, int length)
 271     OBJC_HASH_AVAILABILITY;
 272     /* assumes that buffer is a non NULL buffer of at least
 273     length characters.  Returns a previously created string or
 274     a new string that is a copy of buffer.
 275     If buffer contains \0, string will be truncated.
 276     As for NXUniqueString, returned string should never be modified.  */
 277
 278 OBJC_EXPORT NXAtom _Nullable
 279 NXUniqueStringNoCopy(const char * _Nullable string)
 280     OBJC_HASH_AVAILABILITY;
 281     /* If there is already a unique string equal to string, returns the original.
 282     Otherwise, string is entered in the table, without making a copy.  Argument should then never be modified.  */
 283
 284 OBJC_EXPORT char * _Nullable
 285 NXCopyStringBuffer(const char * _Nullable buffer)
 286     OBJC_HASH_AVAILABILITY;
 287     /* given a buffer, allocates a new string copy of buffer.
 288     Buffer should be \0 terminated; returned string is \0 terminated. */
 289
 290 OBJC_EXPORT char * _Nullable
 291 NXCopyStringBufferFromZone(const char * _Nullable buffer, void * _Nullable z)
 292     OBJC_HASH_AVAILABILITY;
 293     /* given a buffer, allocates a new string copy of buffer.
 294     Buffer should be \0 terminated; returned string is \0 terminated. */
 295
 296 #endif
 297
 298 __END_DECLS
 299
 300 #endif /* _OBJC_LITTLE_HASHTABLE_H_ */