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 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(unsigned int maxSize) 00019 : buf(maxSize) 00020 { 00021 m_head = m_tail = 0; 00022 next = 0; 00023 } 00024 00025 inline unsigned int MaxSize() const {return buf.size();} 00026 00027 inline unsigned int 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 unsigned int Put(const byte *begin, unsigned int length) 00043 { 00044 unsigned int 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 unsigned int 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 unsigned int Peek(byte *target, unsigned int copyMax) const 00061 { 00062 unsigned int len = STDMIN(copyMax, m_tail-m_head); 00063 memcpy(target, buf+m_head, len); 00064 return len; 00065 } 00066 00067 inline unsigned int CopyTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const 00068 { 00069 unsigned int len = m_tail-m_head; 00070 target.ChannelPut(channel, buf+m_head, len); 00071 return len; 00072 } 00073 00074 inline unsigned int CopyTo(BufferedTransformation &target, unsigned int copyMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const 00075 { 00076 unsigned int len = STDMIN(copyMax, m_tail-m_head); 00077 target.ChannelPut(channel, buf+m_head, len); 00078 return len; 00079 } 00080 00081 inline unsigned int Get(byte &outByte) 00082 { 00083 unsigned int len = Peek(outByte); 00084 m_head += len; 00085 return len; 00086 } 00087 00088 inline unsigned int Get(byte *outString, unsigned int getMax) 00089 { 00090 unsigned int len = Peek(outString, getMax); 00091 m_head += len; 00092 return len; 00093 } 00094 00095 inline unsigned int TransferTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL) 00096 { 00097 unsigned int 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 unsigned int TransferTo(BufferedTransformation &target, unsigned int transferMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL) 00104 { 00105 unsigned int len = STDMIN(transferMax, m_tail-m_head); 00106 target.ChannelPutModifiable(channel, buf+m_head, len); 00107 m_head += len; 00108 return len; 00109 } 00110 00111 inline unsigned int Skip(unsigned int skipMax) 00112 { 00113 unsigned int len = STDMIN(skipMax, m_tail-m_head); 00114 m_head += len; 00115 return len; 00116 } 00117 00118 inline byte operator[](unsigned int i) const 00119 { 00120 return buf[m_head+i]; 00121 } 00122 00123 ByteQueueNode *next; 00124 00125 SecByteBlock buf; 00126 unsigned int m_head, m_tail; 00127 }; 00128 00129 // ******************************************************** 00130 00131 ByteQueue::ByteQueue(unsigned int nodeSize) 00132 : m_lazyLength(0) 00133 { 00134 SetNodeSize(nodeSize); 00135 m_head = m_tail = new ByteQueueNode(m_nodeSize); 00136 } 00137 00138 void ByteQueue::SetNodeSize(unsigned int 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 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 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 unsigned int ByteQueue::Put2(const byte *inString, unsigned int length, int messageEnd, bool blocking) 00217 { 00218 if (m_lazyLength > 0) 00219 FinalizeLazyPut(); 00220 00221 unsigned int 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, unsigned int 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, unsigned int 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(unsigned int 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 unsigned int len = m_lazyLength; 00287 m_lazyLength = 0; 00288 if (len) 00289 Put(m_lazyString, len); 00290 } 00291 00292 unsigned int 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 unsigned int ByteQueue::Get(byte *outString, unsigned int getMax) 00311 { 00312 ArraySink sink(outString, getMax); 00313 return TransferTo(sink, getMax); 00314 } 00315 00316 unsigned int 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 unsigned int ByteQueue::Peek(byte *outString, unsigned int peekMax) const 00330 { 00331 ArraySink sink(outString, peekMax); 00332 return CopyTo(sink, peekMax); 00333 } 00334 00335 unsigned int ByteQueue::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking) 00336 { 00337 if (blocking) 00338 { 00339 unsigned long bytesLeft = transferBytes; 00340 for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->next) 00341 bytesLeft -= current->TransferTo(target, bytesLeft, channel); 00342 CleanupUsedNodes(); 00343 00344 unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)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 unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); 00362 Skip(transferBytes); 00363 return blockedBytes; 00364 } 00365 } 00366 00367 unsigned int ByteQueue::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const 00368 { 00369 Walker walker(*this); 00370 walker.Skip(begin); 00371 unsigned long transferBytes = end-begin; 00372 unsigned int 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, unsigned int length) 00383 { 00384 unsigned int 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(unsigned int &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(unsigned int &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 unsigned long 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[](unsigned long i) const 00450 { 00451 for (ByteQueueNode *current=m_head; current; current=current->next) 00452 { 00453 if (i < current->CurrentSize()) 00454 return (*current)[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 unsigned int ByteQueue::Walker::Get(byte &outByte) 00486 { 00487 ArraySink sink(&outByte, 1); 00488 return TransferTo(sink, 1); 00489 } 00490 00491 unsigned int ByteQueue::Walker::Get(byte *outString, unsigned int getMax) 00492 { 00493 ArraySink sink(outString, getMax); 00494 return TransferTo(sink, getMax); 00495 } 00496 00497 unsigned int ByteQueue::Walker::Peek(byte &outByte) const 00498 { 00499 ArraySink sink(&outByte, 1); 00500 return CopyTo(sink, 1); 00501 } 00502 00503 unsigned int ByteQueue::Walker::Peek(byte *outString, unsigned int peekMax) const 00504 { 00505 ArraySink sink(outString, peekMax); 00506 return CopyTo(sink, peekMax); 00507 } 00508 00509 unsigned int ByteQueue::Walker::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking) 00510 { 00511 unsigned long bytesLeft = transferBytes; 00512 unsigned int blockedBytes = 0; 00513 00514 while (m_node) 00515 { 00516 unsigned int len = STDMIN(bytesLeft, (unsigned long)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 unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)m_lazyLength); 00538 unsigned int 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 unsigned int ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const 00553 { 00554 Walker walker(*this); 00555 walker.Skip(begin); 00556 unsigned long transferBytes = end-begin; 00557 unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); 00558 begin += transferBytes; 00559 return blockedBytes; 00560 } 00561 00562 NAMESPACE_END 00563 00564 #endif

Generated on Fri Aug 27 15:51:10 2004 for Crypto++ by doxygen 1.3.8