Oolite 1.91.0.7644-241112-7f5034b
Loading...
Searching...
No Matches
OOCache.m File Reference
import "OOCache.h"
import "OOStringParsing.h"
+ Include dependency graph for OOCache.m:

Go to the source code of this file.

Classes

protocol  <OOCacheComparable>
 
category  OOCache(Private)
 
struct  OOCacheImpl
 
struct  OOCacheNode
 

Macros

#define OOCACHE_PERFORM_INTEGRITY_CHECKS   0
 
#define CHECK_INTEGRITY(context)
 

Typedefs

typedef struct OOCacheImpl OOCacheImpl
 
typedef struct OOCacheNode OOCacheNode
 

Enumerations

enum  { kCountUnknown = -1U }
 

Functions

static OOCacheImplCacheAllocate (void)
 
static void CacheFree (OOCacheImpl *cache)
 
static BOOL CacheInsert (OOCacheImpl *cache, id key, id value)
 
static BOOL CacheRemove (OOCacheImpl *cache, id key)
 
static BOOL CacheRemoveOldest (OOCacheImpl *cache, NSString *logKey)
 
static id CacheRetrieve (OOCacheImpl *cache, id key)
 
static unsigned CacheGetCount (OOCacheImpl *cache)
 
static NSArray * CacheArrayOfContentsByAge (OOCacheImpl *cache)
 
static NSArray * CacheArrayOfNodesByAge (OOCacheImpl *cache)
 
static NSString * CacheGetName (OOCacheImpl *cache)
 
static void CacheSetName (OOCacheImpl *cache, NSString *name)
 
static OOCacheNodeCacheNodeAllocate (id< OOCacheComparable > key, id value)
 
static void CacheNodeFree (OOCacheImpl *cache, OOCacheNode *node)
 
static id CacheNodeGetValue (OOCacheNode *node)
 
static void CacheNodeSetValue (OOCacheNode *node, id value)
 
static OOCacheNodeTreeSplay (OOCacheNode **root, id< OOCacheComparable > key)
 
static OOCacheNodeTreeInsert (OOCacheImpl *cache, id< OOCacheComparable > key, id value)
 
static void AgeListMakeYoungest (OOCacheImpl *cache, OOCacheNode *node)
 
static void AgeListRemove (OOCacheImpl *cache, OOCacheNode *node)
 

Variables

static NSString *const kSerializedEntryKeyKey = @"@"key"
 
static NSString *const kSerializedEntryKeyValue = @"@"value"
 

Macro Definition Documentation

◆ CHECK_INTEGRITY

#define CHECK_INTEGRITY ( context)
Value:
do {} while (0)

Definition at line 156 of file OOCache.m.

◆ OOCACHE_PERFORM_INTEGRITY_CHECKS

#define OOCACHE_PERFORM_INTEGRITY_CHECKS   0

Definition at line 115 of file OOCache.m.

Typedef Documentation

◆ OOCacheImpl

typedef struct OOCacheImpl OOCacheImpl

Definition at line 126 of file OOCache.m.

◆ OOCacheNode

typedef struct OOCacheNode OOCacheNode

Definition at line 127 of file OOCache.m.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
kCountUnknown 

Definition at line 130 of file OOCache.m.

130{ kCountUnknown = -1U };
@ kCountUnknown
Definition OOCache.m:130

Function Documentation

◆ AgeListMakeYoungest()

static void AgeListMakeYoungest ( OOCacheImpl * cache,
OOCacheNode * node )
static

Definition at line 904 of file OOCache.m.

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}
static void AgeListRemove(OOCacheImpl *cache, OOCacheNode *node)
Definition OOCache.m:917
OOCacheNode * youngest
Definition OOCache.m:398
OOCacheNode * oldest
Definition OOCache.m:398
OOCacheNode * older
Definition OOCache.m:415
OOCacheNode * younger
Definition OOCache.m:415

References AgeListRemove(), OOCacheNode::older, OOCacheImpl::oldest, OOCacheNode::younger, and OOCacheImpl::youngest.

