Rubber stamped by Hyatt.
[WebKit-https.git] / 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 <WebKit/WebAssertions.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         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         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 }