util.h

#ifndef MOBI_MTLD_UTIL
#define MOBI_MTLD_UTIL

#if defined(_WIN32)
    #pragma warning(disable: 4996 4251)
    #if !defined(DEVATLAS_STATIC)
        #ifdef devatlas_EXPORTS
            #define DA_EXPORT __declspec(dllexport) 
        #else
            #define DA_EXPORT __declspec(dllimport)
        #endif
    #endif
#endif
#ifndef DA_EXPORT
#if __GNUC__ >= 4
#define DA_EXPORT   __attribute__((visibility("default")))
#define DA_PRIVATE  __attribute__((visibility("hidden")))
#else
#define DA_EXPORT
#define DA_PRIVATE
#endif
#endif

#include <algorithm>
#include <cassert>
#include <bitset>
#include <ostream>
#include <utility>
#include <iostream>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <mtld/exception.h>

#if defined(__linux__) || defined(_WIN32)
size_t strlcpy(char *, const char *, size_t);
#endif

namespace Mobi { namespace Mtld { namespace Util {


/*
 * A block of objects extending from start to finish,
 * with a marker to a current position
 */
template <typename T>
struct Buf {
    size_t avail() { return finish - cur; }
    Buf *next;
    T *start;
    T *finish;
    T *cur;
    Buf(size_t capacity_, T *start_) 
        : next(0)
        , start(start_)
        , finish(start_ + capacity_)
        , cur(start)
    {
    }

