WvStreams
wvbufferstore.cc
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * Defines basic buffer storage classes.
00006  * These are not intended for use directly by clients.
00007  * See "wvbufbase.h" for the public API.
00008  */
00009 #include "wvbufstore.h"
00010 #include <string.h>
00011 #include <sys/types.h>
00012 
00020 struct MemOps
00021 {
00023     inline void uninit_copy(void *target, const void *source,
00024         size_t count)
00025     {
00026         memcpy(target, source, count);
00027     }
00029     inline void copy(void *target, const void *source, size_t count)
00030     {
00031         uninit(target, count);
00032         memcpy(target, source, count);
00033     }
00038     inline void uninit_move(void *target, void *source,
00039         size_t count)
00040     {
00041         memmove(target, source, count);
00042         uninit(source, count);
00043     }
00045     inline void swap(void *target, void *source, size_t count)
00046     {
00047         register unsigned char *t1 = (unsigned char*)target;
00048         register unsigned char *t2 = (unsigned char*)source;
00049         while (count-- > 0)
00050         {
00051             register unsigned char temp;
00052             temp = *t1;
00053             *(t1++) = *t2;
00054             *(t2++) = temp;
00055         }
00056     }
00058     inline void uninit(void *target, size_t count)
00059     {
00060     }
00062     inline void *newarray(size_t count)
00063     {
00064         return new unsigned char[count];
00065     }
00067     inline void deletearray(void *buf)
00068     {
00069         deletev (unsigned char*)buf;
00070     }
00071 } memops;
00072 
00074 inline size_t roundup(size_t value, size_t boundary)
00075 {
00076     size_t mod = value % boundary;
00077     return mod ? value + boundary - mod : value;
00078 }
00079 
00080 
00081 
00082 /***** WvBufStore *****/
00083 
00084 WvBufStore::WvBufStore(int _granularity) :
00085     granularity(_granularity)
00086 {
00087 }
00088 
00089 
00090 size_t WvBufStore::peekable(int offset) const
00091 {
00092     if (offset == 0)
00093     {
00094         return used();
00095     }
00096     else if (offset < 0)
00097     {
00098         if (size_t(-offset) <= ungettable())
00099             return size_t(-offset) + used();
00100     }
00101     else
00102     {
00103         int avail = int(used()) - offset;
00104         if (avail > 0)
00105             return avail;
00106     }
00107     return 0; // out-of-bounds
00108 }
00109 
00110 
00111 void WvBufStore::move(void *buf, size_t count)
00112 {
00113     while (count > 0)
00114     {
00115         size_t amount = count;
00116         assert(amount != 0 ||
00117             !"attempted to move() more than used()");
00118         if (amount > count)
00119             amount = count;
00120         const void *data = get(amount);
00121         memops.uninit_copy(buf, data, amount);
00122         buf = (unsigned char*)buf + amount;
00123         count -= amount;
00124     }
00125 }
00126 
00127 
00128 void WvBufStore::copy(void *buf, int offset, size_t count)
00129 {
00130     while (count > 0)
00131     {
00132         size_t amount = optpeekable(offset);
00133         assert(amount != 0 ||
00134             !"attempted to copy() with invalid offset");
00135         if (amount > count)
00136             amount = count;
00137         const void *data = peek(offset, amount);
00138         memops.uninit_copy(buf, data, amount);
00139         buf = (unsigned char*)buf + amount;
00140         count -= amount;
00141         offset += amount;
00142     }
00143 }
00144 
00145 
00146 void WvBufStore::put(const void *data, size_t count)
00147 {
00148     while (count > 0)
00149     {
00150         size_t amount = optallocable();
00151         assert(amount != 0 ||
00152             !"attempted to put() more than free()");
00153         if (amount > count)
00154             amount = count;
00155         void *buf = alloc(amount);
00156         memops.uninit_copy(buf, data, amount);
00157         data = (const unsigned char*)data + amount;
00158         count -= amount;
00159     }
00160 }
00161 
00162 
00163 void WvBufStore::fastput(const void *data, size_t count)
00164 {
00165     void *buf = alloc(count);
00166     memops.uninit_copy(buf, data, count);
00167 }
00168 
00169 
00170 void WvBufStore::poke(const void *data, int offset, size_t count)
00171 {
00172     int limit = int(used());
00173     assert(offset <= limit ||
00174         !"attempted to poke() beyond end of buffer");
00175     int end = offset + count;
00176     if (end >= limit)
00177     {
00178         size_t tail = end - limit;
00179         count -= tail;
00180         put((const unsigned char*)data + count, tail);
00181     }
00182     while (count > 0)
00183     {
00184         size_t amount = optpeekable(offset);
00185         assert(amount != 0 ||
00186             !"attempted to poke() with invalid offset");
00187         if (amount > count)
00188             amount = count;
00189         void *buf = mutablepeek(offset, amount);
00190         memops.copy(buf, data, amount);
00191         data = (const unsigned char*)data + amount;
00192         count -= amount;
00193         offset += amount;
00194     }
00195 }
00196 
00197 
00198 void WvBufStore::merge(WvBufStore &instore, size_t count)
00199 {
00200     if (count == 0)
00201         return;
00202 
00203     if (usessubbuffers() && instore.usessubbuffers())
00204     {
00205         // merge quickly by stealing subbuffers from the other buffer
00206         for (;;)
00207         {
00208             WvBufStore *buf = instore.firstsubbuffer();
00209             if (! buf)
00210                 break; // strange!
00211 
00212             size_t avail = buf->used();
00213             if (avail > count)
00214                 break;
00215                 
00216             // move the entire buffer
00217             bool autofree = instore.unlinksubbuffer(buf, false);
00218             appendsubbuffer(buf, autofree);
00219             count -= avail;
00220             if (count == 0)
00221                 return;
00222         }
00223     }
00224     // merge slowly by copying data
00225     basicmerge(instore, count);
00226 }
00227 
00228 
00229 void WvBufStore::basicmerge(WvBufStore &instore, size_t count)
00230 {
00231     // move bytes as efficiently as we can using only the public API
00232     if (count == 0)
00233         return;
00234     const void *indata = NULL;
00235     void *outdata = NULL;
00236     size_t inavail = 0;
00237     size_t outavail = 0;
00238     for (;;)
00239     {
00240         if (inavail == 0)
00241         {
00242             inavail = instore.optgettable();
00243             assert(inavail != 0 ||
00244                 !"attempted to merge() more than instore.used()");
00245             if (inavail > count)
00246                 inavail = count;
00247             indata = instore.get(inavail);
00248         }
00249         if (outavail == 0)
00250         {
00251             outavail = optallocable();
00252             assert(outavail != 0 ||
00253                 !"attempted to merge() more than free()");
00254             if (outavail > count)
00255                 outavail = count;
00256             outdata = alloc(outavail);
00257         }
00258         if (inavail < outavail)
00259         {
00260             memops.uninit_copy(outdata, indata, inavail);
00261             count -= inavail;
00262             outavail -= inavail;
00263             if (count == 0)
00264             {
00265                 unalloc(outavail);
00266                 return;
00267             }
00268             outdata = (unsigned char*)outdata + inavail;
00269             inavail = 0;
00270         }
00271         else
00272         {
00273             memops.uninit_copy(outdata, indata, outavail);
00274             count -= outavail;
00275             if (count == 0) return;
00276             inavail -= outavail;
00277             indata = (const unsigned char*)indata + outavail;
00278             outavail = 0;
00279         }
00280     }
00281 }
00282 
00283 
00284 
00285 /***** WvInPlaceBufStore *****/
00286 
00287 WvInPlaceBufStore::WvInPlaceBufStore(int _granularity,
00288     void *_data, size_t _avail, size_t _size, bool _autofree) :
00289     WvBufStore(_granularity), data(NULL)
00290 {
00291     reset(_data, _avail, _size, _autofree);
00292 }
00293 
00294 
00295 WvInPlaceBufStore::WvInPlaceBufStore(int _granularity, size_t _size) :
00296     WvBufStore(_granularity), data(NULL)
00297 {
00298     reset(memops.newarray(_size), 0, _size, true);
00299 }
00300 
00301 
00302 WvInPlaceBufStore::~WvInPlaceBufStore()
00303 {
00304     if (data && xautofree)
00305         memops.deletearray(data);
00306 }
00307 
00308 
00309 void WvInPlaceBufStore::reset(void *_data, size_t _avail,
00310     size_t _size, bool _autofree = false)
00311 {
00312     assert(_data != NULL || _avail == 0);
00313     if (data && _data != data && xautofree)
00314         memops.deletearray(data);
00315     data = _data;
00316     xautofree = _autofree;
00317     xsize = _size;
00318     setavail(_avail);
00319 }
00320 
00321 
00322 void WvInPlaceBufStore::setavail(size_t _avail)
00323 {
00324     assert(_avail <= xsize);
00325     readidx = 0;
00326     writeidx = _avail;
00327 }
00328 
00329 
00330 size_t WvInPlaceBufStore::used() const
00331 {
00332     return writeidx - readidx;
00333 }
00334 
00335 
00336 const void *WvInPlaceBufStore::get(size_t count)
00337 {
00338     assert(count <= writeidx - readidx ||
00339         !"attempted to get() more than used()");
00340     const void *tmpptr = (const unsigned char*)data + readidx;
00341     readidx += count;
00342     return tmpptr;
00343 }
00344 
00345 
00346 void WvInPlaceBufStore::unget(size_t count)
00347 {
00348     assert(count <= readidx ||
00349         !"attempted to unget() more than ungettable()");
00350     readidx -= count;
00351 }
00352 
00353 
00354 size_t WvInPlaceBufStore::ungettable() const
00355 {
00356     return readidx;
00357 }
00358 
00359 
00360 void WvInPlaceBufStore::zap()
00361 {
00362     readidx = writeidx = 0;
00363 }
00364 
00365 
00366 size_t WvInPlaceBufStore::free() const
00367 {
00368     return xsize - writeidx;
00369 }
00370 
00371 
00372 void *WvInPlaceBufStore::alloc(size_t count)
00373 {
00374     assert(count <= xsize - writeidx ||
00375         !"attempted to alloc() more than free()");
00376     void *tmpptr = (unsigned char*)data + writeidx;
00377     writeidx += count;
00378     return tmpptr;
00379 }
00380 
00381 
00382 void WvInPlaceBufStore::unalloc(size_t count)
00383 {
00384     assert(count <= writeidx - readidx ||
00385         !"attempted to unalloc() more than unallocable()");
00386     writeidx -= count;
00387 }
00388 
00389 
00390 size_t WvInPlaceBufStore::unallocable() const
00391 {
00392     return writeidx - readidx;
00393 }
00394 
00395 
00396 void *WvInPlaceBufStore::mutablepeek(int offset, size_t count)
00397 {
00398     if (count == 0)
00399         return NULL;
00400     assert(((offset <= 0) ? 
00401         size_t(-offset) <= readidx :
00402         size_t(offset) < writeidx - readidx) ||
00403         ! "attempted to peek() with invalid offset or count");
00404     return (unsigned char*)data + readidx + offset;
00405 }
00406 
00407 
00408 
00409 /***** WvConstInPlaceBufStore *****/
00410 
00411 WvConstInPlaceBufStore::WvConstInPlaceBufStore(int _granularity,
00412     const void *_data, size_t _avail) :
00413     WvReadOnlyBufferStoreMixin<WvBufStore>(_granularity), data(NULL)
00414 {
00415     reset(_data, _avail);
00416 }
00417 
00418 
00419 void WvConstInPlaceBufStore::reset(const void *_data, size_t _avail)
00420 {
00421     assert(_data != NULL || _avail == 0);
00422     data = _data;
00423     setavail(_avail);
00424 }
00425 
00426 
00427 size_t WvConstInPlaceBufStore::used() const
00428 {
00429     return avail - readidx;
00430 }
00431 
00432 
00433 void WvConstInPlaceBufStore::setavail(size_t _avail)
00434 {
00435     avail = _avail;
00436     readidx = 0;
00437 }
00438 
00439 
00440 const void *WvConstInPlaceBufStore::get(size_t count)
00441 {
00442     assert(count <= avail - readidx ||
00443         ! "attempted to get() more than used()");
00444     const void *ptr = (const unsigned char*)data + readidx;
00445     readidx += count;
00446     return ptr;
00447 }
00448 
00449 
00450 void WvConstInPlaceBufStore::unget(size_t count)
00451 {
00452     assert(count <= readidx ||
00453         ! "attempted to unget() more than ungettable()");
00454     readidx -= count;
00455 }
00456 
00457 
00458 size_t WvConstInPlaceBufStore::ungettable() const
00459 {
00460     return readidx;
00461 }
00462 
00463 
00464 const void *WvConstInPlaceBufStore::peek(int offset, size_t count)
00465 {
00466     if (count == 0)
00467         return NULL;
00468     assert(((offset <= 0) ? 
00469         size_t(-offset) <= readidx :
00470         size_t(offset) < avail - readidx) ||
00471         ! "attempted to peek() with invalid offset or count");
00472     return (const unsigned char*)data + readidx + offset;
00473 }
00474 
00475 
00476 void WvConstInPlaceBufStore::zap()
00477 {
00478     readidx = avail = 0;
00479 }
00480 
00481 
00482 
00483 /***** WvCircularBufStore *****/
00484 
00485 WvCircularBufStore::WvCircularBufStore(int _granularity,
00486     void *_data, size_t _avail, size_t _size, bool _autofree) :
00487     WvBufStore(_granularity), data(NULL)
00488 {
00489     reset(_data, _avail, _size, _autofree);
00490 }
00491 
00492 
00493 WvCircularBufStore::WvCircularBufStore(int _granularity, size_t _size) :
00494     WvBufStore(_granularity), data(NULL)
00495 {
00496     reset(memops.newarray(_size), 0, _size, true);
00497 }
00498 
00499 
00500 WvCircularBufStore::~WvCircularBufStore()
00501 {
00502     if (data && xautofree)
00503         memops.deletearray(data);
00504 }
00505 
00506 
00507 void WvCircularBufStore::reset(void *_data, size_t _avail,
00508     size_t _size, bool _autofree = false)
00509 {
00510     assert(_data != NULL || _avail == 0);
00511     if (data && _data != data && xautofree)
00512         memops.deletearray(data);
00513     data = _data;
00514     xautofree = _autofree;
00515     xsize = _size;
00516     setavail(_avail);
00517 }
00518 
00519 
00520 void WvCircularBufStore::setavail(size_t _avail)
00521 {
00522     assert(_avail <= xsize);
00523     head = 0;
00524     totalused = totalinit = _avail;
00525 }
00526 
00527 
00528 size_t WvCircularBufStore::used() const
00529 {
00530     return totalused;
00531 }
00532 
00533 
00534 size_t WvCircularBufStore::optgettable() const
00535 {
00536     size_t avail = xsize - head;
00537     if (avail > totalused)
00538         avail = totalused;
00539     return avail;
00540 }
00541 
00542 
00543 const void *WvCircularBufStore::get(size_t count)
00544 {
00545     assert(count <= totalused ||
00546         ! "attempted to get() more than used()");
00547     size_t first = ensurecontiguous(0, count, false /*keephistory*/);
00548     const void *tmpptr = (const unsigned char*)data + first;
00549     head = (head + count) % xsize;
00550     totalused -= count;
00551     return tmpptr;
00552 }
00553 
00554 
00555 void WvCircularBufStore::unget(size_t count)
00556 {
00557     assert(count <= totalinit - totalused ||
00558         !"attempted to unget() more than ungettable()");
00559     head = (head + xsize - count) % xsize;
00560     totalused += count;
00561 }
00562 
00563 
00564 size_t WvCircularBufStore::ungettable() const
00565 {
00566     return totalinit - totalused;
00567 }
00568 
00569 
00570 void WvCircularBufStore::zap()
00571 {
00572     head = 0;
00573     totalused = totalinit = 0;
00574 }
00575 
00576 
00577 size_t WvCircularBufStore::free() const
00578 {
00579     return xsize - totalused;
00580 }
00581 
00582 
00583 size_t WvCircularBufStore::optallocable() const
00584 {
00585     size_t tail = head + totalused;
00586     if (tail >= xsize)
00587         return xsize - totalused;
00588     return xsize - tail;
00589 }
00590 
00591 
00592 void *WvCircularBufStore::alloc(size_t count)
00593 {
00594     assert(count <= xsize - totalused ||
00595         !"attempted to alloc() more than free()");
00596     totalinit = totalused; // always discard history
00597     size_t first = ensurecontiguous(totalused, count,
00598         false /*keephistory*/);
00599     void *tmpptr = (unsigned char*)data + first;
00600     totalused += count;
00601     totalinit += count;
00602     return tmpptr;
00603 }
00604 
00605 
00606 void WvCircularBufStore::unalloc(size_t count)
00607 {
00608     assert(count <= totalused ||
00609         !"attempted to unalloc() more than unallocable()");
00610     totalused -= count;
00611     totalinit -= count;
00612 }
00613 
00614 
00615 size_t WvCircularBufStore::unallocable() const
00616 {
00617     return totalused;
00618 }
00619 
00620 
00621 void *WvCircularBufStore::mutablepeek(int offset, size_t count)
00622 {
00623     if (count == 0)
00624         return NULL;
00625     assert(((offset <= 0) ? 
00626         size_t(-offset) <= totalinit - totalused :
00627         size_t(offset) < totalused) ||
00628         ! "attempted to peek() with invalid offset or count");
00629     size_t first = ensurecontiguous(offset, count,
00630         true /*keephistory*/);
00631     void *tmpptr = (unsigned char*)data + first;
00632     return tmpptr;
00633 }
00634 
00635 
00636 void WvCircularBufStore::normalize()
00637 {
00638     // discard history to minimize data transfers
00639     totalinit = totalused;
00640 
00641     // normalize the buffer
00642     compact(data, xsize, head, totalused);
00643     head = 0;
00644 }
00645 
00646 
00647 size_t WvCircularBufStore::ensurecontiguous(int offset,
00648     size_t count, bool keephistory)
00649 {
00650     // determine the region of interest
00651     size_t start = (head + offset + xsize) % xsize;
00652     if (count != 0)
00653     {   
00654         size_t end = start + count;
00655         if (end > xsize)
00656         {
00657             // the region is not entirely contiguous
00658             // determine the region that must be normalized
00659             size_t keepstart = head;
00660             if (keephistory)
00661             {
00662                 // adjust the region to include history
00663                 keepstart += totalused - totalinit + xsize;
00664             }
00665             else
00666             {
00667                 // discard history to minimize data transfers
00668                 totalinit = totalused;
00669             }
00670             keepstart %= xsize;
00671 
00672             // normalize the buffer over this region
00673             compact(data, xsize, keepstart, totalinit);
00674             head = totalinit - totalused;
00675 
00676             // compute the new start offset
00677             start = (head + offset + xsize) % xsize;
00678         }
00679     }
00680     return start;
00681 }
00682 
00683 
00684 void WvCircularBufStore::compact(void *data, size_t size,
00685     size_t head, size_t count)
00686 {
00687     if (count == 0)
00688     {
00689         // Case 1: Empty region
00690         // Requires 0 moves
00691         return;
00692     }
00693 
00694     if (head + count <= size)
00695     {
00696         // Case 2: Contiguous region
00697         // Requires count moves
00698         memops.uninit_move(data, (unsigned char*)data + head, count);
00699         return;
00700     }
00701     
00702     size_t headcount = size - head;
00703     size_t tailcount = count - headcount;
00704     size_t freecount = size - count;
00705     if (freecount >= headcount)
00706     {
00707         // Case 3: Non-contiguous region, does not require swapping
00708         // Requires count moves
00709         memops.uninit_move((unsigned char*)data + headcount,
00710             data, tailcount);
00711         memops.uninit_move(data, (unsigned char*)data + head,
00712             headcount);
00713         return;
00714     }
00715 
00716     // Case 4: Non-contiguous region, requires swapping
00717     // Requires count * 2 moves
00718     unsigned char *start = (unsigned char*)data;
00719     unsigned char *end = (unsigned char*)data + head;
00720     while (tailcount >= headcount)
00721     {
00722         memops.swap(start, end, headcount);
00723         start += headcount;
00724         tailcount -= headcount;
00725     }
00726     // Now the array looks like: |a|b|c|g|h|_|d|e|f|   
00727     // FIXME: this is an interim solution
00728     void *buf = memops.newarray(tailcount);
00729     memops.uninit_move(buf, start, tailcount);
00730     memops.uninit_move(start, end, headcount);
00731     memops.uninit_move(start + headcount, buf, tailcount);
00732     memops.deletearray(buf);
00733 }
00734 
00735 
00736 
00737 /***** WvLinkedBufferStore *****/
00738 
00739 WvLinkedBufferStore::WvLinkedBufferStore(int _granularity) :
00740     WvBufStore(_granularity), totalused(0), maxungettable(0)
00741 {
00742 }
00743 
00744 
00745 bool WvLinkedBufferStore::usessubbuffers() const
00746 {
00747     return true;
00748 }
00749 
00750 
00751 size_t WvLinkedBufferStore::numsubbuffers() const
00752 {
00753     return list.count();
00754 }
00755 
00756 
00757 WvBufStore *WvLinkedBufferStore::firstsubbuffer() const
00758 {
00759     return list.first();
00760 }
00761 
00762 
00763 void WvLinkedBufferStore::appendsubbuffer(WvBufStore *buffer,
00764     bool autofree)
00765 {
00766     list.append(buffer, autofree);
00767     totalused += buffer->used();
00768 }
00769 
00770 
00771 void WvLinkedBufferStore::prependsubbuffer(WvBufStore *buffer,
00772     bool autofree)
00773 {
00774     list.prepend(buffer, autofree);
00775     totalused += buffer->used();
00776     maxungettable = 0;
00777 }
00778 
00779 
00780 bool WvLinkedBufferStore::unlinksubbuffer(WvBufStore *buffer,
00781     bool allowautofree)
00782 {
00783     WvBufStoreList::Iter it(list);
00784     WvLink *link = it.find(buffer);
00785     assert(link);
00786     
00787     bool autofree = it.get_autofree();
00788     totalused -= buffer->used();
00789     if (buffer == list.first())
00790         maxungettable = 0;
00791     if (! allowautofree)
00792         it.set_autofree(false);
00793     it.unlink(); // do not recycle the buffer
00794     return autofree;
00795 }
00796 
00797 
00798 size_t WvLinkedBufferStore::used() const
00799 {
00800     assert(!totalused || !list.isempty());
00801     return totalused;
00802 }
00803 
00804 
00805 size_t WvLinkedBufferStore::optgettable() const
00806 {
00807     // find the first buffer with an optgettable() and return that
00808     size_t count;
00809     WvBufStoreList::Iter it(list);
00810     for (it.rewind(); it.next(); )
00811         if ((count = it->optgettable()) != 0)
00812             return count;
00813     return 0;
00814 }
00815 
00816 
00817 const void *WvLinkedBufferStore::get(size_t count)
00818 {
00819     assert(!totalused || !list.isempty());
00820     if (count == 0)
00821         return NULL;
00822 
00823     assert(count <= totalused);
00824     assert(count > 0);
00825     
00826     totalused -= count;
00827 
00828     assert(totalused >= 0);
00829     
00830     // search for first non-empty buffer
00831     WvBufStore *buf;
00832     size_t availused;
00833     WvBufStoreList::Iter it(list);
00834     for (;;)
00835     {
00836         it.rewind(); it.next();
00837         buf = it.ptr();
00838         assert(buf && "attempted to get() more than used()" &&
00839                 "totalused is wrong!");
00840 
00841         availused = buf->used();
00842         if (availused != 0)
00843             break;
00844 
00845         // unlink the leading empty buffer
00846         do_xunlink(it);
00847     }
00848 
00849     // return the data
00850     if (availused < count)
00851         buf = coalesce(it, count);
00852 
00853     maxungettable += count;
00854     return buf->get(count);
00855 }
00856 
00857 
00858 void WvLinkedBufferStore::unget(size_t count)
00859 {
00860     assert(!totalused || !list.isempty());
00861     if (count == 0)
00862         return;
00863     assert(count > 0);
00864     assert(!list.isempty());
00865     assert(count <= maxungettable);
00866     totalused += count;
00867     maxungettable -= count;
00868     list.first()->unget(count);
00869 }
00870 
00871 
00872 size_t WvLinkedBufferStore::ungettable() const
00873 {
00874     assert(!totalused || !list.isempty());
00875     if (list.isempty())
00876     {
00877         assert(maxungettable == 0);
00878         return 0;
00879     }
00880 
00881     // maxungettable and list.first()->ungettable() can get out of sync in two ways:
00882     // - coalescing moves data from later buffers to the first one, which
00883     // leaves it as ungettable in those buffers.  So when we first start to
00884     // use a buffer, its ungettable() count may be too high.  (This is the
00885     // reason maxungettable exists.) 
00886     // - some calls (ie. alloc) may clear all ungettable data from the first
00887     // buffer without telling us.  So there might be less data to unget than we
00888     // think.
00889     size_t avail = list.first()->ungettable();
00890     if (avail > maxungettable)
00891         avail = maxungettable;
00892     return avail;
00893 }
00894 
00895 
00896 void WvLinkedBufferStore::zap()
00897 {
00898     totalused = 0;
00899     maxungettable = 0;
00900     WvBufStoreList::Iter it(list);
00901     for (it.rewind(); it.next(); )
00902         do_xunlink(it);
00903 }
00904 
00905 
00906 size_t WvLinkedBufferStore::free() const
00907 {
00908     if (!list.isempty())
00909         return list.last()->free();
00910     return 0;
00911 }
00912 
00913 
00914 size_t WvLinkedBufferStore::optallocable() const
00915 {
00916     if (!list.isempty())
00917         return list.last()->optallocable();
00918     return 0;
00919 }
00920 
00921 
00922 void *WvLinkedBufferStore::alloc(size_t count)
00923 {
00924     if (count == 0)
00925         return NULL;
00926     assert(!list.isempty() && "attempted to alloc() more than free()");
00927     totalused += count;
00928     return list.last()->alloc(count);
00929 }
00930 
00931 
00932 void WvLinkedBufferStore::unalloc(size_t count)
00933 {
00934     assert(count <= totalused);
00935 
00936     totalused -= count;
00937     while (count > 0)
00938     {
00939         assert(!list.isempty() &&
00940                 "attempted to unalloc() more than unallocable()" &&
00941                 "totalused is wrong");
00942         WvBufStore *buf = list.last();
00943         size_t avail = buf->unallocable();
00944         if (count < avail)
00945         {
00946             buf->unalloc(count);
00947             break;
00948         }
00949         
00950         WvBufStoreList::Iter it(list);
00951         it.find(buf);
00952         do_xunlink(it);
00953         
00954         count -= avail;
00955     }
00956 }
00957 
00958 
00959 size_t WvLinkedBufferStore::unallocable() const
00960 {
00961     return totalused;
00962 }
00963 
00964 
00965 size_t WvLinkedBufferStore::optpeekable(int offset) const
00966 {
00967     // search for the buffer that contains the offset
00968     WvBufStoreList::Iter it(list);
00969     int newoffset = search(it, offset);
00970     WvBufStore *buf = it.ptr();
00971     if (!buf)
00972         return 0; // out of bounds
00973     return buf->optpeekable(newoffset);
00974 }
00975 
00976 
00977 void *WvLinkedBufferStore::mutablepeek(int offset, size_t count)
00978 {
00979     if (count == 0)
00980         return NULL;
00981     
00982     // search for the buffer that contains the offset
00983     WvBufStoreList::Iter it(list);
00984     offset = search(it, offset);
00985     WvBufStore *buf = it.ptr();
00986     assert(buf && "attempted to peek() with invalid offset or count");
00987     
00988     // return data if we have enough
00989     size_t availpeek = buf->peekable(offset);
00990     if (availpeek < count)
00991         buf = coalesce(it, count);
00992     return buf->mutablepeek(offset, count);
00993 }
00994 
00995 
00996 WvBufStore *WvLinkedBufferStore::newbuffer(size_t minsize)
00997 {
00998     minsize = roundup(minsize, granularity);
00999     //return new WvInPlaceBufStore(granularity, minsize);
01000     return new WvCircularBufStore(granularity, minsize);
01001 }
01002 
01003 
01004 void WvLinkedBufferStore::recyclebuffer(WvBufStore *buffer)
01005 {
01006     delete buffer;
01007 }
01008 
01009 
01010 int WvLinkedBufferStore::search(WvBufStoreList::Iter &it,
01011     int offset) const
01012 {
01013     it.rewind();
01014     if (it.next())
01015     {
01016         if (offset < 0)
01017         {
01018             // inside unget() region
01019             WvBufStore *buf = it.ptr();
01020             if (size_t(-offset) <= buf->ungettable())
01021                 return offset;
01022             it.rewind(); // mark out of bounds
01023         }
01024         else
01025         {
01026             // inside get() region
01027             do
01028             {
01029                 WvBufStore *buf = it.ptr();
01030                 size_t avail = buf->used();
01031                 if (size_t(offset) < avail)
01032                     return offset;
01033                 offset -= avail;
01034             }
01035             while (it.next());
01036         }
01037     }
01038     return 0;
01039 }
01040 
01041 
01042 WvBufStore *WvLinkedBufferStore::coalesce(WvBufStoreList::Iter &it,
01043                                           size_t count)
01044 {
01045     WvBufStore *buf = it.ptr();
01046     size_t availused = buf->used();
01047     if (count <= availused)
01048         return buf;
01049 
01050     // allocate a new buffer if there is not enough room to coalesce
01051     size_t needed = count - availused;
01052     size_t availfree = buf->free();
01053     size_t mustskip = 0;
01054     if (availfree < needed)
01055     {
01056         // if this is the first buffer, then we need to unget as
01057         // much as possible to ensure it does not get discarded
01058         // during the coalescing phase
01059         if (buf == list.first() && totalused != 0)
01060         {
01061             // use ungettable() instead of buf->ungettable() because we might
01062             // have reset it to 0
01063             // FIXME: uh... who might have reset it to 0, and why?
01064             mustskip = ungettable();
01065             buf->unget(mustskip);
01066         }
01067 
01068         needed = count + mustskip;
01069         buf = newbuffer(needed);
01070 
01071         // insert the buffer before the previous link
01072         list.add_after(it.prev, buf, true);
01073         it.find(buf);
01074     }
01075     
01076     // coalesce subsequent buffers into the first
01077     while (it.next())
01078     {
01079         WvBufStore *itbuf = it.ptr();
01080         size_t chunk = itbuf->used();
01081         if (chunk > 0)
01082         {
01083             if (chunk > needed)
01084                 chunk = needed;
01085             buf->merge(*itbuf, chunk);
01086             needed -= chunk;
01087             if (needed == 0)
01088             {
01089                 buf->skip(mustskip);
01090                 return buf;
01091             }
01092         }
01093         do_xunlink(it); // buffer is now empty
01094     }
01095     assert(false && "invalid count during get() or peek()");
01096     return NULL;
01097 }
01098 
01099 
01100 void WvLinkedBufferStore::do_xunlink(WvBufStoreList::Iter &it)
01101 {
01102     WvBufStore *buf = it.ptr();
01103     if (buf == list.first())
01104         maxungettable = 0;
01105 
01106     bool autofree = it.get_autofree();
01107     it.set_autofree(false);
01108     it.xunlink();
01109     if (autofree)
01110         recyclebuffer(buf);
01111 }
01112 
01113 
01114 
01115 /***** WvDynBufStore *****/
01116 
01117 WvDynBufStore::WvDynBufStore(size_t _granularity,
01118     size_t _minalloc, size_t _maxalloc) :
01119     WvLinkedBufferStore(_granularity),
01120     minalloc(_minalloc), maxalloc(_maxalloc)
01121 {
01122     assert(maxalloc >= minalloc);
01123 }
01124 
01125 
01126 size_t WvDynBufStore::free() const
01127 {
01128     return UNLIMITED_FREE_SPACE;
01129 }
01130 
01131 
01132 size_t WvDynBufStore::optallocable() const
01133 {
01134     size_t avail = WvLinkedBufferStore::optallocable();
01135     if (avail == 0)
01136         avail = UNLIMITED_FREE_SPACE;
01137     return avail;
01138 }
01139 
01140 
01141 void *WvDynBufStore::alloc(size_t count)
01142 {
01143     if (count > WvLinkedBufferStore::free())
01144     {
01145         WvBufStore *buf = newbuffer(count);
01146         appendsubbuffer(buf, true);
01147     }
01148     return WvLinkedBufferStore::alloc(count);
01149 }
01150 
01151 
01152 WvBufStore *WvDynBufStore::newbuffer(size_t minsize)
01153 {
01154     // allocate a new buffer
01155     // try to approximate exponential growth by at least doubling
01156     // the amount of space available for immediate use
01157     size_t size = used();
01158     if (size < minsize * 2)
01159         size = minsize * 2;
01160     if (size < minalloc)
01161         size = minalloc;
01162     else if (size > maxalloc)
01163         size = maxalloc;
01164     if (size < minsize)
01165         size = minsize;
01166     return WvLinkedBufferStore::newbuffer(size);
01167 }
01168 
01169 
01170 
01171 /***** WvNullBufStore *****/
01172 
01173 WvNullBufStore::WvNullBufStore(size_t _granularity) :
01174     WvWriteOnlyBufferStoreMixin<
01175         WvReadOnlyBufferStoreMixin<WvBufStore> >(_granularity)
01176 {
01177 }
01178 
01179 
01180 
01181 /***** WvBufCursorStore *****/
01182 
01183 WvBufCursorStore::WvBufCursorStore(size_t _granularity,
01184     WvBufStore *_buf, int _start, size_t _length) :
01185     WvReadOnlyBufferStoreMixin<WvBufStore>(_granularity),
01186     buf(_buf), start(_start), length(_length), shift(0)
01187 {
01188 }
01189 
01190 
01191 bool WvBufCursorStore::isreadable() const
01192 {
01193     return buf->isreadable();
01194 }
01195 
01196 
01197 size_t WvBufCursorStore::used() const
01198 {
01199     return length - shift;
01200 }
01201 
01202 
01203 size_t WvBufCursorStore::optgettable() const
01204 {
01205     size_t avail = buf->optpeekable(start + shift);
01206     assert(avail != 0 || length == shift ||
01207         ! "buffer cursor operating over invalid region");
01208     if (avail > length)
01209         avail = length;
01210     return avail;
01211 }
01212 
01213 
01214 const void *WvBufCursorStore::get(size_t count)
01215 {
01216     assert(count <= length - shift ||
01217         ! "attempted to get() more than used()");
01218     const void *data = buf->peek(start + shift, count);
01219     shift += count;
01220     return data;
01221 }
01222 
01223 
01224 void WvBufCursorStore::skip(size_t count)
01225 {
01226     assert(count <= length - shift ||
01227         ! "attempted to skip() more than used()");
01228     shift += count;
01229 }
01230 
01231 
01232 void WvBufCursorStore::unget(size_t count)
01233 {
01234     assert(count <= shift ||
01235         ! "attempted to unget() more than ungettable()");
01236     shift -= count;
01237 }
01238 
01239 
01240 size_t WvBufCursorStore::ungettable() const
01241 {
01242     return shift;
01243 }
01244 
01245 
01246 void WvBufCursorStore::zap()
01247 {
01248     shift = length;
01249 }
01250 
01251 
01252 size_t WvBufCursorStore::peekable(int offset) const
01253 {
01254     offset += shift;
01255     offset -= start;
01256     if (offset < 0 || offset > int(length))
01257         return 0;
01258     return length - size_t(offset);
01259 }
01260 
01261 
01262 size_t WvBufCursorStore::optpeekable(int offset) const
01263 {
01264     size_t avail = buf->optpeekable(start + shift + offset);
01265     assert(avail != 0 || length == shift ||
01266         ! "buffer cursor operating over invalid region");
01267     size_t max = peekable(offset);
01268     if (avail > max)
01269         avail = max;
01270     return avail;
01271 }
01272 
01273 
01274 const void *WvBufCursorStore::peek(int offset, size_t count)
01275 {
01276     offset += shift;
01277     assert((offset >= start && offset - start + count <= length) ||
01278         ! "attempted to peek() with invalid offset or count");
01279     return buf->peek(offset, count);
01280 }
01281 
01282 
01283 bool WvBufCursorStore::iswritable() const
01284 {
01285     // check if mutablepeek() is supported
01286     return buf->iswritable();
01287 }
01288 
01289 
01290 void *WvBufCursorStore::mutablepeek(int offset, size_t count)
01291 {
01292     offset += shift;
01293     assert((offset >= start && offset - start + count <= length) ||
01294         ! "attempted to peek() with invalid offset or count");
01295     return buf->mutablepeek(offset, count);
01296 }