hashtable2.h 12 KB

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