/ray/src/lib/tl/tlstring.cc

Go to the documentation of this file.

/*
 * lib/tl/tlstring.cc
 * 
 * Thread-save reference-counting string class. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#include "tlstring.h"
#include <string.h>
#include <stdio.h>   /* for snprintf() */

void TLString::SData::_EnsureSize(size_t s)
{
    //if(refcnt.val()!=1)
    //{  fprintf(stderr,"oops<%d -%s- %u %u %u>\n",
    //  refcnt.val(),str,s,asize,len);  }
    Assert(refcnt.val()==1);
    
    // asize<s here. 
    // We need to re-allocate the pointer, so allocat a bit too much 
    // so that we probably need not realloc the next time. 
    // I will allocate 50% more but limited to 256 bytes. 
    // (Hint: 512*50% = 256 :)
    asize=GrowRoundUp(s);
    str=REALLOC(str,asize);
}


void TLString::SData::_DoTightenSize()
{
    Assert(refcnt.val()==1);
    
    // asize>len+1 here. 
    asize=len+1;
    str=REALLOC(str,asize);
}


void TLString::SData::DownSizeIfNeeded(size_t s)
{
    Assert(refcnt.val()==1);
    // If we are 150% above or more than 16k bytes, re-allocate. 
    Assert(s<=asize);
    if(s<16)  s=10;   // never go below 16 bytes (10+10>>1 = 15 -> round -> 16)
    size_t above = asize>s ? asize-s : 0;
    if(above>16384 || above>(s+s>>1))
    {
        size_t old_asize=asize;
        asize=GrowRoundUp(s);
        Assert(asize<old_asize);  // On failure: tweak threshold above. 
        str=REALLOC(str,asize);
    }
}


TLString::SData::SData(const char *s) : 
    refcnt(1)  /* CORRECT. */
{
    len=strlen(s);
    asize=RoundUp(len+1);
    str=ALLOC<char>(asize);
    strcpy(str,s);
}

TLString::SData::SData(const char *s,size_t len) : 
    refcnt(1)  /* CORRECT. */
{
    asize=RoundUp(len+1);
    str=ALLOC<char>(asize);
    memcpy(str,s,len);
    str[len]='\0';
}

TLString::SData::SData(const SData &s) : 
    refcnt(1)  /* CORRECT. */
{
    len=s.len;
    asize=RoundUp(len+1);
    str=ALLOC<char>(asize);
    strcpy(str,s.str);
}

TLString::SData::SData(size_t ensure_size) : 
    refcnt(1)  /* CORRECT. */
{
    len=0;
    asize=GrowRoundUp(ensure_size);
    str=ALLOC<char>(asize);
    *str='\0';
}

//------------------------------------------------------------------------------

void TLString::append(const char *str)
{
    if(!str)  return;
    
    if(d)
    {
        _detachN();
        size_t len=strlen(str);
        d->_EnsureSize(d->len+len+1);
        strcpy(d->str+d->len,str);
        d->len+=len;
    }
    else
    {  _storeN(str);  }
}

void TLString::append(const char *str,size_t len)
{
    if(!str)  return;
    
    if(d)
    {
        _detachN();
        d->_EnsureSize(d->len+len+1);
        memcpy(d->str+d->len,str,len);
        d->len+=len;
        d->str[d->len]='\0';
    }
    else
    {  _storeN(str,len);  }
}

void TLString::append(const TLString &str)
{
    if(!str)  return;  // NOTE: This is TLString::operator!(). 
    
    // NOZE: there is a tricky case one tends to forget: &str==this. 
    
    // if(d && d->refcnt.val()==1)
    // {  optimized version here! }   <-- below str._aqrefN();
    
    if(d)
    {
        _detachN();
        
        // The following is probably not needed and makes problems
        // in the case &str==this. 
        //str._aqrefN();  // Aquire a refernce so that it will not be modified. 
        
        SData *s=str.d;
        d->_EnsureSize(d->len+s->len+1);
        memcpy(d->str+d->len,s->str,s->len);  // <-- not len+1 (aliasing)
        d->len+=s->len;
        d->str[d->len]='\0';  // <-- Needed in case &str==this. 
        
        //str._derefN();  // "unlock"
    }
    else
    {
        // Simply reference it. 
        _referenceN(str);
    }
}


