server/server/dynbuf.C

#include "global.h"

#include <cstdio>

dynbuf::dynbuf (int initial, int extend)
{
  ext = extend;
  _size = 0;

  first = last = (chunk *)salloc<char> (sizeof (chunk) + initial);
  first->alloc = sizeof (chunk) + initial;
  first->next = 0;

  ptr = first->data;
  end = ptr + initial;
}

dynbuf::~dynbuf ()
{
  _clear ();
}

void
dynbuf::_clear ()
{
  while (first)
    {
      chunk *next = first->next;

      sfree<char> ((char *)first, first->alloc);
      first = next;
    }
}

void
dynbuf::clear ()
{
  _clear ();
  _size = 0;

  first = last = (chunk *)salloc<char> (sizeof (chunk) + ext);
  first->alloc = sizeof (chunk) + ext;
  first->next = 0;

  ptr = first->data;
  end = ptr + ext;
}

void
dynbuf::finish ()
{
  // finalise current chunk
  _size += last->size = ptr - last->data;
}

void
dynbuf::_reserve (int size)
{
  finish ();

  do
    {
      ext += ext >> 1;
      ext = (ext + 15) & ~15;
    }
  while (ext < size);

  chunk *add = (chunk *) salloc<char> (sizeof (chunk) + ext);
  add->alloc = sizeof (chunk) + ext;
  add->next = 0;

  last->next = add;
  last = add;

  ptr = last->data;
  end = ptr + ext;
}

void
dynbuf::linearise (void *data)
{
  last->size = ptr - last->data;

  for (chunk *c = first; c; c = c->next)
    {
      memcpy (data, c->data, c->size);
      data = (void *)(((char *)data) + c->size);
    }
}

char *
dynbuf::linearise ()
{
  if (first->next)
    {
      finish ();

      chunk *add = (chunk *) salloc<char> (sizeof (chunk) + _size);
      add->alloc = sizeof (chunk) + _size;
      add->next = 0;

      linearise ((void *)add->data);
      _clear ();

      first = last = add;
      ptr = last->data + _size;
      end = ptr;
      _size = 0;
    }

  return first->data;
}

dynbuf::operator std::string ()
{
  // could optimise
  return std::string (linearise (), size ());
}

void
dynbuf_text::printf (const char *format, ...)
{
  int len;

  {
    force (128);

    va_list ap;
    va_start (ap, format);
    len = vsnprintf (ptr, end - ptr, format, ap);
    va_end (ap);

    assert (len >= 0); // shield against broken vsnprintf's

    // was enough room available
    if (ptr + len < end)
      {
        alloc (len);
        return;
      }
  }

  // longer, try harder
  va_list ap;
  va_start (ap, format);
  vsnprintf (force (len + 1), len + 1, format, ap);
  va_end (ap);

  alloc (len);
}

// simply return a mask with "bits" bits set
inline uint64
m (int b)
{
  return (uint64 (1) << b) - 1;
}

// convert 9 digits to ascii, using only a single multiplication
// (depending on cpu and compiler).
// will generate a single 0 as output when v=lz=0
inline char *
i2a_9 (char *ptr, uint32 v, bool lz)
{
  // convert to 4.56 fixed-point representation
  // this should be optimal on 64 bit cpus, and rather
  // slow on 32 bit cpus. go figure :)
  const int bits = 7*8; // 7 bits per post-comma digit

  uint64 u = v * ((m (bits) + 100000000) / 100000000); // 10**8

  if (lz)
    {
      // output leading zeros
      // good compilers will compile this into only shifts, masks and adds
      *ptr++ = char (u >> (bits - 0)) + '0'; u = (u & m (bits - 0)) * 5;
      *ptr++ = char (u >> (bits - 1)) + '0'; u = (u & m (bits - 1)) * 5;
      *ptr++ = char (u >> (bits - 2)) + '0'; u = (u & m (bits - 2)) * 5;
      *ptr++ = char (u >> (bits - 3)) + '0'; u = (u & m (bits - 3)) * 5;
      *ptr++ = char (u >> (bits - 4)) + '0'; u = (u & m (bits - 4)) * 5;
      *ptr++ = char (u >> (bits - 5)) + '0'; u = (u & m (bits - 5)) * 5;
      *ptr++ = char (u >> (bits - 6)) + '0'; u = (u & m (bits - 6)) * 5;
      *ptr++ = char (u >> (bits - 7)) + '0'; u = (u & m (bits - 7)) * 5;
      *ptr++ = char (u >> (bits - 8)) + '0';
    }
  else
    {
      // do not output leading zeroes (except if v == 0)
      // good compilers will compile this into completely branchless code
      char digit, nz = 0;

      digit = (u >> (bits - 0)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 0)) * 5;
      digit = (u >> (bits - 1)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 1)) * 5;
      digit = (u >> (bits - 2)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 2)) * 5;
      digit = (u >> (bits - 3)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 3)) * 5;
      digit = (u >> (bits - 4)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 4)) * 5;
      digit = (u >> (bits - 5)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 5)) * 5;
      digit = (u >> (bits - 6)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 6)) * 5;
      digit = (u >> (bits - 7)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 7)) * 5;
      digit = (u >> (bits - 8)); *ptr = digit + '0'; nz |= digit; ptr += 1;
    }

  return ptr;
}

