/*
Copyright (C) 1997, 1998, 1999, 2000 by Alex Pfaffe
(Digital Dawn Graphics Inc)
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free
Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef _ddgCache_Class_
#define _ddgCache_Class_
#include "util/ddgerror.h"
typedef unsigned short ddgCacheIndex;
class WEXP ddgCacheNode
{
friend class ddgCache;
ddgCacheIndex _next;
public:
ddgCacheNode(void) : _next(0) {}
inline ddgCacheIndex next(void) { return _next; }
inline void next(ddgCacheIndex ci) { _next = ci; }
};
class WEXP ddgCache
{
ddgCacheNode * _nList;
ddgCacheIndex _fList;
unsigned int _cacheSize;
unsigned int _size;
unsigned int _nodeSize;
unsigned int _maxSize;
public:
ddgCache(void );
~ddgCache(void);
bool init( unsigned int cacheSize, unsigned int nodeSize );
ddgCacheIndex allocNode(void);
void freeNode(ddgCacheIndex n);
inline unsigned int size(void) { return _size; }
void reset(void);
inline ddgCacheNode *get(ddgCacheIndex i)
{
ddgAsserts(i >= 0 && i < _cacheSize,"Invalid cache index");
return &(_nList[i*_nodeSize]);
}
};
class WEXP ddgLNode : public ddgCacheNode {
friend class ddgLCache;
private:
ddgCacheIndex _prev;
public:
void prev(ddgCacheIndex ci ) { _prev = ci; }
ddgCacheIndex prev(void) { return _prev; }
};
class WEXP ddgLCache : public ddgCache {
typedef ddgCache super;
public:
inline ddgLNode* get(ddgCacheIndex n)
{
return (ddgLNode*) super::get(n);
}
inline ddgCacheIndex insert(ddgCacheIndex nextNode)
{
ddgCacheIndex ci = allocNode();
// Initialize the new node.
ddgLNode *n = get(ci);
// Insert at head of the list.
n->next(nextNode);
if (nextNode)
{
n->prev(get(nextNode)->prev());
// Update the neighbours.
if (n->prev())
get(n->prev())->next(ci);
get(n->next())->prev(ci);
}
else
n->prev(0);
ddgAssert(ci);
return ci;
}
inline void remove(ddgCacheIndex ci)
{
ddgAssert(ci);
ddgLNode *n = get(ci);
if (n->prev())
{
get(n->prev())->next(n->next());
}
if (n->next())
{
get(n->next())->prev(n->prev());
}
freeNode(ci);
}
inline ddgCacheIndex insertHead(ddgCacheIndex nextNode)
{
ddgCacheIndex ci = allocNode();
// Initialize the new node.
ddgLNode *n = get(ci);
// Insert at head of the list.
n->next(nextNode);
if (nextNode)
{
get(n->next())->prev(ci);
}
n->prev(0);
ddgAssert(ci);
return ci;
}
inline ddgCacheIndex insertTail(ddgCacheIndex prevNode)
{
ddgCacheIndex ci = allocNode();
// Initialize the new node.
ddgLNode *n = get(ci);
// Insert at head of the list.
n->prev(prevNode);
if (prevNode)
{
get(n->prev())->next(ci);
}
n->next(0);
ddgAssert(ci);
return ci;
}
};
class WEXP ddgSNode : public ddgLNode {
friend class ddgSCache;
private:
short _bucket;
public:
inline short bucket(void) { return _bucket; }
inline void bucket(short b) { _bucket = b; }
};
class WEXP ddgSCache : public ddgLCache {
typedef ddgLCache super;
ddgCacheIndex *_bucket;
ddgCacheIndex _head;
ddgCacheIndex _tail;
short _bucketNo;
bool _reverse;
public:
ddgSCache(void)
{
_bucket = 0;
_bucketNo = 0;
_head = 0;
_tail = 0;
}
~ddgSCache(void)
{
delete[] _bucket;
_head = 0;
_tail = 0;
_bucket = 0;
}
inline void reset(void)
{
ddgCache::reset();
_head = 0;
_tail = 0;
unsigned int i = _bucketNo;
while (i)
_bucket[--i] = 0;
}
void init (unsigned int size, unsigned int nodeSize, unsigned int bn, bool r = false ) {
ddgAssert(bn < 0xFFFF);
_bucketNo = bn;
_reverse = r;
super::init(size,nodeSize);
_bucket = new ddgCacheIndex[_bucketNo];
ddgAsserts(_bucket, "Failed to allocate memory.");
ddgMemorySet(ddgCacheIndex,_bucketNo);
reset();
}
inline ddgSNode* get(unsigned short index)
{
return (ddgSNode*) ddgCache::get(index);
}
inline short bucketNo(void) { return _bucketNo; }
inline short convert( short b )
{
return _reverse ? _bucketNo - b - 1 : b;
}
inline ddgCacheIndex insert(short b)
{
ddgAsserts(b >= 0 && b < _bucketNo,"Bucket key is out of range!");
ddgAsserts(_bucket, "Failed to allocate memory.");
if (_reverse)
b = _bucketNo - b - 1;
ddgCacheIndex ci = super::insert(_bucket[b]);
// Initialize the new node.
ddgSNode *n = get(ci);
n->bucket(b);
// We are now the head of the list.
_bucket[b] = ci;
// Reset the head and tail of the queue if need be.
if (_head < ddgCacheIndex(b))
_head = b;
else if (_tail > ddgCacheIndex(b))
_tail = b;
ddgAssert(ci);
return ci;
}
inline void remove(ddgCacheIndex ci)
{
ddgAssert(ci);
ddgSNode *n = get(ci);
short b = n->bucket();
ddgAssert(b >= 0 && b < _bucketNo);
ddgAsserts(_bucket, "Failed to allocate memory.");
// If the deleted node was the head of the queue update the head.
if (_bucket[b] == ci)
{
_bucket[b] = n->next();
}
// Remove the actual item and free it.
super::remove(ci);
}
inline ddgCacheIndex head(void)
{
while (!_bucket[_head] && _head > 0 )
_head--;
return _bucket[_head];
}
inline ddgCacheIndex tail(void)
{
while (!_bucket[_tail] && _tail < _bucketNo-1 )
_tail++;
return _bucket[_tail];
}
inline ddgCacheIndex next(ddgCacheIndex ci)
{
ddgAssert(ci);
ddgSNode *n = get(ci);
short b = n->bucket();
const short blim = (short)_tail;
if (n->next())
return n->next();
// Find next bucket with something in it.
while (--b > blim && !_bucket[b] ){}
return b < 0 ? 0 : _bucket[b];
}
};
#endif
