WvStreams
|
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 }