Reviewed by Tim Hatcher's rubberstamp
authorbeidson <beidson@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 28 Aug 2006 18:22:32 +0000 (18:22 +0000)
committerbeidson <beidson@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 28 Aug 2006 18:22:32 +0000 (18:22 +0000)
        Rolled out my last change (16070 - pruning WebFileDatabase code) as it caused a difficult-to-track down
        failure in layout tests on a release build.

        * Misc/WebFileDatabase.h:
        * Misc/WebFileDatabase.m:
        (+[WebFileDatabaseOp opWithCode:key:object:]):
        (-[WebFileDatabaseOp initWithCode:key:object:]):
        (-[WebFileDatabaseOp opcode]):
        (-[WebFileDatabaseOp key]):
        (-[WebFileDatabaseOp object]):
        (-[WebFileDatabaseOp perform:]):
        (-[WebFileDatabaseOp dealloc]):
        (SetThreadPriority):
        (-[WebFileDatabase _createLRUList:]):
        (-[WebFileDatabase _truncateToSizeLimit:]):
        (+[WebFileDatabase _syncLoop:]):
        (databaseInit):
        (-[WebFileDatabase setTimer]):
        (-[WebFileDatabase setObject:forKey:]):
        (-[WebFileDatabase removeObjectForKey:]):
        (-[WebFileDatabase removeAllObjects]):
        (-[WebFileDatabase objectForKey:]):
        (-[WebFileDatabase performSetObject:forKey:]):
        (-[WebFileDatabase performRemoveObjectForKey:]):
        (-[WebFileDatabase open]):
        (-[WebFileDatabase close]):
        (-[WebFileDatabase lazySync:]):
        (-[WebFileDatabase sync]):
        (-[WebFileDatabase sizeLimit]):
        (-[WebFileDatabase count]):
        (-[WebFileDatabase usage]):
        (-[WebFileDatabase setSizeLimit:]):
        * Misc/WebIconDatabase.m:
        (-[WebIconDatabase _createFileDatabase]):
        (-[WebIconDatabase _loadIconDictionaries]):
        * WebKit.xcodeproj/project.pbxproj:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@16074 268f45cc-cd09-0410-ab3c-d52691b4dbfc

WebKit/ChangeLog
WebKit/Misc/WebFileDatabase.h
WebKit/Misc/WebFileDatabase.m
WebKit/Misc/WebIconDatabase.m
WebKit/Misc/WebLRUFileList.h [new file with mode: 0644]
WebKit/Misc/WebLRUFileList.m [new file with mode: 0644]
WebKit/WebKit.xcodeproj/project.pbxproj

index 085184d9a51463804f03fe62b6e3bbd685b9cb8d..7c1c7569c3e159e730ee8e139f553506f9e9bff8 100644 (file)
@@ -1,3 +1,44 @@
+2006-08-28  Brady Eidson  <beidson@apple.com>
+
+        Reviewed by Tim Hatcher's rubberstamp
+
+        Rolled out my last change (16070 - pruning WebFileDatabase code) as it caused a difficult-to-track down
+        failure in layout tests on a release build.
+
+        * Misc/WebFileDatabase.h:
+        * Misc/WebFileDatabase.m:
+        (+[WebFileDatabaseOp opWithCode:key:object:]):
+        (-[WebFileDatabaseOp initWithCode:key:object:]):
+        (-[WebFileDatabaseOp opcode]):
+        (-[WebFileDatabaseOp key]):
+        (-[WebFileDatabaseOp object]):
+        (-[WebFileDatabaseOp perform:]):
+        (-[WebFileDatabaseOp dealloc]):
+        (SetThreadPriority):
+        (-[WebFileDatabase _createLRUList:]):
+        (-[WebFileDatabase _truncateToSizeLimit:]):
+        (+[WebFileDatabase _syncLoop:]):
+        (databaseInit):
+        (-[WebFileDatabase setTimer]):
+        (-[WebFileDatabase setObject:forKey:]):
+        (-[WebFileDatabase removeObjectForKey:]):
+        (-[WebFileDatabase removeAllObjects]):
+        (-[WebFileDatabase objectForKey:]):
+        (-[WebFileDatabase performSetObject:forKey:]):
+        (-[WebFileDatabase performRemoveObjectForKey:]):
+        (-[WebFileDatabase open]):
+        (-[WebFileDatabase close]):
+        (-[WebFileDatabase lazySync:]):
+        (-[WebFileDatabase sync]):
+        (-[WebFileDatabase sizeLimit]):
+        (-[WebFileDatabase count]):
+        (-[WebFileDatabase usage]):
+        (-[WebFileDatabase setSizeLimit:]):
+        * Misc/WebIconDatabase.m:
+        (-[WebIconDatabase _createFileDatabase]):
+        (-[WebIconDatabase _loadIconDictionaries]):
+        * WebKit.xcodeproj/project.pbxproj:
+
 2006-08-28  Darin Adler  <darin@apple.com>
 
         Reviewed by Tim Hatcher.
index bff3970f60828a6cae5f966f8810c8daf4838950..54d9ee69ef445084e04b62b4a906a4ce869f721f 100644 (file)
     unsigned count;
     BOOL isOpen;
     unsigned sizeLimit;
-
+    unsigned usage;
+    
+    struct WebLRUFileList *lru;
+    NSMutableArray *ops;
+    NSMutableDictionary *setCache;
+    NSMutableSet *removeCache;
+    
+    NSTimer *timer;
+    NSTimeInterval touch;
+    NSRecursiveLock *mutex;
 }
 
+- (void)setObject:(id)object forKey:(id)key;
+- (void)removeObjectForKey:(id)key;
+- (void)removeAllObjects;
 - (id)objectForKey:(id)key;
 
 - (id)initWithPath:(NSString *)thePath;
 
 - (void)open;
 - (void)close;
+- (void)sync;
 
 - (NSString *)path;
 - (BOOL)isOpen;
 
+- (unsigned)count;
+- (unsigned)sizeLimit;
+- (void)setSizeLimit:(unsigned)limit;
+- (unsigned)usage;
+
+- (void)performSetObject:(id)object forKey:(id)key;
+- (void)performRemoveObjectForKey:(id)key;
+
 @end
index 5b38736cbd4c80f96965d54952887323163c3501..19174c2dc07979a2a47183a9a9162402495992fe 100644 (file)
 
 #import <WebKit/WebFileDatabase.h>
 #import <WebKit/WebKitLogging.h>
