monotone

monotone Mtn Source Tree

Root/cryptopp/queue.cpp

1// queue.cpp - written and placed in the public domain by Wei Dai
2
3#include "pch.h"
4#include "queue.h"
5#include "filters.h"
6
7NAMESPACE_BEGIN(CryptoPP)
8
9// this class for use by ByteQueue only
10class ByteQueueNode
11{
12public:
13ByteQueueNode(unsigned int maxSize)
14: buf(maxSize)
15{
16m_head = m_tail = 0;
17next = 0;
18}
19
20inline unsigned int MaxSize() const {return buf.size();}
21
22inline unsigned int CurrentSize() const
23{
24return m_tail-m_head;
25}
26
27inline bool UsedUp() const
28{
29return (m_head==MaxSize());
30}
31
32inline void Clear()
33{
34m_head = m_tail = 0;
35}
36
37/*inline unsigned int Put(byte inByte)
38{
39if (MaxSize()==m_tail)
40return 0;
41
42buf[m_tail++]=inByte;
43return 1;
44}
45*/
46inline unsigned int Put(const byte *begin, unsigned int length)
47{
48unsigned int l = STDMIN(length, MaxSize()-m_tail);
49memcpy(buf+m_tail, begin, l);
50m_tail += l;
51return l;
52}
53
54inline unsigned int Peek(byte &outByte) const
55{
56if (m_tail==m_head)
57return 0;
58
59outByte=buf[m_head];
60return 1;
61}
62
63inline unsigned int Peek(byte *target, unsigned int copyMax) const
64{
65unsigned int len = STDMIN(copyMax, m_tail-m_head);
66memcpy(target, buf+m_head, len);
67return len;
68}
69
70inline unsigned int CopyTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const
71{
72unsigned int len = m_tail-m_head;
73target.ChannelPut(channel, buf+m_head, len);
74return len;
75}
76
77inline unsigned int CopyTo(BufferedTransformation &target, unsigned int copyMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const
78{
79unsigned int len = STDMIN(copyMax, m_tail-m_head);
80target.ChannelPut(channel, buf+m_head, len);
81return len;
82}
83
84inline unsigned int Get(byte &outByte)
85{
86unsigned int len = Peek(outByte);
87m_head += len;
88return len;
89}
90
91inline unsigned int Get(byte *outString, unsigned int getMax)
92{
93unsigned int len = Peek(outString, getMax);
94m_head += len;
95return len;
96}
97
98inline unsigned int TransferTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL)
99{
100unsigned int len = m_tail-m_head;
101target.ChannelPutModifiable(channel, buf+m_head, len);
102m_head = m_tail;
103return len;
104}
105
106inline unsigned int TransferTo(BufferedTransformation &target, unsigned int transferMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL)
107{
108unsigned int len = STDMIN(transferMax, m_tail-m_head);
109target.ChannelPutModifiable(channel, buf+m_head, len);
110m_head += len;
111return len;
112}
113
114inline unsigned int Skip(unsigned int skipMax)
115{
116unsigned int len = STDMIN(skipMax, m_tail-m_head);
117m_head += len;
118return len;
119}
120
121inline byte operator[](unsigned int i) const
122{
123return buf[m_head+i];
124}
125
126ByteQueueNode *next;
127
128SecByteBlock buf;
129unsigned int m_head, m_tail;
130};
131
132// ********************************************************
133
134ByteQueue::ByteQueue(unsigned int m_nodeSize)
135: m_nodeSize(m_nodeSize), m_lazyLength(0)
136{
137m_head = m_tail = new ByteQueueNode(m_nodeSize);
138}
139
140ByteQueue::ByteQueue(const ByteQueue &copy)
141{
142CopyFrom(copy);
143}
144
145void ByteQueue::CopyFrom(const ByteQueue &copy)
146{
147m_lazyLength = 0;
148m_nodeSize = copy.m_nodeSize;
149m_head = m_tail = new ByteQueueNode(*copy.m_head);
150
151for (ByteQueueNode *current=copy.m_head->next; current; current=current->next)
152{
153m_tail->next = new ByteQueueNode(*current);
154m_tail = m_tail->next;
155}
156
157m_tail->next = NULL;
158
159Put(copy.m_lazyString, copy.m_lazyLength);
160}
161
162ByteQueue::~ByteQueue()
163{
164Destroy();
165}
166
167void ByteQueue::Destroy()
168{
169ByteQueueNode *next;
170
171for (ByteQueueNode *current=m_head; current; current=next)
172{
173next=current->next;
174delete current;
175}
176}
177
178void ByteQueue::IsolatedInitialize(const NameValuePairs &parameters)
179{
180m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256);
181Clear();
182}
183
184unsigned long ByteQueue::CurrentSize() const
185{
186unsigned long size=0;
187
188for (ByteQueueNode *current=m_head; current; current=current->next)
189size += current->CurrentSize();
190
191return size + m_lazyLength;
192}
193
194bool ByteQueue::IsEmpty() const
195{
196return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0;
197}
198
199void ByteQueue::Clear()
200{
201Destroy();
202m_head = m_tail = new ByteQueueNode(m_nodeSize);
203m_lazyLength = 0;
204}
205
206unsigned int ByteQueue::Put2(const byte *inString, unsigned int length, int messageEnd, bool blocking)
207{
208if (m_lazyLength > 0)
209FinalizeLazyPut();
210
211unsigned int len;
212while ((len=m_tail->Put(inString, length)) < length)
213{
214m_tail->next = new ByteQueueNode(m_nodeSize);
215m_tail = m_tail->next;
216inString += len;
217length -= len;
218}
219
220return 0;
221}
222
223void ByteQueue::CleanupUsedNodes()
224{
225while (m_head != m_tail && m_head->UsedUp())
226{
227ByteQueueNode *temp=m_head;
228m_head=m_head->next;
229delete temp;
230}
231
232if (m_head->CurrentSize() == 0)
233m_head->Clear();
234}
235
236void ByteQueue::LazyPut(const byte *inString, unsigned int size)
237{
238if (m_lazyLength > 0)
239FinalizeLazyPut();
240m_lazyString = inString;
241m_lazyLength = size;
242}
243
244void ByteQueue::UndoLazyPut(unsigned int size)
245{
246if (m_lazyLength < size)
247throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large");
248
249m_lazyLength -= size;
250}
251
252void ByteQueue::FinalizeLazyPut()
253{
254unsigned int len = m_lazyLength;
255m_lazyLength = 0;
256if (len)
257Put(m_lazyString, len);
258}
259
260unsigned int ByteQueue::Get(byte &outByte)
261{
262if (m_head->Get(outByte))
263{
264if (m_head->UsedUp())
265CleanupUsedNodes();
266return 1;
267}
268else if (m_lazyLength > 0)
269{
270outByte = *m_lazyString++;
271m_lazyLength--;
272return 1;
273}
274else
275return 0;
276}
277
278unsigned int ByteQueue::Get(byte *outString, unsigned int getMax)
279{
280ArraySink sink(outString, getMax);
281return TransferTo(sink, getMax);
282}
283
284unsigned int ByteQueue::Peek(byte &outByte) const
285{
286if (m_head->Peek(outByte))
287return 1;
288else if (m_lazyLength > 0)
289{
290outByte = *m_lazyString;
291return 1;
292}
293else
294return 0;
295}
296
297unsigned int ByteQueue::Peek(byte *outString, unsigned int peekMax) const
298{
299ArraySink sink(outString, peekMax);
300return CopyTo(sink, peekMax);
301}
302
303unsigned int ByteQueue::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking)
304{
305if (blocking)
306{
307unsigned long bytesLeft = transferBytes;
308for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->next)
309bytesLeft -= current->TransferTo(target, bytesLeft, channel);
310CleanupUsedNodes();
311
312unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)m_lazyLength);
313if (len)
314{
315target.ChannelPut(channel, m_lazyString, len);
316m_lazyString += len;
317m_lazyLength -= len;
318bytesLeft -= len;
319}
320transferBytes -= bytesLeft;
321return 0;
322}
323else
324{
325Walker walker(*this);
326unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
327Skip(transferBytes);
328return blockedBytes;
329}
330}
331
332unsigned int ByteQueue::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const
333{
334Walker walker(*this);
335walker.Skip(begin);
336unsigned long transferBytes = end-begin;
337unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
338begin += transferBytes;
339return blockedBytes;
340}
341
342void ByteQueue::Unget(byte inByte)
343{
344Unget(&inByte, 1);
345}
346
347void ByteQueue::Unget(const byte *inString, unsigned int length)
348{
349// TODO: make this more efficient
350ByteQueueNode *newHead = new ByteQueueNode(length);
351newHead->next = m_head;
352m_head = newHead;
353m_head->Put(inString, length);
354}
355
356const byte * ByteQueue::Spy(unsigned int &contiguousSize) const
357{
358contiguousSize = m_head->m_tail - m_head->m_head;
359if (contiguousSize == 0 && m_lazyLength > 0)
360{
361contiguousSize = m_lazyLength;
362return m_lazyString;
363}
364else
365return m_head->buf + m_head->m_head;
366}
367
368byte * ByteQueue::CreatePutSpace(unsigned int &size)
369{
370if (m_lazyLength > 0)
371FinalizeLazyPut();
372
373if (m_tail->m_tail == m_tail->MaxSize())
374{
375m_tail->next = new ByteQueueNode(size < m_nodeSize ? m_nodeSize : STDMAX(m_nodeSize, 1024U));
376m_tail = m_tail->next;
377}
378
379size = m_tail->MaxSize() - m_tail->m_tail;
380return m_tail->buf + m_tail->m_tail;
381}
382
383ByteQueue & ByteQueue::operator=(const ByteQueue &rhs)
384{
385Destroy();
386CopyFrom(rhs);
387return *this;
388}
389
390bool ByteQueue::operator==(const ByteQueue &rhs) const
391{
392const unsigned long currentSize = CurrentSize();
393
394if (currentSize != rhs.CurrentSize())
395return false;
396
397Walker walker1(*this), walker2(rhs);
398byte b1, b2;
399
400while (walker1.Get(b1) && walker2.Get(b2))
401if (b1 != b2)
402return false;
403
404return true;
405}
406
407byte ByteQueue::operator[](unsigned long i) const
408{
409for (ByteQueueNode *current=m_head; current; current=current->next)
410{
411if (i < current->CurrentSize())
412return (*current)[i];
413
414i -= current->CurrentSize();
415}
416
417assert(i < m_lazyLength);
418return m_lazyString[i];
419}
420
421void ByteQueue::swap(ByteQueue &rhs)
422{
423std::swap(m_nodeSize, rhs.m_nodeSize);
424std::swap(m_head, rhs.m_head);
425std::swap(m_tail, rhs.m_tail);
426std::swap(m_lazyString, rhs.m_lazyString);
427std::swap(m_lazyLength, rhs.m_lazyLength);
428}
429
430// ********************************************************
431
432void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs &parameters)
433{
434m_node = m_queue.m_head;
435m_position = 0;
436m_offset = 0;
437m_lazyString = m_queue.m_lazyString;
438m_lazyLength = m_queue.m_lazyLength;
439}
440
441unsigned int ByteQueue::Walker::Get(byte &outByte)
442{
443ArraySink sink(&outByte, 1);
444return TransferTo(sink, 1);
445}
446
447unsigned int ByteQueue::Walker::Get(byte *outString, unsigned int getMax)
448{
449ArraySink sink(outString, getMax);
450return TransferTo(sink, getMax);
451}
452
453unsigned int ByteQueue::Walker::Peek(byte &outByte) const
454{
455ArraySink sink(&outByte, 1);
456return CopyTo(sink, 1);
457}
458
459unsigned int ByteQueue::Walker::Peek(byte *outString, unsigned int peekMax) const
460{
461ArraySink sink(outString, peekMax);
462return CopyTo(sink, peekMax);
463}
464
465unsigned int ByteQueue::Walker::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking)
466{
467unsigned long bytesLeft = transferBytes;
468unsigned int blockedBytes = 0;
469
470while (m_node)
471{
472unsigned int len = STDMIN(bytesLeft, (unsigned long)m_node->CurrentSize()-m_offset);
473blockedBytes = target.ChannelPut2(channel, m_node->buf+m_node->m_head+m_offset, len, 0, blocking);
474
475if (blockedBytes)
476goto done;
477
478m_position += len;
479bytesLeft -= len;
480
481if (!bytesLeft)
482{
483m_offset += len;
484goto done;
485}
486
487m_node = m_node->next;
488m_offset = 0;
489}
490
491if (bytesLeft && m_lazyLength)
492{
493unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)m_lazyLength);
494unsigned int blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking);
495if (blockedBytes)
496goto done;
497
498m_lazyString += len;
499m_lazyLength -= len;
500bytesLeft -= len;
501}
502
503done:
504transferBytes -= bytesLeft;
505return blockedBytes;
506}
507
508unsigned int ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const
509{
510Walker walker(*this);
511walker.Skip(begin);
512unsigned long transferBytes = end-begin;
513unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
514begin += transferBytes;
515return blockedBytes;
516}
517
518NAMESPACE_END

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status