void TLString::prepend(const char *str)
{
    if(!str)  return;
    
    if(d)
    {
        _detachN();
        size_t len=strlen(str);
        d->_EnsureSize(d->len+len+1);
        memmove(d->str+len,d->str,d->len+1);
        memcpy(d->str,str,len);
        d->len+=len;
    }
    else
    {  _storeN(str);  }
}

void TLString::prepend(const TLString &str)
{
    if(!str)  return;  // NOTE: This is TLString::operator!(). 
    
    if(d)
    {
        _detachN();
        
        // The following is probably not needed and makes problems
        // in the case &str==this. 
        //str._aqrefN();  // Aquire a refernce so that it will not be modified. 
        
        SData *s=str.d;
        d->_EnsureSize(d->len+s->len+1);
        memmove(d->str+s->len,d->str,d->len+1);
        memcpy(d->str,s->str,s->len);
        d->len+=s->len;
        
        //str._derefN();  // "unlock"
    }
    else
    {
        // Simply reference it. 
        _referenceN(str);
    }
}


int TLString::compare(const TLString &strB)
{
    // NOTE: All the relational string operators dealing with two TLStrings 
    //       could internally use this compare() function. 
    
    if(!*this || !strB)
    {
        if(!*this && !strB)  return(0);
        return(!*this ? -2 : 2);
    }
    
    int rv;
    strB._aqrefN();  // Aquire a refernce so that it will not be modified. 
    if(d==strB.d)  rv=0;  // same internal data
    else
    {
        size_t minlen = d->len<strB.d->len ? d->len : strB.d->len;
        rv = memcmp(d->str,strB.d->str,minlen);
        // The shorter string is smaller. 
        if(!rv && d->len!=strB.d->len)
        {  rv = d->len<strB.d->len ? -1 : 1;  }
    }
    strB._derefN();  // "unlock"
    
    return(rv);
}


bool operator==(const TLString &strA,const TLString &strB)
{
    if(strA && strB)
    {
        bool rv;
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        strB._aqrefN();  // Aquire a refernce so that it will not be modified. 
        if(strA.d==strB.d)  rv=1;  // same internal data
        else if(strA.d->len!=strB.d->len)  rv=0;   // length mismatch
        else  rv=!memcmp(strA.d->str,strB.d->str,strA.d->len);
        strB._derefN();  // "unlock"
        strA._derefN();  // "unlock"
        return(rv);
    }
    return(!(strA || strB));
}

bool operator==(const TLString &strA,const char *strB)
{
    if(strA && strB)
    {
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        bool equal=1;
        for(const char *a=strA.d->str,*aend=a+strA.d->len,*b=strB; ; a++,b++)
        {
            if(!*b)
            {
                if(a!=aend)  equal=0;
                break;
            }
            if(*a!=*b || a==aend)
            {  equal=0;  break;  }
        }
        strA._derefN();  // "unlock"
        return(equal);
    }
    return(!(strA || strB));
}


bool operator<(const TLString &strA,const TLString &strB)
{
    if(strA && strB)
    {
        int rv;
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        strB._aqrefN();  // Aquire a refernce so that it will not be modified. 
        if(strA.d==strB.d)  rv=0;  // same internal data
        else
        {
            size_t minlen=strA.d->len<strB.d->len ? strA.d->len : strB.d->len;
            rv = memcmp(strA.d->str,strB.d->str,minlen);
            // The shorter string is smaller. 
            rv = rv ? (rv<0) : (strA.d->len<strB.d->len);
        }
        strB._derefN();  // "unlock"
        strA._derefN();  // "unlock"
        return(rv);
    }
    return(0);
}

bool operator<(const TLString &strA,const char *strB)
{
    if(strA && strB)
    {
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        bool rv;
        for(const char *a=strA.d->str,*aend=a+strA.d->len,*b=strB; ; a++,b++)
        {
            if(!*b)
            {  rv=0;  break;  }
            if(a==aend)   // a shorter than b
            {  rv=1;  break;  }
            if(*a!=*b)
            {  rv=*a<*b;  break;  }
        }
        strA._derefN();  // "unlock"
        return(rv);
    }
    return(0);
}