+#import <WebKit/WebLRUFileList.h>
 #import <WebKit/WebNSFileManagerExtras.h>
 
 #import <fcntl.h>
 #import <fts.h>
+#import <pthread.h>
 #import <string.h>
 #import <sys/stat.h>
 #import <sys/types.h>
     NS_ENDHANDLER
 #endif
 
+static pthread_once_t databaseInitControl = PTHREAD_ONCE_INIT;
+static NSNumber *WebFileDirectoryPOSIXPermissions;
+static NSNumber *WebFilePOSIXPermissions;
+static NSRunLoop *syncRunLoop;
+
 #define UniqueFilePathSize (34)
+static void UniqueFilePathForKey(id key, char *buffer);
+
+#define MinThreadPriority (10)
+static int SetThreadPriority(int priority);
+
+typedef enum
+{
+    WebFileDatabaseSetObjectOp,
+    WebFileDatabaseRemoveObjectOp,
+} WebFileDatabaseOpcode;
+
+enum
+{
+    MAX_UNSIGNED_LENGTH = 20, // long enough to hold the string representation of a 64-bit unsigned number
+    SYNC_IDLE_THRESHOLD = 10,
+};
+
+// interface WebFileDatabaseOp -------------------------------------------------------------
+
+@interface WebFileDatabaseOp : NSObject
+{
+    WebFileDatabaseOpcode opcode;
+    id key;
+    id object; 
+}
+
++(id)opWithCode:(WebFileDatabaseOpcode)opcode key:(id)key object:(id)object;
+-(id)initWithCode:(WebFileDatabaseOpcode)opcode key:(id)key object:(id)object;
+
+-(WebFileDatabaseOpcode)opcode;
+-(id)key;
+-(id)object;
+-(void)perform:(WebFileDatabase *)target;
+
+@end
+
+
+// implementation WebFileDatabaseOp -------------------------------------------------------------
+
+@implementation WebFileDatabaseOp
+
++(id)opWithCode:(WebFileDatabaseOpcode)theOpcode key:(id)theKey object:(id)theObject
+{
+    return [[[WebFileDatabaseOp alloc] initWithCode:theOpcode key:theKey object:theObject] autorelease];
+}
+
+-(id)initWithCode:(WebFileDatabaseOpcode)theOpcode key:(id)theKey object:(id)theObject
+{
+    ASSERT(theKey);
+
+    if ((self = [super init])) {
+        
+        opcode = theOpcode;
+        key = [theKey retain];
+        object = [theObject retain];
+        
+        return self;
+    }
+  
+    return nil;
+}
+
+-(WebFileDatabaseOpcode)opcode
+{
+    return opcode;
+}
+
+-(id)key
+{
+    return key;
+}
+
+-(id)object
+{
+    return object;
+}
+
+-(void)perform:(WebFileDatabase *)target
+{
+    ASSERT(target);
+
+    switch (opcode) {
+        case WebFileDatabaseSetObjectOp:
+            [target performSetObject:object forKey:key];
+            break;
+        case WebFileDatabaseRemoveObjectOp:
+            [target performRemoveObjectForKey:key];
+            break;
+        default:
+            ASSERT_NOT_REACHED();
+            break;
+    }
+}
+
+-(void)dealloc
+{
+    [key release];
+    [object release];
+    [super dealloc];
+}
+
+@end
+
+
+// interface WebFileDatabasePrivate -----------------------------------------------------------
+
+@interface WebFileDatabase (WebFileDatabasePrivate)
+
+-(void)_createLRUList:(id)arg;
+-(void)_truncateToSizeLimit:(unsigned)size;
+
+@end
+
+// implementation WebFileDatabasePrivate ------------------------------------------------------
+
+@implementation WebFileDatabase (WebFileDatabasePrivate)
+
+static int SetThreadPriority(int priority) 
+{
+    struct sched_param sp;
+
+    memset(&sp, 0, sizeof(struct sched_param));
+    sp.sched_priority=priority;
+    if (pthread_setschedparam(pthread_self(), SCHED_OTHER, &sp) == -1) {
+        LOG_ERROR("Failed to change priority.");
+        return -1;
+    }
+    return 0;
+}
 
 static void UniqueFilePathForKey(id key, char *buffer)
 {
@@ -81,6 +217,56 @@ static void UniqueFilePathForKey(id key, char *buffer)
 #endif
 }
 
+-(void)_createLRUList:(id)arg
+{
+    SetThreadPriority(MinThreadPriority + 1); // make this a little higher priority than the syncRunLoop thread
+
+    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
+
+    BEGIN_EXCEPTION_HANDLER
+    
+    WebLRUFileList *fileList = WebLRUFileListCreate();
+    WebLRUFileListRebuildFileDataUsingRootDirectory(fileList, [path fileSystemRepresentation]);
+    lru = fileList;
+
+    END_EXCEPTION_HANDLER
+
+    LOG(FileDatabaseActivity, "lru list created");
+
+    [pool drain];
+}
+
+-(void)_truncateToSizeLimit:(unsigned)size
+{
+    NSFileManager *defaultManager;
+    
+    if (!lru || size > [self usage]) {
+        return;
+    }
+
+    if (size == 0) {
+        [self removeAllObjects];
+    }
+    else {
+        defaultManager = [NSFileManager defaultManager];
+        [mutex lock];
+        while ([self usage] > size) {
+            char uniqueKey[UniqueFilePathSize];
+            if (!WebLRUFileListGetPathOfOldestFile(lru, uniqueKey, UniqueFilePathSize)) {
+                break;
+            }
+            NSString *filePath = [[NSString alloc] initWithFormat:@"%@/%s", path, uniqueKey];
+            [defaultManager _webkit_removeFileOnlyAtPath:filePath];
+            [filePath release];
+            WebLRUFileListRemoveOldestFileFromList(lru);
+        }
+        [mutex unlock];
+    }
+}
+
+@end
+
+
 // implementation WebFileDatabase -------------------------------------------------------------
 
 @implementation WebFileDatabase
@@ -88,8 +274,47 @@ static void UniqueFilePathForKey(id key, char *buffer)
 // creation functions ---------------------------------------------------------------------------
 #pragma mark creation functions
 
