Dillo v3.1.1-14-g8f67d6e0
Loading...
Searching...
No Matches
misc.hh
Go to the documentation of this file.
1#ifndef __LOUT_MISC_HH__
2#define __LOUT_MISC_HH__
3
4#include <stdio.h>
5#include <stdarg.h>
6#include <stdlib.h>
7#include <string.h>
8#include <assert.h>
9
10namespace lout {
11
17namespace misc {
18
19template <class T> inline T min (T a, T b) { return a < b ? a : b; }
20template <class T> inline T max (T a, T b) { return a > b ? a : b; }
21
22template <class T> inline T min (T a, T b, T c)
23{
24 return (min (a, min (b, c)));
25}
26template <class T> inline T max (T a, T b, T c)
27{
28 return (max (a, max (b, c)));
29}
30
31extern const char *prgName;
32
33void init (int argc, char *argv[]);
34
35inline void assertNotReached ()
36{
37 fprintf (stderr, "*** [%s] This should not happen! ***\n", prgName);
38 abort ();
39}
40
41inline void assertNotReached (const char *fmt, ...)
42{
43 va_list argp;
44 va_start(argp, fmt);
45
46 fprintf (stderr, "*** [%s] This should not happen: ", prgName);
47 vfprintf(stderr, fmt, argp);
48 fprintf (stderr, "! ***\n");
49
50 va_end(argp);
51
52 abort ();
53}
54
55inline void notImplemented (const char *name)
56{
57 fprintf (stderr, "*** [%s] Not implemented: %s ***\n", prgName, name);
58 abort ();
59}
60
61inline int roundInt(double d)
62{
63 return (int) ((d > 0) ? (d + 0.5) : (d - 0.5));
64}
65
66inline int AsciiTolower(char c)
67{
68 return ((c >= 'A' && c <= 'Z') ? c + 0x20 : c);
69}
70
71inline int AsciiToupper(char c)
72{
73 return ((c >= 'a' && c <= 'z') ? c - 0x20 : c);
74}
75
76inline int AsciiStrcasecmp(const char *s1, const char *s2)
77{
78 int ret = 0;
79
80 while ((*s1 || *s2) && !(ret = AsciiTolower(*s1) - AsciiTolower(*s2))) {
81 s1++;
82 s2++;
83 }
84 return ret;
85}
86
87inline const char *boolToStr (bool b) { return b ? "true" : "false"; }
88
93template <class T> class SimpleVector
94{
95private:
98
99 inline void resize ()
100 {
101 /* This algorithm was tuned for memory&speed with this huge page:
102 * http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
103 */
104 if (array == NULL) {
105 this->numAlloc = 1;
106 this->array = (T*) malloc (sizeof (T));
107 }
108 if (this->numAlloc < this->num) {
109 this->numAlloc = (this->num < 100) ?
110 this->num : this->num + this->num/10;
111 this->array =
112 (T*) realloc(this->array, (this->numAlloc * sizeof (T)));
113 }
114 }
115
116public:
117 inline SimpleVector (int initAlloc = 1)
118 {
119 this->num = 0;
120 this->numAlloc = initAlloc;
121 this->array = NULL;
122 }
123
124 inline SimpleVector (const SimpleVector &o) {
125 this->array = NULL;
126 this->num = o.num;
127 this->numAlloc = o.numAlloc;
128 resize ();
129 memcpy (this->array, o.array, sizeof (T) * num);
130 }
131
133 {
134 if (this->array)
135 free (this->array);
136 }
137
141 inline int size() const { return this->num; }
142
143 inline bool empty() const { return size() == 0; }
144
145 inline T* getArray() const { return array; }
146
147 inline T* detachArray() {
148 T* arr = array;
149 array = NULL;
150 numAlloc = 0;
151 num = 0;
152 return arr;
153 }
154
160 inline void increase() { setSize(this->num + 1); }
161
167 inline void setSize(int newSize) {
168 assert (newSize >= 0);
169 this->num = newSize;
170 this->resize ();
171 }
172
178 inline void setSize (int newSize, T t) {
179 int oldSize = this->num;
180 setSize (newSize);
181 for (int i = oldSize; i < newSize; i++)
182 set (i, t);
183 }
184
190 inline T* getRef (int i) const {
191 assert (i >= 0 && this->num - i > 0);
192 return array + i;
193 }
194
201 inline T get (int i) const {
202 assert (i >= 0 && this->num - i > 0);
203 return this->array[i];
204 }
205
209 inline T* getFirstRef () const {
210 assert (this->num > 0);
211 return this->array;
212 }
213
217 inline T getFirst () const {
218 assert (this->num > 0);
219 return this->array[0];
220 }
221
225 inline T* getLastRef () const {
226 assert (this->num > 0);
227 return this->array + this->num - 1;
228 }
229
233 inline T getLast () const {
234 assert (this->num > 0);
235 return this->array[this->num - 1];
236 }
237
246 inline void set (int i, T t) {
247 assert (i >= 0 && this->num - i > 0);
248 this->array[i] = t;
249 }
250
254 inline void setLast (T t) {
255 assert (this->num > 0);
256 this->array[this->num - 1] = t;
257 }
258
266 inline void copyTo(SimpleVector<T> *dest, int thisStart = 0,
267 int thisLast = -1, int destStart = 0) {
268 assert (dest != this);
269 if (thisLast == -1)
270 thisLast = this->size () - 1;
271 for (int i = thisStart; i <= thisLast; i++)
272 dest->set (i - thisStart + destStart, get (i));
273 }
274};
275
310template <class T> class NotSoSimpleVector
311{
312private:
315
316 inline void resizeMain ()
317 {
318 /* This algorithm was tuned for memory&speed with this huge page:
319 * http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
320 */
321 if (arrayMain == NULL) {
322 this->numAllocMain = 1;
323 this->arrayMain = (T*) malloc (sizeof (T));
324 }
325 if (this->numAllocMain < this->numMain) {
326 this->numAllocMain = (this->numMain < 100) ?
327 this->numMain : this->numMain + this->numMain/10;
328 this->arrayMain =
329 (T*) realloc(this->arrayMain, (this->numAllocMain * sizeof (T)));
330 }
331 }
332
333 inline void resizeExtra ()
334 {
335 /* This algorithm was tuned for memory&speed with this huge page:
336 * http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
337 */
338 if (arrayExtra1 == NULL) {
339 this->numAllocExtra = 1;
340 this->arrayExtra1 = (T*) malloc (sizeof (T));
341 this->arrayExtra2 = (T*) malloc (sizeof (T));
342 }
343 if (this->numAllocExtra < this->numExtra) {
344 this->numAllocExtra = (this->numExtra < 100) ?
345 this->numExtra : this->numExtra + this->numExtra/10;
346 this->arrayExtra1 =
347 (T*) realloc(this->arrayExtra1, (this->numAllocExtra * sizeof (T)));
348 this->arrayExtra2 =
349 (T*) realloc(this->arrayExtra2, (this->numAllocExtra * sizeof (T)));
350 }
351 }
352
354 {
355 if (startExtra != -1) {
356 numMain += numExtra;
357 resizeMain ();
359 (numMain - (startExtra + numExtra)) * sizeof (T));
360 memmove (arrayMain + startExtra, arrayExtra1, numExtra * sizeof (T));
361 startExtra = -1;
362 numExtra = 0;
363 }
364 }
365
366public:
367 inline NotSoSimpleVector (int initAlloc)
368 {
369 this->numMain = this->numExtra = 0;
370 this->numAllocMain = initAlloc;
371 this->numAllocExtra = initAlloc;
372 this->arrayMain = this->arrayExtra1 = this->arrayExtra2 = NULL;
373 this->startExtra = -1;
374 }
375
377 {
378 this->arrayMain = NULL;
379 this->numMain = o.numMain;
380 this->numAllocMain = o.numAllocMain;
381 resizeMain ();
382 memcpy (this->arrayMain, o.arrayMain, sizeof (T) * numMain);
383
384 this->arrayExtra = NULL;
385 this->numExtra = o.numExtra;
386 this->numAllocExtra = o.numAllocExtra;
387 resizeExtra ();
388 memcpy (this->arrayExtra, o.arrayExtra, sizeof (T) * numExtra);
389
390 this->startExtra = o.startExtra;
391 }
392
394 {
395 if (this->arrayMain)
396 free (this->arrayMain);
397 if (this->arrayExtra1)
398 free (this->arrayExtra1);
399 if (this->arrayExtra2)
400 free (this->arrayExtra2);
401 }
402
403 inline int size() const { return this->numMain + this->numExtra; }
404
405 inline bool empty() const { return size() == 0; }
406
407 inline void increase() { setSize(size() + 1); }
408
409 inline void setSize(int newSize)
410 {
411 assert (newSize >= 0);
412 this->numMain = newSize - numExtra;
413 this->resizeMain ();
414 }
415
416 void insert (int index, int numInsert)
417 {
418 assert (numInsert >= 0);
419
420 // The following lines are a simple (but inefficient) replacement.
421 //setSize (numMain + numInsert);
422 //memmove (arrayMain + index + numInsert, arrayMain + index,
423 // (numMain - index - numInsert) * sizeof (T));
424 //return;
425
426 if (this->startExtra == -1) {
427 // simple case
428 this->numExtra = numInsert;
429 this->startExtra = index;
430 resizeExtra ();
431 } else {
432 if (index < startExtra) {
433 consolidate ();
434 insert (index, numInsert);
435 } else if (index < startExtra + numExtra) {
436 int oldNumExtra = numExtra;
437 numExtra += numInsert;
438 resizeExtra ();
439
440 int toMove = startExtra + oldNumExtra - index;
441 memmove (arrayExtra1 + numExtra - toMove,
442 arrayExtra1 + index - startExtra,
443 toMove * sizeof (T));
444 } else {
445 int oldNumExtra = numExtra;
446 numExtra += numInsert;
447 resizeExtra ();
448
449 // Note: index refers to the *logical* adress, not to the
450 // *physical* one.
451 int diff = index - this->startExtra - oldNumExtra;
452 T *arrayMainI = arrayMain + this->startExtra;
453 for (int i = diff + oldNumExtra - 1; i >= 0; i--) {
454 T *src = i < oldNumExtra ?
455 this->arrayExtra1 + i : arrayMainI + (i - oldNumExtra);
456 T *dest = i < diff ?
457 arrayMainI + i : arrayExtra2 + (i - diff);
458 *dest = *src;
459 }
460
461 memcpy (arrayExtra1, arrayExtra2, sizeof (T) * oldNumExtra);
462 startExtra = index - oldNumExtra;
463 }
464 }
465 }
466
472 inline T* getRef (int i) const
473 {
474 if (this->startExtra == -1) {
475 assert (i >= 0 && i < this->numMain);
476 return this->arrayMain + i;
477 } else {
478 if (i < this->startExtra) {
479 assert (i >= 0);
480 return this->arrayMain + i;
481 } else if (i >= this->startExtra + this->numExtra) {
482 // The original assertion
484 // "assert (i < this->numMain + this->numExtra)"
485 //
486 // causes this warnung in dw::Textblock::breakAdded:
487 //
488 // "assuming signed overflow does not occur when assuming that
489 // (X - c) > X is always false [-Wstrict-overflow]"
490 //
491 // Subtracting numExtra from both sides solves this,
492 // interrestingly.
493
494 assert (i - this->numExtra < this->numMain);
495 return this->arrayMain + i - this->numExtra;
496 } else
497 return this->arrayExtra1 + i - this->startExtra;
498 }
499 }
500
507 inline T get (int i) const
508 {
509 return *(this->getRef(i));
510 }
511
515 inline T* getFirstRef () const {
516 assert (size () > 0);
517 return this->getRef(0);
518 }
519
523 inline T getFirst () const {
524 return *(this->getFirstRef());
525 }
526
530 inline T* getLastRef () const {
531 assert (size () > 0);
532 return this->getRef(size () - 1);
533 }
534
538 inline T getLast () const {
539 return *(this->getLastRef());
540 }
541
550 inline void set (int i, T t) {
551 *(this->getRef(i)) = t;
552 }
553
557 inline void setLast (T t) {
558 *(this->getLastRef()) = t;
559 }
560};
561
566{
567private:
568 struct Node
569 {
570 char *data;
572 };
573
576 char *str;
578
579public:
580 StringBuffer();
582
589 inline void append(const char *str) { appendNoCopy(strdup(str)); }
590 inline void appendInt(int n)
591 { char buf[32]; sprintf (buf, "%d", n); append (buf); }
592 inline void appendPointer(void *p)
593 { char buf[32]; sprintf (buf, "%p", p); append (buf); }
594 inline void appendBool(bool b) { append (b ? "true" : "false"); }
595 void appendNoCopy(char *str);
596 const char *getChars();
597 void clear ();
598};
599
600
605{
606private:
607 unsigned char *bits;
609
610 inline int bytesForBits(int bits) { return bits == 0 ? 1 : (bits + 7) / 8; }
611
612public:
613 BitSet(int initBits);
614 ~BitSet();
616 bool get(int i) const;
617 void set(int i, bool val);
618 void clear();
619};
620
627{
628private:
630 SimpleVector <char*> *pools;
631 SimpleVector <char*> *bulk;
632
633public:
635 this->poolSize = poolSize;
636 this->poolLimit = poolSize / 4;
637 this->freeIdx = poolSize;
638 this->pools = new SimpleVector <char*> (1);
639 this->bulk = new SimpleVector <char*> (1);
640 };
641
643 zoneFree ();
644 delete pools;
645 delete bulk;
646 }
647
648 inline void * zoneAlloc (size_t t) {
649 void *ret;
650
651 if (t > poolLimit) {
652 bulk->increase ();
653 bulk->set (bulk->size () - 1, (char*) malloc (t));
654 return bulk->get (bulk->size () - 1);
655 }
656
657 if (t > poolSize - freeIdx) {
658 pools->increase ();
659 pools->set (pools->size () - 1, (char*) malloc (poolSize));
660 freeIdx = 0;
661 }
662
663 ret = pools->get (pools->size () - 1) + freeIdx;
664 freeIdx += t;
665 return ret;
666 }
667
668 inline void zoneFree () {
669 for (int i = 0; i < pools->size (); i++)
670 free (pools->get (i));
671 pools->setSize (0);
672 for (int i = 0; i < bulk->size (); i++)
673 free (bulk->get (i));
674 bulk->setSize (0);
676 }
677
678 inline const char *strndup (const char *str, size_t t) {
679 char *new_str = (char *) zoneAlloc (t + 1);
680 memcpy (new_str, str, t);
681 new_str[t] = '\0';
682 return new_str;
683 }
684
685 inline const char *strdup (const char *str) {
686 return strndup (str, strlen (str));
687 }
688};
689
690} // namespace misc
691
692} // namespace lout
693
694#endif // __LOUT_MISC_HH__
A bit set, which automatically reallocates when needed.
Definition misc.hh:605
void intoStringBuffer(misc::StringBuffer *sb)
Definition misc.cc:147
void set(int i, bool val)
Definition misc.cc:163
bool get(int i) const
Definition misc.cc:155
int bytesForBits(int bits)
Definition misc.hh:610
unsigned char * bits
Definition misc.hh:607
Container similar to lout::misc::SimpleVector, but some cases of insertion optimized (used for hyphen...
Definition misc.hh:311
NotSoSimpleVector(int initAlloc)
Definition misc.hh:367
T getFirst() const
Return the first element, explicitly.
Definition misc.hh:523
void set(int i, T t)
Store an object in the vector.
Definition misc.hh:550
T * getLastRef() const
Return the reference of the last element (convenience method).
Definition misc.hh:530
void insert(int index, int numInsert)
Definition misc.hh:416
T * getFirstRef() const
Return the reference of the first element (convenience method).
Definition misc.hh:515
void setSize(int newSize)
Definition misc.hh:409
T get(int i) const
Return the one element, explicitly.
Definition misc.hh:507
T getLast() const
Return the last element, explicitly.
Definition misc.hh:538
T * getRef(int i) const
Return the reference of one element.
Definition misc.hh:472
NotSoSimpleVector(const NotSoSimpleVector &o)
Definition misc.hh:376
void setLast(T t)
Store an object at the end of the vector.
Definition misc.hh:557
Simple (simpler than container::untyped::Vector and container::typed::Vector) template based vector.
Definition misc.hh:94
SimpleVector(const SimpleVector &o)
Definition misc.hh:124
void setSize(int newSize)
Set the size explicitly.
Definition misc.hh:167
void increase()
Increase the vector size by one.
Definition misc.hh:160
T * getArray() const
Definition misc.hh:145
void copyTo(SimpleVector< T > *dest, int thisStart=0, int thisLast=-1, int destStart=0)
Copies some elements into another vector of the same type.
Definition misc.hh:266
T getFirst() const
Return the first element, explicitly.
Definition misc.hh:217
void setSize(int newSize, T t)
Set the size explicitly and initialize new values.
Definition misc.hh:178
T * getFirstRef() const
Return the reference of the first element (convenience method).
Definition misc.hh:209
void set(int i, T t)
Store an object in the vector.
Definition misc.hh:246
T get(int i) const
Return the one element, explicitly.
Definition misc.hh:201
int size() const
Return the number of elements put into this vector.
Definition misc.hh:141
T * getRef(int i) const
Return the reference of one element.
Definition misc.hh:190
T * getLastRef() const
Return the reference of the last element (convenience method).
Definition misc.hh:225
void setLast(T t)
Store an object at the end of the vector.
Definition misc.hh:254
bool empty() const
Definition misc.hh:143
T getLast() const
Return the last element, explicitly.
Definition misc.hh:233
SimpleVector(int initAlloc=1)
Definition misc.hh:117
A class for fast concatenation of a large number of strings.
Definition misc.hh:566
void appendBool(bool b)
Definition misc.hh:594
void appendPointer(void *p)
Definition misc.hh:592
void clear()
Remove all strings appended to the string buffer.
Definition misc.cc:116
void appendInt(int n)
Definition misc.hh:590
void append(const char *str)
Append a NUL-terminated string to the buffer, with copying.
Definition misc.hh:589
void appendNoCopy(char *str)
Append a NUL-terminated string to the buffer, without copying.
Definition misc.cc:68
const char * getChars()
Return a NUL-terminated strings containing all appended strings.
Definition misc.cc:92
A simple allocator optimized to handle many small chunks of memory.
Definition misc.hh:627
const char * strdup(const char *str)
Definition misc.hh:685
const char * strndup(const char *str, size_t t)
Definition misc.hh:678
void * zoneAlloc(size_t t)
Definition misc.hh:648
ZoneAllocator(size_t poolSize)
Definition misc.hh:634
SimpleVector< char * > * bulk
Definition misc.hh:631
SimpleVector< char * > * pools
Definition misc.hh:630
T min(T a, T b)
Definition misc.hh:19
void notImplemented(const char *name)
Definition misc.hh:55
T max(T a, T b)
Definition misc.hh:20
const char * prgName
Definition misc.cc:33
int AsciiStrcasecmp(const char *s1, const char *s2)
Definition misc.hh:76
int roundInt(double d)
Definition misc.hh:61
void init(int argc, char *argv[])
Definition misc.cc:35
int AsciiTolower(char c)
Definition misc.hh:66
int AsciiToupper(char c)
Definition misc.hh:71
void assertNotReached()
Definition misc.hh:35
const char * boolToStr(bool b)
Definition misc.hh:87