Oolite 1.91.0.7644-241112-7f5034b
Loading...
Searching...
No Matches
OOCache.m
Go to the documentation of this file.
1/*
2
3OOCache.m
4By Jens Ayton
5
6Oolite
7Copyright (C) 2004-2013 Giles C Williams and contributors
8
9This program is free software; you can redistribute it and/or
10modify it under the terms of the GNU General Public License
11as published by the Free Software Foundation; either version 2
12of the License, or (at your option) any later version.
13
14This program is distributed in the hope that it will be useful,
15but WITHOUT ANY WARRANTY; without even the implied warranty of
16MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17GNU General Public License for more details.
18
19You should have received a copy of the GNU General Public License
20along with this program; if not, write to the Free Software
21Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
22MA 02110-1301, USA.
23
24*/
25
26/* IMPLEMENTATION NOTES
27 A cache needs to be able to implement three types of operation
28 efficiently:
29 * Retrieving: looking up an element by key.
30 * Inserting: setting the element associated with a key.
31 * Deleting: removing a single element.
32 * Pruning: removing one or more least-recently used elements.
33
34 An NSMutableDictionary performs the first three operations efficiently but
35 has no support for pruning - specifically no support for finding the
36 least-recently-accessed element. Using standard Foundation containers, it
37 would be necessary to use several dictionaries and arrays, which would be
38 quite inefficient since small NSArrays aren’t very good at head insertion
39 or deletion. Alternatively, a standard dictionary whose value objects
40 maintain an age-sorted list could be used.
41
42 I chose instead to implement a custom scheme from scratch. It uses two
43 parallel data structures: a doubly-linked list sorted by age, and a splay
44 tree to implement insertion/deletion. The implementation is largely
45 procedural C. Deserialization, pruning and modification tracking is done
46 in the ObjC class; everything else is done in C functions.
47
48 A SPLAY TREE is a type of semi-balanced binary search tree with certain
49 useful properties:
50 * Simplicity. All look-up and restructuring operations are based on a
51 single operation, splaying, which brings the node with the desired key
52 (or the node whose key is "left" of the desired key, if there is no
53 exact match) to the root, while maintaining the binary search tree
54 invariant. Splaying itself is sufficient for look-up; insertion and
55 deletion work by splaying and then manipulating at the root.
56 * Self-optimization. Because each look-up brings the sought element to
57 the root, often-used elements tend to stay near the top. (Oolite often
58 performs sequences of identical look-ups, for instance when creating
59 an asteroid field, or the racing ring set-up which uses lots of
60 identical ring segments; during combat, missiles, canisters and hull
61 plates will be commonly used.) Also, this means that for a retrieve-
62 attempt/insert sequence, the retrieve attempt will optimize the tree
63 for the insertion.
64 * Efficiency. In addition to the self-optimization, splay trees have a
65 small code size and no storage overhead for flags.
66 The amortized worst-case cost of splaying (cost averaged over a
67 worst-case sequence of operations) is O(log n); a single worst-case
68 splay is O(n), but that worst-case also improves the balance of the
69 tree, so you can't have two worst cases in a row. Insertion and
70 deletion are also O(log n), consisting of a splay plus an O(1)
71 operation.
72 References for splay trees:
73 * http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
74 Original research paper.
75 * http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.html
76 Java applet demonstrating splaying.
77 * http://www.link.cs.cmu.edu/link/ftp-site/splaying/top-down-splay.c
78 Sample implementation by one of the inventors. The TreeSplay(),
79 TreeInsert() and CacheRemove() functions are based on this.
80
81 The AGE LIST is a doubly-linked list, ordered from oldest to youngest.
82 Whenever an element is retrieved or inserted, it is promoted to the
83 youngest end of the age list. Pruning proceeds from the oldest end of the
84 age list.
85
86 if (autoPrune)
87 {
88 PRUNING is batched, handling 20% of the cache at once. This is primarily
89 because deletion somewhat pessimizes the tree (see "Self-optimization"
90 below). It also provides a bit of code coherency. To reduce pruning
91 batches while in flight, pruning is also performed before serialization
92 (which in turn is done, if the cache has changed, whenever the user
93 docks). This has the effect that the number of items in the cache on disk
94 never exceeds 80% of the prune threshold. This is probably not actually
95 poinful, since pruning should be a very small portion of the per-frame run
96 time in any case. Premature optimization and all that jazz.
97 Pruning performs at most 0.2n deletions, and is thus O(n log n).
98 }
99 else
100 {
101 PRUNING is performed manually by calling -prune.
102 }
103
104 If the macro OOCACHE_PERFORM_INTEGRITY_CHECKS is set to a non-zero value,
105 the integrity of the tree and the age list will be checked before and
106 after each high-level operation. This is an inherently O(n) operation.
107*/
108
109
110#import "OOCache.h"
111#import "OOStringParsing.h"
112
113
114#ifndef OOCACHE_PERFORM_INTEGRITY_CHECKS
115#define OOCACHE_PERFORM_INTEGRITY_CHECKS 0
116#endif
117
118
119// Protocol used internally to squash idiotic warnings in gnu-gcc.
120@protocol OOCacheComparable <NSObject, NSCopying>
121- (NSComparisonResult) compare:(id<OOCacheComparable>)other;
122- (id) copy;
123@end
124
125
128
129
130enum { kCountUnknown = -1U };
131
132
133static NSString * const kSerializedEntryKeyKey = @"key";
134static NSString * const kSerializedEntryKeyValue = @"value";
135
136
137static OOCacheImpl *CacheAllocate(void);
138static void CacheFree(OOCacheImpl *cache);
139
140static BOOL CacheInsert(OOCacheImpl *cache, id key, id value);
141static BOOL CacheRemove(OOCacheImpl *cache, id key);
142static BOOL CacheRemoveOldest(OOCacheImpl *cache, NSString *logKey);
143static id CacheRetrieve(OOCacheImpl *cache, id key);
144static unsigned CacheGetCount(OOCacheImpl *cache);
145static NSArray *CacheArrayOfContentsByAge(OOCacheImpl *cache);
146static NSArray *CacheArrayOfNodesByAge(OOCacheImpl *cache);
147static NSString *CacheGetName(OOCacheImpl *cache);
148static void CacheSetName(OOCacheImpl *cache, NSString *name);
149
150#if OOCACHE_PERFORM_INTEGRITY_CHECKS
151static NSString * const kOOLogCacheIntegrityCheck = @"dataCache.integrityCheck";
152static void CacheCheckIntegrity(OOCacheImpl *cache, NSString *context);
153
154#define CHECK_INTEGRITY(context) CacheCheckIntegrity(cache, (context))
155#else
156#define CHECK_INTEGRITY(context) do {} while (0)
157#endif
158
159
160@interface OOCache (Private)
161
162- (void)loadFromArray:(NSArray *)inArray;
163
164@end
165
166
167@implementation OOCache
168
169
170- (void)dealloc
171{
172 CHECK_INTEGRITY(@"dealloc");
173 CacheFree(cache);
174
175 [super dealloc];
176}
177
178
179- (NSString *)description
180{
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"];
182}
183
184
185- (id)init
186{
187 return [self initWithPList:nil];
188}
189
190
191- (id)initWithPList:(id)pList
192{
193 BOOL OK = YES;
194
195 self = [super init];
196 OK = self != nil;
197
198 if (OK)
199 {
200 cache = CacheAllocate();
201 if (cache == NULL) OK = NO;
202 }
203
204 if (pList != nil)
205 {
206 if (OK) OK = [pList isKindOfClass:[NSArray class]];
207 if (OK) [self loadFromArray:pList];
208 }
209 if (OK)
210 {
211 pruneThreshold = kOOCacheDefaultPruneThreshold;
212 autoPrune = YES;
213 }
214
215 if (!OK)
216 {
217 [self release];
218 self = nil;
219 }
220
221 return self;
222}
223
224
225- (id)pListRepresentation
226{
227 return CacheArrayOfNodesByAge(cache);
228
229 return nil;
230}
231
232
233- (id)objectForKey:(id)key
234{
235 id result = nil;
236
237 CHECK_INTEGRITY(@"objectForKey: before");
238
239 result = CacheRetrieve(cache, key);
240 // Note: while reordering the age list technically makes the cache dirty, it's not worth rewriting it just for that, so we don't flag it.
241
242 CHECK_INTEGRITY(@"objectForKey: after");
243
244 return [[result retain] autorelease];
245}
246
247
248- (void)setObject:inObject forKey:(id)key
249{
250 CHECK_INTEGRITY(@"setObject:forKey: before");
251
252 if (CacheInsert(cache, key, inObject))
253 {
254 dirty = YES;
255 if (autoPrune) [self prune];
256 }
257
258 CHECK_INTEGRITY(@"setObject:forKey: after");
259}
260
261
262- (void)removeObjectForKey:(id)key
263{
264 CHECK_INTEGRITY(@"removeObjectForKey: before");
265
266 if (CacheRemove(cache, key)) dirty = YES;
267
268 CHECK_INTEGRITY(@"removeObjectForKey: after");
269}
270
271
272- (void)setPruneThreshold:(unsigned)threshold
273{
274 threshold = MAX(threshold, (unsigned)kOOCacheMinimumPruneThreshold);
275 if (threshold != pruneThreshold)
276 {
277 pruneThreshold = threshold;
278 if (autoPrune) [self prune];
279 }
280}
281
282
283- (unsigned)pruneThreshold
284{
285 return pruneThreshold;
286}
287
288
289- (void)setAutoPrune:(BOOL)flag
290{
291 BOOL prune = (flag != NO);
292 if (prune != autoPrune)
293 {
294 autoPrune = prune;
295 [self prune];
296 }
297}
298
299
300- (BOOL)autoPrune
301{
302 return autoPrune;
303}
304
305
306- (void)prune
307{
308 unsigned pruneCount;
309 unsigned desiredCount;
310 unsigned count;
311
312 // Order of operations is to ensure rounding down.
313 if (autoPrune) desiredCount = (pruneThreshold * 4) / 5;
314 else desiredCount = pruneThreshold;
315
316 if (pruneThreshold == kOOCacheNoPrune || (count = CacheGetCount(cache)) <= pruneThreshold) return;
317
318 pruneCount = count - desiredCount;
319
320 NSString *logKey = [NSString stringWithFormat:@"dataCache.prune.%@", CacheGetName(cache)];
321 OOLog(logKey, @"Pruning cache \"%@\" - removing %u entries", CacheGetName(cache), pruneCount);
322 OOLogIndentIf(logKey);
323
324 while (pruneCount--) CacheRemoveOldest(cache, logKey);
325
326 OOLogOutdentIf(logKey);
327}
328
329
330- (BOOL)dirty
331{
332 return dirty;
333}
334
335
336- (void)markClean
337{
338 dirty = NO;
339}
340
341
342- (NSString *)name
343{
344 return CacheGetName(cache);
345}
346
347
348- (void)setName:(NSString *)name
349{
350 CacheSetName(cache, name);
351}
352
353
354- (NSArray *) objectsByAge
355{
356 return CacheArrayOfContentsByAge(cache);
357}
358
359@end
360
361
362@implementation OOCache (Private)
363
364- (void)loadFromArray:(NSArray *)array
365{
366 NSEnumerator *entryEnum = nil;
367 NSDictionary *entry = nil;
368 NSString *key = nil;
369 id value = nil;
370
371 if (array == nil) return;
372
373 for (entryEnum = [array objectEnumerator]; (entry = [entryEnum nextObject]); )
374 {
375 if ([entry isKindOfClass:[NSDictionary class]])
376 {
377 key = [entry objectForKey:kSerializedEntryKeyKey];
378 value = [entry objectForKey:kSerializedEntryKeyValue];
379 if ([key isKindOfClass:[NSString class]] && value != nil)
380 {
381 [self setObject:value forKey:key];
382 }
383 }
384 }
385}
386
387@end
388
389
390/***** Most of the implementation. In C. Because I'm inconsistent and slightly m. *****/
391
393{
394 // Splay tree root
396
397 // Ends of age list
398 OOCacheNode *oldest, *youngest;
399
400 unsigned count;
401 NSString *name;
402};
403
404
406{
407 // Payload
408 id<OOCacheComparable> key;
410
411 // Splay tree
412 OOCacheNode *leftChild, *rightChild;
413
414 // Age list
415 OOCacheNode *younger, *older;
416};
417
418static OOCacheNode *CacheNodeAllocate(id<OOCacheComparable> key, id value);
419static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node);
420static id CacheNodeGetValue(OOCacheNode *node);
421static void CacheNodeSetValue(OOCacheNode *node, id value);
422
423#if OOCACHE_PERFORM_INTEGRITY_CHECKS
424static NSString *CacheNodeGetDescription(OOCacheNode *node);
425#endif
426
427static OOCacheNode *TreeSplay(OOCacheNode **root, id<OOCacheComparable> key);
428static OOCacheNode *TreeInsert(OOCacheImpl *cache, id<OOCacheComparable> key, id value);
429
430#if OOCACHE_PERFORM_INTEGRITY_CHECKS
431static unsigned TreeCountNodes(OOCacheNode *node);
432static OOCacheNode *TreeCheckIntegrity(OOCacheImpl *cache, OOCacheNode *node, OOCacheNode *expectedParent, NSString *context);
433#endif
434
435static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node);
436static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node);
437
438#if OOCACHE_PERFORM_INTEGRITY_CHECKS
439static void AgeListCheckIntegrity(OOCacheImpl *cache, NSString *context);
440#endif
441
442
443/***** CacheImpl functions *****/
444
446{
447 return calloc(sizeof (OOCacheImpl), 1);
448}
449
450
451static void CacheFree(OOCacheImpl *cache)
452{
453 if (cache == NULL) return;
454
455 CacheNodeFree(cache, cache->root);
456 [cache->name autorelease];
457 free(cache);
458}
459
460
461static BOOL CacheInsert(OOCacheImpl *cache, id key, id value)
462{
463 OOCacheNode *node = NULL;
464
465 if (cache == NULL || key == nil || value == nil) return NO;
466
467 node = TreeInsert(cache, key, value);
468 if (node != NULL)
469 {
470 AgeListMakeYoungest(cache, node);
471 return YES;
472 }
473 else return NO;
474}
475
476
477static BOOL CacheRemove(OOCacheImpl *cache, id key)
478{
479 OOCacheNode *node = NULL, *newRoot = NULL;
480
481 node = TreeSplay(&cache->root, key);
482 if (node != NULL)
483 {
484 if (node->leftChild == NULL) newRoot = node->rightChild;
485 else
486 {
487 newRoot = node->leftChild;
488 TreeSplay(&newRoot, key);
489 newRoot->rightChild = node->rightChild;
490 }
491 node->leftChild = NULL;
492 node->rightChild = NULL;
493
494 cache->root = newRoot;
495 --cache->count;
496
497 AgeListRemove(cache, node);
498 CacheNodeFree(cache, node);
499
500 return YES;
501 }
502 else return NO;
503}
504
505
506static BOOL CacheRemoveOldest(OOCacheImpl *cache, NSString *logKey)
507{
508 // This could be more efficient, but does it need to be?
509 if (cache == NULL || cache->oldest == NULL) return NO;
510
511 OOLog(logKey, @"Pruning cache \"%@\": removing %@", cache->name, cache->oldest->key);
512 return CacheRemove(cache, cache->oldest->key);
513}
514
515
516static id CacheRetrieve(OOCacheImpl *cache, id key)
517{
518 OOCacheNode *node = NULL;
519 id result = nil;
520
521 if (cache == NULL || key == NULL) return nil;
522
523 node = TreeSplay(&cache->root, key);
524 if (node != NULL)
525 {
526 result = CacheNodeGetValue(node);
527 AgeListMakeYoungest(cache, node);
528 }
529 return result;
530}
531
532
534{
535 OOCacheNode *node = NULL;
536 NSMutableArray *result = nil;
537
538 if (cache == NULL || cache->count == 0) return nil;
539
540 result = [NSMutableArray arrayWithCapacity:cache->count];
541
542 for (node = cache->youngest; node != NULL; node = node->older)
543 {
544 [result addObject:node->value];
545 }
546 return result;
547}
548
549
550static NSArray *CacheArrayOfNodesByAge(OOCacheImpl *cache)
551{
552 OOCacheNode *node = NULL;
553 NSMutableArray *result = nil;
554
555 if (cache == NULL || cache->count == 0) return nil;
556
557 result = [NSMutableArray arrayWithCapacity:cache->count];
558
559 for (node = cache->oldest; node != NULL; node = node->younger)
560 {
561 [result addObject:[NSDictionary dictionaryWithObjectsAndKeys:node->key, kSerializedEntryKeyKey, node->value, kSerializedEntryKeyValue, nil]];
562 }
563 return result;
564}
565
566
567static NSString *CacheGetName(OOCacheImpl *cache)
568{
569 return cache->name;
570}
571
572
573static void CacheSetName(OOCacheImpl *cache, NSString *name)
574{
575 [cache->name autorelease];
576 cache->name = [name copy];
577}
578
579
580static unsigned CacheGetCount(OOCacheImpl *cache)
581{
582 return cache->count;
583}
584
585#if OOCACHE_PERFORM_INTEGRITY_CHECKS
586
587static void CacheCheckIntegrity(OOCacheImpl *cache, NSString *context)
588{
589 unsigned trueCount;
590
591 cache->root = TreeCheckIntegrity(cache, cache->root, NULL, context);
592
593 trueCount = TreeCountNodes(cache->root);
594 if (kCountUnknown == cache->count) cache->count = trueCount;
595 else if (cache->count != trueCount)
596 {
597 OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): count is %u, but should be %u.", context, cache->name, cache->count, trueCount);
598 cache->count = trueCount;
599 }
600
601 AgeListCheckIntegrity(cache, context);
602}
603
604#endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
605
606
607/***** CacheNode functions *****/
608
609// CacheNodeAllocate(): create a cache node for a key, value pair, without inserting it in the structures.
610static OOCacheNode *CacheNodeAllocate(id<OOCacheComparable> key, id value)
611{
612 OOCacheNode *result = NULL;
613
614 if (key == nil || value == nil) return NULL;
615
616 result = calloc(sizeof *result, 1);
617 if (result != NULL)
618 {
619 result->key = [key copy];
620 result->value = [value retain];
621 }
622
623 return result;
624}
625
626
627// CacheNodeFree(): recursively delete a cache node and its children in the splay tree. To delete an individual node, first clear its child pointers.
628static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node)
629{
630 id key, value;
631
632 if (node == NULL) return;
633
634 AgeListRemove(cache, node);
635
636 key = node->key;
637 node->key = nil;
638 [key release];
639
640 value = node->value;
641 node->value = nil;
642 [value release];
643
644 CacheNodeFree(cache, node->leftChild);
645 CacheNodeFree(cache, node->rightChild);
646
647 free(node);
648}
649
650
651// CacheNodeGetValue(): retrieve the value of a cache node
653{
654 if (node == NULL) return nil;
655
656 return node->value;
657}
658
659
660// CacheNodeSetValue(): change the value of a cache node (as when setObject:forKey: is called for an existing key).
661static void CacheNodeSetValue(OOCacheNode *node, id value)
662{
663 if (node == NULL) return;
664
665 id tmp = node->value;
666 node->value = [value retain];
667 [tmp release];
668}
669
670
671#if OOCACHE_PERFORM_INTEGRITY_CHECKS
672// CacheNodeGetDescription(): get a description of a cache node for debugging purposes.
673static NSString *CacheNodeGetDescription(OOCacheNode *node)
674{
675 if (node == NULL) return @"0[null]";
676
677 return [NSString stringWithFormat:@"%p[\"%@\"]", node, node->key];
678}
679#endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
680
681
682/***** Tree functions *****/
683
684/* TreeSplay()
685 This is the fundamental operation of a splay tree. It searches for a node
686 with a given key, and rebalances the tree so that the found node becomes
687 the root. If no match is found, the node moved to the root is the one that
688 would have been found before the target, and will thus be a neighbour of
689 the target if the key is subsequently inserted.
690*/
691static OOCacheNode *TreeSplay(OOCacheNode **root, id<OOCacheComparable> key)
692{
693 NSComparisonResult order;
694 OOCacheNode N = { .leftChild = NULL, .rightChild = NULL };
695 OOCacheNode *node = NULL, *temp = NULL, *l = &N, *r = &N;
696 BOOL exact = NO;
697
698 if (root == NULL || *root == NULL || key == nil) return NULL;
699
700 node = *root;
701
702 for (;;)
703 {
704#ifndef NDEBUG
705 if (node == NULL)
706 {
707 OOLog(@"node.error", @"%@", @"node is NULL");
708 }
709 else if (node->key == NULL)
710 {
711 OOLog(@"node.error", @"%@", @"node->key is NULL");
712 }
713#endif
714 order = [key compare:node->key];
715 if (order == NSOrderedAscending)
716 {
717 // Closest match is in left subtree
718 if (node->leftChild == NULL) break;
719 if ([key compare:node->leftChild->key] == NSOrderedAscending)
720 {
721 // Rotate right
722 temp = node->leftChild;
723 node->leftChild = temp->rightChild;
724 temp->rightChild = node;
725 node = temp;
726 if (node->leftChild == NULL) break;
727 }
728 // Link right
729 r->leftChild = node;
730 r = node;
731 node = node->leftChild;
732 }
733 else if (order == NSOrderedDescending)
734 {
735 // Closest match is in right subtree
736 if (node->rightChild == NULL) break;
737 if ([key compare:node->rightChild->key] == NSOrderedDescending)
738 {
739 // Rotate left
740 temp = node->rightChild;
741 node->rightChild = temp->leftChild;
742 temp->leftChild = node;
743 node = temp;
744 if (node->rightChild == NULL) break;
745 }
746 // Link left
747 l->rightChild = node;
748 l = node;
749 node = node->rightChild;
750 }
751 else
752 {
753 // Found exact match
754 exact = YES;
755 break;
756 }
757 }
758
759 // Assemble
760 l->rightChild = node->leftChild;
761 r->leftChild = node->rightChild;
762 node->leftChild = N.rightChild;
763 node->rightChild = N.leftChild;
764
765 *root = node;
766 return exact ? node : NULL;
767}
768
769
770static OOCacheNode *TreeInsert(OOCacheImpl *cache, id<OOCacheComparable> key, id value)
771{
772 OOCacheNode *closest = NULL,
773 *node = NULL;
774 NSComparisonResult order;
775
776 if (cache == NULL || key == nil || value == nil) return NULL;
777
778 if (cache->root == NULL)
779 {
780 node = CacheNodeAllocate(key, value);
781 cache->root = node;
782 cache->count = 1;
783 }
784 else
785 {
786 node = TreeSplay(&cache->root, key);
787 if (node != NULL)
788 {
789 // Exact match: key already exists, reuse its node
790 CacheNodeSetValue(node, value);
791 }
792 else
793 {
794 closest = cache->root;
795 node = CacheNodeAllocate(key, value);
796 if (EXPECT_NOT(node == NULL)) return NULL;
797
798 order = [key compare:closest->key];
799
800 if (order == NSOrderedAscending)
801 {
802 // Insert to left
803 node->leftChild = closest->leftChild;
804 node->rightChild = closest;
805 closest->leftChild = NULL;
806 cache->root = node;
807 ++cache->count;
808 }
809 else if (order == NSOrderedDescending)
810 {
811 // Insert to right
812 node->rightChild = closest->rightChild;
813 node->leftChild = closest;
814 closest->rightChild = NULL;
815 cache->root = node;
816 ++cache->count;
817 }
818 else
819 {
820 // Key already exists, which we should have caught above
821 OOLog(@"dataCache.inconsistency", @"%s() internal inconsistency for cache \"%@\", insertion failed.", __PRETTY_FUNCTION__, cache->name);
822 CacheNodeFree(cache, node);
823 return NULL;
824 }
825 }
826 }
827
828 return node;
829}
830
831
832#if OOCACHE_PERFORM_INTEGRITY_CHECKS
833static unsigned TreeCountNodes(OOCacheNode *node)
834{
835 if (node == NULL) return 0;
836 return 1 + TreeCountNodes(node->leftChild) + TreeCountNodes(node->rightChild);
837}
838
839
840// TreeCheckIntegrity(): verify the links and contents of a (sub-)tree. If successful, returns the root of the subtree (which could theoretically be changed), otherwise returns NULL.
841static OOCacheNode *TreeCheckIntegrity(OOCacheImpl *cache, OOCacheNode *node, OOCacheNode *expectedParent, NSString *context)
842{
843 NSComparisonResult order;
844 BOOL OK = YES;
845
846 if (node == NULL) return NULL;
847
848 if (OK && node->key == nil)
849 {
850 OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node \"%@\" has nil key; deleting subtree.", context, cache->name, CacheNodeGetDescription(node));
851 OK = NO;
852 }
853
854 if (OK && node->value == nil)
855 {
856 OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node \"%@\" has nil value, deleting.", context, cache->name, CacheNodeGetDescription(node));
857 OK = NO;
858 }
859 if (OK && node->leftChild != NULL)
860 {
861 order = [node->key compare:node->leftChild->key];
862 if (order != NSOrderedDescending)
863 {
864 OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node %@'s left child %@ is not correctly ordered. Deleting subtree.", context, cache->name, CacheNodeGetDescription(node), CacheNodeGetDescription(node->leftChild));
865 CacheNodeFree(cache, node->leftChild);
866 node->leftChild = NULL;
867 cache->count = kCountUnknown;
868 }
869 else
870 {
871 node->leftChild = TreeCheckIntegrity(cache, node->leftChild, node, context);
872 }
873 }
874 if (node->rightChild != NULL)
875 {
876 order = [node->key compare:node->rightChild->key];
877 if (order != NSOrderedAscending)
878 {
879 OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node \"%@\"'s right child \"%@\" is not correctly ordered. Deleting subtree.", context, cache->name, CacheNodeGetDescription(node), CacheNodeGetDescription(node->rightChild));
880 CacheNodeFree(cache, node->rightChild);
881 node->rightChild = NULL;
882 cache->count = kCountUnknown;
883 }
884 else
885 {
886 node->rightChild = TreeCheckIntegrity(cache, node->rightChild, node, context);
887 }
888 }
889
890 if (OK) return node;
891 else
892 {
893 cache->count = kCountUnknown;
894 CacheNodeFree(cache, node);
895 return NULL;
896 }
897}
898#endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
899
900
901/***** Age list functions *****/
902
903// AgeListMakeYoungest(): place a given cache node at the youngest end of the age list.
905{
906 if (cache == NULL || node == NULL) return;
907
908 AgeListRemove(cache, node);
909 node->older = cache->youngest;
910 if (NULL != cache->youngest) cache->youngest->younger = node;
911 cache->youngest = node;
912 if (cache->oldest == NULL) cache->oldest = node;
913}
914
915
916// AgeListRemove(): remove a cache node from the age-sorted tree. Does not affect its position in the splay tree.
917static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node)
918{
919 OOCacheNode *younger = NULL;
920 OOCacheNode *older = NULL;
921
922 if (node == NULL) return;
923
924 younger = node->younger;
925 older = node->older;
926
927 if (cache->youngest == node) cache->youngest = older;
928 if (cache->oldest == node) cache->oldest = younger;
929
930 node->younger = NULL;
931 node->older = NULL;
932
933 if (younger != NULL) younger->older = older;
934 if (older != NULL) older->younger = younger;
935}
936
937
938#if OOCACHE_PERFORM_INTEGRITY_CHECKS
939
940static void AgeListCheckIntegrity(OOCacheImpl *cache, NSString *context)
941{
942 OOCacheNode *node = NULL, *next = NULL;
943 unsigned seenCount = 0;
944
945 if (cache == NULL || context == NULL) return;
946
947 node = cache->youngest;
948
949 if (node) for (;;)
950 {
951 next = node->older;
952 ++seenCount;
953 if (next == NULL) break;
954
955 if (next->younger != node)
956 {
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));
958 next->older = node;
959 }
960 node = next;
961 }
962
963 if (seenCount != cache->count)
964 {
965 // This is especially bad since this function is called just after verifying that the count field reflects the number of objects in the tree.
966 OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): expected %u nodes, found %u. Cannot repair; clearing cache.", context, cache->name, cache->count, seenCount);
967
968 /* Start of temporary extra logging */
969 node = cache->youngest;
970
971 if (node)
972 {
973 for (;;)
974 {
975 next = node->older;
976 ++seenCount;
977 if (next == NULL) break;
978
979 if (node->key != NULL)
980 {
981 OOLog(kOOLogCacheIntegrityCheck,@"Key is: %@",node->key);
982 }
983 else
984 {
985 OOLog(kOOLogCacheIntegrityCheck,@"Key is: NULL");
986 }
987
988 if (node->value != NULL)
989 {
990 OOLog(kOOLogCacheIntegrityCheck,@"Value is: %@",node->value);
991 }
992 else
993 {
994 OOLog(kOOLogCacheIntegrityCheck,@"Value is: NULL");
995 }
996
997 node = next;
998 }
999 }
1000 /* End of temporary extra logging */
1001
1002 cache->count = 0;
1003 CacheNodeFree(cache, cache->root);
1004 cache->root = NULL;
1005 cache->youngest = NULL;
1006 cache->oldest = NULL;
1007 return;
1008 }
1009
1010 if (node != cache->oldest)
1011 {
1012 OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): oldest pointer in cache is wrong (should be \"%@\", is \"%@\"); repairing.", context, cache->name, CacheNodeGetDescription(node), CacheNodeGetDescription(cache->oldest));
1013 cache->oldest = node;
1014 }
1015}
1016
1017#endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
1018
1019
1020#if DEBUG_GRAPHVIZ
1021
1022/* NOTE: enabling AGE_LIST can result in graph rendering times of many hours,
1023 because determining paths for non-constraint arcs is NP-hard. In particular,
1024 I gave up on rendering a dump of a fairly minimal cache manager after
1025 three and a half hours. Individual caches were fine.
1026*/
1027#define AGE_LIST 0
1028
1029@implementation OOCache (DebugGraphViz)
1030
1031- (void) appendNodesFromSubTree:(OOCacheNode *)subTree toString:(NSMutableString *)ioString
1032{
1033 [ioString appendFormat:@"\tn%p [label=\"<f0> | <f1> %@ | <f2>\"];\n", subTree, EscapedGraphVizString([subTree->key description])];
1034
1035 if (subTree->leftChild != NULL)
1036 {
1037 [self appendNodesFromSubTree:subTree->leftChild toString:ioString];
1038 [ioString appendFormat:@"\tn%p:f0 -> n%p:f1;\n", subTree, subTree->leftChild];
1039 }
1040 if (subTree->rightChild != NULL)
1041 {
1042 [self appendNodesFromSubTree:subTree->rightChild toString:ioString];
1043 [ioString appendFormat:@"\tn%p:f2 -> n%p:f1;\n", subTree, subTree->rightChild];
1044 }
1045}
1046
1047
1048- (NSString *) generateGraphVizBodyWithRootNamed:(NSString *)rootName
1049{
1050 NSMutableString *result = nil;
1051
1052 result = [NSMutableString string];
1053
1054 // Root node representing cache
1055 [result appendFormat:@"\t%@ [label=\"Cache \\\"%@\\\"\" shape=box];\n"
1056 "\tnode [shape=record];\n\t\n", rootName, EscapedGraphVizString([self name])];
1057
1058 if (cache == NULL) return result;
1059
1060 // Cache
1061 [self appendNodesFromSubTree:cache->root toString:result];
1062
1063 // Arc from cache object to root node
1064 [result appendString:@"\tedge [color=black constraint=true];\n"];
1065 [result appendFormat:@"\t%@ -> n%p:f1;\n", rootName, cache->root];
1066
1067#if AGE_LIST
1068 OOCacheNode *node = NULL;
1069 // Arcs representing age list
1070 [result appendString:@"\t\n\t// Age-sorted list in blue\n\tedge [color=blue constraint=false];\n"];
1071 node = cache->oldest;
1072 while (node->younger != NULL)
1073 {
1074 [result appendFormat:@"\tn%p:f2 -> n%p:f0;\n", node, node->younger];
1075 node = node->younger;
1076 }
1077#endif
1078
1079 return result;
1080}
1081
1082
1083- (NSString *) generateGraphViz
1084{
1085 NSMutableString *result = nil;
1086
1087 result = [NSMutableString string];
1088
1089 // Header
1090 [result appendFormat:
1091 @"// OOCache dump\n\n"
1092 "digraph cache\n"
1093 "{\n"
1094 "\tgraph [charset=\"UTF-8\", label=\"OOCache \"%@\" debug dump\", labelloc=t, labeljust=l];\n\t\n", [self name]];
1095
1096 [result appendString:[self generateGraphVizBodyWithRootNamed:@"cache"]];
1097
1098 [result appendString:@"}\n"];
1099
1100 return result;
1101}
1102
1103
1104- (void) writeGraphVizToURL:(NSURL *)url
1105{
1106 NSString *graphViz = nil;
1107 NSData *data = nil;
1108
1109 graphViz = [self generateGraphViz];
1110 data = [graphViz dataUsingEncoding:NSUTF8StringEncoding];
1111
1112 if (data != nil)
1113 {
1114 [data writeToURL:url atomically:YES];
1115 }
1116}
1117
1118
1119- (void) writeGraphVizToPath:(NSString *)path
1120{
1121 [self writeGraphVizToURL:[NSURL fileURLWithPath:path]];
1122}
1123
1124@end
1125#endif
1126
@ kOOCacheDefaultPruneThreshold
Definition OOCache.h:52
@ kOOCacheNoPrune
Definition OOCache.h:53
@ kOOCacheMinimumPruneThreshold
Definition OOCache.h:51
static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node)
Definition OOCache.m:904
static NSString *const kSerializedEntryKeyKey
Definition OOCache.m:133
static NSString * CacheGetName(OOCacheImpl *cache)
Definition OOCache.m:567
static void CacheNodeSetValue(OOCacheNode *node, id value)
Definition OOCache.m:661
static OOCacheNode * CacheNodeAllocate(id< OOCacheComparable > key, id value)
Definition OOCache.m:610
static void CacheFree(OOCacheImpl *cache)
Definition OOCache.m:451
static NSArray * CacheArrayOfContentsByAge(OOCacheImpl *cache)
Definition OOCache.m:533
static unsigned CacheGetCount(OOCacheImpl *cache)
Definition OOCache.m:580
#define CHECK_INTEGRITY(context)
Definition OOCache.m:156
@ kCountUnknown
Definition OOCache.m:130
static OOCacheNode * TreeInsert(OOCacheImpl *cache, id< OOCacheComparable > key, id value)
Definition OOCache.m:770
static NSArray * CacheArrayOfNodesByAge(OOCacheImpl *cache)
Definition OOCache.m:550
static BOOL CacheRemoveOldest(OOCacheImpl *cache, NSString *logKey)
Definition OOCache.m:506
static OOCacheImpl * CacheAllocate(void)
Definition OOCache.m:445
static id CacheNodeGetValue(OOCacheNode *node)
Definition OOCache.m:652
static id CacheRetrieve(OOCacheImpl *cache, id key)
Definition OOCache.m:516
static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node)
Definition OOCache.m:917
static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node)
Definition OOCache.m:628
static BOOL CacheRemove(OOCacheImpl *cache, id key)
Definition OOCache.m:477
static NSString *const kSerializedEntryKeyValue
Definition OOCache.m:134
static void CacheSetName(OOCacheImpl *cache, NSString *name)
Definition OOCache.m:573
static BOOL CacheInsert(OOCacheImpl *cache, id key, id value)
Definition OOCache.m:461
static OOCacheNode * TreeSplay(OOCacheNode **root, id< OOCacheComparable > key)
Definition OOCache.m:691
#define EXPECT_NOT(x)
#define OOLogOutdentIf(class)
Definition OOLogging.h:102
#define OOLog(class, format,...)
Definition OOLogging.h:88
#define OOLogIndentIf(class)
Definition OOLogging.h:101
#define MAX(A, B)
Definition OOMaths.h:114
unsigned count
return nil
unsigned count
Definition OOCache.m:400
OOCacheNode * root
Definition OOCache.m:395
OOCacheNode * youngest
Definition OOCache.m:398
NSString * name
Definition OOCache.m:401
OOCacheNode * oldest
Definition OOCache.m:398
OOCacheNode * rightChild
Definition OOCache.m:412
OOCacheNode * older
Definition OOCache.m:415
OOCacheNode * younger
Definition OOCache.m:415
id< OOCacheComparable > key
Definition OOCache.m:408
OOCacheNode * leftChild
Definition OOCache.m:412