++(void)_syncLoop:(id)arg
+{
+    SetThreadPriority(MinThreadPriority);
+
+    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
+    NSPort *placeholderPort;
+
+    BEGIN_EXCEPTION_HANDLER
+
+    syncRunLoop = [NSRunLoop currentRunLoop];
+
+    while (YES) {
+        BEGIN_EXCEPTION_HANDLER
+        // we specifically use an NSRunLoop here to get autorelease pool support
+        placeholderPort = [NSPort port];
+        [syncRunLoop addPort:placeholderPort forMode:NSDefaultRunLoopMode];
+        [syncRunLoop run];
+        [syncRunLoop removePort:placeholderPort forMode:NSDefaultRunLoopMode];
+        END_EXCEPTION_HANDLER
+    }
+
+    END_EXCEPTION_HANDLER
+
+    [pool drain];
+}
+
+static void databaseInit()
+{
+    // set file perms to owner read/write/execute only
+    WebFileDirectoryPOSIXPermissions = [[NSNumber numberWithInt:(WEB_UREAD | WEB_UWRITE | WEB_UEXEC)] retain];
+
+    // set file perms to owner read/write only
+    WebFilePOSIXPermissions = [[NSNumber numberWithInt:(WEB_UREAD | WEB_UWRITE)] retain];
+
+    [NSThread detachNewThreadSelector:@selector(_syncLoop:) toTarget:[WebFileDatabase class] withObject:nil];
+}
+
 -(id)initWithPath:(NSString *)thePath
 {
+    pthread_once(&databaseInitControl, databaseInit);
+
     if (!(self = [super init])) 
         return nil;
         
@@ -101,6 +326,13 @@ static void UniqueFilePathForKey(id key, char *buffer)
     
     isOpen = NO;
     sizeLimit = 0;
+    usage = 0;
+
+    ops = [[NSMutableArray alloc] init];
+    setCache = [[NSMutableDictionary alloc] init];
+    removeCache = [[NSMutableSet alloc] init];
+    timer = nil;
+    mutex = [[NSRecursiveLock alloc] init];
     
     return self;
 }
@@ -111,15 +343,97 @@ static void UniqueFilePathForKey(id key, char *buffer)
     [super dealloc];
 }
 
+
+-(void)setTimer
+{
+    if (timer == nil) {
+        NSDate *fireDate = [[NSDate alloc] initWithTimeIntervalSinceNow:SYNC_IDLE_THRESHOLD];
+        timer = [[NSTimer alloc] initWithFireDate:fireDate interval:SYNC_IDLE_THRESHOLD target:self selector:@selector(lazySync:) userInfo:nil repeats:YES];
+        [fireDate release];
+        [syncRunLoop addTimer:timer forMode:NSDefaultRunLoopMode];
+    }
+}
+
 // database functions ---------------------------------------------------------------------------
 #pragma mark database functions
 
+-(void)setObject:(id)object forKey:(id)key
+{
+    WebFileDatabaseOp *op;
+
+    ASSERT(object);
+    ASSERT(key);
+
+    touch = CFAbsoluteTimeGetCurrent();
+
+    LOG(FileDatabaseActivity, "%p - %@", object, key);
+    
+    [mutex lock];
+    
+    [setCache setObject:object forKey:key];
+    op = [[WebFileDatabaseOp alloc] initWithCode:WebFileDatabaseSetObjectOp key:key object:object];
+    [ops addObject:op];
+    [op release];
+    [self setTimer];
+    
+    [mutex unlock];
+}
+
+-(void)removeObjectForKey:(id)key
+{
+    WebFileDatabaseOp *op;
+
+    ASSERT(key);
+
+    touch = CFAbsoluteTimeGetCurrent();
+    
+    [mutex lock];
+    
+    [removeCache addObject:key];
+    op = [[WebFileDatabaseOp alloc] initWithCode:WebFileDatabaseRemoveObjectOp key:key object:nil];
+    [ops addObject:op];
+    [op release];
+    [self setTimer];
+    
+    [mutex unlock];
+}
+
+-(void)removeAllObjects
+{
+    touch = CFAbsoluteTimeGetCurrent();
+
+    [mutex lock];
+    [setCache removeAllObjects];
+    [removeCache removeAllObjects];
+    [ops removeAllObjects];
+    [self close];
+    [[NSFileManager defaultManager] _webkit_backgroundRemoveFileAtPath:path];
+    [self open];
+    [mutex unlock];
+
+    LOG(FileDatabaseActivity, "removeAllObjects");
+}
+
 -(id)objectForKey:(id)key
 {
     volatile id result;
     
     ASSERT(key);
 
+    touch = CFAbsoluteTimeGetCurrent();
+
+    // check caches
+    [mutex lock];
+    if ([removeCache containsObject:key]) {
+        [mutex unlock];
+        return nil;
+    }
+    if ((result = [setCache objectForKey:key])) {
+        [mutex unlock];
+        return result;
+    }
+    [mutex unlock];
+
     // go to disk
     char uniqueKey[UniqueFilePathSize];
     UniqueFilePathForKey(key, uniqueKey);
@@ -138,6 +452,11 @@ static void UniqueFilePathForKey(id key, char *buffer)
                         // Decoded objects go away when the unarchiver does, so we need to
                         // retain this so we can return it to our caller.
                         result = [[object retain] autorelease];
+                        if (lru) {
+                            // if we can't update the list yet, that's too bad
+                            // but not critically bad
+                            WebLRUFileListTouchFileWithPath(lru, uniqueKey);
+                        }
                         LOG(FileDatabaseActivity, "read disk cache file - %@", key);
                     }
                 }
@@ -151,16 +470,90 @@ static void UniqueFilePathForKey(id key, char *buffer)
     [unarchiver release];
     [data release];
     [filePath release];
+
+    LOG(Timing, "getting value for %@ took %f", key, (CFAbsoluteTimeGetCurrent() - touch));
     
     return result;
 }
 