    virtual ~Buf() { }
};

/*
 * A buffer with backing data allocated from the heap
 */
template <typename T>
struct HeapBuf : public Buf<T> {
    HeapBuf(size_t capacity)
        : Buf<T>(capacity, new T[capacity]) {}
    ~HeapBuf() {
        delete[] this->start;
    }
};

/*
 * A buffer of a fixed size allocated inline
 */
template <size_t size, typename T>
struct FixedBuf : public Buf<T> {
    T buf[size];
    FixedBuf() : Buf<T>(size, buf) {}
    ~FixedBuf() { }
};


/*
 * An allocator that supports multiple allocations
 * that are all freed when the allocator is freed.
 * Consists of a chain of Buffers. Allocations
 * are satisfied from existing buffers if there
 * is room, or else a new buffer is created.
 */
template <size_t Size>
class Alloc {
    FixedBuf<Size, char> first;
    Buf<char> *chain;
public:
    inline Alloc<Size>();
    inline ~Alloc<Size>();
    template <typename ObjectType> inline ObjectType *allocate(size_t count = 1);
    template <typename ObjectType> inline void allocate(ObjectType *&ptr, size_t count = 1) { ptr = allocate<ObjectType>(count); }
};

template <size_t Size>
Alloc<Size>::Alloc()
    : chain(&first)
{ }

template <size_t Size>
Alloc<Size>::~Alloc()
{
    Buf<char> *next;
    for (Buf<char> *buf = chain; buf != &first; buf = next) {
        next = buf->next;
        delete buf;
    }
}

template <size_t Size>
template <typename ObjectType>
ObjectType *
Alloc<Size>::allocate(size_t count)
{
    static const size_t align = std::min(size_t(8), sizeof (ObjectType));
    int space = count * sizeof (ObjectType);

    Buf<char> *buf;

    /*
     * Find an existing buffer on the chain that can meet our
     * allocation demand, or allocate a new one if needed.
     */
    char *p;
    for (buf = chain;;  buf = buf->next) {
        if (buf == 0) {
            buf = new HeapBuf<char>(std::max(int(Size), space));
            buf->next = chain;
            chain = buf;
            p = buf->cur;
            break;
        }
        p = buf->cur;
        int misalign = (intptr_t)p % align;
        if (misalign)
            p += align - misalign;
        if (buf->finish - p >= space)
            break;
    }

    ObjectType *t = reinterpret_cast<ObjectType *>(p);
    buf->cur = p + space;
    assert(buf->cur <= buf->finish); // buf had space for our allocation
    return t;
}

template <typename El, typename Container> class templ_iterator {
    Container *container;
    size_t offset;
public:
    std::pair<int, El> operator *() const {
        return std::make_pair(int(offset + container->first), container->elements[offset]);
    }
    templ_iterator &operator++() { ++offset; return *this; }
    bool operator==(const templ_iterator &rhs) { return rhs.offset == offset; }
    bool operator!=(const templ_iterator &rhs) { return rhs.offset != offset; }
    templ_iterator(Container *this_, int offset_) : container(this_), offset(offset_) {}
    templ_iterator() : container(0), offset(0) {}
};

// Array-like container that limits itself to minimal contiguous spanned array for the non-null indexes.
// Eg: the set 9, 10, 30 will have an array of size (30 - 9 + 1) = 22, with the "9" occupying index 0 of the array.

template <typename Element> class CharacterIndex {
    int first;
    size_t count;
    Element *elements;
public:
    Element &operator[](int index) {
        int off = index - first;

        if (elements == 0) {
            first = off;
            count = 1;
            elements = new Element[1];
        } else if (off < 0) {
            off = -off;
            // need "off" extra elements at start.
            size_t newCount = count + off;
            Element *newElements = new Element[newCount];
            memset(newElements, 0, off * sizeof(Element));
            memcpy(newElements + off, elements, count * sizeof(Element));
            delete[] elements;
            elements = newElements;
            count = newCount;
            first = index;
        } else if (size_t(off) >= count) {
            size_t newCount = static_cast<size_t>(off) + 1;
            Element *newElements = new Element[newCount];
            memset(newElements, 0, newCount * sizeof(Element));
            memcpy(newElements, elements, count * sizeof(Element));
            delete[] elements;
            count = newCount;
            elements = newElements;
        }

        return elements[index - first];
    }



    friend class templ_iterator<Element, const CharacterIndex<Element> >;
    friend class templ_iterator<Element, CharacterIndex<Element> >;
    typedef templ_iterator<Element, const CharacterIndex<Element> > const_iterator;
    typedef templ_iterator<Element, CharacterIndex<Element> > iterator;

    iterator begin() { return iterator(this, 0); }
    iterator find(int idx)
    { return idx >= first && idx < first + count ? iterator(this, idx - first) : iterator(this, count); }
    iterator end() { return iterator(this, count); }

    const_iterator begin() const { return const_iterator(this, 0); }
    const_iterator find(int idx) const
    { return idx >= first && idx < int(first + count) ? const_iterator(this, idx - first) : const_iterator(this, count); }
    const_iterator end() const { return const_iterator(this, count); }

    CharacterIndex() 
        : first(0)
        , count(0)
        , elements(0)
    {
    }

    ~CharacterIndex() {
        delete [] elements;
    }

    bool empty() const { return count == 0; }
};

enum CharFlags {
    SKIPQUOTE = 1 << 0,
    NULLOK = 1 << 1
};

DA_EXPORT inline const char *
pad(unsigned depth)
{
    static const char spaces[] = 
        "                                        "
        "                                        "
        "                                        ";
    if (depth > sizeof spaces - 1)
        depth = sizeof spaces - 1;
    return spaces + sizeof spaces - 1 - depth;
}

DA_EXPORT inline char
nextchar(const char *&p, int flags)
{
    for (;;) {
        switch (*p) {
            case 0: {
                if (flags & NULLOK)
                    return 0;
                Exception e;
                e << "invalid encoding";
                throw e;
            }

            case '"': 
                if (flags & SKIPQUOTE) {
                    p++;
                    continue;
                }
                // fallthrough
            default:
                return *p++;
        }
    }
}

DA_EXPORT inline char
nextword(char *result, const char *&p, const char *terms, int flags)
{
    for (;;) {
        char c = nextchar(p, flags);
        if (strchr(terms, c) != 0) {
            *result = 0;
            return c;
        }
        *result++ = c;
    }
    *result = 0;
}


}}}

#endif