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 Wed Jul 28 08:07:08 2004 for Crypto++ by doxygen 1.3.7