+-(void)performSetObject:(id)object forKey:(id)key
+{
+    NSString *filePath;
+    NSMutableData *data;
+    NSDictionary *attributes;
+    NSDictionary *directoryAttributes;
+    NSArchiver *archiver;
+    NSFileManager *defaultManager;
+    char uniqueKey[UniqueFilePathSize];
+    BOOL result;
+
+    ASSERT(object);
+    ASSERT(key);
+
+    UniqueFilePathForKey(key, uniqueKey);
+
+    LOG(FileDatabaseActivity, "%@ - %s", key, uniqueKey);
+
+    data = [NSMutableData data];
+    archiver = [[NSArchiver alloc] initForWritingWithMutableData:data];
+    [archiver encodeObject:key];
+    [archiver encodeObject:object];
+    
+    attributes = [NSDictionary dictionaryWithObjectsAndKeys:
+        NSUserName(), NSFileOwnerAccountName,
+        WebFilePOSIXPermissions, NSFilePosixPermissions,
+        NULL
+    ];
+
+    directoryAttributes = [NSDictionary dictionaryWithObjectsAndKeys:
+        NSUserName(), NSFileOwnerAccountName,
+        WebFileDirectoryPOSIXPermissions, NSFilePosixPermissions,
+        NULL
+    ];
+
+    defaultManager = [NSFileManager defaultManager];
+
+    filePath = [[NSString alloc] initWithFormat:@"%@/%s", path, uniqueKey];
+    attributes = [defaultManager fileAttributesAtPath:filePath traverseLink:YES];
+
+    // update usage and truncate before writing file
+    // this has the effect of _always_ keeping disk usage under sizeLimit by clearing away space in anticipation of the write.
+    WebLRUFileListSetFileData(lru, uniqueKey, [data length], CFAbsoluteTimeGetCurrent());
+    [self _truncateToSizeLimit:[self sizeLimit]];
+
+    result = [defaultManager _webkit_createFileAtPathWithIntermediateDirectories:filePath contents:data attributes:attributes directoryAttributes:directoryAttributes];
+
+    if (!result) {
+        WebLRUFileListRemoveFileWithPath(lru, uniqueKey);
+    }
+
+    [archiver release];
+    [filePath release];    
+}
+
+-(void)performRemoveObjectForKey:(id)key
+{
+    NSString *filePath;
+    char uniqueKey[UniqueFilePathSize];
+    
+    ASSERT(key);
+
+    LOG(FileDatabaseActivity, "%@", key);
+
+    UniqueFilePathForKey(key, uniqueKey);
+    filePath = [[NSString alloc] initWithFormat:@"%@/%s", path, uniqueKey];
+    [[NSFileManager defaultManager] _webkit_removeFileOnlyAtPath:filePath];
+    WebLRUFileListRemoveFileWithPath(lru, uniqueKey);
+    [filePath release];
+}
+
 // database management functions ---------------------------------------------------------------------------
 #pragma mark database management functions
 
 -(void)open
 {
     NSFileManager *manager;
+    NSDictionary *attributes;
     BOOL isDir;
     
     if (!isOpen) {
@@ -170,14 +563,119 @@ static void UniqueFilePathForKey(id key, char *buffer)
                 isOpen = YES;
             }
         }
+        else {
+            attributes = [NSDictionary dictionaryWithObjectsAndKeys:
+                [NSDate date], @"NSFileModificationDate",
+                NSUserName(), @"NSFileOwnerAccountName",
+                WebFileDirectoryPOSIXPermissions, @"NSFilePosixPermissions",
+                NULL
+            ];
+            
+            isOpen = [manager _webkit_createDirectoryAtPathWithIntermediateDirectories:path attributes:attributes];
+        }
+
         // remove any leftover turds
         [manager _webkit_backgroundRemoveLeftoverFiles:path];
+        
+        if (isOpen) {
+            [NSThread detachNewThreadSelector:@selector(_createLRUList:) toTarget:self withObject:nil];
+        }
     }
 }
 
 -(void)close
 {
-    isOpen = NO;
+    if (isOpen) {
+        isOpen = NO;
+        if (lru) {
+            WebLRUFileListRelease(lru);
+            lru = NULL;
+        }
+    }
+}
+
+-(void)lazySync:(NSTimer *)theTimer
+{
+    if (!lru) {
+        // wait for lru to finish getting created        
+        return;
+    }
+
+#ifndef NDEBUG
+    CFTimeInterval mark = CFAbsoluteTimeGetCurrent();
+#endif
+
+    LOG(FileDatabaseActivity, ">>> BEFORE lazySync\n%@", WebLRUFileListDescription(lru));
+
+    WebFileDatabaseOp *op;
+
+    ASSERT(theTimer);
+
+    while (touch + SYNC_IDLE_THRESHOLD < CFAbsoluteTimeGetCurrent() && [ops count] > 0) {
+        [mutex lock];
+
+        if (timer) {
+            [timer invalidate];
+            [timer autorelease];
+            timer = nil;
+        }
+        
+        op = [ops lastObject];
+        if (op) {
+            [op retain];
+            [ops removeLastObject];
+            [op perform:self];
+            [setCache removeObjectForKey:[op key]];
+            [removeCache removeObject:[op key]];
+            [op release];
+        }
+
+        [mutex unlock];
+    }
+
+    // come back later to finish the work...
+    if ([ops count] > 0) {
+        [mutex lock];
+        [self setTimer];
+        [mutex unlock];
+    }
+
+#ifndef NDEBUG
+    if (lru)
+        LOG(FileDatabaseActivity, "<<< AFTER lazySync\n%@", WebLRUFileListDescription(lru));
+
+    CFTimeInterval now = CFAbsoluteTimeGetCurrent();
+    LOG(FileDatabaseActivity, "lazySync ran in %.3f secs.", now - mark);
+#endif
+}
+
+-(void)sync
+{
+    NSArray *array;
+
+    if (!lru) {
+        // wait for lru to finish getting created        
+        return;
+    }
+
+    touch = CFAbsoluteTimeGetCurrent();
+
+    LOG(FileDatabaseActivity, ">>> BEFORE sync\n%@", WebLRUFileListDescription(lru));
+    
+    [mutex lock];
+    array = [ops copy];
+    [ops removeAllObjects];
+    [timer invalidate];
+    [timer autorelease];
+    timer = nil;
+    [setCache removeAllObjects];
+    [removeCache removeAllObjects];
+    [mutex unlock];
+
+    [array makeObjectsPerformSelector:@selector(perform:) withObject:self];
+    [array release];
+
+    LOG(FileDatabaseActivity, "<<< AFTER sync\n%@", WebLRUFileListDescription(lru));
 }
 
 -(NSString *)path
@@ -190,4 +688,35 @@ static void UniqueFilePathForKey(id key, char *buffer)
     return isOpen;
 }
 
+-(unsigned)sizeLimit
+{
+    return sizeLimit;
+}
+
+-(unsigned)count
+{
+    if (lru)
+        return WebLRUFileListCountItems(lru);
+    
+    return 0;
+}
+
+-(unsigned)usage
+{
+    if (lru)
+        return WebLRUFileListGetTotalSize(lru);
+    
+    return 0;
+}
+
+-(void)setSizeLimit:(unsigned)limit
+{
+    sizeLimit = limit;
+    if (limit < [self usage]) {
+        [self _truncateToSizeLimit:limit];
+    }
+}
+
+
+
 @end