void
dynbuf_text::add (sint32 i)
{
  force (11); // 10 digits + '-'

  *ptr = '-'; ptr += i < 0 ? 1 : 0;
  uint32 u = i < 0 ? -i : i;

  if (expect_true (u < 10)) // we have a lot of single-digit numbers, so optimise
    fadd (char (u + '0'));
  else if (expect_true (u < 1000000000)) // 9 0's
    ptr = i2a_9 (ptr, u, false);
  else
    {
      sint32 div = u / 1000000000;
      uint32 rem = u % 1000000000;

      ptr = i2a_9 (ptr, div, false);
      ptr = i2a_9 (ptr, rem, true);
    }
}

void
dynbuf_text::add (sint64 i)
{
  force (20); // 19 digits + '-'

  *ptr = '-'; ptr += i < 0 ? 1 : 0;
  uint64 u = i < 0 ? -i : i;

  // split the number into a 1-digit part
  // (#19) and two 9 digit parts (9..18 and 0..8)

  // good compilers will only use multiplications here

  if (u < 10) // we have a lot of single-digit numbers, so optimise
    fadd (char (u + '0'));
  else if (expect_true (u < 1000000000)) // 9 0's
    ptr = i2a_9 (ptr, u, false);
  else if (expect_true (u < UINT64_C (1000000000000000000))) // 18 0's
    {
      sint32 div = u / 1000000000;
      uint32 rem = u % 1000000000;

      ptr = i2a_9 (ptr, div, false);
      ptr = i2a_9 (ptr, rem, true);
    }
  else
    {
      // a biggy
      sint32 div = u / UINT64_C (1000000000000000000);
      uint64 rem = u % UINT64_C (1000000000000000000);

      fadd (char (div + '0'));
      u = rem;

      {
        sint32 div = u / 1000000000;
        uint32 rem = u % 1000000000;

        ptr = i2a_9 (ptr, div, true);
        ptr = i2a_9 (ptr, rem, true);
      }
    }
}

