Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

wvbuffer.cc

Go to the documentation of this file.
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * Declarations for WvMiniBuffer (a statically-sized data buffer with
00006  * get/put functions) and WvBuffer (a dynamically-sized buffer made from
00007  * a list of WvMiniBuffers).
00008  *
00009  * All these functions are described in wvbuffer.h
00010  */
00011 #include "wvbuffer.h"
00012 #include <assert.h>
00013 #include <stdio.h> // for printf()
00014 
00015 #if 0
00016 #define Dprintf printf
00017 #else
00018 #define Dprintf if (0) printf
00019 #endif
00020 
00021 #define MINSIZE 128
00022 
00024 
00025 
00026 size_t WvMiniBuffer::strchr(unsigned char ch) const
00027 {
00028     unsigned char *cptr;
00029     
00030     for (cptr = head; cptr < tail; cptr++)
00031         if (*cptr == ch) return cptr - head + 1;
00032     
00033     return 0;
00034 }
00035 
00036 
00037 size_t WvMiniBuffer::match(const unsigned char chlist[], size_t numch,
00038                              bool reverse) const
00039 {
00040     const unsigned char *cptr, *cp2, *cpe = chlist + numch;
00041     
00042     for (cptr = head; cptr < tail; cptr++)
00043     {
00044         if (reverse)
00045         {
00046             // stop if this character matches ANY of chlist
00047             for (cp2 = chlist; cp2 < cpe; cp2++)
00048                 if (*cptr == *cp2) return cptr - head;
00049         }
00050         else
00051         {
00052             // stop if this character matches NONE of chlist
00053             for (cp2 = chlist; cp2 < cpe; cp2++)
00054                 if (*cptr == *cp2) break;
00055             if (cp2 == cpe) return cptr - head;
00056         }
00057     }
00058 
00059     return cptr - head;
00060 }
00061 
00062 
00064 
00065 
00066 void WvBuffer::zap()
00067 {
00068     WvMiniBufferList::Iter i(list);
00069     
00070     for (i.rewind(); i.next(); )
00071         i->zap();
00072     inuse = 0;
00073 }
00074 
00075 
00076 unsigned char *WvBuffer::get(size_t num)
00077 {
00078     WvMiniBufferList::Iter i(list);
00079     WvMiniBuffer *firstb, *b, *destb;
00080     size_t got, avail;
00081 
00082     if (inuse < num  ||  num == 0)
00083         return NULL;
00084     
00085     assert(inuse >= num); // so there must be enough buffers
00086     
00087     inuse -= num;
00088     
00089     i.rewind(); i.next();
00090     
00091     // if the first minibuffer is empty, delete it.
00092     firstb = i.ptr();
00093     if (firstb->used() == 0)
00094     {
00095         Dprintf("<del-0 MiniBuffer(%d)\n", firstb->total());
00096         i.unlink();
00097     }
00098 
00099     // if the (new) first minibuffer has enough data, just use that.
00100     firstb = i.ptr();
00101     if (firstb->used() >= num)
00102         return firstb->get(num);
00103 
00104     // nope.  Is there enough empty space in this buffer to hold the rest of
00105     // the data?
00106     if (firstb->free() >= num - firstb->used())
00107     {
00108         got = firstb->used();
00109         destb = firstb;
00110     }
00111     else
00112     {
00113         // must allocate a new "first" buffer to hold entire 'num' bytes
00114         got = 0;
00115         destb = new WvMiniBuffer(num);
00116         list.prepend(destb, true);
00117         Dprintf("<new-1 MiniBuffer(%d)>\n", num);
00118     }
00119 
00120     for (i.rewind(), i.next(); i.cur(); )
00121     {
00122         b = i.ptr();
00123         if (b == destb)
00124         {
00125             i.next();
00126             continue;
00127         }
00128         
00129         if (b->used() > num - got)
00130             avail = num - got;
00131         else
00132             avail = b->used();
00133         got += avail;
00134         
00135         destb->put(b->get(avail), avail);
00136         if (!b->used())
00137         {
00138             Dprintf("<del-1 MiniBuffer(%d)\n", b->total());
00139             i.unlink();
00140         }
00141         else
00142             i.next();
00143     }
00144     
00145     return destb->get(num);
00146 }
00147 
00148 
00149 void WvBuffer::unget(size_t num)
00150 {
00151     WvMiniBuffer *b;
00152     WvMiniBufferList::Iter i(list);
00153     size_t ungettable;
00154     
00155     i.rewind(); i.next();
00156     b = &i();
00157     
00158     ungettable = b->total() - b->used() - b->free();
00159     
00160     if (num > ungettable)
00161         num = ungettable;
00162     
00163     b->unget(num);
00164     inuse += num;
00165 }
00166 
00167 
00168 unsigned char *WvBuffer::alloc(size_t num)
00169 {
00170     WvMiniBuffer *lastb, *b;
00171     size_t newsize;
00172     
00173     if (list.tail && list.tail->data)
00174     {
00175         lastb = (WvMiniBuffer *)list.tail->data;
00176         if (lastb->free() >= num)
00177         {
00178             inuse += num;
00179             return lastb->alloc(num);
00180         }
00181     }
00182     else
00183         lastb = NULL;
00184     
00185     // otherwise, we need a new MiniBuffer so we can provide contiguous 'num'
00186     // bytes.  New buffers grow in size exponentially, and have minimum size
00187     // of MINSIZE.
00188     newsize = 0;
00189     if (lastb)
00190     {
00191         newsize = lastb->total();
00192         if (lastb->used() > lastb->total() / 2)
00193             newsize *= 2;
00194     }
00195     if (newsize < MINSIZE)
00196         newsize = MINSIZE;
00197     if (newsize < num)
00198         newsize = num;
00199     b = new WvMiniBuffer(newsize);
00200     Dprintf("<new-2 MiniBuffer(%d)>\n", newsize);
00201     
00202     list.append(b, true);
00203     
00204     inuse += num;
00205     return b->alloc(num);
00206 }
00207 
00208 
00209 void WvBuffer::unalloc(size_t num)
00210 {
00211     WvMiniBuffer *lastb, *b;
00212     
00213     assert(inuse >= num);
00214     
00215     if (inuse < num  ||  num == 0)
00216         return; // strange
00217     
00218     inuse -= num;
00219     
00220     // fast track:  if enough bytes are in the very last minibuffer (the
00221     // usual case) then we can unalloc() it quickly.
00222     lastb = (WvMiniBuffer *)list.tail->data;
00223     if (lastb->used() >= num)
00224     {
00225         lastb->unalloc(num);
00226         return;
00227     }
00228         
00229     // free up as much as we can from the last buffer, counting backwards
00230     // each time.  This is slow because we have only a singly-linked list.
00231     WvMiniBufferList::Iter i(list);
00232     
00233     while (num > 0)
00234     {
00235         // iterate through to the last element
00236         for (i.rewind(); i.next() && i.cur()->next; )
00237             ;
00238         
00239         b = i.ptr();
00240         
00241         if (b->used() < num)
00242         {
00243             num -= b->used();
00244             Dprintf("<del-2 MiniBuffer(%d)>\n", b->total());
00245             i.unlink();
00246         }
00247         else
00248         {
00249             // only unalloc part of the now-last element
00250             b->unalloc(num);
00251             num = 0;
00252         }
00253     }
00254 }
00255 
00256 
00257 /*
00258  * we could do this with alloc() and memcpy(), but that can waste space. If
00259  * we know the data already, append whatever fits to the last buffer, then
00260  * add any remaining data to a new one.
00261  */
00262 void WvBuffer::put(const void *data, size_t num)
00263 {
00264     WvMiniBuffer *lastb, *b;
00265     size_t newsize;
00266     
00267     inuse += num;
00268 
00269     // use up any space in the currently-last minibuffer
00270     if (list.tail && list.tail->data)
00271     {
00272         lastb = (WvMiniBuffer *)list.tail->data;
00273         
00274         newsize = lastb->free() >= num ? num : lastb->free();
00275         lastb->put(data, newsize);
00276         num -= newsize;
00277         data = (char *)data + newsize;
00278     }
00279     else
00280         lastb = NULL;
00281     
00282     // otherwise, we need a new MiniBuffer so we can provide contiguous 'num'
00283     // bytes.  New buffers grow in size exponentially, and have minimum size
00284     // of 10.
00285     if (num > 0)
00286     {
00287         newsize = 0;
00288         if (lastb)
00289         {
00290             newsize = lastb->total();
00291             if (lastb->used() >= lastb->total() / 2)
00292                 newsize *= 2;
00293         }
00294         if (newsize < 10)
00295             newsize = 10;
00296         if (newsize < num)
00297             newsize = num;
00298         b = new WvMiniBuffer(newsize);
00299         Dprintf("<new-3 MiniBuffer(%d)>\n", newsize);
00300         
00301         list.append(b, true);
00302         b->put(data, num);
00303     }
00304 }
00305 
00306 
00307 void WvBuffer::put(const WvString &str)
00308 {
00309     if (!!str)
00310         put(str, strlen(str));
00311 }
00312 
00313 
00314 // to merge another WvBuffer into this one, simply move all of its
00315 // WvMiniBuffer objects into our own list.
00316 void WvBuffer::merge(WvBuffer &buf)
00317 {
00318     WvMiniBufferList::Iter i(buf.list);
00319     
00320     for (i.rewind(); i.next(); )
00321     {
00322         i.cur()->auto_free = false;
00323         list.append(&i(), true);
00324     }
00325     
00326     inuse += buf.used();
00327     buf.zap();
00328 }
00329 
00330 
00331 WvString WvBuffer::getstr()
00332 {
00333     WvString s;
00334     size_t len = used();
00335     s.setsize(len + 1);
00336     
00337     char *cptr = s.edit();
00338     memcpy(cptr, get(len), len);
00339     cptr[len] = 0;
00340     
00341     return s;
00342 }
00343 
00344 
00345 size_t WvBuffer::strchr(unsigned char ch)
00346 {
00347     WvMiniBufferList::Iter i(list);
00348     size_t off = 0, t;
00349     
00350     for (i.rewind(); i.next(); )
00351     {
00352         WvMiniBuffer &b = i;
00353         
00354         t = b.strchr(ch);
00355         
00356         if (t)
00357             return off + t; // found it
00358         else
00359             off += b.used();
00360     }
00361     
00362     return 0;
00363 }
00364 
00365 
00366 size_t WvBuffer::match(const unsigned char chlist[], size_t numch,
00367                          bool reverse)
00368 {
00369     WvMiniBufferList::Iter i(list);
00370     size_t off = 0, t;
00371     
00372     for (i.rewind(); i.next(); )
00373     {
00374         WvMiniBuffer &b = i;
00375         
00376         t = b.match(chlist, numch, reverse);
00377         
00378         if (t < b.used())
00379             return off + t; // done
00380         else
00381             off += b.used();
00382     }
00383     
00384     return off;
00385 }

Generated on Sat Aug 24 21:36:59 2002 for WvStreams by doxygen1.2.15