index a002a2e6936eddace417870743404e5250a8902c..56467993c9d2b4f9577e4f9e8a5e4d44cbfa1fe5 100644 (file)
@@ -338,6 +338,7 @@ NSSize WebIconLargeSize = {128, 128};
     databaseDirectory = [databaseDirectory stringByExpandingTildeInPath];
     
     _private->fileDatabase = [[WebFileDatabase alloc] initWithPath:databaseDirectory];
+    [_private->fileDatabase setSizeLimit:20000000];
     [_private->fileDatabase open];
 }
 
@@ -380,8 +381,11 @@ NSSize WebIconLargeSize = {128, 128};
     NSMutableDictionary *pageURLToIconURL = nil;
     if (v <= WebIconDatabaseCurrentVersion) {
         pageURLToIconURL = [fileDB objectForKey:WebURLToIconURLKey];
-        // Removing old unnecessary mapping files is unecessary here as it will
-        // happen after the conversion to WebCore format when we wipe everything
+        // Remove the old unnecessary mapping files.
+        if (v < WebIconDatabaseCurrentVersion) {
+            [fileDB removeObjectForKey:ObsoleteIconsOnDiskKey];
+            [fileDB removeObjectForKey:ObsoleteIconURLToURLsKey];
+        }        
     }
     
     // Must double-check all values read from disk. If any are bogus, we just throw out the whole icon cache.