Referenced by CacheInsert(), and CacheRetrieve().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ AgeListRemove()

static void AgeListRemove ( OOCacheImpl * cache,
OOCacheNode * node )
static

Definition at line 917 of file OOCache.m.

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}

Referenced by AgeListMakeYoungest(), CacheNodeFree(), and CacheRemove().

+ Here is the caller graph for this function:

◆ CacheAllocate()

static OOCacheImpl * CacheAllocate ( void )
static

Definition at line 445 of file OOCache.m.

446{
447 return calloc(sizeof (OOCacheImpl), 1);
448}

◆ CacheArrayOfContentsByAge()

static NSArray * CacheArrayOfContentsByAge ( OOCacheImpl * cache)
static

Definition at line 533 of file OOCache.m.

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}
return nil
unsigned count
Definition OOCache.m:400

References OOCacheImpl::count, nil, OOCacheNode::older, and OOCacheImpl::youngest.

◆ CacheArrayOfNodesByAge()

static NSArray * CacheArrayOfNodesByAge ( OOCacheImpl * cache)
static

Definition at line 550 of file OOCache.m.

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}
static NSString *const kSerializedEntryKeyKey
Definition OOCache.m:133
static NSString *const kSerializedEntryKeyValue
Definition OOCache.m:134
id< OOCacheComparable > key
Definition OOCache.m:408

References OOCacheImpl::count, nil, OOCacheImpl::oldest, and OOCacheNode::younger.

◆ CacheFree()

static void CacheFree ( OOCacheImpl * cache)
static

Definition at line 451 of file OOCache.m.

452{
453 if (cache == NULL) return;
454
455 CacheNodeFree(cache, cache->root);
456 [cache->name autorelease];
457 free(cache);
458}
static void CacheNodeFree(OOCacheImpl *cache, OOCacheNode *node)
Definition OOCache.m:628
OOCacheNode * root
Definition OOCache.m:395
NSString * name
Definition OOCache.m:401

References CacheNodeFree(), and OOCacheImpl::root.

+ Here is the call graph for this function:

◆ CacheGetCount()

static unsigned CacheGetCount ( OOCacheImpl * cache)
static

Definition at line 580 of file OOCache.m.

581{
582 return cache->count;
583}

References OOCacheImpl::count.

◆ CacheGetName()

static NSString * CacheGetName ( OOCacheImpl * cache)
static

Definition at line 567 of file OOCache.m.

568{
569 return cache->name;
570}

References OOCacheImpl::name.

◆ CacheInsert()

static BOOL CacheInsert ( OOCacheImpl * cache,
id key,
id value )
static

Definition at line 461 of file OOCache.m.

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}
static void AgeListMakeYoungest(OOCacheImpl *cache, OOCacheNode *node)
Definition OOCache.m:904
static OOCacheNode * TreeInsert(OOCacheImpl *cache, id< OOCacheComparable > key, id value)
Definition OOCache.m:770

References AgeListMakeYoungest(), nil, and TreeInsert().

+ Here is the call graph for this function:

◆ CacheNodeAllocate()

static OOCacheNode * CacheNodeAllocate ( id< OOCacheComparable > key,
id value )
static

Definition at line 610 of file OOCache.m.

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}

References OOCacheNode::key, nil, and OOCacheNode::value.

Referenced by TreeInsert().

+ Here is the caller graph for this function:

◆ CacheNodeFree()

static void CacheNodeFree ( OOCacheImpl * cache,
OOCacheNode * node )
static

Definition at line 628 of file OOCache.m.

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}
OOCacheNode * rightChild
Definition OOCache.m:412
OOCacheNode * leftChild
Definition OOCache.m:412

References AgeListRemove(), CacheNodeFree(), OOCacheNode::key, OOCacheNode::leftChild, nil, OOCacheNode::rightChild, and OOCacheNode::value.

Referenced by CacheFree(), CacheNodeFree(), CacheRemove(), and TreeInsert().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ CacheNodeGetValue()

