114#ifndef OOCACHE_PERFORM_INTEGRITY_CHECKS
115#define OOCACHE_PERFORM_INTEGRITY_CHECKS 0
120@protocol OOCacheComparable <NSObject, NSCopying>
121- (NSComparisonResult) compare:(
id<OOCacheComparable>)other;
150#if OOCACHE_PERFORM_INTEGRITY_CHECKS
151static NSString *
const kOOLogCacheIntegrityCheck =
@"dataCache.integrityCheck";
152static void CacheCheckIntegrity(
OOCacheImpl *cache, NSString *context);
154#define CHECK_INTEGRITY(context) CacheCheckIntegrity(cache, (context))
156#define CHECK_INTEGRITY(context) do {} while (0)
160@interface OOCache (Private)
162- (void)loadFromArray:(NSArray *)inArray;
179- (NSString *)description
181 return [NSString stringWithFormat:@"<%@ %p>{\"%@\", %u elements, prune threshold=%u, auto-prune=%s dirty=%s}", [
self class], self, [
self name], CacheGetCount(cache), pruneThreshold, autoPrune ? "yes" : "no", dirty ? "yes" : "no"];
187 return [
self initWithPList:nil];
191- (id)initWithPList:(
id)pList
201 if (cache == NULL) OK = NO;
206 if (OK) OK = [pList isKindOfClass:[NSArray class]];
207 if (OK) [
self loadFromArray:pList];
225- (id)pListRepresentation
233- (id)objectForKey:(
id)key
244 return [[result retain] autorelease];
248- (void)setObject:inObject forKey:(
id)key
255 if (autoPrune) [
self prune];
262- (void)removeObjectForKey:(
id)key
272- (void)setPruneThreshold:(
unsigned)threshold
275 if (threshold != pruneThreshold)
277 pruneThreshold = threshold;
278 if (autoPrune) [
self prune];
283- (unsigned)pruneThreshold
285 return pruneThreshold;
289- (void)setAutoPrune:(BOOL)flag
291 BOOL prune = (flag != NO);
292 if (prune != autoPrune)
309 unsigned desiredCount;
313 if (autoPrune) desiredCount = (pruneThreshold * 4) / 5;
314 else desiredCount = pruneThreshold;
318 pruneCount =
count - desiredCount;
320 NSString *logKey = [NSString stringWithFormat:@"dataCache.prune.%@", CacheGetName(cache)];
321 OOLog(logKey,
@"Pruning cache \"%@\
" - removing %u entries",
CacheGetName(cache), pruneCount);
348- (void)setName:(NSString *)name
354- (NSArray *) objectsByAge
362@implementation OOCache (Private)
364- (void)loadFromArray:(NSArray *)array
366 NSEnumerator *entryEnum =
nil;
367 NSDictionary *entry =
nil;
371 if (array ==
nil)
return;
373 for (entryEnum = [array objectEnumerator]; (entry = [entryEnum nextObject]); )
375 if ([entry isKindOfClass:[NSDictionary
class]])
377 key = [entry objectForKey:kSerializedEntryKeyKey];
378 value = [entry objectForKey:kSerializedEntryKeyValue];
379 if ([key isKindOfClass:[NSString
class]] && value !=
nil)
381 [
self setObject:value forKey:key];
408 id<OOCacheComparable>
key;
423#if OOCACHE_PERFORM_INTEGRITY_CHECKS
424static NSString *CacheNodeGetDescription(
OOCacheNode *node);
430#if OOCACHE_PERFORM_INTEGRITY_CHECKS
438#if OOCACHE_PERFORM_INTEGRITY_CHECKS
439static void AgeListCheckIntegrity(
OOCacheImpl *cache, NSString *context);
453 if (cache == NULL)
return;
456 [cache->name autorelease];
465 if (cache == NULL || key ==
nil || value ==
nil)
return NO;
494 cache->
root = newRoot;
509 if (cache == NULL || cache->
oldest == NULL)
return NO;
521 if (cache == NULL || key == NULL)
return nil;
536 NSMutableArray *result =
nil;
538 if (cache == NULL || cache->
count == 0)
return nil;
540 result = [NSMutableArray arrayWithCapacity:cache->count];
542 for (node = cache->
youngest; node != NULL; node = node->
older)
544 [result addObject:node->value];
553 NSMutableArray *result =
nil;
555 if (cache == NULL || cache->
count == 0)
return nil;
557 result = [NSMutableArray arrayWithCapacity:cache->count];
559 for (node = cache->
oldest; node != NULL; node = node->
younger)
561 [result addObject:[NSDictionary dictionaryWithObjectsAndKeys:node->key, kSerializedEntryKeyKey, node->value, kSerializedEntryKeyValue, nil]];
575 [cache->name autorelease];
576 cache->
name = [name copy];
585#if OOCACHE_PERFORM_INTEGRITY_CHECKS
587static void CacheCheckIntegrity(
OOCacheImpl *cache, NSString *context)
591 cache->
root = TreeCheckIntegrity(cache, cache->
root, NULL, context);
593 trueCount = TreeCountNodes(cache->
root);
595 else if (cache->
count != trueCount)
597 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): count is %u, but should be %u.", context, cache->
name, cache->
count, trueCount);
598 cache->
count = trueCount;
601 AgeListCheckIntegrity(cache, context);
614 if (key ==
nil || value ==
nil)
return NULL;
616 result = calloc(
sizeof *result, 1);
619 result->
key = [key copy];
620 result->
value = [value retain];
632 if (node == NULL)
return;
654 if (node == NULL)
return nil;
663 if (node == NULL)
return;
665 id tmp = node->
value;
666 node->
value = [value retain];
671#if OOCACHE_PERFORM_INTEGRITY_CHECKS
673static NSString *CacheNodeGetDescription(
OOCacheNode *node)
675 if (node == NULL)
return @"0[null]";
677 return [NSString stringWithFormat:@"%p[\"%@\"]", node, node->key];
693 NSComparisonResult order;
694 OOCacheNode N = { .leftChild = NULL, .rightChild = NULL };
695 OOCacheNode *node = NULL, *temp = NULL, *l = &N, *r = &N;
698 if (root == NULL || *root == NULL || key ==
nil)
return NULL;
707 OOLog(
@"node.error",
@"%@",
@"node is NULL");
709 else if (node->
key == NULL)
711 OOLog(
@"node.error",
@"%@",
@"node->key is NULL");
714 order = [key compare:node->key];
715 if (order == NSOrderedAscending)
719 if ([key compare:node->
leftChild->
key] == NSOrderedAscending)
733 else if (order == NSOrderedDescending)
737 if ([key compare:node->
rightChild->
key] == NSOrderedDescending)
747 l->rightChild = node;
766 return exact ? node : NULL;
774 NSComparisonResult order;
776 if (cache == NULL || key ==
nil || value ==
nil)
return NULL;
778 if (cache->
root == NULL)
794 closest = cache->
root;
798 order = [key compare:closest->key];
800 if (order == NSOrderedAscending)
809 else if (order == NSOrderedDescending)
821 OOLog(
@"dataCache.inconsistency",
@"%s() internal inconsistency for cache \"%@\
", insertion failed.", __PRETTY_FUNCTION__, cache->
name);
832#if OOCACHE_PERFORM_INTEGRITY_CHECKS
835 if (node == NULL)
return 0;
836 return 1 + TreeCountNodes(node->leftChild) + TreeCountNodes(node->rightChild);
843 NSComparisonResult order;
846 if (node == NULL)
return NULL;
848 if (OK && node->
key ==
nil)
850 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): node \"%@\" has nil key; deleting subtree.", context, cache->
name, CacheNodeGetDescription(node));
856 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): node \"%@\" has nil value, deleting.", context, cache->
name, CacheNodeGetDescription(node));
861 order = [node->key compare:node->leftChild->key];
862 if (order != NSOrderedDescending)
864 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): node %@'s left child %@ is not correctly ordered. Deleting subtree.", context, cache->
name, CacheNodeGetDescription(node), CacheNodeGetDescription(node->
leftChild));
876 order = [node->key compare:node->rightChild->key];
877 if (order != NSOrderedAscending)
879 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): node \"%@\"'s right child \"%@\" is not correctly ordered. Deleting subtree.", context, cache->
name, CacheNodeGetDescription(node), CacheNodeGetDescription(node->
rightChild));
906 if (cache == NULL || node == NULL)
return;
922 if (node == NULL)
return;
933 if (younger != NULL) younger->
older = older;
934 if (older != NULL) older->
younger = younger;
938#if OOCACHE_PERFORM_INTEGRITY_CHECKS
940static void AgeListCheckIntegrity(
OOCacheImpl *cache, NSString *context)
943 unsigned seenCount = 0;
945 if (cache == NULL || context == NULL)
return;
953 if (next == NULL)
break;
955 if (next->younger != node)
957 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): node \"%@\" has invalid older link (should be \"%@\", is \"%@\"); repairing.", context, cache->
name, CacheNodeGetDescription(next), CacheNodeGetDescription(node), CacheNodeGetDescription(next->older));
963 if (seenCount != cache->
count)
966 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): expected %u nodes, found %u. Cannot repair; clearing cache.", context, cache->
name, cache->
count, seenCount);
977 if (next == NULL)
break;
979 if (node->
key != NULL)
981 OOLog(kOOLogCacheIntegrityCheck,
@"Key is: %@",node->
key);
985 OOLog(kOOLogCacheIntegrityCheck,
@"Key is: NULL");
988 if (node->
value != NULL)
990 OOLog(kOOLogCacheIntegrityCheck,
@"Value is: %@",node->
value);
994 OOLog(kOOLogCacheIntegrityCheck,
@"Value is: NULL");
1010 if (node != cache->
oldest)
1012 OOLog(kOOLogCacheIntegrityCheck,
@"Integrity check (%@ for \"%@\
"): oldest pointer in cache is wrong (should be \"%@\", is \"%@\"); repairing.", context, cache->
name, CacheNodeGetDescription(node), CacheNodeGetDescription(cache->
oldest));
1029@implementation OOCache (DebugGraphViz)
1031- (void) appendNodesFromSubTree:(
OOCacheNode *)subTree toString:(NSMutableString *)ioString
1033 [ioString appendFormat:@"\tn%p [label=\"<f0> | <f1> %@ | <f2>\"];\n", subTree, EscapedGraphVizString([subTree->key description])];
1037 [
self appendNodesFromSubTree:subTree->leftChild toString:ioString];
1038 [ioString appendFormat:@"\tn%p:f0 -> n%p:f1;\n", subTree, subTree->leftChild];
1042 [
self appendNodesFromSubTree:subTree->rightChild toString:ioString];
1043 [ioString appendFormat:@"\tn%p:f2 -> n%p:f1;\n", subTree, subTree->rightChild];
1048- (NSString *) generateGraphVizBodyWithRootNamed:(NSString *)rootName
1050 NSMutableString *result =
nil;
1052 result = [NSMutableString string];
1055 [result appendFormat:@"\t%@ [label=\"Cache \\\"%@\\\"\" shape=box];\n"
1056 "\tnode [shape=record];\n\t\n", rootName, EscapedGraphVizString([
self name])];
1058 if (cache == NULL)
return result;
1061 [
self appendNodesFromSubTree:cache->root toString:result];
1064 [result appendString:@"\tedge [color=black constraint=true];\n"];
1065 [result appendFormat:@"\t%@ -> n%p:f1;\n", rootName, cache->root];
1070 [result appendString:@"\t\n\t// Age-sorted list in blue\n\tedge [color=blue constraint=false];\n"];
1074 [result appendFormat:@"\tn%p:f2 -> n%p:f0;\n", node, node->younger];
1083- (NSString *) generateGraphViz
1085 NSMutableString *result =
nil;
1087 result = [NSMutableString string];
1090 [result appendFormat:
1091 @"// OOCache dump\n\n"
1094 "\tgraph [charset=\"UTF-8\", label=\"OOCache \"%@\" debug dump\", labelloc=t, labeljust=l];\n\t\n", [
self name]];
1096 [result appendString:[
self generateGraphVizBodyWithRootNamed:@"cache"]];
1098 [result appendString:@"}\n"];
1104- (void) writeGraphVizToURL:(NSURL *)url
1106 NSString *graphViz =
nil;
1109 graphViz = [
self generateGraphViz];
1110 data = [graphViz dataUsingEncoding:NSUTF8StringEncoding];
1114 [data writeToURL:url atomically:YES];
1119- (void) writeGraphVizToPath:(NSString *)path
1121 [
self writeGraphVizToURL:[NSURL fileURLWithPath:path]];
@ kOOCacheDefaultPruneThreshold
@ kOOCacheMinimumPruneThreshold
static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node)
static NSString *const kSerializedEntryKeyKey
static NSString * CacheGetName(OOCacheImpl *cache)
static void CacheNodeSetValue(OOCacheNode *node, id value)
static OOCacheNode * CacheNodeAllocate(id< OOCacheComparable > key, id value)
static void CacheFree(OOCacheImpl *cache)
static NSArray * CacheArrayOfContentsByAge(OOCacheImpl *cache)
static unsigned CacheGetCount(OOCacheImpl *cache)
#define CHECK_INTEGRITY(context)
static OOCacheNode * TreeInsert(OOCacheImpl *cache, id< OOCacheComparable > key, id value)
static NSArray * CacheArrayOfNodesByAge(OOCacheImpl *cache)
static BOOL CacheRemoveOldest(OOCacheImpl *cache, NSString *logKey)
static OOCacheImpl * CacheAllocate(void)
static id CacheNodeGetValue(OOCacheNode *node)
static id CacheRetrieve(OOCacheImpl *cache, id key)
static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node)
static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node)
static BOOL CacheRemove(OOCacheImpl *cache, id key)
static NSString *const kSerializedEntryKeyValue
static void CacheSetName(OOCacheImpl *cache, NSString *name)
static BOOL CacheInsert(OOCacheImpl *cache, id key, id value)
static OOCacheNode * TreeSplay(OOCacheNode **root, id< OOCacheComparable > key)
#define OOLogOutdentIf(class)
#define OOLog(class, format,...)
#define OOLogIndentIf(class)
id< OOCacheComparable > key