#if 0
struct dynbuf_test_class {
  dynbuf_test_class ()
  {
    sint64 s = 0;
    for (int i = 0; i < 10000000; ++i)
      {
        char b1[256], b2[256];

        dynbuf_text db;
        db.add (s);
        db.add (char (0));

        db.linearise (b1);
        sprintf (b2, "%ld", s);

        if (strcmp (b1, b2))
          printf ("<%s,%s>\n", b1, b2);

        if (i < 20)
          s = (sint64) pow (10., i);
        else
          s = (sint64) exp (random () * (43.6682723752766 / RAND_MAX));
      }

    exit (0);
  }
} dynbuf_test;
#endif
Revision:	1.12
Committed:	Sun May 27 22:57:43 2007 UTC (16 years, 11 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-2_1
Changes since 1.11:	+1 -9 lines
Log Message:	do not generate the - sign twice...
#	Content
1	#include "global.h"
2
3	#include <cstdio>
4
5	dynbuf::dynbuf (int initial, int extend)
6	{
7	ext = extend;
8	_size = 0;
9
10	first = last = (chunk *)salloc<char> (sizeof (chunk) + initial);
11	first->alloc = sizeof (chunk) + initial;
12	first->next = 0;
13
14	ptr = first->data;
15	end = ptr + initial;
16	}
17
18	dynbuf::~dynbuf ()
19	{
20	_clear ();
21	}
22
23	void
24	dynbuf::_clear ()
25	{
26	while (first)
27	{
28	chunk *next = first->next;
29
30	sfree<char> ((char *)first, first->alloc);
31	first = next;
32	}
33	}
34
35	void
36	dynbuf::clear ()
37	{
38	_clear ();
39	_size = 0;
40
41	first = last = (chunk *)salloc<char> (sizeof (chunk) + ext);
42	first->alloc = sizeof (chunk) + ext;
43	first->next = 0;
44
45	ptr = first->data;
46	end = ptr + ext;
47	}
48
49	void
50	dynbuf::finish ()
51	{
52	// finalise current chunk
53	_size += last->size = ptr - last->data;
54	}
55
56	void
57	dynbuf::_reserve (int size)
58	{
59	finish ();
60
61	do
62	{
63	ext += ext >> 1;
64	ext = (ext + 15) & ~15;
65	}
66	while (ext < size);
67
68	chunk add = (chunk ) salloc<char> (sizeof (chunk) + ext);
69	add->alloc = sizeof (chunk) + ext;
70	add->next = 0;
71
72	last->next = add;
73	last = add;
74
75	ptr = last->data;
76	end = ptr + ext;
77	}
78
79	void
80	dynbuf::linearise (void *data)
81	{
82	last->size = ptr - last->data;
83
84	for (chunk *c = first; c; c = c->next)
85	{
86	memcpy (data, c->data, c->size);
87	data = (void )(((char )data) + c->size);
88	}
89	}
90
91	char *
92	dynbuf::linearise ()
93	{
94	if (first->next)
95	{
96	finish ();
97
98	chunk add = (chunk ) salloc<char> (sizeof (chunk) + _size);
99	add->alloc = sizeof (chunk) + _size;
100	add->next = 0;
101
102	linearise ((void *)add->data);
103	_clear ();
104
105	first = last = add;
106	ptr = last->data + _size;
107	end = ptr;
108	_size = 0;
109	}
110
111	return first->data;
112	}
113
114	dynbuf::operator std::string ()
115	{
116	// could optimise
117	return std::string (linearise (), size ());
118	}
119
120	void
121	dynbuf_text::printf (const char *format, ...)
122	{
123	int len;
124
125	{
126	force (128);
127
128	va_list ap;
129	va_start (ap, format);
130	len = vsnprintf (ptr, end - ptr, format, ap);
131	va_end (ap);
132
133	assert (len >= 0); // shield against broken vsnprintf's
134
135	// was enough room available
136	if (ptr + len < end)
137	{
138	alloc (len);
139	return;
140	}
141	}
142
143	// longer, try harder
144	va_list ap;
145	va_start (ap, format);
146	vsnprintf (force (len + 1), len + 1, format, ap);
147	va_end (ap);
148
149	alloc (len);
150	}
151
152	// simply return a mask with "bits" bits set
153	inline uint64
154	m (int b)
155	{
156	return (uint64 (1) << b) - 1;
157	}
158
159	// convert 9 digits to ascii, using only a single multiplication
160	// (depending on cpu and compiler).
161	// will generate a single 0 as output when v=lz=0
162	inline char *
163	i2a_9 (char *ptr, uint32 v, bool lz)
164	{
165	// convert to 4.56 fixed-point representation
166	// this should be optimal on 64 bit cpus, and rather
167	// slow on 32 bit cpus. go figure :)
168	const int bits = 7*8; // 7 bits per post-comma digit
169
170	uint64 u = v * ((m (bits) + 100000000) / 100000000); // 10**8
171
172	if (lz)
173	{
174	// output leading zeros
175	// good compilers will compile this into only shifts, masks and adds
176	ptr++ = char (u >> (bits - 0)) + '0'; u = (u & m (bits - 0)) 5;
177	ptr++ = char (u >> (bits - 1)) + '0'; u = (u & m (bits - 1)) 5;
178	ptr++ = char (u >> (bits - 2)) + '0'; u = (u & m (bits - 2)) 5;
179	ptr++ = char (u >> (bits - 3)) + '0'; u = (u & m (bits - 3)) 5;
180	ptr++ = char (u >> (bits - 4)) + '0'; u = (u & m (bits - 4)) 5;
181	ptr++ = char (u >> (bits - 5)) + '0'; u = (u & m (bits - 5)) 5;
182	ptr++ = char (u >> (bits - 6)) + '0'; u = (u & m (bits - 6)) 5;
183	ptr++ = char (u >> (bits - 7)) + '0'; u = (u & m (bits - 7)) 5;
184	*ptr++ = char (u >> (bits - 8)) + '0';
185	}
186	else
187	{
188	// do not output leading zeroes (except if v == 0)
189	// good compilers will compile this into completely branchless code
190	char digit, nz = 0;
191
192	digit = (u >> (bits - 0)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 0)) 5;
193	digit = (u >> (bits - 1)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 1)) 5;
194	digit = (u >> (bits - 2)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 2)) 5;
195	digit = (u >> (bits - 3)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 3)) 5;
196	digit = (u >> (bits - 4)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 4)) 5;
197	digit = (u >> (bits - 5)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 5)) 5;
198	digit = (u >> (bits - 6)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 6)) 5;
199	digit = (u >> (bits - 7)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 7)) 5;
200	digit = (u >> (bits - 8)); *ptr = digit + '0'; nz \|= digit; ptr += 1;
201	}
202
203	return ptr;
204	}
205
206	void
207	dynbuf_text::add (sint32 i)
208	{
209	force (11); // 10 digits + '-'
210
211	*ptr = '-'; ptr += i < 0 ? 1 : 0;
212	uint32 u = i < 0 ? -i : i;
213
214	if (expect_true (u < 10)) // we have a lot of single-digit numbers, so optimise
215	fadd (char (u + '0'));
216	else if (expect_true (u < 1000000000)) // 9 0's
217	ptr = i2a_9 (ptr, u, false);
218	else
219	{
220	sint32 div = u / 1000000000;
221	uint32 rem = u % 1000000000;
222
223	ptr = i2a_9 (ptr, div, false);
224	ptr = i2a_9 (ptr, rem, true);
225	}
226	}
227
228	void
229	dynbuf_text::add (sint64 i)
230	{
231	force (20); // 19 digits + '-'
232
233	*ptr = '-'; ptr += i < 0 ? 1 : 0;
234	uint64 u = i < 0 ? -i : i;
235
236	// split the number into a 1-digit part
237	// (#19) and two 9 digit parts (9..18 and 0..8)
238
239	// good compilers will only use multiplications here
240
241	if (u < 10) // we have a lot of single-digit numbers, so optimise
242	fadd (char (u + '0'));
243	else if (expect_true (u < 1000000000)) // 9 0's
244	ptr = i2a_9 (ptr, u, false);
245	else if (expect_true (u < UINT64_C (1000000000000000000))) // 18 0's
246	{
247	sint32 div = u / 1000000000;
248	uint32 rem = u % 1000000000;
249
250	ptr = i2a_9 (ptr, div, false);
251	ptr = i2a_9 (ptr, rem, true);
252	}
253	else
254	{
255	// a biggy
256	sint32 div = u / UINT64_C (1000000000000000000);
257	uint64 rem = u % UINT64_C (1000000000000000000);
258
259	fadd (char (div + '0'));
260	u = rem;
261
262	{
263	sint32 div = u / 1000000000;
264	uint32 rem = u % 1000000000;
265
266	ptr = i2a_9 (ptr, div, true);
267	ptr = i2a_9 (ptr, rem, true);
268	}
269	}
270	}
271
272	#if 0
273	struct dynbuf_test_class {
274	dynbuf_test_class ()
275	{
276	sint64 s = 0;
277	for (int i = 0; i < 10000000; ++i)
278	{
279	char b1[256], b2[256];
280
281	dynbuf_text db;
282	db.add (s);
283	db.add (char (0));
284
285	db.linearise (b1);
286	sprintf (b2, "%ld", s);
287
288	if (strcmp (b1, b2))
289	printf ("<%s,%s>\n", b1, b2);
290
291	if (i < 20)
292	s = (sint64) pow (10., i);
293	else
294	s = (sint64) exp (random () * (43.6682723752766 / RAND_MAX));
295	}
296
297	exit (0);
298	}
299	} dynbuf_test;
300	#endif