Below is my first contribution to Snippet Swappit, the C++ static string cache class I discussed in Algorithmically Speaking.  As will be the norm, this code is covered by the Works On My Machine certification; this means it works in my code, on my rig, using my compiler, and I take no responsibility if the same cannot be said for you.
There are a few functions missing from this version, partly because they are not essential to the operation of the class, but also due to the use of several as-yet undocumented portions of code that would just confuse people if I left them in as-is.  Also, I have expanded the code formatting a bit to make it easier to read.  I have provided simple code comments, but if anyone has trouble figuring out how the code works (namely the Cache() function) I can always come back and step-by-step comment it.

/*
STRINGCACHE

Self-growing class which enables 'static' strings to be cached and retrieved using indices.
*/
class STRINGCACHE
{
private:
    UINT size,grow,used;
    std::vector<WORD> len;
    char *data;
    static enum
    {
        MINGROW=256,         // Minimum cache growth rate
        GROWTH=(1<<12),    // Default cache growth rate
        MINSIZE=(1<<16),    // Minimum initial cache size
        MAXSIZE=(1<<24),   // Maximum initial cache size
        PADDING=255          // Padding amount when resizing
    };

public:
    STRINGCACHE(const UINT bufsize=0,const UINT growth=GROWTH);
    ~STRINGCACHE();

    // Returns the number of bytes currently used by cached strings.
    inline UINT Used(void) { return used; }

    // Returns the number of strings currently cached.
    inline UINT Count(void) { return (UINT)len.size(); }

    char *Cache(const char *string,UINT *index=NULL,bool add=false);

    UINT SetIndex(const char *string);
    char *Set(const char *string,UINT *index=NULL);

    char *Get(const UINT index);
    char *Get(const char *string);
};

/*
STRINGCACHE()

Constructor for a new static string cache, where bufsize is the initial size of the string buffer and growth is the amount to grow that buffer by if the cache runs out of space.
*/
STRINGCACHE::STRINGCACHE(const UINT bufsize,const UINT growth)
{
    if (bufsize<MINSIZE) size=MINSIZE;
    else if (bufsize>MAXSIZE) size=MAXSIZE;
    else size=bufsize;
    grow=max(MINGROW,growth);
    size=((size+grow+PADDING)&~PADDING);
    data=new char[size];
    memset(data,0,size);
    len.push_back(1);
    used=1;
}

/*
~STRINGCACHE()

Destructor, frees up all used memory.
*/
STRINGCACHE::~STRINGCACHE()
{
    if (data) delete [] data;
    len.clear();
}

/*
Cache()

Catch-all function which handles cache searches and additions.  If string is found in the cache, Cache() sets index to the index of the start of the cached occurrence and a pointer to it is returned.  If string is not cached and add is true, it is added as a 'new' string and returned as above.  Otherwise, the cache is deemed 'read only'; index is set to 0 and NULL is returned.

Note that this could be made to return 'cache index 0' rather than 'NULL' if required.
*/
char *STRINGCACHE::Cache(const char *string,UINT *index,bool add)
{
    if (index) *index=0;
    if (!(string && *string)) return NULL;
    WORD sl=(WORD)(strlen(string)+1);
    if (used>=sl)
    {
        char *p=data+used-2,*s=(char *)string+sl-2;
        UINT li=(UINT)len.size()-1;
        do
        {
            WORD pl=len[li--];
            if (pl==sl)
            {
                char *q=s;
                do
                {
                    if (*p!=*q) break;
                    if ((--pl)==1) { if (index) *index=(UINT)(p-data); return p; }
                    p--; q--;
                }
                while (pl>1);
            }
            p-=pl;
        }
        while (li);
    }
    if (!add) return NULL;
    if ((used+sl)>=size)
    {
        while ((used+sl)>=size) size+=grow;
        char *dold=data;
        data=new char[size];
        memcpy(data,dold,used);
        delete [] dold;
        memset(data+used,0,size-used);
    }
    UINT ret=used;
    used+=sl;
    strcpy(data+ret,string);
    len.push_back(sl);
    if (index) *index=ret;
    return data+ret;
}

/*
SetIndex()

Same as Cache() above, but assumes that a non-cached string should always be added to the cache, and returns the cache index directly.

This is actually the 'set' function I use most often, but MSVC++ overloading rules prevented me from also calling it Set().
*/
UINT STRINGCACHE::SetIndex(const char *string)
{
    UINT index;
    Cache(string,&index,true);
    return index;
}

/*
Set()

Same as Cache() above, but assumes that a non-cached string should always be added to the cache.
*/
char *STRINGCACHE::Set(const char *string,UINT *index)
{
    return Cache(string,index,true);
}

/*
Get()

Returns a pointer to the string cached at index, or NULL if not cached.

As with SetIndex(), this is the 'get' function I use most often, as replacing strings with indices is kinda the point of the exercise. :P
*/
char *STRINGCACHE::Get(const UINT index)
{
    return (index<used) ? (data+index) : NULL;
}

/*
Get()

Same as Cache() above, but assumes that a non-cached string should always return NULL.

Mostly here as a convenience.
*/
char *STRINGCACHE::Get(const char *string)
{
    return Cache(string,NULL,false);
}

 

    Snippet Swappit

    Real working code I've written over the years, free to use or abuse as you see fit.

    DISCLAIMER:
    Any and all code I post here is either entirely or primarily my own; any code derived in a reasonable capacity from other sources, or based significantly on code and/or technical details published by other authors, will be clearly marked as such, with references to the original source provide to the best of my ability.  As such, I take no responsibility for any code, technical details, algorithms or other information posted by others, nor for any disputes arising as to who an 'original author' is, even where it may in fact differ from that which I sourced it.

    Archives

    July 2012

    Categories

    All