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)

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

)

Value:

do {} while (0)

Definition at line 183 of file OOCache.m.

Referenced by OOCache::dealloc, OOCache::objectForKey:, OOCache::removeObjectForKey:, and OOCache::setObject:forKey:.

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()

void AgeListMakeYoungest ( OOCacheImpl * cache, OOCacheNode * node )

static

Definition at line 905 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()

void AgeListRemove ( OOCacheImpl * cache, OOCacheNode * node )

static

Definition at line 918 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;
}

References OOCacheNode::older, OOCacheImpl::oldest, OOCacheNode::younger, and OOCacheImpl::youngest.

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

Here is the caller graph for this function:

CacheAllocate()

OOCacheImpl * CacheAllocate ( void )

static

Definition at line 446 of file OOCache.m.

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

Referenced by OOCache::initWithPList:.

Here is the caller graph for this function:

CacheArrayOfContentsByAge()

NSArray * CacheArrayOfContentsByAge ( OOCacheImpl * cache )

static

Definition at line 534 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.

Referenced by OOCache::objectsByAge.

Here is the caller graph for this function:

CacheArrayOfNodesByAge()

NSArray * CacheArrayOfNodesByAge ( OOCacheImpl * cache )

static

Definition at line 551 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.

Referenced by OOCache::pListRepresentation.

Here is the caller graph for this function:

CacheFree()

void CacheFree ( OOCacheImpl * cache )

static

Definition at line 452 of file OOCache.m.

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

References CacheNodeFree(), and OOCacheImpl::root.

Referenced by OOCache::dealloc.

Here is the call graph for this function:

Here is the caller graph for this function:

CacheGetCount()

unsigned CacheGetCount ( OOCacheImpl * cache )

static

Definition at line 581 of file OOCache.m.

{
    return cache->count;
}

References OOCacheImpl::count.

Referenced by OOCache::prune.

Here is the caller graph for this function:

CacheGetName()

NSString * CacheGetName ( OOCacheImpl * cache )

static

Definition at line 568 of file OOCache.m.

{
    return cache->name;
}

References OOCacheImpl::name.

Referenced by OOCache::name, and OOCache::prune.

Here is the caller graph for this function:

CacheInsert()

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

static

Definition at line 462 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().

Referenced by OOCache::setObject:forKey:.

Here is the call graph for this function:

Here is the caller graph for this function:

CacheNodeAllocate()

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

static

Definition at line 611 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()

void CacheNodeFree ( OOCacheImpl * cache, OOCacheNode * node )

static

Definition at line 629 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()

id CacheNodeGetValue ( OOCacheNode * node )

static

Definition at line 653 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()

void CacheNodeSetValue ( OOCacheNode * node, id value )

static

Definition at line 662 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()

BOOL CacheRemove ( OOCacheImpl * cache, id key )

static

Definition at line 478 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(), and OOCache::removeObjectForKey:.

Here is the call graph for this function:

Here is the caller graph for this function:

CacheRemoveOldest()

BOOL CacheRemoveOldest ( OOCacheImpl * cache, NSString * logKey )

static

Definition at line 507 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.

Referenced by OOCache::prune.

Here is the call graph for this function:

Here is the caller graph for this function:

CacheRetrieve()

id CacheRetrieve ( OOCacheImpl * cache, id key )

static

Definition at line 517 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().

Referenced by OOCache::objectForKey:.

Here is the call graph for this function:

Here is the caller graph for this function:

CacheSetName()

void CacheSetName ( OOCacheImpl * cache, NSString * name )

static

Definition at line 574 of file OOCache.m.

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

References OOCacheImpl::name.

Referenced by OOCache::setName:.

Here is the caller graph for this function:

TreeInsert()

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

static

Definition at line 771 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()

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

static

Definition at line 692 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.