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>
struct	OOCacheImpl
struct	OOCacheNode
category	OOCache(Private)

Macros
#define	OOCACHE_PERFORM_INTEGRITY_CHECKS   0
#define	CHECK_INTEGRITY(context)   do {} while (0)

Typedefs
typedef struct OOCacheImpl	OOCacheImpl
typedef struct OOCacheNode	OOCacheNode

Enumerations
enum	{ kCountUnknown = -1U }

Functions
static OOCacheImpl *	CacheAllocate (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 OOCacheNode *	CacheNodeAllocate (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 OOCacheNode *	TreeSplay (OOCacheNode **root, id< OOCacheComparable > key)
static OOCacheNode *	TreeInsert (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

)

do {} while (0)

Definition at line 183 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 157 of file OOCache.m.

{ kCountUnknown = -1U };

Function Documentation

AgeListMakeYoungest()

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

static

Definition at line 904 of file OOCache.m.

{
    if (cache == NULL || node == NULL) return;
    
    AgeListRemove(cache, node);
    node->older = cache->youngest;
    if (NULL != cache->youngest) cache->youngest->younger = node;
    cache->youngest = node;
    if (cache->oldest == NULL) cache->oldest = node;
}

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.

{
    OOCacheNode         *younger = NULL;
    OOCacheNode         *older = NULL;
    
    if (node == NULL) return;
    
    younger = node->younger;
    older = node->older;
    
    if (cache->youngest == node) cache->youngest = older;
    if (cache->oldest == node) cache->oldest = younger;
    
    node->younger = NULL;
    node->older = NULL;
    
    if (younger != NULL) younger->older = older;
    if (older != NULL) older->younger = younger;
}

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.

{
    return calloc(sizeof (OOCacheImpl), 1);
}

CacheArrayOfContentsByAge()

static NSArray * CacheArrayOfContentsByAge ( OOCacheImpl *  cache )

static

Definition at line 533 of file OOCache.m.

{
    OOCacheNode         *node = NULL;
    NSMutableArray      *result = nil;
    
    if (cache == NULL || cache->count == 0) return nil;
    
    result = [NSMutableArray arrayWithCapacity:cache->count];
    
    for (node = cache->youngest; node != NULL; node = node->older)
    {
        [result addObject:node->value];
    }
    return result;
}

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

CacheArrayOfNodesByAge()

static NSArray * CacheArrayOfNodesByAge ( OOCacheImpl *  cache )

static

Definition at line 550 of file OOCache.m.

{
    OOCacheNode         *node = NULL;
    NSMutableArray      *result = nil;
    
    if (cache == NULL || cache->count == 0) return nil;
    
    result = [NSMutableArray arrayWithCapacity:cache->count];
    
    for (node = cache->oldest; node != NULL; node = node->younger)
    {
        [result addObject:[NSDictionary dictionaryWithObjectsAndKeys:node->key, kSerializedEntryKeyKey, node->value, kSerializedEntryKeyValue, nil]];
    }
    return result;
}

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

CacheFree()

static void CacheFree ( OOCacheImpl *  cache )

static

Definition at line 451 of file OOCache.m.

{
    if (cache == NULL) return;
    
    CacheNodeFree(cache, cache->root);
    [cache->name autorelease];
    free(cache);
}

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.

{
    return cache->count;
}

References OOCacheImpl::count.

CacheGetName()

static NSString * CacheGetName ( OOCacheImpl *  cache )

static

Definition at line 567 of file OOCache.m.

{
    return cache->name;
}

References OOCacheImpl::name.

CacheInsert()

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

static

Definition at line 461 of file OOCache.m.

{
    OOCacheNode             *node = NULL;
    
    if (cache == NULL || key == nil || value == nil) return NO;
    
    node = TreeInsert(cache, key, value);
    if (node != NULL)
    {
        AgeListMakeYoungest(cache, node);
        return YES;
    }
    else  return NO;
}

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.

{
    OOCacheNode         *result = NULL;
    
    if (key == nil || value == nil) return NULL;
    
    result = calloc(sizeof *result, 1);
    if (result != NULL)
    {
        result->key = [key copy];
        result->value = [value retain];
    }
    
    return result;
}

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.

{
    id key, value;
    
    if (node == NULL) return;
    
    AgeListRemove(cache, node);
    
    key = node->key;
    node->key = nil;
    [key release];
    
    value = node->value;
    node->value = nil;
    [value release];
    
    CacheNodeFree(cache, node->leftChild);
    CacheNodeFree(cache, node->rightChild);
    
    free(node);
}

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.

{
    if (node == NULL) return nil;
    
    return node->value;
}

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.

{
    if (node == NULL) return;
 
    id tmp = node->value;
    node->value = [value retain];
    [tmp release];
}

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.

{
    OOCacheNode             *node = NULL, *newRoot = NULL;
    
    node = TreeSplay(&cache->root, key);
    if (node != NULL)
    {
        if (node->leftChild == NULL)  newRoot = node->rightChild;
        else
        {
            newRoot = node->leftChild;
            TreeSplay(&newRoot, key);
            newRoot->rightChild = node->rightChild;
        }
        node->leftChild = NULL;
        node->rightChild = NULL;
        
        cache->root = newRoot;
        --cache->count;
        
        AgeListRemove(cache, node);
        CacheNodeFree(cache, node);
        
        return YES;
    }
    else  return NO;
}

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.

{
    // This could be more efficient, but does it need to be?
    if (cache == NULL || cache->oldest == NULL) return NO;
    
    OOLog(logKey, @"Pruning cache \"%@\": removing %@", cache->name, cache->oldest->key);
    return CacheRemove(cache, cache->oldest->key);
}

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.

{
    OOCacheNode         *node = NULL;
    id                  result = nil;
    
    if (cache == NULL || key == NULL) return nil;
    
    node = TreeSplay(&cache->root, key);
    if (node != NULL)
    {
        result = CacheNodeGetValue(node);
        AgeListMakeYoungest(cache, node);
    }
    return result;
}

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.

{
    [cache->name autorelease];
    cache->name = [name copy];
}

References OOCacheImpl::name.

TreeInsert()

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

static

Definition at line 770 of file OOCache.m.

{
    OOCacheNode             *closest = NULL,
                            *node = NULL;
    NSComparisonResult      order;
    
    if (cache == NULL || key == nil || value == nil) return NULL;
    
    if (cache->root == NULL)
    {
        node = CacheNodeAllocate(key, value);
        cache->root = node;
        cache->count = 1;
    }
    else
    {
        node = TreeSplay(&cache->root, key);
        if (node != NULL)
        {
            // Exact match: key already exists, reuse its node
            CacheNodeSetValue(node, value);
        }
        else
        {
            closest = cache->root;
            node = CacheNodeAllocate(key, value);
            if (EXPECT_NOT(node == NULL))  return NULL;
            
            order = [key compare:closest->key];
            
            if (order == NSOrderedAscending)
            {
                // Insert to left
                node->leftChild = closest->leftChild;
                node->rightChild = closest;
                closest->leftChild = NULL;
                cache->root = node;
                ++cache->count;
            }
            else if (order == NSOrderedDescending)
            {
                // Insert to right
                node->rightChild = closest->rightChild;
                node->leftChild = closest;
                closest->rightChild = NULL;
                cache->root = node;
                ++cache->count;
            }
            else
            {
                // Key already exists, which we should have caught above
                OOLog(@"dataCache.inconsistency", @"%s() internal inconsistency for cache \"%@\", insertion failed.", __PRETTY_FUNCTION__, cache->name);
                CacheNodeFree(cache, node);
                return NULL;
            }
        }
    }
    
    return node;
}

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.

{
    NSComparisonResult      order;
    OOCacheNode             N = { .leftChild = NULL, .rightChild = NULL };
    OOCacheNode             *node = NULL, *temp = NULL, *l = &N, *r = &N;
    BOOL                    exact = NO;
    
    if (root == NULL || *root == NULL || key == nil) return NULL;
    
    node = *root;
    
    for (;;)
    {
#ifndef NDEBUG
        if (node == NULL)
        {
            OOLog(@"node.error", @"%@", @"node is NULL");
        }
        else if (node->key == NULL)
        {
            OOLog(@"node.error", @"%@", @"node->key is NULL");
        }
#endif
        order = [key compare:node->key];
        if (order == NSOrderedAscending)
        {
            // Closest match is in left subtree
            if (node->leftChild == NULL) break;
            if ([key compare:node->leftChild->key] == NSOrderedAscending)
            {
                // Rotate right
                temp = node->leftChild;
                node->leftChild = temp->rightChild;
                temp->rightChild = node;
                node = temp;
                if (node->leftChild == NULL) break;
            }
            // Link right
            r->leftChild = node;
            r = node;
            node = node->leftChild;
        }
        else if (order == NSOrderedDescending)
        {
            // Closest match is in right subtree
            if (node->rightChild == NULL) break;
            if ([key compare:node->rightChild->key] == NSOrderedDescending)
            {
                // Rotate left
                temp = node->rightChild;
                node->rightChild = temp->leftChild;
                temp->leftChild = node;
                node = temp;
                if (node->rightChild == NULL) break;
            }
            // Link left
            l->rightChild = node;
            l = node;
            node = node->rightChild;
        }
        else
        {
            // Found exact match
            exact = YES;
            break;
        }
    }
    
    // Assemble
    l->rightChild = node->leftChild;
    r->leftChild = node->rightChild;
    node->leftChild = N.rightChild;
    node->rightChild = N.leftChild;
    
    *root = node;
    return exact ? node : NULL;
}

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 160 of file OOCache.m.

kSerializedEntryKeyValue

NSString* const kSerializedEntryKeyValue = @"@"value"

static

Definition at line 161 of file OOCache.m.