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 0 : struct OOCacheImpl
130 : {
131 : // Splay tree root
132 0 : OOCacheNode *root;
133 :
134 : // Ends of age list
135 0 : OOCacheNode *oldest, *youngest;
136 :
137 0 : unsigned count;
138 0 : NSString *name;
139 : };
140 :
141 :
142 0 : struct OOCacheNode
143 : {
144 : // Payload
145 0 : id<OOCacheComparable> key;
146 0 : id value;
147 :
148 : // Splay tree
149 0 : OOCacheNode *leftChild, *rightChild;
150 :
151 : // Age list
152 0 : OOCacheNode *younger, *older;
153 : };
154 :
155 :
156 :
157 0 : enum { kCountUnknown = -1U };
158 :
159 :
160 0 : static NSString * const kSerializedEntryKeyKey = @"key";
161 0 : static NSString * const kSerializedEntryKeyValue = @"value";
162 :
163 :
164 : static OOCacheImpl *CacheAllocate(void);
165 : static void CacheFree(OOCacheImpl *cache);
166 :
167 : static BOOL CacheInsert(OOCacheImpl *cache, id key, id value);
168 : static BOOL CacheRemove(OOCacheImpl *cache, id key);
169 : static BOOL CacheRemoveOldest(OOCacheImpl *cache, NSString *logKey);
170 : static id CacheRetrieve(OOCacheImpl *cache, id key);
171 : static unsigned CacheGetCount(OOCacheImpl *cache);
172 : static NSArray *CacheArrayOfContentsByAge(OOCacheImpl *cache);
173 : static NSArray *CacheArrayOfNodesByAge(OOCacheImpl *cache);
174 : static NSString *CacheGetName(OOCacheImpl *cache);
175 : static void CacheSetName(OOCacheImpl *cache, NSString *name);
176 :
177 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
178 : static NSString * const kOOLogCacheIntegrityCheck = @"dataCache.integrityCheck";
179 : static void CacheCheckIntegrity(OOCacheImpl *cache, NSString *context);
180 :
181 : #define CHECK_INTEGRITY(context) CacheCheckIntegrity(cache, (context))
182 : #else
183 0 : #define CHECK_INTEGRITY(context) do {} while (0)
184 : #endif
185 :
186 :
187 : @interface OOCache (Private)
188 :
189 0 : - (void)loadFromArray:(NSArray *)inArray;
190 :
191 : @end
192 :
193 :
194 : @implementation OOCache
195 :
196 :
197 0 : - (void)dealloc
198 : {
199 : CHECK_INTEGRITY(@"dealloc");
200 : CacheFree(cache);
201 :
202 : [super dealloc];
203 : }
204 :
205 :
206 0 : - (NSString *)description
207 : {
208 : 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"];
209 : }
210 :
211 :
212 : - (id)init
213 : {
214 : return [self initWithPList:nil];
215 : }
216 :
217 :
218 : - (id)initWithPList:(id)pList
219 : {
220 : BOOL OK = YES;
221 :
222 : self = [super init];
223 : OK = self != nil;
224 :
225 : if (OK)
226 : {
227 : cache = CacheAllocate();
228 : if (cache == NULL) OK = NO;
229 : }
230 :
231 : if (pList != nil)
232 : {
233 : if (OK) OK = [pList isKindOfClass:[NSArray class]];
234 : if (OK) [self loadFromArray:pList];
235 : }
236 : if (OK)
237 : {
238 : pruneThreshold = kOOCacheDefaultPruneThreshold;
239 : autoPrune = YES;
240 : }
241 :
242 : if (!OK)
243 : {
244 : [self release];
245 : self = nil;
246 : }
247 :
248 : return self;
249 : }
250 :
251 :
252 : - (id)pListRepresentation
253 : {
254 : return CacheArrayOfNodesByAge(cache);
255 :
256 : return nil;
257 : }
258 :
259 :
260 : - (id)objectForKey:(id)key
261 : {
262 : id result = nil;
263 :
264 : CHECK_INTEGRITY(@"objectForKey: before");
265 :
266 : result = CacheRetrieve(cache, key);
267 : // 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.
268 :
269 : CHECK_INTEGRITY(@"objectForKey: after");
270 :
271 : return [[result retain] autorelease];
272 : }
273 :
274 :
275 : - (void)setObject:inObject forKey:(id)key
276 : {
277 : CHECK_INTEGRITY(@"setObject:forKey: before");
278 :
279 : if (CacheInsert(cache, key, inObject))
280 : {
281 : dirty = YES;
282 : if (autoPrune) [self prune];
283 : }
284 :
285 : CHECK_INTEGRITY(@"setObject:forKey: after");
286 : }
287 :
288 :
289 : - (void)removeObjectForKey:(id)key
290 : {
291 : CHECK_INTEGRITY(@"removeObjectForKey: before");
292 :
293 : if (CacheRemove(cache, key)) dirty = YES;
294 :
295 : CHECK_INTEGRITY(@"removeObjectForKey: after");
296 : }
297 :
298 :
299 : - (void)setPruneThreshold:(unsigned)threshold
300 : {
301 : threshold = MAX(threshold, (unsigned)kOOCacheMinimumPruneThreshold);
302 : if (threshold != pruneThreshold)
303 : {
304 : pruneThreshold = threshold;
305 : if (autoPrune) [self prune];
306 : }
307 : }
308 :
309 :
310 : - (unsigned)pruneThreshold
311 : {
312 : return pruneThreshold;
313 : }
314 :
315 :
316 : - (void)setAutoPrune:(BOOL)flag
317 : {
318 : BOOL prune = (flag != NO);
319 : if (prune != autoPrune)
320 : {
321 : autoPrune = prune;
322 : [self prune];
323 : }
324 : }
325 :
326 :
327 : - (BOOL)autoPrune
328 : {
329 : return autoPrune;
330 : }
331 :
332 :
333 : - (void)prune
334 : {
335 : unsigned pruneCount;
336 : unsigned desiredCount;
337 : unsigned count;
338 :
339 : // Order of operations is to ensure rounding down.
340 : if (autoPrune) desiredCount = (pruneThreshold * 4) / 5;
341 : else desiredCount = pruneThreshold;
342 :
343 : if (pruneThreshold == kOOCacheNoPrune || (count = CacheGetCount(cache)) <= pruneThreshold) return;
344 :
345 : pruneCount = count - desiredCount;
346 :
347 : NSString *logKey = [NSString stringWithFormat:@"dataCache.prune.%@", CacheGetName(cache)];
348 : OOLog(logKey, @"Pruning cache \"%@\" - removing %u entries", CacheGetName(cache), pruneCount);
349 : OOLogIndentIf(logKey);
350 :
351 : while (pruneCount--) CacheRemoveOldest(cache, logKey);
352 :
353 : OOLogOutdentIf(logKey);
354 : }
355 :
356 :
357 : - (BOOL)dirty
358 : {
359 : return dirty;
360 : }
361 :
362 :
363 : - (void)markClean
364 : {
365 : dirty = NO;
366 : }
367 :
368 :
369 : - (NSString *)name
370 : {
371 : return CacheGetName(cache);
372 : }
373 :
374 :
375 : - (void)setName:(NSString *)name
376 : {
377 : CacheSetName(cache, name);
378 : }
379 :
380 :
381 : - (NSArray *) objectsByAge
382 : {
383 : return CacheArrayOfContentsByAge(cache);
384 : }
385 :
386 : @end
387 :
388 :
389 : @implementation OOCache (Private)
390 :
391 : - (void)loadFromArray:(NSArray *)array
392 : {
393 : NSEnumerator *entryEnum = nil;
394 : NSDictionary *entry = nil;
395 : NSString *key = nil;
396 : id value = nil;
397 :
398 : if (array == nil) return;
399 :
400 : for (entryEnum = [array objectEnumerator]; (entry = [entryEnum nextObject]); )
401 : {
402 : if ([entry isKindOfClass:[NSDictionary class]])
403 : {
404 : key = [entry objectForKey:kSerializedEntryKeyKey];
405 : value = [entry objectForKey:kSerializedEntryKeyValue];
406 : if ([key isKindOfClass:[NSString class]] && value != nil)
407 : {
408 : [self setObject:value forKey:key];
409 : }
410 : }
411 : }
412 : }
413 :
414 : @end
415 :
416 :
417 : /***** Most of the implementation. In C. Because I'm inconsistent and slightly m. *****/
418 :
419 : static OOCacheNode *CacheNodeAllocate(id<OOCacheComparable> key, id value);
420 : static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node);
421 : static id CacheNodeGetValue(OOCacheNode *node);
422 : static void CacheNodeSetValue(OOCacheNode *node, id value);
423 :
424 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
425 : static NSString *CacheNodeGetDescription(OOCacheNode *node);
426 : #endif
427 :
428 : static OOCacheNode *TreeSplay(OOCacheNode **root, id<OOCacheComparable> key);
429 : static OOCacheNode *TreeInsert(OOCacheImpl *cache, id<OOCacheComparable> key, id value);
430 :
431 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
432 : static unsigned TreeCountNodes(OOCacheNode *node);
433 : static OOCacheNode *TreeCheckIntegrity(OOCacheImpl *cache, OOCacheNode *node, OOCacheNode *expectedParent, NSString *context);
434 : #endif
435 :
436 : static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node);
437 : static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node);
438 :
439 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
440 : static void AgeListCheckIntegrity(OOCacheImpl *cache, NSString *context);
441 : #endif
442 :
443 :
444 : /***** CacheImpl functions *****/
445 :
446 0 : static OOCacheImpl *CacheAllocate(void)
447 : {
448 : return calloc(sizeof (OOCacheImpl), 1);
449 : }
450 :
451 :
452 0 : static void CacheFree(OOCacheImpl *cache)
453 : {
454 : if (cache == NULL) return;
455 :
456 : CacheNodeFree(cache, cache->root);
457 : [cache->name autorelease];
458 : free(cache);
459 : }
460 :
461 :
462 0 : static BOOL CacheInsert(OOCacheImpl *cache, id key, id value)
463 : {
464 : OOCacheNode *node = NULL;
465 :
466 : if (cache == NULL || key == nil || value == nil) return NO;
467 :
468 : node = TreeInsert(cache, key, value);
469 : if (node != NULL)
470 : {
471 : AgeListMakeYoungest(cache, node);
472 : return YES;
473 : }
474 : else return NO;
475 : }
476 :
477 :
478 0 : static BOOL CacheRemove(OOCacheImpl *cache, id key)
479 : {
480 : OOCacheNode *node = NULL, *newRoot = NULL;
481 :
482 : node = TreeSplay(&cache->root, key);
483 : if (node != NULL)
484 : {
485 : if (node->leftChild == NULL) newRoot = node->rightChild;
486 : else
487 : {
488 : newRoot = node->leftChild;
489 : TreeSplay(&newRoot, key);
490 : newRoot->rightChild = node->rightChild;
491 : }
492 : node->leftChild = NULL;
493 : node->rightChild = NULL;
494 :
495 : cache->root = newRoot;
496 : --cache->count;
497 :
498 : AgeListRemove(cache, node);
499 : CacheNodeFree(cache, node);
500 :
501 : return YES;
502 : }
503 : else return NO;
504 : }
505 :
506 :
507 0 : static BOOL CacheRemoveOldest(OOCacheImpl *cache, NSString *logKey)
508 : {
509 : // This could be more efficient, but does it need to be?
510 : if (cache == NULL || cache->oldest == NULL) return NO;
511 :
512 : OOLog(logKey, @"Pruning cache \"%@\": removing %@", cache->name, cache->oldest->key);
513 : return CacheRemove(cache, cache->oldest->key);
514 : }
515 :
516 :
517 0 : static id CacheRetrieve(OOCacheImpl *cache, id key)
518 : {
519 : OOCacheNode *node = NULL;
520 : id result = nil;
521 :
522 : if (cache == NULL || key == NULL) return nil;
523 :
524 : node = TreeSplay(&cache->root, key);
525 : if (node != NULL)
526 : {
527 : result = CacheNodeGetValue(node);
528 : AgeListMakeYoungest(cache, node);
529 : }
530 : return result;
531 : }
532 :
533 :
534 0 : static NSArray *CacheArrayOfContentsByAge(OOCacheImpl *cache)
535 : {
536 : OOCacheNode *node = NULL;
537 : NSMutableArray *result = nil;
538 :
539 : if (cache == NULL || cache->count == 0) return nil;
540 :
541 : result = [NSMutableArray arrayWithCapacity:cache->count];
542 :
543 : for (node = cache->youngest; node != NULL; node = node->older)
544 : {
545 : [result addObject:node->value];
546 : }
547 : return result;
548 : }
549 :
550 :
551 0 : static NSArray *CacheArrayOfNodesByAge(OOCacheImpl *cache)
552 : {
553 : OOCacheNode *node = NULL;
554 : NSMutableArray *result = nil;
555 :
556 : if (cache == NULL || cache->count == 0) return nil;
557 :
558 : result = [NSMutableArray arrayWithCapacity:cache->count];
559 :
560 : for (node = cache->oldest; node != NULL; node = node->younger)
561 : {
562 : [result addObject:[NSDictionary dictionaryWithObjectsAndKeys:node->key, kSerializedEntryKeyKey, node->value, kSerializedEntryKeyValue, nil]];
563 : }
564 : return result;
565 : }
566 :
567 :
568 0 : static NSString *CacheGetName(OOCacheImpl *cache)
569 : {
570 : return cache->name;
571 : }
572 :
573 :
574 0 : static void CacheSetName(OOCacheImpl *cache, NSString *name)
575 : {
576 : [cache->name autorelease];
577 : cache->name = [name copy];
578 : }
579 :
580 :
581 0 : static unsigned CacheGetCount(OOCacheImpl *cache)
582 : {
583 : return cache->count;
584 : }
585 :
586 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
587 :
588 : static void CacheCheckIntegrity(OOCacheImpl *cache, NSString *context)
589 : {
590 : unsigned trueCount;
591 :
592 : cache->root = TreeCheckIntegrity(cache, cache->root, NULL, context);
593 :
594 : trueCount = TreeCountNodes(cache->root);
595 : if (kCountUnknown == cache->count) cache->count = trueCount;
596 : else if (cache->count != trueCount)
597 : {
598 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): count is %u, but should be %u.", context, cache->name, cache->count, trueCount);
599 : cache->count = trueCount;
600 : }
601 :
602 : AgeListCheckIntegrity(cache, context);
603 : }
604 :
605 : #endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
606 :
607 :
608 : /***** CacheNode functions *****/
609 :
610 : // CacheNodeAllocate(): create a cache node for a key, value pair, without inserting it in the structures.
611 0 : static OOCacheNode *CacheNodeAllocate(id<OOCacheComparable> key, id value)
612 : {
613 : OOCacheNode *result = NULL;
614 :
615 : if (key == nil || value == nil) return NULL;
616 :
617 : result = calloc(sizeof *result, 1);
618 : if (result != NULL)
619 : {
620 : result->key = [key copy];
621 : result->value = [value retain];
622 : }
623 :
624 : return result;
625 : }
626 :
627 :
628 : // CacheNodeFree(): recursively delete a cache node and its children in the splay tree. To delete an individual node, first clear its child pointers.
629 0 : static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node)
630 : {
631 : id key, value;
632 :
633 : if (node == NULL) return;
634 :
635 : AgeListRemove(cache, node);
636 :
637 : key = node->key;
638 : node->key = nil;
639 : [key release];
640 :
641 : value = node->value;
642 : node->value = nil;
643 : [value release];
644 :
645 : CacheNodeFree(cache, node->leftChild);
646 : CacheNodeFree(cache, node->rightChild);
647 :
648 : free(node);
649 : }
650 :
651 :
652 : // CacheNodeGetValue(): retrieve the value of a cache node
653 0 : static id CacheNodeGetValue(OOCacheNode *node)
654 : {
655 : if (node == NULL) return nil;
656 :
657 : return node->value;
658 : }
659 :
660 :
661 : // CacheNodeSetValue(): change the value of a cache node (as when setObject:forKey: is called for an existing key).
662 0 : static void CacheNodeSetValue(OOCacheNode *node, id value)
663 : {
664 : if (node == NULL) return;
665 :
666 : id tmp = node->value;
667 : node->value = [value retain];
668 : [tmp release];
669 : }
670 :
671 :
672 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
673 : // CacheNodeGetDescription(): get a description of a cache node for debugging purposes.
674 : static NSString *CacheNodeGetDescription(OOCacheNode *node)
675 : {
676 : if (node == NULL) return @"0[null]";
677 :
678 : return [NSString stringWithFormat:@"%p[\"%@\"]", node, node->key];
679 : }
680 : #endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
681 :
682 :
683 : /***** Tree functions *****/
684 :
685 : /* TreeSplay()
686 : This is the fundamental operation of a splay tree. It searches for a node
687 : with a given key, and rebalances the tree so that the found node becomes
688 : the root. If no match is found, the node moved to the root is the one that
689 : would have been found before the target, and will thus be a neighbour of
690 : the target if the key is subsequently inserted.
691 : */
692 0 : static OOCacheNode *TreeSplay(OOCacheNode **root, id<OOCacheComparable> key)
693 : {
694 : NSComparisonResult order;
695 : OOCacheNode N = { .leftChild = NULL, .rightChild = NULL };
696 : OOCacheNode *node = NULL, *temp = NULL, *l = &N, *r = &N;
697 : BOOL exact = NO;
698 :
699 : if (root == NULL || *root == NULL || key == nil) return NULL;
700 :
701 : node = *root;
702 :
703 : for (;;)
704 : {
705 : #ifndef NDEBUG
706 : if (node == NULL)
707 : {
708 : OOLog(@"node.error", @"%@", @"node is NULL");
709 : }
710 : else if (node->key == NULL)
711 : {
712 : OOLog(@"node.error", @"%@", @"node->key is NULL");
713 : }
714 : #endif
715 : order = [key compare:node->key];
716 : if (order == NSOrderedAscending)
717 : {
718 : // Closest match is in left subtree
719 : if (node->leftChild == NULL) break;
720 : if ([key compare:node->leftChild->key] == NSOrderedAscending)
721 : {
722 : // Rotate right
723 : temp = node->leftChild;
724 : node->leftChild = temp->rightChild;
725 : temp->rightChild = node;
726 : node = temp;
727 : if (node->leftChild == NULL) break;
728 : }
729 : // Link right
730 : r->leftChild = node;
731 : r = node;
732 : node = node->leftChild;
733 : }
734 : else if (order == NSOrderedDescending)
735 : {
736 : // Closest match is in right subtree
737 : if (node->rightChild == NULL) break;
738 : if ([key compare:node->rightChild->key] == NSOrderedDescending)
739 : {
740 : // Rotate left
741 : temp = node->rightChild;
742 : node->rightChild = temp->leftChild;
743 : temp->leftChild = node;
744 : node = temp;
745 : if (node->rightChild == NULL) break;
746 : }
747 : // Link left
748 : l->rightChild = node;
749 : l = node;
750 : node = node->rightChild;
751 : }
752 : else
753 : {
754 : // Found exact match
755 : exact = YES;
756 : break;
757 : }
758 : }
759 :
760 : // Assemble
761 : l->rightChild = node->leftChild;
762 : r->leftChild = node->rightChild;
763 : node->leftChild = N.rightChild;
764 : node->rightChild = N.leftChild;
765 :
766 : *root = node;
767 : return exact ? node : NULL;
768 : }
769 :
770 :
771 0 : static OOCacheNode *TreeInsert(OOCacheImpl *cache, id<OOCacheComparable> key, id value)
772 : {
773 : OOCacheNode *closest = NULL,
774 : *node = NULL;
775 : NSComparisonResult order;
776 :
777 : if (cache == NULL || key == nil || value == nil) return NULL;
778 :
779 : if (cache->root == NULL)
780 : {
781 : node = CacheNodeAllocate(key, value);
782 : cache->root = node;
783 : cache->count = 1;
784 : }
785 : else
786 : {
787 : node = TreeSplay(&cache->root, key);
788 : if (node != NULL)
789 : {
790 : // Exact match: key already exists, reuse its node
791 : CacheNodeSetValue(node, value);
792 : }
793 : else
794 : {
795 : closest = cache->root;
796 : node = CacheNodeAllocate(key, value);
797 : if (EXPECT_NOT(node == NULL)) return NULL;
798 :
799 : order = [key compare:closest->key];
800 :
801 : if (order == NSOrderedAscending)
802 : {
803 : // Insert to left
804 : node->leftChild = closest->leftChild;
805 : node->rightChild = closest;
806 : closest->leftChild = NULL;
807 : cache->root = node;
808 : ++cache->count;
809 : }
810 : else if (order == NSOrderedDescending)
811 : {
812 : // Insert to right
813 : node->rightChild = closest->rightChild;
814 : node->leftChild = closest;
815 : closest->rightChild = NULL;
816 : cache->root = node;
817 : ++cache->count;
818 : }
819 : else
820 : {
821 : // Key already exists, which we should have caught above
822 : OOLog(@"dataCache.inconsistency", @"%s() internal inconsistency for cache \"%@\", insertion failed.", __PRETTY_FUNCTION__, cache->name);
823 : CacheNodeFree(cache, node);
824 : return NULL;
825 : }
826 : }
827 : }
828 :
829 : return node;
830 : }
831 :
832 :
833 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
834 : static unsigned TreeCountNodes(OOCacheNode *node)
835 : {
836 : if (node == NULL) return 0;
837 : return 1 + TreeCountNodes(node->leftChild) + TreeCountNodes(node->rightChild);
838 : }
839 :
840 :
841 : // 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.
842 : static OOCacheNode *TreeCheckIntegrity(OOCacheImpl *cache, OOCacheNode *node, OOCacheNode *expectedParent, NSString *context)
843 : {
844 : NSComparisonResult order;
845 : BOOL OK = YES;
846 :
847 : if (node == NULL) return NULL;
848 :
849 : if (OK && node->key == nil)
850 : {
851 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node \"%@\" has nil key; deleting subtree.", context, cache->name, CacheNodeGetDescription(node));
852 : OK = NO;
853 : }
854 :
855 : if (OK && node->value == nil)
856 : {
857 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node \"%@\" has nil value, deleting.", context, cache->name, CacheNodeGetDescription(node));
858 : OK = NO;
859 : }
860 : if (OK && node->leftChild != NULL)
861 : {
862 : order = [node->key compare:node->leftChild->key];
863 : if (order != NSOrderedDescending)
864 : {
865 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node %@'s left child %@ is not correctly ordered. Deleting subtree.", context, cache->name, CacheNodeGetDescription(node), CacheNodeGetDescription(node->leftChild));
866 : CacheNodeFree(cache, node->leftChild);
867 : node->leftChild = NULL;
868 : cache->count = kCountUnknown;
869 : }
870 : else
871 : {
872 : node->leftChild = TreeCheckIntegrity(cache, node->leftChild, node, context);
873 : }
874 : }
875 : if (node->rightChild != NULL)
876 : {
877 : order = [node->key compare:node->rightChild->key];
878 : if (order != NSOrderedAscending)
879 : {
880 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node \"%@\"'s right child \"%@\" is not correctly ordered. Deleting subtree.", context, cache->name, CacheNodeGetDescription(node), CacheNodeGetDescription(node->rightChild));
881 : CacheNodeFree(cache, node->rightChild);
882 : node->rightChild = NULL;
883 : cache->count = kCountUnknown;
884 : }
885 : else
886 : {
887 : node->rightChild = TreeCheckIntegrity(cache, node->rightChild, node, context);
888 : }
889 : }
890 :
891 : if (OK) return node;
892 : else
893 : {
894 : cache->count = kCountUnknown;
895 : CacheNodeFree(cache, node);
896 : return NULL;
897 : }
898 : }
899 : #endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
900 :
901 :
902 : /***** Age list functions *****/
903 :
904 : // AgeListMakeYoungest(): place a given cache node at the youngest end of the age list.
905 0 : static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node)
906 : {
907 : if (cache == NULL || node == NULL) return;
908 :
909 : AgeListRemove(cache, node);
910 : node->older = cache->youngest;
911 : if (NULL != cache->youngest) cache->youngest->younger = node;
912 : cache->youngest = node;
913 : if (cache->oldest == NULL) cache->oldest = node;
914 : }
915 :
916 :
917 : // AgeListRemove(): remove a cache node from the age-sorted tree. Does not affect its position in the splay tree.
918 0 : static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node)
919 : {
920 : OOCacheNode *younger = NULL;
921 : OOCacheNode *older = NULL;
922 :
923 : if (node == NULL) return;
924 :
925 : younger = node->younger;
926 : older = node->older;
927 :
928 : if (cache->youngest == node) cache->youngest = older;
929 : if (cache->oldest == node) cache->oldest = younger;
930 :
931 : node->younger = NULL;
932 : node->older = NULL;
933 :
934 : if (younger != NULL) younger->older = older;
935 : if (older != NULL) older->younger = younger;
936 : }
937 :
938 :
939 : #if OOCACHE_PERFORM_INTEGRITY_CHECKS
940 :
941 : static void AgeListCheckIntegrity(OOCacheImpl *cache, NSString *context)
942 : {
943 : OOCacheNode *node = NULL, *next = NULL;
944 : unsigned seenCount = 0;
945 :
946 : if (cache == NULL || context == NULL) return;
947 :
948 : node = cache->youngest;
949 :
950 : if (node) for (;;)
951 : {
952 : next = node->older;
953 : ++seenCount;
954 : if (next == NULL) break;
955 :
956 : if (next->younger != node)
957 : {
958 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): node \"%@\" has invalid older link (should be \"%@\", is \"%@\"); repairing.", context, cache->name, CacheNodeGetDescription(next), CacheNodeGetDescription(node), CacheNodeGetDescription(next->older));
959 : next->older = node;
960 : }
961 : node = next;
962 : }
963 :
964 : if (seenCount != cache->count)
965 : {
966 : // This is especially bad since this function is called just after verifying that the count field reflects the number of objects in the tree.
967 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): expected %u nodes, found %u. Cannot repair; clearing cache.", context, cache->name, cache->count, seenCount);
968 :
969 : /* Start of temporary extra logging */
970 : node = cache->youngest;
971 :
972 : if (node)
973 : {
974 : for (;;)
975 : {
976 : next = node->older;
977 : ++seenCount;
978 : if (next == NULL) break;
979 :
980 : if (node->key != NULL)
981 : {
982 : OOLog(kOOLogCacheIntegrityCheck,@"Key is: %@",node->key);
983 : }
984 : else
985 : {
986 : OOLog(kOOLogCacheIntegrityCheck,@"Key is: NULL");
987 : }
988 :
989 : if (node->value != NULL)
990 : {
991 : OOLog(kOOLogCacheIntegrityCheck,@"Value is: %@",node->value);
992 : }
993 : else
994 : {
995 : OOLog(kOOLogCacheIntegrityCheck,@"Value is: NULL");
996 : }
997 :
998 : node = next;
999 : }
1000 : }
1001 : /* End of temporary extra logging */
1002 :
1003 : cache->count = 0;
1004 : CacheNodeFree(cache, cache->root);
1005 : cache->root = NULL;
1006 : cache->youngest = NULL;
1007 : cache->oldest = NULL;
1008 : return;
1009 : }
1010 :
1011 : if (node != cache->oldest)
1012 : {
1013 : OOLog(kOOLogCacheIntegrityCheck, @"Integrity check (%@ for \"%@\"): oldest pointer in cache is wrong (should be \"%@\", is \"%@\"); repairing.", context, cache->name, CacheNodeGetDescription(node), CacheNodeGetDescription(cache->oldest));
1014 : cache->oldest = node;
1015 : }
1016 : }
1017 :
1018 : #endif // OOCACHE_PERFORM_INTEGRITY_CHECKS
1019 :
1020 :
1021 : #if DEBUG_GRAPHVIZ
1022 :
1023 : /* NOTE: enabling AGE_LIST can result in graph rendering times of many hours,
1024 : because determining paths for non-constraint arcs is NP-hard. In particular,
1025 : I gave up on rendering a dump of a fairly minimal cache manager after
1026 : three and a half hours. Individual caches were fine.
1027 : */
1028 : #define AGE_LIST 0
1029 :
1030 : @implementation OOCache (DebugGraphViz)
1031 :
1032 : - (void) appendNodesFromSubTree:(OOCacheNode *)subTree toString:(NSMutableString *)ioString
1033 : {
1034 : [ioString appendFormat:@"\tn%p [label=\"<f0> | <f1> %@ | <f2>\"];\n", subTree, EscapedGraphVizString([subTree->key description])];
1035 :
1036 : if (subTree->leftChild != NULL)
1037 : {
1038 : [self appendNodesFromSubTree:subTree->leftChild toString:ioString];
1039 : [ioString appendFormat:@"\tn%p:f0 -> n%p:f1;\n", subTree, subTree->leftChild];
1040 : }
1041 : if (subTree->rightChild != NULL)
1042 : {
1043 : [self appendNodesFromSubTree:subTree->rightChild toString:ioString];
1044 : [ioString appendFormat:@"\tn%p:f2 -> n%p:f1;\n", subTree, subTree->rightChild];
1045 : }
1046 : }
1047 :
1048 :
1049 : - (NSString *) generateGraphVizBodyWithRootNamed:(NSString *)rootName
1050 : {
1051 : NSMutableString *result = nil;
1052 :
1053 : result = [NSMutableString string];
1054 :
1055 : // Root node representing cache
1056 : [result appendFormat:@"\t%@ [label=\"Cache \\\"%@\\\"\" shape=box];\n"
1057 : "\tnode [shape=record];\n\t\n", rootName, EscapedGraphVizString([self name])];
1058 :
1059 : if (cache == NULL) return result;
1060 :
1061 : // Cache
1062 : [self appendNodesFromSubTree:cache->root toString:result];
1063 :
1064 : // Arc from cache object to root node
1065 : [result appendString:@"\tedge [color=black constraint=true];\n"];
1066 : [result appendFormat:@"\t%@ -> n%p:f1;\n", rootName, cache->root];
1067 :
1068 : #if AGE_LIST
1069 : OOCacheNode *node = NULL;
1070 : // Arcs representing age list
1071 : [result appendString:@"\t\n\t// Age-sorted list in blue\n\tedge [color=blue constraint=false];\n"];
1072 : node = cache->oldest;
1073 : while (node->younger != NULL)
1074 : {
1075 : [result appendFormat:@"\tn%p:f2 -> n%p:f0;\n", node, node->younger];
1076 : node = node->younger;
1077 : }
1078 : #endif
1079 :
1080 : return result;
1081 : }
1082 :
1083 :
1084 : - (NSString *) generateGraphViz
1085 : {
1086 : NSMutableString *result = nil;
1087 :
1088 : result = [NSMutableString string];
1089 :
1090 : // Header
1091 : [result appendFormat:
1092 : @"// OOCache dump\n\n"
1093 : "digraph cache\n"
1094 : "{\n"
1095 : "\tgraph [charset=\"UTF-8\", label=\"OOCache \"%@\" debug dump\", labelloc=t, labeljust=l];\n\t\n", [self name]];
1096 :
1097 : [result appendString:[self generateGraphVizBodyWithRootNamed:@"cache"]];
1098 :
1099 : [result appendString:@"}\n"];
1100 :
1101 : return result;
1102 : }
1103 :
1104 :
1105 : - (void) writeGraphVizToURL:(NSURL *)url
1106 : {
1107 : NSString *graphViz = nil;
1108 : NSData *data = nil;
1109 :
1110 : graphViz = [self generateGraphViz];
1111 : data = [graphViz dataUsingEncoding:NSUTF8StringEncoding];
1112 :
1113 : if (data != nil)
1114 : {
1115 : [data writeToURL:url atomically:YES];
1116 : }
1117 : }
1118 :
1119 :
1120 : - (void) writeGraphVizToPath:(NSString *)path
1121 : {
1122 : [self writeGraphVizToURL:[NSURL fileURLWithPath:path]];
1123 : }
1124 :
1125 : @end
1126 : #endif
1127 :
|
