Line data Source code
1 0 : /*
2 :
3 : OOCache.m
4 : By Jens Ayton
5 :
6 : Oolite
7 : Copyright (C) 2004-2013 Giles C Williams and contributors
8 :
9 : This program is free software; you can redistribute it and/or
10 : modify it under the terms of the GNU General Public License
11 : as published by the Free Software Foundation; either version 2
12 : of the License, or (at your option) any later version.
13 :
14 : This program is distributed in the hope that it will be useful,
15 : but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 : GNU General Public License for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with this program; if not, write to the Free Software
21 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
22 : MA 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 0 : #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 0 : - (NSComparisonResult) compare:(id<OOCacheComparable>)other;
122 0 : - (id) copy;
123 : @end
124 :
125 :
126 0 : typedef struct OOCacheImpl OOCacheImpl;
127 0 : typedef struct OOCacheNode OOCacheNode;
128 :
129 :
130 0 : enum { kCountUnknown = -1U };
131 :
132 :
133 0 : static NSString * const kSerializedEntryKeyKey = @"key";
134 0 : static NSString * const kSerializedEntryKeyValue = @"value";
135 :
136 :
137 : static OOCacheImpl *CacheAllocate(void);
138 : static void CacheFree(OOCacheImpl *cache);
139 :
140 : static BOOL CacheInsert(OOCacheImpl *cache, id key, id value);
141 : static BOOL CacheRemove(OOCacheImpl *cache, id key);
142 : static BOOL CacheRemoveOldest(OOCacheImpl *cache, NSString *logKey);
143 : static id CacheRetrieve(OOCacheImpl *cache, id key);
144 : static unsigned CacheGetCount(OOCacheImpl *cache);
145 : static NSArray *CacheArrayOfContentsByAge(OOCacheImpl *cache);
146 : static NSArray *CacheArrayOfNodesByAge(OOCacheImpl *cache);
147 : static NSString *CacheGetName(OOCacheImpl *cache);
148 : static void CacheSetName(OOCacheImpl *cache, NSString *name);
149 :
150 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
151 : static NSString * const kOOLogCacheIntegrityCheck = @"dataCache.integrityCheck";
152 : static void CacheCheckIntegrity(OOCacheImpl *cache, NSString *context);
153 :
154 : #define CHECK_INTEGRITY(context) CacheCheckIntegrity(cache, (context))
155 : #else
156 0 : #define CHECK_INTEGRITY(context) do {} while (0)
157 : #endif
158 :
159 :
160 : @interface OOCache (Private)
161 :
162 0 : - (void)loadFromArray:(NSArray *)inArray;
163 :
164 : @end
165 :
166 :
167 : @implementation OOCache
168 :
169 :
170 0 : - (void)dealloc
171 : {
172 : CHECK_INTEGRITY(@"dealloc");
173 : CacheFree(cache);
174 :
175 : [super dealloc];
176 : }
177 :
178 :
179 0 : - (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 :
392 0 : struct OOCacheImpl
393 : {
394 : // Splay tree root
395 0 : OOCacheNode *root;
396 :
397 : // Ends of age list
398 0 : OOCacheNode *oldest, *youngest;
399 :
400 0 : unsigned count;
401 0 : NSString *name;
402 : };
403 :
404 :
405 0 : struct OOCacheNode
406 : {
407 : // Payload
408 0 : id<OOCacheComparable> key;
409 0 : id value;
410 :
411 : // Splay tree
412 0 : OOCacheNode *leftChild, *rightChild;
413 :
414 : // Age list
415 0 : OOCacheNode *younger, *older;
416 : };
417 :
418 : static OOCacheNode *CacheNodeAllocate(id<OOCacheComparable> key, id value);
419 : static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node);
420 : static id CacheNodeGetValue(OOCacheNode *node);
421 : static void CacheNodeSetValue(OOCacheNode *node, id value);
422 :
423 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
424 : static NSString *CacheNodeGetDescription(OOCacheNode *node);
425 : #endif
426 :
427 : static OOCacheNode *TreeSplay(OOCacheNode **root, id<OOCacheComparable> key);
428 : static OOCacheNode *TreeInsert(OOCacheImpl *cache, id<OOCacheComparable> key, id value);
429 :
430 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
431 : static unsigned TreeCountNodes(OOCacheNode *node);
432 : static OOCacheNode *TreeCheckIntegrity(OOCacheImpl *cache, OOCacheNode *node, OOCacheNode *expectedParent, NSString *context);
433 : #endif
434 :
435 : static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node);
436 : static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node);
437 :
438 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
439 : static void AgeListCheckIntegrity(OOCacheImpl *cache, NSString *context);
440 : #endif
441 :
442 :
443 : /***** CacheImpl functions *****/
444 :
445 0 : static OOCacheImpl *CacheAllocate(void)
446 : {
447 : return calloc(sizeof (OOCacheImpl), 1);
448 : }
449 :
450 :
451 0 : static 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 :
461 0 : static 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 :
477 0 : static 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 :
506 0 : static 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 :
516 0 : static 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 :
533 0 : static NSArray *CacheArrayOfContentsByAge(OOCacheImpl *cache)
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 :
550 0 : static 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 :
567 0 : static NSString *CacheGetName(OOCacheImpl *cache)
568 : {
569 : return cache->name;
570 : }
571 :
572 :
573 0 : static void CacheSetName(OOCacheImpl *cache, NSString *name)
574 : {
575 : [cache->name autorelease];
576 : cache->name = [name copy];
577 : }
578 :
579 :
580 0 : static unsigned CacheGetCount(OOCacheImpl *cache)
581 : {
582 : return cache->count;
583 : }
584 :
585 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
586 :
587 : static 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.
610 0 : static 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.
628 0 : static 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
652 0 : static id CacheNodeGetValue(OOCacheNode *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).
661 0 : static 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.
673 : static 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 : */
691 0 : static 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 :
770 0 : static 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
833 : static 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.
841 : static 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.
904 0 : static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node)
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.
917 0 : static 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 :
940 : static 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 :
|
