monotone

monotone Mtn Source Tree

Root/string_queue.hh

1#ifndef __STRING_QUEUE_HH__
2#define __STRING_QUEUE_HH__
3
4// copyright (C) 2005 Eric Anderson <anderse@hpl.hp.com>
5// all rights reserved.
6// licensed to the public under the terms of the GNU GPL (>= 2)
7// see the file COPYING for details
8
9#include <string>
10#include <cstring>
11#include <cstdlib>
12
13#include "sanity.hh"
14
15// a class for handling inserting at the back of a string and removing
16// from the front efficiently while still preserving the data as
17// contiguous; could also do the reverse, but that wasn't needed, and
18// so hasn't been implemented.
19
20class string_queue
21{
22public:
23 string_queue (size_t default_size = 8192)
24 {
25 buf = new char[default_size];
26 front = back = buf;
27 end = buf + default_size;
28 }
29
30 ~string_queue ()
31 {
32 delete[]buf;
33 }
34
35 void append (const std::string & v)
36 {
37 selfcheck ();
38 reserve_additional (v.size ());
39 simple_append (v);
40 if (do_selfcheck)
41 {
42 selfcheck_str.append (v);
43 selfcheck ();
44 }
45 };
46
47 void append (const char *str, size_t bytes)
48 {
49 selfcheck ();
50 reserve_additional (bytes);
51 simple_append (str, bytes);
52 if (do_selfcheck)
53 {
54 selfcheck_str.append (std::string (str, bytes));
55 selfcheck ();
56 }
57 };
58
59 void append (const char v)
60 {
61 selfcheck ();
62 if (available_size () >= 1)
63 {
64 *back = v;
65 ++back;
66 }
67 else
68 {
69 std::string tmp;
70 tmp += v;
71 I (tmp.size () == 1 && tmp[0] == v);
72 append (tmp);
73 }
74 if (do_selfcheck)
75 {
76 selfcheck_str += v;
77 selfcheck ();
78 }
79 }
80
81 string_queue & operator+= (const char v)
82 {
83 append (v);
84 return *this;
85 }
86
87 string_queue & operator+= (const std::string & v)
88 {
89 append (v);
90 return *this;
91 }
92
93 char &operator[] (size_t pos)
94 {
95 I (pos < used_size ());
96 return front[pos];
97 }
98
99 const char &operator[] (size_t pos) const
100 {
101 I (pos < used_size ());
102 return front[pos];
103 }
104
105 void pop_front (size_t amount)
106 {
107 selfcheck ();
108 I (used_size () >= amount);
109 front += amount;
110 if (front == back)
111 {
112 front = back = buf;
113 }
114 if (used_size () * 3 < buffer_size () && buffer_size () > (1024 * 1024))
115 {
116 // don't bother shrinking unless it will help a lot, and
117 // we're using enough memory to care.
118 size_t a_new_size = (size_t) (used_size () * 1.1);// leave some headroom
119 resize_buffer (std::max ((size_t) 8192, a_new_size));
120 }
121 if (do_selfcheck)
122 {
123 selfcheck_str.erase (0, amount);
124 selfcheck ();
125 }
126 }
127
128 std::string substr (size_t pos, size_t size) const
129 {
130 I (size <= max_string_queue_incr);
131 I (pos <= max_string_queue_size);
132 I (used_size () >= (pos + size));
133 return std::string (front + pos, size);
134 }
135
136 const char *front_pointer (size_t strsize) const
137 {
138 I (strsize <= max_string_queue_size);
139 I (used_size () >= strsize);
140 return front;
141 }
142
143 size_t size () const
144 {
145 return used_size ();
146 }
147 size_t used_size () const
148 {
149 return (size_t) (back - front);
150 }
151 size_t buffer_size () const
152 {
153 return (size_t) (end - buf);
154 }
155 size_t available_size () const
156 {
157 return (size_t) (end - back);
158 }
159 bool empty () const
160 {
161 return front == back;
162 }
163
164 void selfcheck ()
165 {
166 if (do_selfcheck)
167 {
168 I (buf <= front && front <= back && back <= end);
169 I (selfcheck_str.size () == used_size ()
170 && std::memcmp (selfcheck_str.data (), front, used_size ()) == 0);
171 }
172 }
173
174 void reserve_total (size_t amount)
175 {
176 if ((size_t) (end - front) >= amount)
177 {
178 return;
179 }
180 reserve_additional (amount - available_size ());
181 }
182
183 void reserve_additional (size_t amount)
184 {
185 I(amount <= max_string_queue_incr);
186 if (available_size () >= amount)
187 return;
188 if (1.25 * (used_size () + amount) < buffer_size ())
189 {
190 // 1.25* to make sure that we don't do a lot of remove 1 byte from
191 // beginning, move entire array, append a byte, etc.
192 size_t save_used_size = used_size ();
193 std::memmove (buf, front, save_used_size);
194 front = buf;
195 back = front + save_used_size;
196 selfcheck ();
197 return;
198 }
199 // going to expand the buffer, increase by at least 1.25x so that
200 // we don't have a pathological case of reserving a little extra
201 // a whole bunch of times
202 size_t new_buffer_size =
203 std::max ((size_t) (1.25 * buffer_size ()),
204 used_size () + amount);
205 resize_buffer (new_buffer_size);
206 selfcheck ();
207 }
208
209protected:
210 void simple_append (const std::string & v)
211 {
212 I ((size_t) (end - back) >= v.size ());
213 I (v.size() <= max_string_queue_incr);
214 std::memcpy (back, v.data (), v.size ());
215 back += v.size ();
216 }
217
218 void simple_append (const char *str, size_t bytes)
219 {
220 I ((size_t) (end - back) >= bytes);
221 I (bytes <= max_string_queue_incr);
222 std::memcpy (back, str, bytes);
223 back += bytes;
224 }
225
226 void resize_buffer (size_t new_buffer_size)
227 {
228 I (new_buffer_size <= max_string_queue_size);
229 size_t save_used_size = used_size ();
230 char *newbuf = new char[new_buffer_size];
231 std::memcpy (newbuf, front, save_used_size);
232 delete[]buf;
233 buf = front = newbuf;
234 back = front + save_used_size;
235 end = buf + new_buffer_size;
236 }
237
238private:
239 static const bool do_selfcheck = false;
240 // used to avoid integer wraparound, 500 megs should be enough:
241 static const size_t max_string_queue_size = 500 * 1024 * 1024;
242 static const size_t max_string_queue_incr = 500 * 1024 * 1024;
243 string_queue (string_queue & from)
244 {
245 std::abort ();
246 }
247 char *buf, *front, *back, *end;
248 std::string selfcheck_str;
249};
250
251#endif

Archive Download this file

Branches

Tags

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