diff --git a/WebKit/Misc/WebLRUFileList.h b/WebKit/Misc/WebLRUFileList.h
new file mode 100644 (file)
index 0000000..2926efa
--- /dev/null
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2005 Apple Computer, Inc.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer. 
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution. 
+ * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
+ *     its contributors may be used to endorse or promote products derived
+ *     from this software without specific prior written permission. 
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#import <CoreFoundation/CoreFoundation.h>
+
+typedef struct WebLRUFileList WebLRUFileList;
+
+WebLRUFileList *WebLRUFileListCreate(void);
+void WebLRUFileListRelease(WebLRUFileList *list);
+
+int WebLRUFileListRebuildFileDataUsingRootDirectory(WebLRUFileList *list, const char *path);
+
+unsigned int WebLRUFileListRemoveFileWithPath(WebLRUFileList *list, const char *path);
+void WebLRUFileListTouchFileWithPath(WebLRUFileList *list, const char *path);
+void WebLRUFileListSetFileData(WebLRUFileList *list, const char *path, unsigned long fileSize, CFTimeInterval time);
+
+Boolean WebLRUFileListGetPathOfOldestFile(WebLRUFileList *list, char *buffer, unsigned int length);
+unsigned int WebLRUFileListRemoveOldestFileFromList(WebLRUFileList *list);
+
+Boolean WebLRUFileListContainsItem(WebLRUFileList *list, const char *path);
+unsigned int WebLRUFileListGetFileSize(WebLRUFileList *list, const char *path);
+unsigned int WebLRUFileListCountItems(WebLRUFileList *list);
+unsigned int WebLRUFileListGetTotalSize(WebLRUFileList *list);
+void WebLRUFileListRemoveAllFilesFromList(WebLRUFileList *list);
+
+NSString *WebLRUFileListDescription(WebLRUFileList *list);
diff --git a/WebKit/Misc/WebLRUFileList.m b/WebKit/Misc/WebLRUFileList.m
new file mode 100644 (file)
index 0000000..b5d0220
--- /dev/null
@@ -0,0 +1,481 @@
+/*
+ * Copyright (C) 2005 Apple Computer, Inc.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer. 
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution. 
+ * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
+ *     its contributors may be used to endorse or promote products derived
+ *     from this software without specific prior written permission. 
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#import <JavaScriptCore/Assertions.h>
+#import <WebKit/WebKitLogging.h>
+#import <WebKit/WebLRUFileList.h>
+
+#import <stdlib.h>
+#import <sys/types.h>
+#import <sys/stat.h>
+#import <fts.h>
+
+#define RemoveFromHeap (TRUE)
+#define DontRemoveFromHeap (FALSE)
+
+struct WebLRUFileList
+{
+    char *rootDirectory;
+    CFBinaryHeapRef heap;
+    CFMutableDictionaryRef dict;
+    unsigned int count;
+    unsigned int totalSize;
+};
+
+typedef struct NSLRUFileData NSLRUFileData;
+
+struct NSLRUFileData
+{
+    unsigned long fileSize;
+    CFTimeInterval heapTime;
+    CFTimeInterval updatedTime;
+    unsigned int markRemoved;
+    char path[1]; // variable size, big enough to hold path string and trailing nul
+};
+
+static CFComparisonResult compareTimes(const void *val1, const void *val2, void *context);
+static Boolean cStringEqual(const void *val1, const void *val2);
+static CFHashCode cStringHash(const void *val);
+static Boolean NSLRUFileDataEqual(const void *val1, const void *val2);
+
+static NSLRUFileData *WebLRUFileListGetOldestFileData(WebLRUFileList *list, Boolean removeFromHeap);
+
+static void NSLRUFileDataReleaseApplierFunction(const void *key, const void *value, void *context);
+static void NSLRUFileDataRelease(CFAllocatorRef allocator, const void *value);
+
+
+WebLRUFileList *WebLRUFileListCreate(void)
+{
+    CFBinaryHeapCallBacks heapCallbacks = {0, NULL, NULL, NULL, compareTimes};
+    CFBinaryHeapCompareContext heapCompareContext = {0, NULL, NULL, NULL, NULL}; 
+    CFDictionaryKeyCallBacks dictKeyCallbacks = {0, NULL, NULL, NULL, cStringEqual, cStringHash};    
+    CFDictionaryValueCallBacks dictValCallbacks = {0, NULL, NULL, NULL, NSLRUFileDataEqual};
+    
+    WebLRUFileList *list = malloc(sizeof(WebLRUFileList));
+    
+    list->rootDirectory = NULL;
+    list->heap = CFBinaryHeapCreate(NULL, 0, &heapCallbacks, &heapCompareContext);
+    list->dict = CFDictionaryCreateMutable(NULL, 0, &dictKeyCallbacks, &dictValCallbacks);    
+    list->count = 0;
+    list->totalSize = 0;
+    
+    return list;
+}
+
+void WebLRUFileListRelease(WebLRUFileList *list)
+{
+    ASSERT(list);
+    free(list->rootDirectory);
+    WebLRUFileListRemoveAllFilesFromList(list);
+    CFRelease(list->heap);
+    CFRelease(list->dict);
+    free(list);
+}
+
+int WebLRUFileListRebuildFileDataUsingRootDirectory(WebLRUFileList *list, const char *path)
+{
+    ASSERT(list);
+    ASSERT(path);
+
+    FTS *fts;
+    FTSENT *ent;
+    char *paths[2];
+    struct stat statInfo;
+    
+    if (stat(path, &statInfo) == -1) {
+        return errno;
+    }
+    if ((statInfo.st_mode & S_IFDIR) == 0) {
+        return ENOTDIR;
+    }
+
+    WebLRUFileListRemoveAllFilesFromList(list);
+    free(list->rootDirectory);
+    list->rootDirectory = strdup(path);
+    int pathLength = strlen(path);
+    
+    paths[0] = (char *)path;
+    paths[1] = NULL;
+    
+    fts = fts_open(paths, FTS_COMFOLLOW | FTS_LOGICAL, NULL);
+    
+    while ((ent = fts_read(fts))) {
+        if (ent->fts_statp->st_mode & S_IFREG) {
+            const char *filePath = ent->fts_accpath + pathLength + 1;
+            WebLRUFileListSetFileData(list, filePath, ent->fts_statp->st_size, ent->fts_statp->st_ctimespec.tv_sec - kCFAbsoluteTimeIntervalSince1970);
+        }
+    }
+
+    fts_close(fts);
+    
+    return 0;
+}
+
+unsigned int WebLRUFileListRemoveFileWithPath(WebLRUFileList *list, const char *path)
+{
+    ASSERT(list);
+    ASSERT(path);
+
+    unsigned int removedFileSize = 0;
+
+    NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
+    if (data) {
+        CFDictionaryRemoveValue(list->dict, path);
+        data->markRemoved = 1;
+        removedFileSize = data->fileSize;
+        list->totalSize -= data->fileSize;
+        ASSERT(list->count > 0);
+        list->count--;
+    }
+    
+    return removedFileSize;
+}
+
+void WebLRUFileListTouchFileWithPath(WebLRUFileList *list, const char *path)
+{
+    ASSERT(list);
+    ASSERT(path);
+
+    NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
+    if (data) {
+        // This is not the same as the "real" mod time of the file on disk
+        // but it is close enough for our purposes
+        data->updatedTime = CFAbsoluteTimeGetCurrent();
+    }
+}
+
+void WebLRUFileListSetFileData(WebLRUFileList *list, const char *path, unsigned long fileSize, CFTimeInterval time)
+{
+    ASSERT(list);
+    ASSERT(path);
+
+    NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
+    if (data) {
+        // update existing data
+        list->totalSize -= data->fileSize;
+        list->totalSize += fileSize;
+        data->fileSize = fileSize;
+        data->updatedTime = time;
+    }
+    else {
+        // create new data object
+        // malloc a block that can accommodate the string
+        // account for the size of the string when
+        // allocating the correct size block.
+        size_t mallocSize = offsetof(NSLRUFileData, path) + strlen(path) + 1;
+        data = malloc(mallocSize);
+        data->fileSize = fileSize;
+        data->heapTime = data->updatedTime = time;
+        data->markRemoved = 0;
+        strcpy(data->path, path);
+        list->totalSize += fileSize;
+        list->count++;
+        CFBinaryHeapAddValue(list->heap, data);
+        CFDictionarySetValue(list->dict, data->path, data);
+    }
+}
+
+Boolean WebLRUFileListGetPathOfOldestFile(WebLRUFileList *list, char *buffer, unsigned int length)
+{
+    ASSERT(list);
+
+    NSLRUFileData *data = WebLRUFileListGetOldestFileData(list, DontRemoveFromHeap);
+
+    if (data) {
+        unsigned pathLength = strlen(data->path);
+        if (length - 1 >= pathLength) {
+            strcpy(buffer, data->path);
+            return TRUE;
+        }
+    }
+    
+    return FALSE;
+}
+
+unsigned int WebLRUFileListRemoveOldestFileFromList(WebLRUFileList *list)
+{
+    ASSERT(list);
+
+    if (list->count == 0) {
+        return 0;
+    }
+
+    NSLRUFileData *data = WebLRUFileListGetOldestFileData(list, RemoveFromHeap);
+
+    if (!data) {
+        LOG_ERROR("list->count > 0, but no data returned from WebLRUFileListGetOldestFileData");
+    }
+    
+    // no need to remove from heap explicitly
+    // WebLRUFileListGetOldestFileData with RemoveFromHeap call does that
+    CFDictionaryRemoveValue(list->dict, data->path);
+    ASSERT(list->count > 0);
+    list->count--;
+    unsigned int removedFileSize = data->fileSize;
+    list->totalSize -= removedFileSize;
+    LOG(FileDatabaseActivity, "\n\t%s : %ld : %.0f : %.0f\n", data->path, data->fileSize, data->heapTime, data->updatedTime);
+    NSLRUFileDataRelease(NULL, data);
+    return removedFileSize;
+}
+
+Boolean WebLRUFileListContainsItem(WebLRUFileList *list, const char *path)
+{
+    ASSERT(list);
+    ASSERT(path);
+
+    if (list->count == 0) {
+        return FALSE;
+    }
+    
+    NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
+    if (!data) {
+        return FALSE;
+    }
+
+    return TRUE;
+}
+
+unsigned int WebLRUFileListGetFileSize(WebLRUFileList *list, const char *path)
+{
+    ASSERT(list);
+    ASSERT(path);
+
+    unsigned int result = 0;
+
+    if (list->count == 0) {
+        return result;
+    }
+    
+    NSLRUFileData *data = (NSLRUFileData *)CFDictionaryGetValue(list->dict, path);
+    if (!data) {
+        LOG_ERROR("list->count > 0, but no data returned from CFDictionaryGetValue with path: %s", path);
+    }
+
+    result = data->fileSize;
+    
+    return result;
+}
+
+unsigned int WebLRUFileListCountItems(WebLRUFileList *list)
+{
+    ASSERT(list);
+    return list->count;
+}
+
+unsigned int WebLRUFileListGetTotalSize(WebLRUFileList *list)
+{
+    ASSERT(list);
+    return list->totalSize;
+}
+
+void WebLRUFileListRemoveAllFilesFromList(WebLRUFileList *list)
+{
+    ASSERT(list);
+
+    // use dictionary applier function to free all NSLRUFileData objects
+    CFDictionaryApplyFunction(list->dict, NSLRUFileDataReleaseApplierFunction, NULL);
+    
+    CFDictionaryRemoveAllValues(list->dict);
+    CFBinaryHeapRemoveAllValues(list->heap);
+    list->count = 0;
+    list->totalSize = 0;
+}
+
+static CFComparisonResult compareTimes(const void *val1, const void *val2, void *context)
+{
+    ASSERT(val1);
+    ASSERT(val2);
+
+    CFTimeInterval t1 = ((NSLRUFileData *)val1)->heapTime;
+    CFTimeInterval t2 = ((NSLRUFileData *)val2)->heapTime;
+    
+    if (t1 > t2) return kCFCompareGreaterThan;
+    if (t1 < t2) return kCFCompareLessThan;
+    return kCFCompareEqualTo;
+}
+
+static Boolean cStringEqual(const void *val1, const void *val2)
+{
+    ASSERT(val1);
+    ASSERT(val2);
+
+    const char *s1 = (const char *)val1;
+    const char *s2 = (const char *)val2;
+    return strcmp(s1, s2) == 0;
+}
+
+// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
+// or anything like that.
+static const unsigned PHI = 0x9e3779b9U;
+
+// This hash algorithm comes from:
+// http://burtleburtle.net/bob/hash/hashfaq.html
+// http://burtleburtle.net/bob/hash/doobs.html
+static CFHashCode cStringHash(const void *val)
+{
+    ASSERT(val);
+
+    const char *s = (const char *)val;
+    int length = strlen(s);
+    int prefixLength = length < 8 ? length : 8;
+    int suffixPosition = length < 16 ? 8 : length - 8;
+    int i;
+
+    unsigned h = PHI;
+    h += length;
+    h += (h << 10); 
+    h ^= (h << 6); 
+
+    for (i = 0; i < prefixLength; i++) {
+        h += (unsigned char)s[i];
+        h += (h << 10); 
+        h ^= (h << 6); 
+    }
+    for (i = suffixPosition; i < length; i++) {
+        h += (unsigned char)s[i];
+        h += (h << 10); 
+        h ^= (h << 6); 
+    }
+
+    h += (h << 3);
+    h ^= (h >> 11);
+    h += (h << 15);
+    return h;
+}
+
+static Boolean NSLRUFileDataEqual(const void *val1, const void *val2)
+{
+    ASSERT(val1);
+    ASSERT(val2);
+
+    NSLRUFileData *d1 = (NSLRUFileData *)val1;
+    NSLRUFileData *d2 = (NSLRUFileData *)val2;
+    return (d1->fileSize == d2->fileSize &&
+        d1->heapTime == d2->heapTime && 
+        d1->updatedTime == d2->updatedTime && 
+        d1->markRemoved == d2->markRemoved &&
+        strcmp(d1->path, d2->path) == 0);
+}
+
+static NSLRUFileData *WebLRUFileListGetOldestFileData(WebLRUFileList *list, Boolean removeFromHeap)
+{
+    ASSERT(list);
+
+    // Use the heap count directory to account for the need to do lazy removal of heap objects 
+    // that may have been left over by calls to WebLRUFileListRemoveFileWithPath
+    // since whenever WebLRUFileListRemoveFileWithPath is called, 
+    // list->count and the heap's count may no longer be equal
+    unsigned int heapCount = CFBinaryHeapGetCount(list->heap);
+    if (heapCount == 0) {
+        return NULL;
+    }
+
+    unsigned i;
+    NSLRUFileData *data;
+
+    for (i = 0; i < heapCount; i++) {
+        data = (NSLRUFileData *)CFBinaryHeapGetMinimum(list->heap);
+        if (data->markRemoved) {
+            // clean up this object that was marked for removal earlier
+            CFBinaryHeapRemoveMinimumValue(list->heap);
+            NSLRUFileDataRelease(NULL, data);        
+        }
+        else if (data->heapTime != data->updatedTime) {
+            // update this object
+            // reinsert into heap
+            CFBinaryHeapRemoveMinimumValue(list->heap);
+            data->heapTime = data->updatedTime;
+            CFBinaryHeapAddValue(list->heap, data);    
+        }
+        else {
+            // found an object that was neither updated nor marked for removal
+            // return it
+            if (removeFromHeap) {
+                CFBinaryHeapRemoveMinimumValue(list->heap);
+            }
+            return data;
+        }
+    }        
+    
+    // we "wrapped around"
+    // all nodes were touched after they were added, and we are back at the start
+    // just pop off the object that is on top now.
+    data = (NSLRUFileData *)CFBinaryHeapGetMinimum(list->heap);
+    if (data && removeFromHeap) {
+        ASSERT(data->heapTime == data->updatedTime);
+        CFBinaryHeapRemoveMinimumValue(list->heap);
+    }
+    return data;
+}
+
+static void NSLRUFileDataReleaseApplierFunction(const void *key, const void *value, void *context)
+{
+    ASSERT(value);
+    free((NSLRUFileData *)value);
+}
+
+static void NSLRUFileDataRelease(CFAllocatorRef allocator, const void *value)
+{
+    ASSERT(value);
+    free((NSLRUFileData *)value);
+}
+
+// -----------------------------------------------------
+// debugging
+
+static void NSLRUFileDataBinaryHeapDumpApplierFunction(const void *value, void *context)
+{
+    NSMutableString *string = (NSMutableString *)context;
+    NSLRUFileData *data = (NSLRUFileData *)value;
+    [string appendFormat:@"   %s : %6ld : %.0f : %.0f\n", data->path, data->fileSize, data->heapTime, data->updatedTime];
+}
+
+static void NSLRUFileDataDictDumpApplierFunction(const void *key, const void *value, void *context)
+{
+    NSMutableString *string = (NSMutableString *)context;
+    NSLRUFileData *data = (NSLRUFileData *)value;
+    [string appendFormat:@"   %s -> %6ld : %.0f : %.0f\n", (const char *)key, data->fileSize, data->heapTime, data->updatedTime];
+}
+
+NSString *WebLRUFileListDescription(WebLRUFileList *list)
+{
+    NSMutableString *string = [NSMutableString string];
+
+    [string appendFormat:@"\nList root path: %s\n", list->rootDirectory];
+    [string appendFormat:@"List count: %d items\n", list->count];
+    [string appendFormat:@"List total size: %d bytes\n", list->totalSize];
+
+    [string appendFormat:@"\nHeap data: %ld items\n", CFBinaryHeapGetCount(list->heap)];
+    CFBinaryHeapApplyFunction(list->heap, NSLRUFileDataBinaryHeapDumpApplierFunction, string);
+
+    [string appendFormat:@"\nDict data: %ld items\n", CFDictionaryGetCount(list->dict)];
+    CFDictionaryApplyFunction(list->dict, NSLRUFileDataDictDumpApplierFunction, string);
+    
+    return string;
+}
index 06c4f2e8be5010fc9f7f4a3978057cb015d37711..967ee45ccd4d124cc7b4dfa71da5d512c4dbfb11 100644 (file)
                939810790824BF01008DF038 /* WebLocalizableStrings.h in Headers */ = {isa = PBXBuildFile; fileRef = BEE18F990472B73200CA289C /* WebLocalizableStrings.h */; settings = {ATTRIBUTES = (Private, ); }; };
                9398107A0824BF01008DF038 /* WebKitSystemBits.h in Headers */ = {isa = PBXBuildFile; fileRef = BEE52D4A0473032500CA289C /* WebKitSystemBits.h */; };
                9398107C0824BF01008DF038 /* WebFileDatabase.h in Headers */ = {isa = PBXBuildFile; fileRef = BE07CEA9047538F000CA289C /* WebFileDatabase.h */; };
