objc/objc_association.m

   1 #import <objc/runtime.h>
   2 #import <Foundation/NSObject.h>
   3 #import <Foundation/NSObject.h>
   4 #ifdef WIN32
   5 #include <windows.h>
   6 #else
   7 #include <unistd.h>
   8 #endif
   9
  10 // the cache entry size must be a power of 2
  11 typedef struct {
  12     void                    *nextEntry;
  13     const void              *key;
  14     id                      object;
  15     objc_AssociationPolicy policy;
  16 } AssociationObjectEntry;
  17
  18 #define BucketsInitialSize 509 // Some prime size (and as a bonus, next three n*2+1 are prime too)
  19 #define AssociationObjectEntrySize    5
  20
  21 #define HASHPTR(p) (((unsigned int)p)>>5)
  22
  23 typedef struct AssociationHashBucket {
  24     struct AssociationHashBucket    *next;
  25     id                              key;
  26     AssociationObjectEntry          *value;
  27 } AssociationHashBucket;
  28
  29 typedef struct AssociationTable {
  30     unsigned int              count;
  31     unsigned int              nBuckets;
  32     AssociationHashBucket **buckets;
  33 } AssociationTable;
  34
  35 AssociationTable *CreateAssociationTable(unsigned int capacity) {
  36     AssociationTable *table=malloc(sizeof(AssociationTable));
  37
  38     table->count=0;
  39     table->nBuckets=(capacity<5)?5:capacity;
  40     table->buckets=calloc(table->nBuckets,sizeof(AssociationHashBucket *));
  41
  42     return table;
  43 }
  44
  45 AssociationObjectEntry *AssociationTableGet(AssociationTable *table,id key){
  46     unsigned int i=HASHPTR(key)%table->nBuckets;
  47     AssociationHashBucket *j;
  48
  49     for(j=table->buckets[i];j!=NULL;j=j->next)
  50         if(j->key==key)
  51             return j->value;
  52
  53     return NULL;
  54 }
  55
  56
  57 void AssociationTableInsert(AssociationTable *table,id key, AssociationObjectEntry *value){
  58     unsigned int        hash=HASHPTR(key);
  59     unsigned int        i=hash%table->nBuckets;
  60     AssociationHashBucket *j;
  61
  62     for(j=table->buckets[i];j!=NULL;j=j->next) {
  63         if(j->key==key){
  64             AssociationObjectEntry *oldValue=j->value;
  65
  66             j->value=value;
  67
  68             free(oldValue);
  69             return;
  70         }
  71     }
  72     int newSize = 0;
  73     if (table->count>=table->nBuckets) {
  74         // Expand the buckets size to limit collisions
  75         newSize=table->nBuckets*2+1; // Let"s use odd size
  76     } else if (table->count > BucketsInitialSize && table->count < table->nBuckets/2) {
  77         // Compact the table - plenty of free room
  78         newSize=table->nBuckets/2;
  79         if (newSize%2) {
  80             // Let"s use odd size
  81             newSize+=1;
  82         }
  83     }
  84     if(newSize != 0){
  85         unsigned int         nBuckets=table->nBuckets;
  86         AssociationHashBucket **buckets=table->buckets;
  87
  88         table->nBuckets=newSize;
  89         table->buckets=calloc(table->nBuckets,sizeof(AssociationHashBucket *));
  90
  91         // Get all of the existing buckets and place them into the new list
  92         for(i=0;i<nBuckets;i++) {
  93             j = buckets[i];
  94             while (j) {
  95                 unsigned int newi=HASHPTR(j->key)%table->nBuckets;
  96
  97                 AssociationHashBucket *next = j->next;
  98                 j->next=table->buckets[newi];
  99                 table->buckets[newi]=j;
 100
 101                 j = next;
 102             }
 103         }
 104         free(buckets);
 105         i=hash%table->nBuckets;
 106     }
 107
 108     j=malloc(sizeof(AssociationHashBucket));
 109     j->key=key;
 110     j->value=value;
 111     j->next=table->buckets[i];
 112     table->buckets[i]=j;
 113     table->count++;
 114 }
 115
 116 void *AssociationTableInsertIfAbsent(AssociationTable *table, id key, AssociationObjectEntry *value){
 117     void *old=AssociationTableGet(table,key);
 118
 119     if(old!=NULL)
 120         return old;
 121     AssociationTableInsert(table,key,value);
 122     return NULL;
 123 }
 124
 125 typedef unsigned int AssociationSpinLock;
 126
 127 void AssociationSpinLockLock( volatile AssociationSpinLock *__lock )
 128 {
 129     while(!__sync_bool_compare_and_swap(__lock, 0, 1))
 130     {
 131 #ifdef WIN32
 132         Sleep(0);
 133 #else
 134         usleep(1);
 135 #endif
 136     }
 137 }
 138
 139 void AssociationSpinLockUnlock( volatile AssociationSpinLock *__lock )
 140 {
 141     __sync_bool_compare_and_swap(__lock, 1, 0);
 142 }
 143
 144 static AssociationSpinLock AssociationLock=0;
 145 static AssociationTable *associationTable = NULL;
 146
 147
 148 void AssociationTableRemove(AssociationTable *table,id key){
 149     AssociationSpinLockLock(&AssociationLock);
 150
 151     unsigned int i=HASHPTR(key)%table->nBuckets;
 152     AssociationHashBucket *j=table->buckets[i],*prev=j;
 153
 154     for(;j!=NULL;j=j->next){
 155         if(j->key==key){
 156             // array to keep track of the objects to release - that must be done outside of the lock
 157             // since the release can trigger more association changes
 158             int releaseCount = 0;
 159             int releaseTableSize = 0;
 160             id *objectsToRelease = NULL;
 161
 162             if(prev==j)
 163                 table->buckets[i]=j->next;
 164             else
 165                 prev->next=j->next;
 166
 167             AssociationObjectEntry *entry = j->value;
 168
 169             for (int i = 0; i < AssociationObjectEntrySize; i++) {
 170                 AssociationObjectEntry *e = entry + i;
 171                 while (e) {
 172                     switch (e->policy) {
 173                         case OBJC_ASSOCIATION_ASSIGN:
 174                             break;
 175                         case OBJC_ASSOCIATION_RETAIN_NONATOMIC:
 176                         case OBJC_ASSOCIATION_RETAIN:
 177                         case OBJC_ASSOCIATION_COPY_NONATOMIC:
 178                         case OBJC_ASSOCIATION_COPY:
 179                             if (releaseCount >= releaseTableSize) {
 180                                 if (releaseTableSize == 0) {
 181                                     releaseTableSize = 8;
 182                                 } else {
 183                                     releaseTableSize *= 2;
 184                                 }
 185                                 objectsToRelease = realloc(objectsToRelease, sizeof(id)*releaseTableSize);
 186                             }
 187                             objectsToRelease[releaseCount++] = e->object;
 188                             break;
 189                     }
 190                     AssociationObjectEntry *currentEntry = e;
 191                     e = e->nextEntry;
 192                     // Don't free the first entry of the list - it's part of the "entry" block that will be freed after the loop
 193                     if (currentEntry != entry + i) {
 194                         free(currentEntry);
 195                     }
 196                 }
 197             }
 198
 199             free(entry);
 200             free(j);
 201             table->count--;
 202
 203             AssociationSpinLockUnlock(&AssociationLock);
 204
 205             // Do the cleaning outside of the lock since it might trigger more association playing
 206             for (int i = 0; i < releaseCount; ++i) {
 207                 [objectsToRelease[i] release];
 208             }
 209             free(objectsToRelease);
 210
 211             return;
 212         }
 213         prev=j;
 214     }
 215     AssociationSpinLockUnlock(&AssociationLock);
 216 }
 217
 218 void objc_removeAssociatedObjects(id object)
 219 {
 220     if (associationTable == NULL) {
 221         return;
 222     }
 223     AssociationTableRemove(associationTable, object);
 224
 225 }
 226
 227 void objc_setAssociatedObject(id object, const void *key, id value, objc_AssociationPolicy policy)
 228 {
 229     AssociationSpinLockLock(&AssociationLock);
 230
 231     if (associationTable == NULL) {
 232         associationTable = CreateAssociationTable(BucketsInitialSize);
 233     }
 234
 235     AssociationObjectEntry   *objectTable = AssociationTableGet(associationTable, object);
 236     if (objectTable == NULL) {
 237         objectTable = calloc(sizeof(AssociationObjectEntry), AssociationObjectEntrySize);
 238         AssociationTableInsert(associationTable, object, objectTable);
 239     }
 240
 241     uintptr_t               index = HASHPTR(key) % AssociationObjectEntrySize;
 242     AssociationObjectEntry *entry = ((AssociationObjectEntry *)objectTable) + index;
 243     if (entry->object == nil) {
 244         entry->policy = policy;
 245         entry->key = key;
 246         switch (policy) {
 247             case OBJC_ASSOCIATION_ASSIGN:
 248                 entry->object = value;
 249                 break;
 250             case OBJC_ASSOCIATION_RETAIN_NONATOMIC:
 251             case OBJC_ASSOCIATION_RETAIN:
 252                 entry->object = [value retain];
 253                 break;
 254             case OBJC_ASSOCIATION_COPY_NONATOMIC:
 255             case OBJC_ASSOCIATION_COPY:
 256                 entry->object = [value copy];
 257                 break;
 258         }
 259     }
 260     else {
 261         AssociationObjectEntry *newEntry;
 262         do {
 263             if (entry->key == key) {
 264                 id objectToRelease = nil;
 265
 266                 switch (entry->policy) {
 267                     case OBJC_ASSOCIATION_ASSIGN:
 268                         break;
 269                     case OBJC_ASSOCIATION_RETAIN_NONATOMIC:
 270                     case OBJC_ASSOCIATION_RETAIN:
 271                     case OBJC_ASSOCIATION_COPY_NONATOMIC:
 272                     case OBJC_ASSOCIATION_COPY:
 273                         objectToRelease = entry->object;
 274                         break;
 275                 }
 276                 entry->policy = policy;
 277                 switch (policy) {
 278                     case OBJC_ASSOCIATION_ASSIGN:
 279                         entry->object = value;
 280                         break;
 281                     case OBJC_ASSOCIATION_RETAIN_NONATOMIC:
 282                     case OBJC_ASSOCIATION_RETAIN:
 283                         entry->object = [value retain];
 284                         break;
 285                     case OBJC_ASSOCIATION_COPY_NONATOMIC:
 286                     case OBJC_ASSOCIATION_COPY:
 287                         entry->object = [value copy];
 288                         break;
 289                 }
 290                 AssociationSpinLockUnlock(&AssociationLock);
 291
 292                 // Do the cleaning outside of the lock since it might trigger more association playing
 293                 [objectToRelease release];
 294
 295                 return;
 296             }
 297             if (entry->nextEntry != nil) {
 298                 entry = entry->nextEntry;
 299             }
 300         } while (entry->nextEntry != nil);
 301
 302         newEntry = malloc(sizeof(AssociationObjectEntry));
 303         newEntry->policy = policy;
 304         newEntry->key = key;
 305         switch (policy) {
 306             case OBJC_ASSOCIATION_ASSIGN:
 307                 newEntry->object = value;
 308                 break;
 309             case OBJC_ASSOCIATION_RETAIN_NONATOMIC:
 310             case OBJC_ASSOCIATION_RETAIN:
 311                 newEntry->object = [value retain];
 312                 break;
 313             case OBJC_ASSOCIATION_COPY_NONATOMIC:
 314             case OBJC_ASSOCIATION_COPY:
 315                 newEntry->object = [value copy];
 316                 break;
 317         }
 318         newEntry->nextEntry = NULL;
 319         entry->nextEntry = newEntry;
 320     }
 321
 322     AssociationSpinLockUnlock(&AssociationLock);
 323 }
 324
 325 id objc_getAssociatedObject(id object, const void *key)
 326 {
 327
 328     if (associationTable == NULL) {
 329         return nil;
 330     }
 331
 332     AssociationSpinLockLock(&AssociationLock);
 333
 334
 335     AssociationObjectEntry   *objectTable = AssociationTableGet(associationTable, object);
 336     if (objectTable == NULL) {
 337         AssociationSpinLockUnlock(&AssociationLock);
 338         return nil;
 339     }
 340
 341     uintptr_t               index = HASHPTR(key) % AssociationObjectEntrySize;
 342     AssociationObjectEntry *entry = ((AssociationObjectEntry *)objectTable) + index;
 343     while (entry) {
 344         if (entry->key == key) {
 345             break;
 346         }
 347         entry = entry->nextEntry;
 348     }
 349     AssociationSpinLockUnlock(&AssociationLock);
 350     if (entry) {
 351         return entry->object;
 352     } else {
 353         return nil;
 354     }
 355 }