Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

queue.cpp

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

Generated on Sun Mar 14 20:44:28 2004 for Crypto++ by doxygen 1.3.6-20040222