+               9398107D0824BF01008DF038 /* WebLRUFileList.h in Headers */ = {isa = PBXBuildFile; fileRef = BE07CEAB047538F000CA289C /* WebLRUFileList.h */; };
                9398107E0824BF01008DF038 /* WebNSURLExtras.h in Headers */ = {isa = PBXBuildFile; fileRef = BE6DC39904C62C4E004D0EF6 /* WebNSURLExtras.h */; settings = {ATTRIBUTES = (Private, ); }; };
                9398107F0824BF01008DF038 /* WebDocumentInternal.h in Headers */ = {isa = PBXBuildFile; fileRef = ED21B9810528F7AA003299AC /* WebDocumentInternal.h */; };
                939810800824BF01008DF038 /* WebDocumentPrivate.h in Headers */ = {isa = PBXBuildFile; fileRef = 833987810543012D00EE146E /* WebDocumentPrivate.h */; settings = {ATTRIBUTES = (Private, ); }; };
                9398110D0824BF01008DF038 /* WebLocalizableStrings.m in Sources */ = {isa = PBXBuildFile; fileRef = BEE18F9A0472B73200CA289C /* WebLocalizableStrings.m */; };
                9398110E0824BF01008DF038 /* WebKitSystemBits.m in Sources */ = {isa = PBXBuildFile; fileRef = BEE52D4B0473032500CA289C /* WebKitSystemBits.m */; };
                939811100824BF01008DF038 /* WebFileDatabase.m in Sources */ = {isa = PBXBuildFile; fileRef = BE07CEAA047538F000CA289C /* WebFileDatabase.m */; };
