// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Pool memory allocation
 *
 * Authors:
 *   Stéphane Gimenez <dev@gim.name>
 *
 * Copyright (C) 2004-2006 Authors
 *
 * Released under GNU GPL v2+, read the file 'COPYING' for more information.
 */

// not thread safe (a pool cannot be shared by threads safely)

/*
-- principle:

 - user operations on a pool of objects of type T are:
   - T *draw() : obtain a unused slot to store an object T
   - void drop(T *) : release a slot

-- implementation:

 - a pool for objects T is:

   * blocks[64] : an array of allocated blocks of memory:
     |---0--> block with capacity 64
     |---1--> block with capacity 64
     |---2--> block with capacity 128
     |---3--> block with capacity 128
     |---4--> block with capacity 256
     |---5--> block with capacity 256
     |---6--> block with capacity 512
     |---7--> not yet allocated
     :
     |---k--> not yet allocated (future capacity ~ 2^(6+k/2))
     :
     '--63--> not yet allocated
   * cblock : the index of the next unallocated block (here 7).
   * next : a pointer to an unused slot inside an allocated bloc

 - the first bytes of an unallocated slot inside a bloc are used to store a
   pointer to some other unallocated slot. (this way, we keep a list of all
   unused slots starting at <next>)

 - insertions and deletions in this list are done at the root <next>.
   if <next> points to NULL (no slots are available) when a draw()
   operation is performed a new block is allocated, and the unused slots
   list is filled with the allocated slots.

 - memory is freed only at pool's deletion.
*/
#ifndef INKSCAPE_TRACE_POOL_H
#define INKSCAPE_TRACE_POOL_H

#include <cstdlib>
#include <exception>
#include <algorithm>

template <typename T>
class Pool
{
public:
    Pool()
    {
        cblock = 0;
        size = std::max(sizeof(T), sizeof(void *));
        next = nullptr;
        for (auto &k : block) {
            k = nullptr;
        }
    }

    ~Pool()
    {
        for (int k = 0; k < cblock; k++) {
            std::free(block[k]);
        }
    }

    T *draw()
    {
        if (!next) addblock();
        void *p = next;
        next = *(void **)p;
        return (T *)p;
    }

    void drop(T *p)
    {
        *(void **)p = next;
        next = (void *)p;
    }

private:
    int size;
    int cblock;
    void *block[64]; // enough to store unlimited number of objects, if 64 is changed: see constructor too
    void *next;

    void addblock()
    {
        int i = cblock++;
        int blocksize = 1 << (6 + (i / 2));
        block[i] = (void *)std::malloc(blocksize * size);
        if (!block[i]) throw std::bad_alloc();
        char *p = (char *)block[i];
        for (int k = 0; k < blocksize - 1; k++) {
            *(void**)p = (void *)(p + size);
            p += size;
        }
        *(void **)p = next;
        next = block[i];
    }
};

#endif // INKSCAPE_TRACE_POOL_H