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

Generated on Tue Jul 8 23:34:22 2003 for Crypto++ by doxygen 1.3.2