- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

# queue.cpp

    00001 // queue.cpp - written and placed in the public domain by Wei Dai
    00002
    00003 #include "pch.h"
    00004
    00005 #ifndef CRYPTOPP_IMPORTS
    00006
    00007 #include "queue.h"
    00008 #include "filters.h"
    00009
    00010 NAMESPACE_BEGIN(CryptoPP)
    00011
    00012 static const unsigned int s_maxAutoNodeSize = 16*1024;
    00013
    00014 // this class for use by ByteQueue only
    00015 class ByteQueueNode
    00016 {
    00017 public:
    00018         ByteQueueNode(size_t maxSize)
    00019                 : buf(maxSize)
    00020         {
    00021                 m_head = m_tail = 0;
    00022                 next = 0;
    00023         }
    00024
    00025         inline size_t MaxSize() const {return buf.size();}
    00026
    00027         inline size_t CurrentSize() const
    00028         {
    00029                 return m_tail-m_head;
    00030         }
    00031
    00032         inline bool UsedUp() const
    00033         {
    00034                 return (m_head==MaxSize());
    00035         }
    00036
    00037         inline void Clear()
    00038         {
    00039                 m_head = m_tail = 0;
    00040         }
    00041
    00042         inline size_t Put(const byte *begin, size_t length)
    00043         {
    00044                 size_t l = STDMIN(length, MaxSize()-m_tail);
    00045                 if (buf+m_tail != begin)
    00046                         memcpy(buf+m_tail, begin, l);
    00047                 m_tail += l;
    00048                 return l;
    00049         }
    00050
    00051         inline size_t Peek(byte &outByte) const
    00052         {
    00053                 if (m_tail==m_head)
    00054                         return 0;
    00055
    00056                 outByte=buf[m_head];
    00057                 return 1;
    00058         }
    00059
    00060         inline size_t Peek(byte *target, size_t copyMax) const
    00061         {
    00062                 size_t len = STDMIN(copyMax, m_tail-m_head);
    00063                 memcpy(target, buf+m_head, len);
    00064                 return len;
    00065         }
    00066
    00067         inline size_t CopyTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const
    00068         {
    00069                 size_t len = m_tail-m_head;
    00070                 target.ChannelPut(channel, buf+m_head, len);
    00071                 return len;
    00072         }
    00073
    00074         inline size_t CopyTo(BufferedTransformation &target, size_t copyMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const
    00075         {
    00076                 size_t len = STDMIN(copyMax, m_tail-m_head);
    00077                 target.ChannelPut(channel, buf+m_head, len);
    00078                 return len;
    00079         }
    00080
    00081         inline size_t Get(byte &outByte)
    00082         {
    00083                 size_t len = Peek(outByte);
    00084                 m_head += len;
    00085                 return len;
    00086         }
    00087
    00088         inline size_t Get(byte *outString, size_t getMax)
    00089         {
    00090                 size_t len = Peek(outString, getMax);
    00091                 m_head += len;
    00092                 return len;
    00093         }
    00094
    00095         inline size_t TransferTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL)
    00096         {
    00097                 size_t len = m_tail-m_head;
    00098                 target.ChannelPutModifiable(channel, buf+m_head, len);
    00099                 m_head = m_tail;
    00100                 return len;
    00101         }
    00102
    00103         inline size_t TransferTo(BufferedTransformation &target, lword transferMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL)
    00104         {
    00105                 size_t len = UnsignedMin(m_tail-m_head, transferMax);
    00106                 target.ChannelPutModifiable(channel, buf+m_head, len);
    00107                 m_head += len;
    00108                 return len;
    00109         }
    00110
    00111         inline size_t Skip(size_t skipMax)
    00112         {
    00113                 size_t len = STDMIN(skipMax, m_tail-m_head);
    00114                 m_head += len;
    00115                 return len;
    00116         }
    00117
    00118         inline byte operator[](size_t i) const
    00119         {
    00120                 return buf[m_head+i];
    00121         }
    00122
    00123         ByteQueueNode *next;
    00124
    00125         SecByteBlock buf;
    00126         size_t m_head, m_tail;
    00127 };
    00128
    00129 // ********************************************************
    00130
    00131 ByteQueue::ByteQueue(size_t nodeSize)
    00132         : m_lazyLength(0)
    00133 {
    00134         SetNodeSize(nodeSize);
    00135         m_head = m_tail = new ByteQueueNode(m_nodeSize);
    00136 }
    00137
    00138 void ByteQueue::SetNodeSize(size_t nodeSize)
    00139 {
    00140         m_autoNodeSize = !nodeSize;
    00141         m_nodeSize = m_autoNodeSize ? 256 : nodeSize;
    00142 }
    00143
    00144 ByteQueue::ByteQueue(const ByteQueue &copy)
    00145 {
    00146         CopyFrom(copy);
    00147 }
    00148
    00149 void ByteQueue::CopyFrom(const ByteQueue &copy)
    00150 {
    00151         m_lazyLength = 0;
    00152         m_autoNodeSize = copy.m_autoNodeSize;
    00153         m_nodeSize = copy.m_nodeSize;
    00154         m_head = m_tail = new ByteQueueNode(*copy.m_head);
    00155
    00156         for (ByteQueueNode *current=copy.m_head->next; current; current=current->next)
    00157         {
    00158                 m_tail->next = new ByteQueueNode(*current);
    00159                 m_tail = m_tail->next;
    00160         }
    00161
    00162         m_tail->next = NULL;
    00163
    00164         Put(copy.m_lazyString, copy.m_lazyLength);
    00165 }
    00166
    00167 ByteQueue::~ByteQueue()
    00168 {
    00169         Destroy();
    00170 }
    00171
    00172 void ByteQueue::Destroy()
    00173 {
    00174         for (ByteQueueNode *next, *current=m_head; current; current=next)
    00175         {
    00176                 next=current->next;
    00177                 delete current;
    00178         }
    00179 }
    00180
    00181 void ByteQueue::IsolatedInitialize(const NameValuePairs &parameters)
    00182 {
    00183         m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256);
    00184         Clear();
    00185 }
    00186
    00187 lword ByteQueue::CurrentSize() const
    00188 {
    00189         lword size=0;
    00190
    00191         for (ByteQueueNode *current=m_head; current; current=current->next)
    00192                 size += current->CurrentSize();
    00193
    00194         return size + m_lazyLength;
    00195 }
    00196
    00197 bool ByteQueue::IsEmpty() const
    00198 {
    00199         return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0;
    00200 }
    00201
    00202 void ByteQueue::Clear()
    00203 {
    00204         for (ByteQueueNode *next, *current=m_head->next; current; current=next)
    00205         {
    00206                 next=current->next;
    00207                 delete current;
    00208         }
    00209
    00210         m_tail = m_head;
    00211         m_head->Clear();
    00212         m_head->next = NULL;
    00213         m_lazyLength = 0;
    00214 }
    00215
    00216 size_t ByteQueue::Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
    00217 {
    00218         if (m_lazyLength > 0)
    00219                 FinalizeLazyPut();
    00220
    00221         size_t len;
    00222         while ((len=m_tail->Put(inString, length)) < length)
    00223         {
    00224                 inString += len;
    00225                 length -= len;
    00226                 if (m_autoNodeSize && m_nodeSize < s_maxAutoNodeSize)
    00227                         do
    00228                         {
    00229                                 m_nodeSize *= 2;
    00230                         }
    00231                         while (m_nodeSize < length && m_nodeSize < s_maxAutoNodeSize);
    00232                 m_tail->next = new ByteQueueNode(STDMAX(m_nodeSize, length));
    00233                 m_tail = m_tail->next;
    00234         }
    00235
    00236         return 0;
    00237 }
    00238
    00239 void ByteQueue::CleanupUsedNodes()
    00240 {
    00241         while (m_head != m_tail && m_head->UsedUp())
    00242         {
    00243                 ByteQueueNode *temp=m_head;
    00244                 m_head=m_head->next;
    00245                 delete temp;
    00246         }
    00247
    00248         if (m_head->CurrentSize() == 0)
    00249                 m_head->Clear();
    00250 }
    00251
    00252 void ByteQueue::LazyPut(const byte *inString, size_t size)
    00253 {
    00254         if (m_lazyLength > 0)
    00255                 FinalizeLazyPut();
    00256
    00257         if (inString == m_tail->buf+m_tail->m_tail)
    00258                 Put(inString, size);
    00259         else
    00260         {
    00261                 m_lazyString = const_cast<byte *>(inString);
    00262                 m_lazyLength = size;
    00263                 m_lazyStringModifiable = false;
    00264         }
    00265 }
    00266
    00267 void ByteQueue::LazyPutModifiable(byte *inString, size_t size)
    00268 {
    00269         if (m_lazyLength > 0)
    00270                 FinalizeLazyPut();
    00271         m_lazyString = inString;
    00272         m_lazyLength = size;
    00273         m_lazyStringModifiable = true;
    00274 }
    00275
    00276 void ByteQueue::UndoLazyPut(size_t size)
    00277 {
    00278         if (m_lazyLength < size)
    00279                 throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large");
    00280
    00281         m_lazyLength -= size;
    00282 }
    00283
    00284 void ByteQueue::FinalizeLazyPut()
    00285 {
    00286         size_t len = m_lazyLength;
    00287         m_lazyLength = 0;
    00288         if (len)
    00289                 Put(m_lazyString, len);
    00290 }
    00291
    00292 size_t ByteQueue::Get(byte &outByte)
    00293 {
    00294         if (m_head->Get(outByte))
    00295         {
    00296                 if (m_head->UsedUp())
    00297                         CleanupUsedNodes();
    00298                 return 1;
    00299         }
    00300         else if (m_lazyLength > 0)
    00301         {
    00302                 outByte = *m_lazyString++;
    00303                 m_lazyLength--;
    00304                 return 1;
    00305         }
    00306         else
    00307                 return 0;
    00308 }
    00309
    00310 size_t ByteQueue::Get(byte *outString, size_t getMax)
    00311 {
    00312         ArraySink sink(outString, getMax);
    00313         return (size_t)TransferTo(sink, getMax);
    00314 }
    00315
    00316 size_t ByteQueue::Peek(byte &outByte) const
    00317 {
    00318         if (m_head->Peek(outByte))
    00319                 return 1;
    00320         else if (m_lazyLength > 0)
    00321         {
    00322                 outByte = *m_lazyString;
    00323                 return 1;
    00324         }
    00325         else
    00326                 return 0;
    00327 }
    00328
    00329 size_t ByteQueue::Peek(byte *outString, size_t peekMax) const
    00330 {
    00331         ArraySink sink(outString, peekMax);
    00332         return (size_t)CopyTo(sink, peekMax);
    00333 }
    00334
    00335 size_t ByteQueue::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
    00336 {
    00337         if (blocking)
    00338         {
    00339                 lword bytesLeft = transferBytes;
    00340                 for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->next)
    00341                         bytesLeft -= current->TransferTo(target, bytesLeft, channel);
    00342                 CleanupUsedNodes();
    00343
    00344                 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
    00345                 if (len)
    00346                 {
    00347                         if (m_lazyStringModifiable)
    00348                                 target.ChannelPutModifiable(channel, m_lazyString, len);
    00349                         else
    00350                                 target.ChannelPut(channel, m_lazyString, len);
    00351                         m_lazyString += len;
    00352                         m_lazyLength -= len;
    00353                         bytesLeft -= len;
    00354                 }
    00355                 transferBytes -= bytesLeft;
    00356                 return 0;
    00357         }
    00358         else
    00359         {
    00360                 Walker walker(*this);
    00361                 size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
    00362                 Skip(transferBytes);
    00363                 return blockedBytes;
    00364         }
    00365 }
    00366
    00367 size_t ByteQueue::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
    00368 {
    00369         Walker walker(*this);
    00370         walker.Skip(begin);
    00371         lword transferBytes = end-begin;
    00372         size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
    00373         begin += transferBytes;
    00374         return blockedBytes;
    00375 }
    00376
    00377 void ByteQueue::Unget(byte inByte)
    00378 {
    00379         Unget(&inByte, 1);
    00380 }
    00381
    00382 void ByteQueue::Unget(const byte *inString, size_t length)
    00383 {
    00384         size_t len = STDMIN(length, m_head->m_head);
    00385         length -= len;
    00386         m_head->m_head -= len;
    00387         memcpy(m_head->buf + m_head->m_head, inString + length, len);
    00388
    00389         if (length > 0)
    00390         {
    00391                 ByteQueueNode *newHead = new ByteQueueNode(length);
    00392                 newHead->next = m_head;
    00393                 m_head = newHead;
    00394                 m_head->Put(inString, length);
    00395         }
    00396 }
    00397
    00398 const byte * ByteQueue::Spy(size_t &contiguousSize) const
    00399 {
    00400         contiguousSize = m_head->m_tail - m_head->m_head;
    00401         if (contiguousSize == 0 && m_lazyLength > 0)
    00402         {
    00403                 contiguousSize = m_lazyLength;
    00404                 return m_lazyString;
    00405         }
    00406         else
    00407                 return m_head->buf + m_head->m_head;
    00408 }
    00409
    00410 byte * ByteQueue::CreatePutSpace(size_t &size)
    00411 {
    00412         if (m_lazyLength > 0)
    00413                 FinalizeLazyPut();
    00414
    00415         if (m_tail->m_tail == m_tail->MaxSize())
    00416         {
    00417                 m_tail->next = new ByteQueueNode(STDMAX(m_nodeSize, size));
    00418                 m_tail = m_tail->next;
    00419         }
    00420
    00421         size = m_tail->MaxSize() - m_tail->m_tail;
    00422         return m_tail->buf + m_tail->m_tail;
    00423 }
    00424
    00425 ByteQueue & ByteQueue::operator=(const ByteQueue &rhs)
    00426 {
    00427         Destroy();
    00428         CopyFrom(rhs);
    00429         return *this;
    00430 }
    00431
    00432 bool ByteQueue::operator==(const ByteQueue &rhs) const
    00433 {
    00434         const lword currentSize = CurrentSize();
    00435
    00436         if (currentSize != rhs.CurrentSize())
    00437                 return false;
    00438
    00439         Walker walker1(*this), walker2(rhs);
    00440         byte b1, b2;
    00441
    00442         while (walker1.Get(b1) && walker2.Get(b2))
    00443                 if (b1 != b2)
    00444                         return false;
    00445
    00446         return true;
    00447 }
    00448
    00449 byte ByteQueue::operator[](lword i) const
    00450 {
    00451         for (ByteQueueNode *current=m_head; current; current=current->next)
    00452         {
    00453                 if (i < current->CurrentSize())
    00454                         return (*current)[(size_t)i];
    00455
    00456                 i -= current->CurrentSize();
    00457         }
    00458
    00459         assert(i < m_lazyLength);
    00460         return m_lazyString[i];
    00461 }
    00462
    00463 void ByteQueue::swap(ByteQueue &rhs)
    00464 {
    00465         std::swap(m_autoNodeSize, rhs.m_autoNodeSize);
    00466         std::swap(m_nodeSize, rhs.m_nodeSize);
    00467         std::swap(m_head, rhs.m_head);
    00468         std::swap(m_tail, rhs.m_tail);
    00469         std::swap(m_lazyString, rhs.m_lazyString);
    00470         std::swap(m_lazyLength, rhs.m_lazyLength);
    00471         std::swap(m_lazyStringModifiable, rhs.m_lazyStringModifiable);
    00472 }
    00473
    00474 // ********************************************************
    00475
    00476 void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs &parameters)
    00477 {
    00478         m_node = m_queue.m_head;
    00479         m_position = 0;
    00480         m_offset = 0;
    00481         m_lazyString = m_queue.m_lazyString;
    00482         m_lazyLength = m_queue.m_lazyLength;
    00483 }
    00484
    00485 size_t ByteQueue::Walker::Get(byte &outByte)
    00486 {
    00487         ArraySink sink(&outByte, 1);
    00488         return (size_t)TransferTo(sink, 1);
    00489 }
    00490
    00491 size_t ByteQueue::Walker::Get(byte *outString, size_t getMax)
    00492 {
    00493         ArraySink sink(outString, getMax);
    00494         return (size_t)TransferTo(sink, getMax);
    00495 }
    00496
    00497 size_t ByteQueue::Walker::Peek(byte &outByte) const
    00498 {
    00499         ArraySink sink(&outByte, 1);
    00500         return (size_t)CopyTo(sink, 1);
    00501 }
    00502
    00503 size_t ByteQueue::Walker::Peek(byte *outString, size_t peekMax) const
    00504 {
    00505         ArraySink sink(outString, peekMax);
    00506         return (size_t)CopyTo(sink, peekMax);
    00507 }
    00508
    00509 size_t ByteQueue::Walker::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
    00510 {
    00511         lword bytesLeft = transferBytes;
    00512         size_t blockedBytes = 0;
    00513
    00514         while (m_node)
    00515         {
    00516                 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_node->CurrentSize()-m_offset);
    00517                 blockedBytes = target.ChannelPut2(channel, m_node->buf+m_node->m_head+m_offset, len, 0, blocking);
    00518
    00519                 if (blockedBytes)
    00520                         goto done;
    00521
    00522                 m_position += len;
    00523                 bytesLeft -= len;
    00524
    00525                 if (!bytesLeft)
    00526                 {
    00527                         m_offset += len;
    00528                         goto done;
    00529                 }
    00530
    00531                 m_node = m_node->next;
    00532                 m_offset = 0;
    00533         }
    00534
    00535         if (bytesLeft && m_lazyLength)
    00536         {
    00537                 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
    00538                 blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking);
    00539                 if (blockedBytes)
    00540                         goto done;
    00541
    00542                 m_lazyString += len;
    00543                 m_lazyLength -= len;
    00544                 bytesLeft -= len;
    00545         }
    00546
    00547 done:
    00548         transferBytes -= bytesLeft;
    00549         return blockedBytes;
    00550 }
    00551
    00552 size_t ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
    00553 {
    00554         Walker walker(*this);
    00555         walker.Skip(begin);
    00556         lword transferBytes = end-begin;
    00557         size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
    00558         begin += transferBytes;
    00559         return blockedBytes;
    00560 }
    00561
    00562 NAMESPACE_END
    00563
    00564 #endif