bool operator>(const TLString &strA,const char *strB)
{
    if(strA && strB)
    {
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        bool rv;
        for(const char *a=strA.d->str,*aend=a+strA.d->len,*b=strB; ; a++,b++)
        {
            if(a==aend)
            {  rv=0;  break;  }
            if(!*b)   // b shorter than a
            {  rv=1;  break;  }
            if(*a!=*b)
            {  rv=*a>*b;  break;  }
        }
        strA._derefN();  // "unlock"
        return(rv);
    }
    return(0);
}


bool operator<=(const TLString &strA,const TLString &strB)
{
    if(strA && strB)
    {
        int rv;
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        strB._aqrefN();  // Aquire a refernce so that it will not be modified. 
        if(strA.d==strB.d)  rv=1;  // same internal data
        else
        {
            size_t minlen=strA.d->len<strB.d->len ? strA.d->len : strB.d->len;
            rv = memcmp(strA.d->str,strB.d->str,minlen);
            // The shorter string is smaller. 
            rv = rv ? (rv<0) : (strA.d->len<=strB.d->len);
        }
        strB._derefN();  // "unlock"
        strA._derefN();  // "unlock"
        return(rv);
    }
    return(0);
}

bool operator<=(const TLString &strA,const char *strB)
{
    if(strA && strB)
    {
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        bool rv;
        for(const char *a=strA.d->str,*aend=a+strA.d->len,*b=strB; ; a++,b++)
        {
            if(a==aend)
            {  rv=1;  break;  }
            if(!*b)
            {  rv=0;  break;  }
            if(*a!=*b)
            {  rv=*a<*b;  break;  }
        }
        strA._derefN();  // "unlock"
        return(rv);
    }
    return(0);
}

bool operator>=(const TLString &strA,const char *strB)
{
    if(strA && strB)
    {
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        bool rv;
        for(const char *a=strA.d->str,*aend=a+strA.d->len,*b=strB; ; a++,b++)
        {
            if(!*b)
            {  rv=1;  break;  }
            if(a==aend)
            {  rv=0;  break;  }
            if(*a!=*b)
            {  rv=*a>*b;  break;  }
        }
        strA._derefN();  // "unlock"
        return(rv);
    }
    return(0);
}


int TLString::zero()
{
    if(!d)  return(0);
    if(d->refcnt.val()>1)  return(1);
    // We are the only user. 
    memset(d->str,'\0',d->len);
    _derefN();
    return(0);
}


void TLString::trunc(size_t len,bool do_not_shrink)
{
    if(!d)  return;
    if(d->len<=len)  return;
    
    if(d->refcnt.val()==1)
    {
        // We are the only user. 
        d->len=len;
        d->str[len]='\0';
        if(!do_not_shrink)
        {  d->DownSizeIfNeeded(len+1); }
    }
    else
    {
        // There are more users. 
        SData *nd=new SData(len+1);
        memcpy(nd->str,d->str,len);
        nd->str[len]='\0';
        _derefN();
        d=nd;
    }
}


void TLString::skip(size_t n)
{
    if(!d || !n)  return;
    
    if(d->refcnt.val()==1)
    {
        // We are the only user. 
        if(d->len<=n)
        {
            d->len=0;
            d->str[0]='\0';
            d->DownSizeIfNeeded(1);
        }
        else
        {
            d->len-=n;
            memmove(d->str,d->str+n,d->len+1);
            d->DownSizeIfNeeded(d->len+1);
        }
    }
    else
    {
        // There are more users. 
        if(d->len<=n)
        {
            _derefN();
            _storeN("");
        }
        else
        {
            size_t len=d->len-n;
            SData *nd=new SData(len+1);
            memcpy(nd->str,d->str+n,len);
            nd->str[len]='\0';
            _derefN();
            d=nd;
        }
    }
}


