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

Archive Download this file

Branches

Tags

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