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

Archive Download this file

Branches

Tags

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