Foundation/NSHashTable.m

   1 /* Copyright (c) 2006-2007 Christopher J. W. Lloyd
   2
   3 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
   4
   5 The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
   6
   7 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
   8 #import <Foundation/NSHashTable.h>
   9 #import <Foundation/NSArray.h>
  10 #import <Foundation/NSString.h>
  11
  12 typedef struct NSHashBucket {
  13    struct NSHashBucket *next;
  14    void *key;
  15 } NSHashBucket;
  16
  17 struct NSHashTable {
  18    NSHashTableCallBacks *callBacks;
  19    NSUInteger       count;
  20    NSUInteger       nBuckets;
  21    NSHashBucket **buckets;
  22 };
  23
  24 NSHashTableCallBacks _NSHashTableFixCallbacks(NSHashTableCallBacks callBacks);
  25
  26 NSHashTable *NSCreateHashTable(NSHashTableCallBacks callBacks,
  27  NSUInteger capacity) {
  28    return NSCreateHashTableWithZone(callBacks,capacity,NULL);
  29 }
  30
  31 NSHashTable *NSCreateHashTableWithZone(NSHashTableCallBacks callBacks,
  32  NSUInteger capacity,NSZone *zone) {
  33    NSHashTable *table;
  34
  35    if(zone==NULL)
  36     zone=NSDefaultMallocZone();
  37
  38    table=NSZoneMalloc(zone,sizeof(NSHashTable));
  39
  40    table->callBacks=NSZoneMalloc(zone,sizeof(NSHashTableCallBacks));
  41    *(table->callBacks)=_NSHashTableFixCallbacks(callBacks);
  42
  43    table->count=0;
  44    table->nBuckets=(capacity<4)?4:capacity;
  45    table->buckets=NSZoneCalloc(zone,table->nBuckets,sizeof(NSHashBucket *));
  46
  47    return table;
  48 }
  49
  50 NSHashTable *NSCopyHashTableWithZone(NSHashTable *table,NSZone *zone) {
  51    NSHashTable *newTable=NSCreateHashTableWithZone(*(table->callBacks),
  52       table->count,zone);
  53    NSHashEnumerator state=NSEnumerateHashTable(table);
  54    void *entry;
  55
  56    while((entry=NSNextHashEnumeratorItem(&state))!=NULL)
  57     NSHashInsert(newTable,entry);
  58
  59    return newTable;
  60 }
  61
  62 void NSFreeHashTable(NSHashTable *table) {
  63    NSZone *zone=NSZoneFromPointer(table);
  64    NSUInteger i;
  65    NSHashBucket *j,*next;
  66
  67    for(i=0;i<table->nBuckets;i++){
  68     for(j=table->buckets[i];j!=NULL;j=next){
  69      table->callBacks->release(table,j->key);
  70      next=j->next;
  71      NSZoneFree(zone,j);
  72     }
  73    }
  74    NSZoneFree(zone,table->buckets);
  75    NSZoneFree(zone,table->callBacks);
  76    NSZoneFree(zone,table);
  77 }
  78
  79 void NSResetHashTable(NSHashTable *table) {
  80    NSZone *zone=NSZoneFromPointer(table);
  81    NSUInteger i;
  82    NSHashBucket *j,*next;
  83
  84    for(i=0;i<table->nBuckets;i++){
  85     for(j=table->buckets[i];j!=NULL;j=next){
  86      table->callBacks->release(table,j->key);
  87      next=j->next;
  88      NSZoneFree(zone,j);
  89     }
  90     table->buckets[i]=NULL;
  91    }
  92    table->count=0;
  93 }
  94
  95 BOOL NSCompareHashTables(NSHashTable *table1,NSHashTable *table2) {
  96    NSUInteger i;
  97    NSHashBucket *j;
  98
  99    if(table1->count!=table2->count)
 100     return NO;
 101
 102    for(i=0;i<table1->nBuckets;i++)
 103     for(j=table1->buckets[i];j!=NULL;j=j->next)
 104      if(NSHashGet(table2,j->key)!=j->key)
 105       return NO;
 106
 107    return YES;
 108 }
 109
 110 NSUInteger NSCountHashTable(NSHashTable *table) {
 111    return table->count;
 112 }
 113
 114 void *NSHashGet(NSHashTable *table,const void *pointer) {
 115    NSUInteger i=table->callBacks->hash(table,pointer)%table->nBuckets;
 116    NSHashBucket *j;
 117
 118    for(j=table->buckets[i];j!=NULL;j=j->next)
 119     if(table->callBacks->isEqual(table,j->key,pointer))
 120      return j->key;
 121
 122    return NULL;
 123 }
 124
 125 NSArray *NSAllHashTableObjects(NSHashTable *table) {
 126    NSMutableArray *array;
 127    NSUInteger i;
 128    NSHashBucket *j;
 129
 130    array=[[[NSMutableArray allocWithZone:NULL] initWithCapacity:table->count] autorelease];
 131
 132    for(i=0;i<table->nBuckets;i++)
 133     for(j=table->buckets[i];j!=NULL;j=j->next)
 134      [array addObject:j->key];
 135
 136    return array;
 137 }
 138
 139 NSHashEnumerator NSEnumerateHashTable(NSHashTable *table) {
 140    NSHashEnumerator state;
 141
 142    state.table=table;
 143    for(state.i=0;state.i<table->nBuckets;state.i++)
 144     if(table->buckets[state.i]!=NULL)
 145      break;
 146    state.j=(state.i<table->nBuckets)?table->buckets[state.i]:NULL;
 147
 148    return state;
 149 }
 150
 151 void *NSNextHashEnumeratorItem(NSHashEnumerator *state) {
 152    void *key;
 153
 154    if(state->j==NULL)
 155     return NULL;
 156
 157    key=state->j->key;
 158
 159    if((state->j=state->j->next)!=NULL)
 160     return key;
 161
 162    for(state->i++;state->i<state->table->nBuckets;state->i++)
 163     if((state->j=state->table->buckets[state->i])!=NULL)
 164      return key;
 165
 166    state->j=NULL;
 167
 168    return key;
 169 }
 170
 171 void NSHashInsert(NSHashTable *table,const void *pointer) {
 172    NSZone *zone;
 173    NSUInteger hash=table->callBacks->hash(table,pointer);
 174    NSUInteger i=hash%table->nBuckets;
 175    NSHashBucket *j;
 176
 177    for(j=table->buckets[i];j!=NULL;j=j->next)
 178     if(table->callBacks->isEqual(table,j->key,pointer)){
 179      void *old=j->key;
 180      table->callBacks->retain(table,pointer);
 181      j->key=(void *)pointer;
 182      table->callBacks->release(table,old);
 183      return;
 184     }
 185
 186    zone=NSZoneFromPointer(table);
 187
 188    if(table->count>=table->nBuckets){
 189     NSUInteger nBuckets=table->nBuckets;
 190     NSHashBucket **buckets=table->buckets,*next;
 191
 192     table->nBuckets=nBuckets*2;
 193     table->buckets=NSZoneCalloc(zone,table->nBuckets,sizeof(NSHashBucket *));
 194     for(i=0;i<nBuckets;i++)
 195      for(j=buckets[i];j!=NULL;j=next){
 196       NSUInteger newi=table->callBacks->hash(table,j->key)%table->nBuckets;
 197       next=j->next;
 198       j->next=table->buckets[newi];
 199       table->buckets[newi]=j;
 200      }
 201     NSZoneFree(zone,buckets);
 202     i=hash%table->nBuckets;
 203    }
 204
 205    table->callBacks->retain(table,pointer);
 206    j=NSZoneMalloc(zone,sizeof(NSHashBucket));
 207    j->key=(void *)pointer;
 208    j->next=table->buckets[i];
 209    table->buckets[i]=j;
 210    table->count++;
 211 }
 212
 213 void NSHashInsertKnownAbsent(NSHashTable *table,const void *pointer) {
 214    if(NSHashGet(table,pointer)!=NULL){
 215     // FIX
 216     // [NSException raise:NSInvalidArgumentException format:@"NSHashGet
 217     //   returned non-nil in NSHashInsertKnownAbsent"];
 218    }
 219    NSHashInsert(table,pointer);
 220 }
 221
 222 void *NSHashInsertIfAbsent(NSHashTable *table,const void *pointer) {
 223    void *old=NSHashGet(table,pointer);
 224
 225    if(old!=NULL)
 226     return old;
 227    NSHashInsert(table,pointer);
 228    return NULL;
 229 }
 230
 231 void NSHashRemove(NSHashTable *table,const void *pointer) {
 232    NSUInteger i=table->callBacks->hash(table,pointer)%table->nBuckets;
 233    NSHashBucket *j=table->buckets[i],*prev=j;
 234
 235    for(;j!=NULL;j=j->next){
 236     if(table->callBacks->isEqual(table,j->key,pointer)){
 237      if(prev==j)
 238       table->buckets[i]=j->next;
 239      else
 240       prev->next=j->next;
 241      table->callBacks->release(table,j->key);
 242      NSZoneFree(NSZoneFromPointer(j),j);
 243      table->count--;
 244      return;
 245     }
 246     prev=j;
 247    }
 248 }
 249
 250 NSString *NSStringFromHashTable(NSHashTable *table) {
 251    NSMutableString *string=[NSMutableString string];
 252    NSString *fmt=@"%p";
 253    NSUInteger i;
 254    NSHashBucket *j;
 255
 256    for(i=0;i<table->nBuckets;i++){
 257     for(j=table->buckets[i];j!=NULL;j=j->next){
 258      NSString *desc;
 259
 260      if((desc=table->callBacks->describe(table,j->key))!=nil)
 261       [string appendString:desc];
 262      else
 263       [string appendFormat:fmt,j->key];
 264     }
 265    }
 266
 267    return string;
 268 }
 269
 270 static NSUInteger _NSHashPointerHash(NSHashTable *table,const void *object){
 271    return (NSUInteger)object>>5;
 272 }
 273
 274 static NSUInteger _NSHashObjectHash(NSHashTable *table,const void *object){
 275    return [(id)object hash];
 276 }
 277
 278 static BOOL _NSHashPointerIsEqual(NSHashTable *table,const void *object1,
 279   const void *object2){
 280    return (object1==object2)?YES:NO;
 281 }
 282
 283 static BOOL _NSHashObjectIsEqual(NSHashTable *table,const void *object1,
 284   const void *object2){
 285    return [(id)object1 isEqual:(id)object2];
 286 }
 287
 288 static void _NSHashEmptyRetain(NSHashTable *table,const void *object){
 289 }
 290
 291 static void _NSHashObjectRetain(NSHashTable *table,const void *object){
 292    [(id)object retain];
 293 }
 294
 295 static void _NSHashEmptyRelease(NSHashTable *table,void *object){
 296 }
 297
 298 static void _NSHashObjectRelease(NSHashTable *table,void *object){
 299    [(id)object release];
 300 }
 301
 302 static void _NSHashPointerRelease(NSHashTable *table,void *object){
 303    NSZoneFree(NSZoneFromPointer(object),object);
 304 }
 305
 306 static NSString *_NSHashEmptyDescribe(NSHashTable *table,const void *object){
 307    return nil;
 308 }
 309
 310 static NSString *_NSHashObjectDescribe(NSHashTable *table,const void *object){
 311    return [(id)object description];
 312 }
 313
 314 static NSUInteger _NSHashPointerToStructHash(NSHashTable *table,const void *object){
 315    const struct { NSInteger i; } *ptr=object;
 316    return (NSUInteger)ptr->i;
 317 }
 318
 319 static BOOL _NSHashPointerToStructIsEqual(NSHashTable *table,const void *object1,
 320   const void *object2){
 321    const struct { NSInteger i; } *ptr1=object1,*ptr2=object2;
 322    return (ptr1->i==ptr2->i)?YES:NO;
 323 }
 324
 325 const NSHashTableCallBacks NSIntHashCallBacks={
 326  NULL, NULL, NULL, NULL, NULL
 327 };
 328
 329 const NSHashTableCallBacks NSNonOwnedPointerHashCallBacks={
 330  NULL, NULL, NULL, NULL, NULL
 331 };
 332
 333 const NSHashTableCallBacks NSNonRetainedObjectHashCallBacks={
 334  _NSHashObjectHash, _NSHashObjectIsEqual, NULL, NULL, _NSHashObjectDescribe
 335 };
 336
 337 const NSHashTableCallBacks NSObjectHashCallBacks={
 338  _NSHashObjectHash, _NSHashObjectIsEqual, _NSHashObjectRetain, _NSHashObjectRelease, _NSHashObjectDescribe
 339 };
 340
 341 const NSHashTableCallBacks NSOwnedObjectIdentityHashCallBacks={
 342  _NSHashPointerHash, _NSHashPointerIsEqual, _NSHashObjectRetain, _NSHashObjectRelease, _NSHashObjectDescribe
 343 };
 344
 345 const NSHashTableCallBacks NSOwnedPointerHashCallBacks={
 346  NULL, NULL, NULL, _NSHashPointerRelease, NULL
 347 };
 348
 349 const NSHashTableCallBacks NSPointerToStructHashCallBacks={
 350  _NSHashPointerToStructHash, _NSHashPointerToStructIsEqual, NULL, _NSHashPointerRelease, NULL
 351 };
 352
 353 NSHashTableCallBacks _NSHashTableFixCallbacks(NSHashTableCallBacks callBacks){
 354    if(callBacks.hash==NULL)
 355     callBacks.hash=_NSHashPointerHash;
 356    if(callBacks.isEqual==NULL)
 357     callBacks.isEqual=_NSHashPointerIsEqual;
 358    if(callBacks.retain==NULL)
 359     callBacks.retain=_NSHashEmptyRetain;
 360    if(callBacks.release==NULL)
 361     callBacks.release=_NSHashEmptyRelease;
 362    if(callBacks.describe==NULL)
 363     callBacks.describe=_NSHashEmptyDescribe;
 364
 365    return callBacks;
 366 }