+               939811110824BF01008DF038 /* WebLRUFileList.m in Sources */ = {isa = PBXBuildFile; fileRef = BE07CEAC047538F000CA289C /* WebLRUFileList.m */; };
                939811120824BF01008DF038 /* WebNSURLExtras.m in Sources */ = {isa = PBXBuildFile; fileRef = BE6DC39A04C62C4E004D0EF6 /* WebNSURLExtras.m */; };
                939811130824BF01008DF038 /* WebHistory.m in Sources */ = {isa = PBXBuildFile; fileRef = 65DA2608052CC18700A97B31 /* WebHistory.m */; };
                939811150824BF01008DF038 /* WebNSDataExtras.m in Sources */ = {isa = PBXBuildFile; fileRef = BECD142A0565830A005BB09C /* WebNSDataExtras.m */; };
                ABDDF20C08EB0DDC001E1241 /* WebDownloadInternal.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = WebDownloadInternal.h; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
                BE07CEA9047538F000CA289C /* WebFileDatabase.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = WebFileDatabase.h; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
                BE07CEAA047538F000CA289C /* WebFileDatabase.m */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.objc; path = WebFileDatabase.m; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
+               BE07CEAB047538F000CA289C /* WebLRUFileList.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = WebLRUFileList.h; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
+               BE07CEAC047538F000CA289C /* WebLRUFileList.m */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.objc; path = WebLRUFileList.m; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
                BE4FBECB0653DF47005EDE15 /* WebEditingDelegate.h */ = {isa = PBXFileReference; fileEncoding = 4; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = WebEditingDelegate.h; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
                BE6DC39904C62C4E004D0EF6 /* WebNSURLExtras.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = WebNSURLExtras.h; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
                BE6DC39A04C62C4E004D0EF6 /* WebNSURLExtras.m */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.objc; path = WebNSURLExtras.m; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
                                F528E3EB031E91AD01CA2ACA /* WebIconDatabasePrivate.h */,
                                BE07CEA9047538F000CA289C /* WebFileDatabase.h */,
                                BE07CEAA047538F000CA289C /* WebFileDatabase.m */,
+                               BE07CEAB047538F000CA289C /* WebLRUFileList.h */,
+                               BE07CEAC047538F000CA289C /* WebLRUFileList.m */,
                                2568C72C0174912D0ECA149E /* WebKit.h */,
                                F5927D4E02D26C5E01CA2DBB /* WebKitErrors.h */,
                                83730F9803FB1E660004736E /* WebKitErrors.m */,
                                939810790824BF01008DF038 /* WebLocalizableStrings.h in Headers */,
                                9398107A0824BF01008DF038 /* WebKitSystemBits.h in Headers */,
                                9398107C0824BF01008DF038 /* WebFileDatabase.h in Headers */,
+                               9398107D0824BF01008DF038 /* WebLRUFileList.h in Headers */,
                                9398107E0824BF01008DF038 /* WebNSURLExtras.h in Headers */,
                                9398107F0824BF01008DF038 /* WebDocumentInternal.h in Headers */,
                                939810800824BF01008DF038 /* WebDocumentPrivate.h in Headers */,
                                9398110D0824BF01008DF038 /* WebLocalizableStrings.m in Sources */,
                                9398110E0824BF01008DF038 /* WebKitSystemBits.m in Sources */,
                                939811100824BF01008DF038 /* WebFileDatabase.m in Sources */,
+                               939811110824BF01008DF038 /* WebLRUFileList.m in Sources */,
                                939811120824BF01008DF038 /* WebNSURLExtras.m in Sources */,
                                939811130824BF01008DF038 /* WebHistory.m in Sources */,
                                939811150824BF01008DF038 /* WebNSDataExtras.m in Sources */,