File: string_queue.hh

package info (click to toggle)
monotone 0.48-3
  • links: PTS
  • area: main
  • in suites: squeeze
  • size: 20,096 kB
  • ctags: 8,077
  • sloc: cpp: 81,000; sh: 6,402; perl: 1,241; lisp: 1,045; makefile: 655; python: 566; sql: 112; ansic: 52
file content (262 lines) | stat: -rw-r--r-- 6,464 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
// Copyright (C) 2005 Eric Anderson <anderse@hpl.hp.com>
//
// This program is made available under the GNU GPL version 2.0 or
// greater. See the accompanying file COPYING for details.
//
// This program is distributed WITHOUT ANY WARRANTY; without even the
// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE.

#ifndef __STRING_QUEUE_HH__
#define __STRING_QUEUE_HH__

#include <cstring>
#include <cstdlib>

#include "sanity.hh"

// a class for handling inserting at the back of a string and removing
// from the front efficiently while still preserving the data as
// contiguous; could also do the reverse, but that wasn't needed, and
// so hasn't been implemented.

class string_queue
{
public:
  string_queue (size_t default_size = 8192)
    {
      buf = new char[default_size];
      front = back = buf;
      end = buf + default_size;
    }

  ~string_queue ()
    {
      delete[]buf;
    }

  void append (const std::string & v)
    {
      selfcheck ();
      reserve_additional (v.size ());
      simple_append (v);
      if (do_selfcheck)
        {
          selfcheck_str.append (v);
          selfcheck ();
        }
    };

  void append (const char *str, size_t bytes)
    {
      selfcheck ();
      reserve_additional (bytes);
      simple_append (str, bytes);
      if (do_selfcheck)
        {
          selfcheck_str.append (std::string (str, bytes));
          selfcheck ();
        }
    };

  void append (const char v)
    {
      selfcheck ();
      if (available_size () >= 1)
        {
          *back = v;
          ++back;
        }
      else
        {
          std::string tmp;
          tmp += v;
          I (tmp.size () == 1 && tmp[0] == v);
          append (tmp);
        }
      if (do_selfcheck)
        {
          selfcheck_str += v;
          selfcheck ();
        }
    }

  string_queue & operator+= (const char v)
    {
      append (v);
      return *this;
    }

  string_queue & operator+= (const std::string & v)
    {
      append (v);
      return *this;
    }

  char &operator[] (size_t pos)
    {
      I (pos < used_size ());
      return front[pos];
    }

  const char &operator[] (size_t pos) const
    {
      I (pos < used_size ());
      return front[pos];
    }

  void pop_front (size_t amount)
    {
      selfcheck ();
      I (used_size () >= amount);
      front += amount;
      if (front == back)
        {
          front = back = buf;
        }
      if (used_size () * 3 < buffer_size () && buffer_size () > (1024 * 1024))
        {
          // don't bother shrinking unless it will help a lot, and
          // we're using enough memory to care.
          size_t a_new_size = (size_t) (used_size () * 1.1);    // leave some headroom
          resize_buffer (std::max ((size_t) 8192, a_new_size));
        }
      if (do_selfcheck)
        {
          selfcheck_str.erase (0, amount);
          selfcheck ();
        }
    }

  std::string substr (size_t pos, size_t size) const
    {
      I (size <= max_string_queue_incr);
      I (pos <= max_string_queue_size);
      I (used_size () >= (pos + size));
      return std::string (front + pos, size);
    }

  const char *front_pointer (size_t strsize) const
    {
      I (strsize <= max_string_queue_size);
      I (used_size () >= strsize);
      return front;
    }

  size_t size () const
    {
      return used_size ();
    }
  size_t used_size () const
    {
      return (size_t) (back - front);
    }
  size_t buffer_size () const
    {
      return (size_t) (end - buf);
    }
  size_t available_size () const
    {
      return (size_t) (end - back);
    }
  bool empty () const
    {
      return front == back;
    }

  void selfcheck ()
    {
      if (do_selfcheck)
        {
          I (buf <= front && front <= back && back <= end);
          I (selfcheck_str.size () == used_size ()
             && std::memcmp (selfcheck_str.data (), front, used_size ()) == 0);
        }
    }

  void reserve_total (size_t amount)
    {
      if ((size_t) (end - front) >= amount)
        {
          return;
        }
      reserve_additional (amount - available_size ());
    }

  void reserve_additional (size_t amount)
    {
      I(amount <= max_string_queue_incr);
      if (available_size () >= amount)
        return;
      if (1.25 * (used_size () + amount) < buffer_size ())
        {
          // 1.25* to make sure that we don't do a lot of remove 1 byte from
          // beginning, move entire array, append a byte, etc.
          size_t save_used_size = used_size ();
          std::memmove (buf, front, save_used_size);
          front = buf;
          back = front + save_used_size;
          selfcheck ();
          return;
        }
      // going to expand the buffer, increase by at least 1.25x so that
      // we don't have a pathological case of reserving a little extra
      // a whole bunch of times
      size_t new_buffer_size =
        std::max ((size_t) (1.25 * buffer_size ()),
                  used_size () + amount);
      resize_buffer (new_buffer_size);
      selfcheck ();
    }

protected:
  void simple_append (const std::string & v)
    {
      I ((size_t) (end - back) >= v.size ());
      I (v.size() <= max_string_queue_incr);
      std::memcpy (back, v.data (), v.size ());
      back += v.size ();
    }

  void simple_append (const char *str, size_t bytes)
    {
      I ((size_t) (end - back) >= bytes);
      I (bytes <= max_string_queue_incr);
      std::memcpy (back, str, bytes);
      back += bytes;
    }

  void resize_buffer (size_t new_buffer_size)
    {
      I (new_buffer_size <= max_string_queue_size);
      size_t save_used_size = used_size ();
      char *newbuf = new char[new_buffer_size];
      std::memcpy (newbuf, front, save_used_size);
      delete[]buf;
      buf = front = newbuf;
      back = front + save_used_size;
      end = buf + new_buffer_size;
    }

private:
  static const bool do_selfcheck = false;
  // used to avoid integer wraparound, 500 megs should be enough:
  static const size_t max_string_queue_size = 500 * 1024 * 1024;
  static const size_t max_string_queue_incr = 500 * 1024 * 1024;
  string_queue (string_queue & from)
    {
      std::abort ();
    }
  char *buf, *front, *back, *end;
  std::string selfcheck_str;
};

#endif

// Local Variables:
// mode: C++
// fill-column: 76
// c-file-style: "gnu"
// indent-tabs-mode: nil
// End:
// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s: