WebKit/Misc/WebLRUFileList.m

   1 /*
   2  * Copyright (C) 2005 Apple Computer, Inc.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1.  Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  * 2.  Redistributions in binary form must reproduce the above copyright
  11  *     notice, this list of conditions and the following disclaimer in the
  12  *     documentation and/or other materials provided with the distribution.
  13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  14  *     its contributors may be used to endorse or promote products derived
  15  *     from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #import <JavaScriptCore/Assertions.h>
  30 #import <WebKit/WebKitLogging.h>
  31 #import <WebKit/WebLRUFileList.h>
  32
  33 #import <stdlib.h>
  34 #import <sys/types.h>
  35 #import <sys/stat.h>
  36 #import <fts.h>
  37
  38 #define RemoveFromHeap (TRUE)
  39 #define DontRemoveFromHeap (FALSE)
  40
  41 struct WebLRUFileList
  42 {
  43     char *rootDirectory;
  44     CFBinaryHeapRef heap;
  45     CFMutableDictionaryRef dict;
  46     unsigned int count;
  47     unsigned int totalSize;
  48 };
  49
  50 typedef struct NSLRUFileData NSLRUFileData;
  51
  52 struct NSLRUFileData
  53 {
  54     unsigned long fileSize;
  55     CFTimeInterval heapTime;
  56     CFTimeInterval updatedTime;
  57     unsigned int markRemoved;
  58     char path[1]; // variable size, big enough to hold path string and trailing nul
  59 };
  60
  61 static CFComparisonResult compareTimes(const void *val1, const void *val2, void *context);
  62 static Boolean cStringEqual(const void *val1, const void *val2);
  63 static CFHashCode cStringHash(const void *val);
  64 static Boolean NSLRUFileDataEqual(const void *val1, const void *val2);
  65
  66 static NSLRUFileData *WebLRUFileListGetOldestFileData(WebLRUFileList *list, Boolean removeFromHeap);
  67
  68 static void NSLRUFileDataReleaseApplierFunction(const void *key, const void *value, void *context);
  69 static void NSLRUFileDataRelease(CFAllocatorRef allocator, const void *value);
  70
  71
  72 WebLRUFileList *WebLRUFileListCreate(void)
  73 {
  74     CFBinaryHeapCallBacks heapCallbacks = {0, NULL, NULL, NULL, compareTimes};
  75     CFBinaryHeapCompareContext heapCompareContext = {0, NULL, NULL, NULL, NULL};
  76     CFDictionaryKeyCallBacks dictKeyCallbacks = {0, NULL, NULL, NULL, cStringEqual, cStringHash};
  77     CFDictionaryValueCallBacks dictValCallbacks = {0, NULL, NULL, NULL, NSLRUFileDataEqual};
  78
  79     WebLRUFileList *list = malloc(sizeof(WebLRUFileList));
  80
  81     list->rootDirectory = NULL;
  82     list->heap = CFBinaryHeapCreate(NULL, 0, &heapCallbacks, &heapCompareContext);
  83     list->dict = CFDictionaryCreateMutable(NULL, 0, &dictKeyCallbacks, &dictValCallbacks);
  84     list->count = 0;
  85     list->totalSize = 0;
  86
  87     return list;
  88 }
  89
  90 void WebLRUFileListRelease(WebLRUFileList *list)
  91 {
  92     ASSERT(list);
  93     free(list->rootDirectory);
  94     WebLRUFileListRemoveAllFilesFromList(list);
  95     CFRelease(list->heap);
  96     CFRelease(list->dict);
  97     free(list);
  98 }
  99
 100 int WebLRUFileListRebuildFileDataUsingRootDirectory(WebLRUFileList *list, const char *path)
 101 {
 102     ASSERT(list);
 103     ASSERT(path);
 104
 105     FTS *fts;
 106     FTSENT *ent;
 107     char *paths[2];
 108     struct stat statInfo;
 109
 110     if (stat(path, &statInfo) == -1) {
 111         return errno;
 112     }
 113     if ((statInfo.st_mode & S_IFDIR) == 0) {
 114         return ENOTDIR;
 115     }
 116
 117     WebLRUFileListRemoveAllFilesFromList(list);
 118     free(list->rootDirectory);
 119     list->rootDirectory = strdup(path);
 120     int pathLength = strlen(path);
 121
 122     paths[0] = (char *)path;
 123     paths[1] = NULL;
 124
 125     fts = fts_open(paths, FTS_COMFOLLOW | FTS_LOGICAL, NULL);
 126
 127     while ((ent = fts_read(fts))) {
 128         if (ent->fts_statp->st_mode & S_IFREG) {
 129             const char *filePath = ent->fts_accpath + pathLength + 1;
 130             WebLRUFileListSetFileData(list, filePath, ent->fts_statp->st_size, ent->fts_statp->st_ctimespec.tv_sec - kCFAbsoluteTimeIntervalSince1970);
 131         }
 132     }
 133
 134     fts_close(fts);
 135
 136     return 0;
 137 }
 138
 139 unsigned int WebLRUFileListRemoveFileWithPath(WebLRUFileList *list, const char *path)
 140 {
 141     ASSERT(list);
 142     ASSERT(path);
 143
 144     unsigned int removedFileSize = 0;
 145
 146     NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
 147     if (data) {
 148         CFDictionaryRemoveValue(list->dict, path);
 149         data->markRemoved = 1;
 150         removedFileSize = data->fileSize;
 151         list->totalSize -= data->fileSize;
 152         ASSERT(list->count > 0);
 153         list->count--;
 154     }
 155
 156     return removedFileSize;
 157 }
 158
 159 void WebLRUFileListTouchFileWithPath(WebLRUFileList *list, const char *path)
 160 {
 161     ASSERT(list);
 162     ASSERT(path);
 163
 164     NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
 165     if (data) {
 166         // This is not the same as the "real" mod time of the file on disk
 167         // but it is close enough for our purposes
 168         data->updatedTime = CFAbsoluteTimeGetCurrent();
 169     }
 170 }
 171
 172 void WebLRUFileListSetFileData(WebLRUFileList *list, const char *path, unsigned long fileSize, CFTimeInterval time)
 173 {
 174     ASSERT(list);
 175     ASSERT(path);
 176
 177     NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
 178     if (data) {
 179         // update existing data
 180         list->totalSize -= data->fileSize;
 181         list->totalSize += fileSize;
 182         data->fileSize = fileSize;
 183         data->updatedTime = time;
 184     }
 185     else {
 186         // create new data object
 187         // malloc a block that can accommodate the string
 188         // account for the size of the string when
 189         // allocating the correct size block.
 190         size_t mallocSize = offsetof(NSLRUFileData, path) + strlen(path) + 1;
 191         data = malloc(mallocSize);
 192         data->fileSize = fileSize;
 193         data->heapTime = data->updatedTime = time;
 194         data->markRemoved = 0;
 195         strcpy(data->path, path);
 196         list->totalSize += fileSize;
 197         list->count++;
 198         CFBinaryHeapAddValue(list->heap, data);
 199         CFDictionarySetValue(list->dict, data->path, data);
 200     }
 201 }
 202
 203 Boolean WebLRUFileListGetPathOfOldestFile(WebLRUFileList *list, char *buffer, unsigned int length)
 204 {
 205     ASSERT(list);
 206
 207     NSLRUFileData *data = WebLRUFileListGetOldestFileData(list, DontRemoveFromHeap);
 208
 209     if (data) {
 210         unsigned pathLength = strlen(data->path);
 211         if (length - 1 >= pathLength) {
 212             strcpy(buffer, data->path);
 213             return TRUE;
 214         }
 215     }
 216
 217     return FALSE;
 218 }
 219
 220 unsigned int WebLRUFileListRemoveOldestFileFromList(WebLRUFileList *list)
 221 {
 222     ASSERT(list);
 223
 224     if (list->count == 0) {
 225         return 0;
 226     }
 227
 228     NSLRUFileData *data = WebLRUFileListGetOldestFileData(list, RemoveFromHeap);
 229
 230     if (!data) {
 231         LOG_ERROR("list->count > 0, but no data returned from WebLRUFileListGetOldestFileData");
 232     }
 233
 234     // no need to remove from heap explicitly
 235     // WebLRUFileListGetOldestFileData with RemoveFromHeap call does that
 236     CFDictionaryRemoveValue(list->dict, data->path);
 237     ASSERT(list->count > 0);
 238     list->count--;
 239     unsigned int removedFileSize = data->fileSize;
 240     list->totalSize -= removedFileSize;
 241     LOG(FileDatabaseActivity, "\n\t%s : %ld : %.0f : %.0f\n", data->path, data->fileSize, data->heapTime, data->updatedTime);
 242     NSLRUFileDataRelease(NULL, data);
 243     return removedFileSize;
 244 }
 245
 246 Boolean WebLRUFileListContainsItem(WebLRUFileList *list, const char *path)
 247 {
 248     ASSERT(list);
 249     ASSERT(path);
 250
 251     if (list->count == 0) {
 252         return FALSE;
 253     }
 254
 255     NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
 256     if (!data) {
 257         return FALSE;
 258     }
 259
 260     return TRUE;
 261 }
 262
 263 unsigned int WebLRUFileListGetFileSize(WebLRUFileList *list, const char *path)
 264 {
 265     ASSERT(list);
 266     ASSERT(path);
 267
 268     unsigned int result = 0;
 269
 270     if (list->count == 0) {
 271         return result;
 272     }
 273
 274     NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
 275     if (!data) {
 276         LOG_ERROR("list->count > 0, but no data returned from CFDictionaryGetValue with path: %s", path);
 277     }
 278
 279     result = data->fileSize;
 280
 281     return result;
 282 }
 283
 284 unsigned int WebLRUFileListCountItems(WebLRUFileList *list)
 285 {
 286     ASSERT(list);
 287     return list->count;
 288 }
 289
 290 unsigned int WebLRUFileListGetTotalSize(WebLRUFileList *list)
 291 {
 292     ASSERT(list);
 293     return list->totalSize;
 294 }
 295
 296 void WebLRUFileListRemoveAllFilesFromList(WebLRUFileList *list)
 297 {
 298     ASSERT(list);
 299
 300     // use dictionary applier function to free all NSLRUFileData objects
 301     CFDictionaryApplyFunction(list->dict, NSLRUFileDataReleaseApplierFunction, NULL);
 302
 303     CFDictionaryRemoveAllValues(list->dict);
 304     CFBinaryHeapRemoveAllValues(list->heap);
 305     list->count = 0;
 306     list->totalSize = 0;
 307 }
 308
 309 static CFComparisonResult compareTimes(const void *val1, const void *val2, void *context)
 310 {
 311     ASSERT(val1);
 312     ASSERT(val2);
 313
 314     CFTimeInterval t1 = ((NSLRUFileData *)val1)->heapTime;
 315     CFTimeInterval t2 = ((NSLRUFileData *)val2)->heapTime;
 316
 317     if (t1 > t2) return kCFCompareGreaterThan;
 318     if (t1 < t2) return kCFCompareLessThan;
 319     return kCFCompareEqualTo;
 320 }
 321
 322 static Boolean cStringEqual(const void *val1, const void *val2)
 323 {
 324     ASSERT(val1);
 325     ASSERT(val2);
 326
 327     const char *s1 = (const char *)val1;
 328     const char *s2 = (const char *)val2;
 329     return strcmp(s1, s2) == 0;
 330 }
 331
 332 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
 333 // or anything like that.
 334 static const unsigned PHI = 0x9e3779b9U;
 335
 336 // This hash algorithm comes from:
 337 // http://burtleburtle.net/bob/hash/hashfaq.html
 338 // http://burtleburtle.net/bob/hash/doobs.html
 339 static CFHashCode cStringHash(const void *val)
 340 {
 341     ASSERT(val);
 342
 343     const char *s = (const char *)val;
 344     int length = strlen(s);
 345     int prefixLength = length < 8 ? length : 8;
 346     int suffixPosition = length < 16 ? 8 : length - 8;
 347     int i;
 348
 349     unsigned h = PHI;
 350     h += length;
 351     h += (h << 10);
 352     h ^= (h << 6);
 353
 354     for (i = 0; i < prefixLength; i++) {
 355         h += (unsigned char)s[i];
 356         h += (h << 10);
 357         h ^= (h << 6);
 358     }
 359     for (i = suffixPosition; i < length; i++) {
 360         h += (unsigned char)s[i];
 361         h += (h << 10);
 362         h ^= (h << 6);
 363     }
 364
 365     h += (h << 3);
 366     h ^= (h >> 11);
 367     h += (h << 15);
 368
 369     return h;
 370 }
 371
 372 static Boolean NSLRUFileDataEqual(const void *val1, const void *val2)
 373 {
 374     ASSERT(val1);
 375     ASSERT(val2);
 376
 377     NSLRUFileData *d1 = (NSLRUFileData *)val1;
 378     NSLRUFileData *d2 = (NSLRUFileData *)val2;
 379     return (d1->fileSize == d2->fileSize &&
 380         d1->heapTime == d2->heapTime &&
 381         d1->updatedTime == d2->updatedTime &&
 382         d1->markRemoved == d2->markRemoved &&
 383         strcmp(d1->path, d2->path) == 0);
 384 }
 385
 386 static NSLRUFileData *WebLRUFileListGetOldestFileData(WebLRUFileList *list, Boolean removeFromHeap)
 387 {
 388     ASSERT(list);
 389
 390     // Use the heap count directory to account for the need to do lazy removal of heap objects
 391     // that may have been left over by calls to WebLRUFileListRemoveFileWithPath
 392     // since whenever WebLRUFileListRemoveFileWithPath is called,
 393     // list->count and the heap's count may no longer be equal
 394     unsigned int heapCount = CFBinaryHeapGetCount(list->heap);
 395     if (heapCount == 0) {
 396         return NULL;
 397     }
 398
 399     unsigned i;
 400     NSLRUFileData *data;
 401
 402     for (i = 0; i < heapCount; i++) {
 403         data = (NSLRUFileData *)CFBinaryHeapGetMinimum(list->heap);
 404         if (data->markRemoved) {
 405             // clean up this object that was marked for removal earlier
 406             CFBinaryHeapRemoveMinimumValue(list->heap);
 407             NSLRUFileDataRelease(NULL, data);
 408         }
 409         else if (data->heapTime != data->updatedTime) {
 410             // update this object
 411             // reinsert into heap
 412             CFBinaryHeapRemoveMinimumValue(list->heap);
 413             data->heapTime = data->updatedTime;
 414             CFBinaryHeapAddValue(list->heap, data);
 415         }
 416         else {
 417             // found an object that was neither updated nor marked for removal
 418             // return it
 419             if (removeFromHeap) {
 420                 CFBinaryHeapRemoveMinimumValue(list->heap);
 421             }
 422             return data;
 423         }
 424     }
 425
 426     // we "wrapped around"
 427     // all nodes were touched after they were added, and we are back at the start
 428     // just pop off the object that is on top now.
 429     data = (NSLRUFileData *)CFBinaryHeapGetMinimum(list->heap);
 430     if (data && removeFromHeap) {
 431         ASSERT(data->heapTime == data->updatedTime);
 432         CFBinaryHeapRemoveMinimumValue(list->heap);
 433     }
 434     return data;
 435 }
 436
 437 static void NSLRUFileDataReleaseApplierFunction(const void *key, const void *value, void *context)
 438 {
 439     ASSERT(value);
 440     free((NSLRUFileData *)value);
 441 }
 442
 443 static void NSLRUFileDataRelease(CFAllocatorRef allocator, const void *value)
 444 {
 445     ASSERT(value);
 446     free((NSLRUFileData *)value);
 447 }
 448
 449 // -----------------------------------------------------
 450 // debugging
 451
 452 static void NSLRUFileDataBinaryHeapDumpApplierFunction(const void *value, void *context)
 453 {
 454     NSMutableString *string = (NSMutableString *)context;
 455     NSLRUFileData *data = (NSLRUFileData *)value;
 456     [string appendFormat:@"   %s : %6ld : %.0f : %.0f\n", data->path, data->fileSize, data->heapTime, data->updatedTime];
 457 }
 458
 459 static void NSLRUFileDataDictDumpApplierFunction(const void *key, const void *value, void *context)
 460 {
 461     NSMutableString *string = (NSMutableString *)context;
 462     NSLRUFileData *data = (NSLRUFileData *)value;
 463     [string appendFormat:@"   %s -> %6ld : %.0f : %.0f\n", (const char *)key, data->fileSize, data->heapTime, data->updatedTime];
 464 }
 465
 466 NSString *WebLRUFileListDescription(WebLRUFileList *list)
 467 {
 468     NSMutableString *string = [NSMutableString string];
 469
 470     [string appendFormat:@"\nList root path: %s\n", list->rootDirectory];
 471     [string appendFormat:@"List count: %d items\n", list->count];
 472     [string appendFormat:@"List total size: %d bytes\n", list->totalSize];
 473
 474     [string appendFormat:@"\nHeap data: %ld items\n", CFBinaryHeapGetCount(list->heap)];
 475     CFBinaryHeapApplyFunction(list->heap, NSLRUFileDataBinaryHeapDumpApplierFunction, string);
 476
 477     [string appendFormat:@"\nDict data: %ld items\n", CFDictionaryGetCount(list->dict)];
 478     CFDictionaryApplyFunction(list->dict, NSLRUFileDataDictDumpApplierFunction, string);
 479
 480     return string;
 481 }