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