static id CacheNodeGetValue ( OOCacheNode * node)
static

Definition at line 652 of file OOCache.m.

653{
654 if (node == NULL) return nil;
655
656 return node->value;
657}

References nil, and OOCacheNode::value.

Referenced by CacheRetrieve().

+ Here is the caller graph for this function:

◆ CacheNodeSetValue()

static void CacheNodeSetValue ( OOCacheNode * node,
id value )
static

Definition at line 661 of file OOCache.m.

662{
663 if (node == NULL) return;
664
665 id tmp = node->value;
666 node->value = [value retain];
667 [tmp release];
668}

References OOCacheNode::value.

Referenced by TreeInsert().

+ Here is the caller graph for this function:

◆ CacheRemove()

static BOOL CacheRemove ( OOCacheImpl * cache,
id key )
static

Definition at line 477 of file OOCache.m.

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}
static OOCacheNode * TreeSplay(OOCacheNode **root, id< OOCacheComparable > key)
Definition OOCache.m:691

References AgeListRemove(), CacheNodeFree(), OOCacheImpl::count, OOCacheNode::leftChild, OOCacheNode::rightChild, OOCacheImpl::root, and TreeSplay().

Referenced by CacheRemoveOldest().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ CacheRemoveOldest()

static BOOL CacheRemoveOldest ( OOCacheImpl * cache,
NSString * logKey )
static

Definition at line 506 of file OOCache.m.

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}
static BOOL CacheRemove(OOCacheImpl *cache, id key)
Definition OOCache.m:477
#define OOLog(class, format,...)
Definition OOLogging.h:88

References CacheRemove(), OOCacheNode::key, OOCacheImpl::name, OOCacheImpl::oldest, and OOLog.

+ Here is the call graph for this function:

◆ CacheRetrieve()

static id CacheRetrieve ( OOCacheImpl * cache,
id key )
static

Definition at line 516 of file OOCache.m.

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}
static id CacheNodeGetValue(OOCacheNode *node)
Definition OOCache.m:652

References AgeListMakeYoungest(), CacheNodeGetValue(), nil, OOCacheImpl::root, and TreeSplay().

+ Here is the call graph for this function:

◆ CacheSetName()

static void CacheSetName ( OOCacheImpl * cache,
NSString * name )
static

Definition at line 573 of file OOCache.m.

574{
575 [cache->name autorelease];
576 cache->name = [name copy];
577}

References OOCacheImpl::name.

◆ TreeInsert()

static OOCacheNode * TreeInsert ( OOCacheImpl * cache,
id< OOCacheComparable > key,
id value )
static

Definition at line 770 of file OOCache.m.

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}
static void CacheNodeSetValue(OOCacheNode *node, id value)
Definition OOCache.m:661
static OOCacheNode * CacheNodeAllocate(id< OOCacheComparable > key, id value)
Definition OOCache.m:610
#define EXPECT_NOT(x)

References CacheNodeAllocate(), CacheNodeFree(), CacheNodeSetValue(), OOCacheImpl::count, EXPECT_NOT, OOCacheNode::leftChild, OOCacheImpl::name, nil, OOLog, OOCacheNode::rightChild, OOCacheImpl::root, and TreeSplay().

Referenced by CacheInsert().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ TreeSplay()

static OOCacheNode * TreeSplay ( OOCacheNode ** root,
id< OOCacheComparable > key )
static

Definition at line 691 of file OOCache.m.

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}

References OOCacheNode::key, OOCacheNode::leftChild, nil, OOLog, and OOCacheNode::rightChild.

Referenced by CacheRemove(), CacheRetrieve(), and TreeInsert().

+ Here is the caller graph for this function:

Variable Documentation

◆ kSerializedEntryKeyKey

NSString* const kSerializedEntryKeyKey = @"@"key"
static

Definition at line 133 of file OOCache.m.

◆ kSerializedEntryKeyValue

NSString* const kSerializedEntryKeyValue = @"@"value"
static

Definition at line 134 of file OOCache.m.