size_t TLString::TightenSize()
{
    if(!d)  return(0);
    if(d->refcnt.val()==1)
    {  d->TightenSize();  }
    return(d->asize+sizeof(SData));
}


void TLString::vsprintf(const char *fmt,va_list ap)
{
    if(d && d->refcnt.val()==1 && d->asize>=32)
    {
        // Optimized version. We are the only user. 
        
        // First, we must get the length of the string in fmt,...
        ssize_t rv=vsnprintf(d->str,d->asize,fmt,ap);
#if 0
        if(rv<0)
        {  fprintf(stderr,"tlstring.cc:%d: vsnprintf() not C99 conform."
            " Please upgrade your libc.\n",__LINE__);  abort();  }
#endif
        CritAssert(rv>=0);   // critical: libc
        
        size_t dlen=rv;  // (without trailing '\0')
        // The length of the string in fmt,... is dlen. 
        if(dlen+1<=d->asize)
        {
            // Wow, the whole string is already there. 
            d->len=dlen;
            return;
        }
        
        d->EnsureSize(dlen+1);
        // Must re-format the string. 
        ssize_t rv2=vsnprintf(d->str,dlen+1,fmt,ap);
        CritAssert(rv==rv2);   // critical: libc
        d->len=dlen;
        
        return;
    }
    
    // Get rid of old stuff: 
    _deref();
    
    // First, we must get the length of the string in fmt,...
    static const ssize_t prealloc=64;
    char buf[prealloc];
    ssize_t rv=vsnprintf(buf,prealloc,fmt,ap);
#if 0
    if(rv<0)
    {  fprintf(stderr,"tlstring.cc:%d: vsnprintf() not C99 conform."
        " Please upgrade your libc.\n",__LINE__);  abort();  }
#endif
    CritAssert(rv>=0);   // critical: libc
    
    size_t dlen=rv;  // (without trailing '\0')
    // The length of the string in fmt,... is dlen. 
    // First, allocate the needed bytes: 
    d=new SData(dlen+1);   // +1 for terminating '\0'
    if(rv<prealloc)  // okay.
    {
        // Whole string fits into prealloc buf. Simply copy. 
        memcpy(d->str,buf,dlen);  // okay. 
    }
    else
    {
        // Must re-format the string. 
        ssize_t rv2=vsnprintf(d->str,dlen+1,fmt,ap);
        CritAssert(rv==rv2);   // critical: libc
    }
    d->len=dlen;
    d->str[dlen]='\0';  // to be sure...
}


void TLString::sprintf(const char *fmt,...)
{
    va_list ap;
    va_start(ap,fmt);
    vsprintf(fmt,ap);
    va_end(ap);
}


ssize_t TLString::index(char c) const
{
    if(!d)  return(-1);
    for(const char *i=d->str,*iend=i+d->len; i<iend; i++)
        if(*i==c)  return(i-d->str);
    return(-1);
}

ssize_t TLString::rindex(char c) const
{
    if(!d)  return(-1);
    for(ssize_t idx=d->len-1; idx>=0; idx--)
        if(d->str[idx]==c)  return(idx);
    return(-1);
}


static char *memfind(const char *buf,const char *tofind,size_t len)
{
    size_t findlen=strlen(tofind);
    if(findlen>len)
    {  return((char*)NULL);  }
    if(len<1)
    {  return((char*)buf);  }
    
    const char *bufend=&buf[len-findlen+1];
    for(const char *c=buf; c<bufend; c++)
    {
        if(*c==*tofind)  // first letter matches
        {
            if(!memcmp(c+1,tofind+1,findlen-1))  // found
            {  return((char*)c);  }
        }
    }
    
    return((char*)NULL);
}

ssize_t TLString::find(const char *str) const
{
    if(!d)  return(-1);
    if(!str)  return(0);
    char *ptr=memfind(d->str,str,d->len);
    if(!ptr)  return(-1);
    return(ptr-d->str);
}

