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