Files
flenser/lout/misc.hh
ADAM David Alan Martin f283391b46 Get some of the last remaining C files into C++
They still need to be fixed up, but they now build with C++.
2025-08-23 02:09:47 -04:00

687 lines
18 KiB
C++

/*
* Dillo Widget
*
* Copyright 2005-2007 Sebastian Geerken <sgeerken@dillo.org>
* Copyright 2024 Rodrigo Arias Mallo <rodarima@gmail.com>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef __LOUT_MISC_HH__
#define __LOUT_MISC_HH__
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "dlib/dlib.hh"
namespace lout {
/**
* \brief Miscellaneous stuff, which does not fit anywhere else.
*
* Actually, the other parts, beginning with \ref object, depend on this.
*/
namespace misc {
extern const char *prgName;
void init (int argc, char *argv[]);
inline void assertNotReached ()
{
fprintf (stderr, "*** [%s] This should not happen! ***\n", prgName);
abort ();
}
inline void assertNotReached (const char *fmt, ...)
{
va_list argp;
va_start(argp, fmt);
fprintf (stderr, "*** [%s] This should not happen: ", prgName);
vfprintf(stderr, fmt, argp);
fprintf (stderr, "! ***\n");
va_end(argp);
abort ();
}
inline void notImplemented (const char *name)
{
fprintf (stderr, "*** [%s] Not implemented: %s ***\n", prgName, name);
abort ();
}
inline int roundInt(double d)
{
return (int) ((d > 0) ? (d + 0.5) : (d - 0.5));
}
inline int AsciiTolower(char c)
{
return ((c >= 'A' && c <= 'Z') ? c + 0x20 : c);
}
inline int AsciiToupper(char c)
{
return ((c >= 'a' && c <= 'z') ? c - 0x20 : c);
}
inline int AsciiStrcasecmp(const char *s1, const char *s2)
{
int ret = 0;
while ((*s1 || *s2) && !(ret = AsciiTolower(*s1) - AsciiTolower(*s2))) {
s1++;
s2++;
}
return ret;
}
inline const char *boolToStr (bool b) { return b ? "true" : "false"; }
/**
* \brief Simple (simpler than container::untyped::Vector and
* container::typed::Vector) template based vector.
*/
template <class T> class SimpleVector
{
private:
T *array;
int num, numAlloc;
inline void resize ()
{
/* This algorithm was tuned for memory&speed with this huge page:
* http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
*/
if (array == NULL) {
this->numAlloc = 1;
this->array = (T*) malloc (sizeof (T));
}
if (this->numAlloc < this->num) {
this->numAlloc = (this->num < 100) ?
this->num : this->num + this->num/10;
this->array =
(T*) realloc(this->array, (this->numAlloc * sizeof (T)));
}
}
public:
inline SimpleVector (int initAlloc = 1)
{
this->num = 0;
this->numAlloc = initAlloc;
this->array = NULL;
}
inline SimpleVector (const SimpleVector &o) {
this->array = NULL;
this->num = o.num;
this->numAlloc = o.numAlloc;
resize ();
memcpy (this->array, o.array, sizeof (T) * num);
}
inline ~SimpleVector ()
{
if (this->array)
free (this->array);
}
/**
* \brief Return the number of elements put into this vector.
*/
inline int size() const { return this->num; }
inline bool empty() const { return size() == 0; }
inline T* getArray() const { return array; }
inline T* detachArray() {
T* arr = array;
array = NULL;
numAlloc = 0;
num = 0;
return arr;
}
/**
* \brief Increase the vector size by one.
*
* May be necessary before calling misc::SimpleVector::set.
*/
inline void increase() { setSize(this->num + 1); }
/**
* \brief Set the size explicitly.
*
* May be necessary before calling misc::SimpleVector::set.
*/
inline void setSize(int newSize) {
assert (newSize >= 0);
this->num = newSize;
this->resize ();
}
/**
* \brief Set the size explicitly and initialize new values.
*
* May be necessary before calling misc::SimpleVector::set.
*/
inline void setSize (int newSize, T t) {
int oldSize = this->num;
setSize (newSize);
for (int i = oldSize; i < newSize; i++)
set (i, t);
}
/**
* \brief Return the reference of one element.
*
* \sa misc::SimpleVector::get
*/
inline T* getRef (int i) const {
assert (i >= 0 && this->num - i > 0);
return array + i;
}
/**
* \brief Return the one element, explicitly.
*
* The element is copied, so for complex elements, you should rather used
* misc::SimpleVector::getRef.
*/
inline T get (int i) const {
assert (i >= 0 && this->num - i > 0);
return this->array[i];
}
/**
* \brief Return the reference of the first element (convenience method).
*/
inline T* getFirstRef () const {
assert (this->num > 0);
return this->array;
}
/**
* \brief Return the first element, explicitly.
*/
inline T getFirst () const {
assert (this->num > 0);
return this->array[0];
}
/**
* \brief Return the reference of the last element (convenience method).
*/
inline T* getLastRef () const {
assert (this->num > 0);
return this->array + this->num - 1;
}
/**
* \brief Return the last element, explicitly.
*/
inline T getLast () const {
assert (this->num > 0);
return this->array[this->num - 1];
}
/**
* \brief Store an object in the vector.
*
* Unlike in container::untyped::Vector and container::typed::Vector,
* you have to care about the size, so a call to
* misc::SimpleVector::increase or misc::SimpleVector::setSize may
* be necessary before.
*/
inline void set (int i, T t) {
assert (i >= 0 && this->num - i > 0);
this->array[i] = t;
}
/**
* \brief Store an object at the end of the vector.
*/
inline void setLast (T t) {
assert (this->num > 0);
this->array[this->num - 1] = t;
}
/**
* \brief Copies some elements into another vector of the same
* type.
*
* Cannot be used to copy elements within one vector. (For this,
* it would have to be extended to copy backwards in some cases.)
*/
inline void copyTo(SimpleVector<T> *dest, int thisStart = 0,
int thisLast = -1, int destStart = 0) {
assert (dest != this);
if (thisLast == -1)
thisLast = this->size () - 1;
for (int i = thisStart; i <= thisLast; i++)
dest->set (i - thisStart + destStart, get (i));
}
};
/**
* \brief Container similar to lout::misc::SimpleVector, but some cases
* of insertion optimized (used for hyphenation).
*
* For hyphenation, words are often split, so that some space must be
* inserted by the method NotSoSimpleVector::insert. Typically, some
* elements are inserted quite at the beginning (when the word at the
* end of the first or at the beginning of the second line is
* hyphenated), then, a bit further (end of second line/beginning of
* third line) and so on. In the first time, nearly all words must be
* moved; in the second time, a bit less, etc. After all, using a
* simple vector would result in O(n<sup>2</sup>) number of elements
* moved total. With this class, however, the number can be kept at
* O(n).
*
* The basic idea is to keep an extra array (actually two, of which
* the second one is used temporarily), which is inserted in a logical
* way. Since there is only one extra array at max, reading is rather
* simple and fast (see NotSoSimpleVector::getRef): check whether the
* position is before, within, or after the extra array. The first
* insertion is also rather simple, when the extra array has to be
* created. The following sketch illustrates the most complex case,
* when an extra array exists, and something is inserted after it (the
* case for which this class has been optimized):
*
* \image html not-so-simple-container.png
*
* Dotted lines are used to keep the boxes aligned.
*
* As you see, only a relatively small fraction of elements has to be
* moved.
*
* There are some other cases, which have to be documented.
*/
template <class T> class NotSoSimpleVector
{
private:
T *arrayMain, *arrayExtra1, *arrayExtra2;
int numMain, numExtra, numAllocMain, numAllocExtra, startExtra;
inline void resizeMain ()
{
/* This algorithm was tuned for memory&speed with this huge page:
* http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
*/
if (arrayMain == NULL) {
this->numAllocMain = 1;
this->arrayMain = (T*) malloc (sizeof (T));
}
if (this->numAllocMain < this->numMain) {
this->numAllocMain = (this->numMain < 100) ?
this->numMain : this->numMain + this->numMain/10;
this->arrayMain =
(T*) realloc(this->arrayMain, (this->numAllocMain * sizeof (T)));
}
}
inline void resizeExtra ()
{
/* This algorithm was tuned for memory&speed with this huge page:
* http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
*/
if (arrayExtra1 == NULL) {
this->numAllocExtra = 1;
this->arrayExtra1 = (T*) malloc (sizeof (T));
this->arrayExtra2 = (T*) malloc (sizeof (T));
}
if (this->numAllocExtra < this->numExtra) {
this->numAllocExtra = (this->numExtra < 100) ?
this->numExtra : this->numExtra + this->numExtra/10;
this->arrayExtra1 =
(T*) realloc(this->arrayExtra1, (this->numAllocExtra * sizeof (T)));
this->arrayExtra2 =
(T*) realloc(this->arrayExtra2, (this->numAllocExtra * sizeof (T)));
}
}
void consolidate ()
{
if (startExtra != -1) {
numMain += numExtra;
resizeMain ();
memmove (arrayMain + startExtra + numExtra, arrayMain + startExtra,
(numMain - (startExtra + numExtra)) * sizeof (T));
memmove (arrayMain + startExtra, arrayExtra1, numExtra * sizeof (T));
startExtra = -1;
numExtra = 0;
}
}
public:
inline NotSoSimpleVector (int initAlloc)
{
this->numMain = this->numExtra = 0;
this->numAllocMain = initAlloc;
this->numAllocExtra = initAlloc;
this->arrayMain = this->arrayExtra1 = this->arrayExtra2 = NULL;
this->startExtra = -1;
}
inline ~NotSoSimpleVector ()
{
if (this->arrayMain)
free (this->arrayMain);
if (this->arrayExtra1)
free (this->arrayExtra1);
if (this->arrayExtra2)
free (this->arrayExtra2);
}
inline int size() const { return this->numMain + this->numExtra; }
inline bool empty() const { return size() == 0; }
inline void increase() { setSize(size() + 1); }
inline void setSize(int newSize)
{
assert (newSize >= 0);
this->numMain = newSize - numExtra;
this->resizeMain ();
}
void insert (int index, int numInsert)
{
assert (numInsert >= 0);
// The following lines are a simple (but inefficient) replacement.
//setSize (numMain + numInsert);
//memmove (arrayMain + index + numInsert, arrayMain + index,
// (numMain - index - numInsert) * sizeof (T));
//return;
if (this->startExtra == -1) {
// simple case
this->numExtra = numInsert;
this->startExtra = index;
resizeExtra ();
} else {
if (index < startExtra) {
consolidate ();
insert (index, numInsert);
} else if (index < startExtra + numExtra) {
int oldNumExtra = numExtra;
numExtra += numInsert;
resizeExtra ();
int toMove = startExtra + oldNumExtra - index;
memmove (arrayExtra1 + numExtra - toMove,
arrayExtra1 + index - startExtra,
toMove * sizeof (T));
} else {
int oldNumExtra = numExtra;
numExtra += numInsert;
resizeExtra ();
// Note: index refers to the *logical* address, not to the
// *physical* one.
int diff = index - this->startExtra - oldNumExtra;
T *arrayMainI = arrayMain + this->startExtra;
for (int i = diff + oldNumExtra - 1; i >= 0; i--) {
T *src = i < oldNumExtra ?
this->arrayExtra1 + i : arrayMainI + (i - oldNumExtra);
T *dest = i < diff ?
arrayMainI + i : arrayExtra2 + (i - diff);
*dest = *src;
}
memcpy (arrayExtra1, arrayExtra2, sizeof (T) * oldNumExtra);
startExtra = index - oldNumExtra;
}
}
}
/**
* \brief Return the reference of one element.
*
* \sa misc::SimpleVector::get
*/
inline T* getRef (int i) const
{
if (this->startExtra == -1) {
assert (i >= 0 && i < this->numMain);
return this->arrayMain + i;
} else {
if (i < this->startExtra) {
assert (i >= 0);
return this->arrayMain + i;
} else if (i >= this->startExtra + this->numExtra) {
// The original assertion
///
// "assert (i < this->numMain + this->numExtra)"
//
// causes this warnung in dw::Textblock::breakAdded:
//
// "assuming signed overflow does not occur when assuming that
// (X - c) > X is always false [-Wstrict-overflow]"
//
// Subtracting numExtra from both sides solves this,
// interrestingly.
assert (i - this->numExtra < this->numMain);
return this->arrayMain + i - this->numExtra;
} else
return this->arrayExtra1 + i - this->startExtra;
}
}
/**
* \brief Return the one element, explicitly.
*
* The element is copied, so for complex elements, you should rather used
* misc::SimpleVector::getRef.
*/
inline T get (int i) const
{
return *(this->getRef(i));
}
/**
* \brief Return the reference of the first element (convenience method).
*/
inline T* getFirstRef () const {
assert (size () > 0);
return this->getRef(0);
}
/**
* \brief Return the first element, explicitly.
*/
inline T getFirst () const {
return *(this->getFirstRef());
}
/**
* \brief Return the reference of the last element (convenience method).
*/
inline T* getLastRef () const {
assert (size () > 0);
return this->getRef(size () - 1);
}
/**
* \brief Return the last element, explicitly.
*/
inline T getLast () const {
return *(this->getLastRef());
}
/**
* \brief Store an object in the vector.
*
* Unlike in container::untyped::Vector and container::typed::Vector,
* you have to care about the size, so a call to
* misc::SimpleVector::increase or misc::SimpleVector::setSize may
* be necessary before.
*/
inline void set (int i, T t) {
*(this->getRef(i)) = t;
}
/**
* \brief Store an object at the end of the vector.
*/
inline void setLast (T t) {
*(this->getLastRef()) = t;
}
};
/**
* \brief A class for fast concatenation of a large number of strings.
*/
class StringBuffer
{
private:
struct Node
{
char *data;
Node *next;
};
Node *firstNode, *lastNode;
int numChars;
char *str;
bool strValid;
public:
StringBuffer();
~StringBuffer();
/**
* \brief Append a NUL-terminated string to the buffer, with copying.
*
* A copy is kept in the buffer, so the caller does not have to care
* about memory management.
*/
inline void append(const char *str) { appendNoCopy(dStrdup(str)); }
inline void appendInt(int n)
{ char buf[32]; sprintf (buf, "%d", n); append (buf); }
inline void appendPointer(const void *p)
{ char buf[32]; sprintf (buf, "%p", p); append (buf); }
inline void appendBool(bool b) { append (b ? "true" : "false"); }
void appendNoCopy(char *str);
const char *getChars();
void clear ();
};
/**
* \brief A bit set, which automatically reallocates when needed.
*/
class BitSet
{
private:
unsigned char *bits;
int numBits, numBytes;
inline int bytesForBits(int bits) { return bits == 0 ? 1 : (bits + 7) / 8; }
public:
BitSet(int initBits);
~BitSet();
void intoStringBuffer(misc::StringBuffer *sb);
bool get(int i) const;
void set(int i, bool val);
void clear();
};
/**
* \brief A simple allocator optimized to handle many small chunks of memory.
* The chunks can not be free'd individually. Instead the whole zone must be
* free'd with zoneFree().
*/
class ZoneAllocator
{
private:
size_t poolSize, poolLimit, freeIdx;
SimpleVector <char*> *pools;
SimpleVector <char*> *bulk;
public:
ZoneAllocator (size_t poolSize) {
this->poolSize = poolSize;
this->poolLimit = poolSize / 4;
this->freeIdx = poolSize;
this->pools = new SimpleVector <char*> (1);
this->bulk = new SimpleVector <char*> (1);
};
~ZoneAllocator () {
zoneFree ();
delete pools;
delete bulk;
}
inline void * zoneAlloc (size_t t) {
void *ret;
if (t > poolLimit) {
bulk->increase ();
bulk->set (bulk->size () - 1, (char*) malloc (t));
return bulk->get (bulk->size () - 1);
}
if (t > poolSize - freeIdx) {
pools->increase ();
pools->set (pools->size () - 1, (char*) malloc (poolSize));
freeIdx = 0;
}
ret = pools->get (pools->size () - 1) + freeIdx;
freeIdx += t;
return ret;
}
inline void zoneFree () {
for (int i = 0; i < pools->size (); i++)
free (pools->get (i));
pools->setSize (0);
for (int i = 0; i < bulk->size (); i++)
free (bulk->get (i));
bulk->setSize (0);
freeIdx = poolSize;
}
inline const char *strndup (const char *str, size_t t) {
char *new_str = (char *) zoneAlloc (t + 1);
memcpy (new_str, str, t);
new_str[t] = '\0';
return new_str;
}
inline const char *strdup (const char *str) {
return strndup (str, strlen (str));
}
};
} // namespace misc
} // namespace lout
#endif // __LOUT_MISC_HH__