1  #import <Foundation/NSException.h>
 2  
 3  #define NUM_BUCKET_SIZES 64
 4  
 5  static const NSUInteger __NSBasicHashIPrimes[NUM_BUCKET_SIZES] = {
 6      0, 3, 7, 13, 23, 41, 71, 127, 191, 251, 383, 631, 1087, 1723,
 7      2803, 4523, 7351, 11959, 19447, 31231, 50683, 81919, 132607,
 8      214519, 346607, 561109, 907759, 1468927, 2376191, 3845119,
 9      6221311, 10066421, 16287743, 26354171, 42641881, 68996069,
10      111638519, 180634607, 292272623, 472907251,
11  #if __LP64__
12      765180413UL, 1238087663UL, 2003267557UL, 3241355263UL, 5244622819UL,
13  #if 0
14      8485977589UL, 13730600407UL, 22216578047UL, 35947178479UL,
15      58163756537UL, 94110934997UL, 152274691561UL, 246385626107UL,
16      398660317687UL, 645045943807UL, 1043706260983UL, 1688752204787UL,
17      2732458465769UL, 4421210670577UL, 7153669136377UL,
18      11574879807461UL, 18728548943849UL, 30303428750843UL
19  #endif
20  #endif
21  };
22  
23  static const NSUInteger __NSBasicHashCapacities[NUM_BUCKET_SIZES] = {
24      0, 3, 6, 11, 19, 32, 52, 85, 118, 155, 237, 390, 672, 1065,
25      1732, 2795, 4543, 7391, 12019, 19302, 31324, 50629, 81956,
26      132580, 214215, 346784, 561026, 907847, 1468567, 2376414,
27      3844982, 6221390, 10066379, 16287773, 26354132, 42641916,
28      68996399, 111638327, 180634415, 292272755,
29  #if __LP64__
30      472907503UL, 765180257UL, 1238087439UL, 2003267722UL, 3241355160UL,
31  #if 0
32      5244622578UL, 8485977737UL, 13730600347UL, 22216578100UL,
33      35947178453UL, 58163756541UL, 94110935011UL, 152274691274UL,
34      246385626296UL, 398660317578UL, 645045943559UL, 1043706261135UL,
35      1688752204693UL, 2732458465840UL, 4421210670552UL,
36      7153669136706UL, 11574879807265UL, 18728548943682UL
37  #endif
38  #endif
39  };
40  
41  static inline NSUInteger __NSBasicHashGetSizeIdx(NSUInteger size) {
42      for (NSUInteger idx = 0; idx < NUM_BUCKET_SIZES; idx++) {
43          if (__NSBasicHashCapacities[idx] > size) {
44              return idx;
45          }
46      }
47  
48      DEBUG_BREAK();
49      return NSNotFound;
50  }
51  
52  static inline void *NSBasicHashAllocate(NSUInteger count, size_t size, NSUInteger *capacity, NSUInteger *sizeidx, BOOL throwOnMallocFailure) {
53      *sizeidx = __NSBasicHashGetSizeIdx(count);
54      *capacity = __NSBasicHashIPrimes[*sizeidx];
55      void *buffer = calloc(*capacity, size);
56      if (buffer == NULL && throwOnMallocFailure) {
57          [NSException raise:NSMallocException format:@"Unable to allocate buffer"];
58      }
59      return buffer;
60  }
61  
62  static inline void *NSBasicHashGrow(NSUInteger count, size_t size, void *buffer, NSUInteger *capacity, NSUInteger *sizeidx, BOOL throwOnMallocFailure) {
63      if (*capacity < count) {
64          *sizeidx = __NSBasicHashGetSizeIdx(count);
65          *capacity = __NSBasicHashIPrimes[*sizeidx];
66          void *newBuffer = realloc(buffer, (*capacity) * size);
67          if (newBuffer == NULL && throwOnMallocFailure) {
68              free(buffer);
69              *capacity = 0;
70              [NSException raise:NSMallocException format:@"Unable to reallocate buffer"];
71          }
72          buffer = newBuffer;
73      }
74      return buffer;
75  }
76  
77  static inline void *NSBasicHashTrim(NSUInteger count, size_t size, void *buffer, NSUInteger *capacity, BOOL throwOnMallocFailure) {
78      if (*capacity > count) {
79          void *newBuffer = realloc(buffer, count * size);
80          if (newBuffer == NULL && throwOnMallocFailure) { // very sad day indeed if trimming causes malloc failure...
81              free(buffer);
82              *capacity = 0;
83              [NSException raise:NSMallocException format:@"Unable to reallocate buffer"];   
84          } else {
85              *capacity = count * size;
86          }
87          buffer = newBuffer;
88      }
89      return buffer;
90  }
91  
92  static inline void NSBasicHashDeallocate(void *buffer) {
93      if (buffer) {
94          free(buffer);
95      }
96  }