ssize_t TLString::find(const TLString &str) const
{
    if(!d)  return(-1);
    if(!str)  return(0);
    
    ssize_t rv=-1;
    str._aqrefN();  // Aquire a refernce so that it will not be modified. 
    
    do {
        if(str.d->len>d->len)  break;
        if(str.d->len<1)
        {  rv=0;  break;  }
        
        const char *bufend=&d->str[d->len-str.d->len];
        for(const char *c=d->str; c<=bufend; c++)  // <= is OK
        {
            if(*c!=*str.d->str) continue;  // first letter mismatch
            if(!memcmp(c+1,str.d->str+1,str.d->len-1))  // found
            {  rv=c-d->str;  break;  }
        }
    } while(0);
    
    str._derefN();  // "unlock"
    return(rv);
}


ssize_t TLString::rfind(const char *str) const
{
    if(!d)  return(-1);
    if(!str || !*str)  return(d->len);
    size_t len=strlen(str);
    if(len>d->len)  return(-1);
    if(!len)  return(d->len);
    const char *end=d->str+d->len-len;
    for(const char *start=end; start>=d->str;  start--)
    {
        if(*start!=*str)  continue;
        if(!memcmp(start+1,str+1,len-1))  return(start-d->str);
    }
    return(-1);
}

ssize_t TLString::rfind(const TLString &str) const
{
    if(!d)  return(-1);
    if(!str)  return(d->len);
    
    ssize_t rv=-1;
    str._aqrefN();  // Aquire a refernce so that it will not be modified. 
    
    do {
        if(str.d->len>d->len)  break;
        if(str.d->len<1)
        {  rv=d->len;  break;  }
        
        const char *end=d->str+d->len-str.d->len;
        for(const char *start=end; start>=d->str;  start--)
        {
            if(*start!=*str.d->str)  continue;
            if(!memcmp(start+1,str.d->str+1,str.d->len-1))
            {  rv=start-d->str;  break;  }
        }
    } while(0);
    
    str._derefN();  // "unlock"
    return(rv);
}


TLString::TLString(const char *strA,const char *strB)
{
    if(strA && strB)
    {
        size_t lenA=strlen(strA);
        size_t lenAB=lenA+strlen(strB);
        d=new SData(lenAB+1);
        strcpy(d->str,strA);
        strcpy(d->str+lenA,strB);
        d->len=lenAB;
    }
    else if(strA)  _storeN(strA);
    else if(strB)  _storeN(strB);
    else  d=NULL;
}

TLString::TLString(const char *strA,const TLString &strB)
{
    if(strA && strB)
    {
        size_t lenA=strlen(strA);
        strB._aqrefN();  // Aquire a refernce so that it will not be modified. 
        size_t lenAB=lenA+strB.d->len;
        d=new SData(lenAB+1);
        strcpy(d->str,strA);
        memcpy(d->str+lenA,strB.d->str,strB.d->len+1);
        strB._derefN();  // "unlock"
        d->len=lenAB;
    }
    else if(strA)  _storeN(strA);
    else if(strB)  _referenceN(strB);
    else  d=NULL;
}

TLString::TLString(const TLString &strA,const char *strB)
{
    if(strA && strB)
    {
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        size_t lenAB=strA.d->len+strlen(strB);
        d=new SData(lenAB+1);
        memcpy(d->str,strA.d->str,strA.d->len);
        strcpy(d->str+strA.d->len,strB);
        strA._derefN();  // "unlock"
        d->len=lenAB;
    }
    else if(strA)  _referenceN(strA);
    else if(strB)  _storeN(strB);
    else  d=NULL;
}

TLString::TLString(const TLString &strA,const TLString &strB)
{
    if(strA && strB)
    {
        strA._aqrefN();  // Aquire a refernce so that it will not be modified. 
        strB._aqrefN();  // Aquire a refernce so that it will not be modified. 
        size_t lenAB=strA.d->len+strB.d->len;
        d=new SData(lenAB+1);
        memcpy(d->str,strA.d->str,strA.d->len);
        memcpy(d->str+strA.d->len,strB.d->str,strB.d->len+1);
        strB._derefN();  // "unlock"
        strA._derefN();  // "unlock"
        d->len=lenAB;
    }
    else if(strA)  _referenceN(strA);
    else if(strB)  _referenceN(strB);
    else  d=NULL;
}

---