// An average HTML DOM tree consists of hundreds or thousands of nodes and

// their attributes. The malloc/new and free/delete are very expensive

// operations for small objects and htmlparser spends majority of the time in

// allocation and deallocation of these small objects.

//

// Usage:

// One Allocator for each type. This approach simplifies the design and

// alignment requirements of different types.

//

//     // Allocator for Node with 8k blocks, and 8 byte alignment boundary.

//     Allocator<Node> node_allocator(8192);

//

//     // Allocator for Attributes with 4k blocks, and 1 byte alignment.

//     Allocator<Attribute> attr_allocator(4096);

//

//     // Default block size.

//     Allocator<Node> node_allocator;  // Block size = OS page_size.

//

// The allocator takes care of alignment requirements of the objects. The blocks

// are always created in the multiples of page_size. For the following Allocator

// the block size is upgraded to 4096 for 4k page_size or 8192 for 8k page_size.

//

//     Allocator<Node> node_allocator(3000);  // Block size = 4096.

//

// To construct the object:

//   Node* node = node_allocator.Construct(NodeType::ELEMENT_NODE);

//

// The construct method supports varargs. Following forwards 4 parameters to the

// AboutMe constructor.

//   Allocator<AboutMe> alloc;

//   AboutMe* name = alloc.Construct("John", "Doe", 94043, MALE);

//

// THREAD SAFETY: Allocator is not thread safe. Multiple threads cannot call

// Allocate() simultaneously. In multi-threaded program a thread local allocator

// per thread is recommended.

//

//

// ---------------------------------------------------------------------------

//                   Internals for code reviewers:

// ---------------------------------------------------------------------------

// The allocator maintains linked list of blocks of memory buffers for

// allocation of small objects.  It allocates blocks on demand, one block at a

// time.

//

// The block is always multiple of page size. It is rounded to nearest page size

// multiple in case caller provided a different size which is not multiple of

// page size. So a 3000 block size request becomes 4096 block and 5000 block

// size request becomes 8192 block size respectively on a 4k page size kernel.

//

// The block_size is the only configurable parameter, and depends on three

// fators: A) Object size, B) Number of objects and C) Alignment boundary.

//

//

// Alignment requirements:

// Every object type has a property called alignment requirement, which is an

// integer value of type std::size_t representing the number of bytes  between

// successive addresses at which objects of this type can be allocated.

// The valid alignment values are non-negative integral powers of two.

//

// We call an object naturally aligned if its address is aligned to its size.

// It's called misaligned otherwise. For example, an 8-byte floating-point data

// is naturally aligned if the address used to identify it has an 8-byte

// alignment.

//

// Following data struture contains members totaling 13 bytes, but it's actual

// size is 24 bytes due to 8 byte alignment.

//

// Alignment is always equal to the largest sized element in the structure.

//

// struct {

//   int32_t a;  // 4 bytes.

//   int64_t b;  // 8 bytes.

//   char c;     // 1 byte.

// };

//

// The above data structure will be padded by compiler to satisfy alignment

// requirement.

// struct {

//   int32_t a;     // 4 byte                                 0x0000

//   char _pad[4];  // compiler added 8 byte padding.

//   int64_t b;     // 8 byte (now at 8 byte alignment).      0x0008

//   char c;        // 1 byte (also at 8 byte alignment).     0x0010

//   char _pad[7]   // compiler added padding

// };

//

// The same data structure if fields are re-organized will consume 16 bytes,

// still at 8 byte alignment.

// struct {

//   int32_t a;     // 4 byte at 0x00000 (like above).        0x0000

//   char c;        // 1 byte char.                           0x0001

//   chr _pad[3]    // 3 bytes for 8 byte alignment.

//   int64_t b;     // at 8 byte alignment.                   0x0010

// };

//

// Allocator computes the alignment requirement of the Type and starts the block

// at the address which is multiple of 8, and hence we say the block is aligned.

//

// +-------------------------------------------------------------------------+

// | Address  |    Block 1  |  Address  |   Block 2  | Address  |  Block 3   |

// +----------+-------------+-----------+------------+----------+------------+

// |   10     |    waste    |   120     |    Obj22   |   164    |   waste    |

// |   11     |    waste    |   121     |            |   165    |   waste    |

// |   12     |    waste    |   122     |            |   166    |   waste    |

// |   13     |    waste    |   123     |            |   167    |   waste    |

// |   14     |    waste    |   124     |            |   168    |   Obj33    |

// |   15     |    waste    |   125     |            |   169    |            |

// |   16     |    Obj1     |   126     |            |   170    |            |

// |   17     |             |   127     |            |   171    |            |

// |   N      |             |   N       |            |   N      |            |

// +-------------------------------------------------------------------------+

//

// In the above diagram there are three blocks with alignment of 8.

//

// Block one start address is 16 so 6 bytes are skipped (or wasted).

// Block two start address is 120 since it is multiple of 8.

// Block three start address is 68 causing 4 bytes to skip (or wasted).

//

// The block alignment is done by std::align or AlignFreeAddress method.

//

// The block is considered full when the remaining bytes are less than the

// object size. So the remaining bytes in the block are skipped and new block

// created. In our tests for 500 objects of 144 bytes and 4096 bytes block

// about 1024 bytes wasted.

//

// Since objects size is always multiple of alignment, subsequent objects can be

// allocated sequentially in the block. So if the object size is 96 bytes, the

// second object in block 1 will be allocated 112 address in block 1.

//

// A block is allocated using operator new at the time of block initialization

// and start address aligned. See NewBlock();

//

// A block is freed at the time of destruction of the allocator object.

// The allocator takes complete ownership of the objects it allocates, client is

// not responsible for deallocating or destroying the objects allocated by this

// allocator. Allocator will call the destructors of the objects it allocated.

// See ~Allocator() and Destroy() method.

//

// IMPORTANT: Tree like structure must not destroy the child nodes or sibling

// nodes. Allocator destroys all the objects and call its destructor, it is an

// error to invoke destructors on objects allocated by this allocator. Allocator

// is the master owner of all the objects. Client treats all objects as const

// pointer as far as destruction goes.

//

// It is not possible to destroy random objects or free up the slots to be

// re-used for allocation of objects. This allocator is used for html parsing

// which should free up the resources after document parsing. A singleton

// allocator for example will keep growing unless Reset() is called upon each

// new parsing.

//

// Bit shifting syntax used in this source:

// A) To round the block size to nearest page size (4096) multiple:

//    ((block_size - 1) | (page_size - 1) + 1.

//    Examples:

//    - block_size = 3000;

//     (3000 - 1) | (4096 - 1) + 1 = 4096.

//    - block_size = 5000;

//     (5000 - 1) | (4096 - 1) + 1 = 8096.

//

// B) If N is multiple of A.

//    (N & (A - 1)) == 0

//    This can also be achieved by modulo operator N % A == 0.

//    Examples:

//    - 40 is multiple of 8?

//     40 & (8 - 1) == 0;

//    - 62 is multiple of 4?

//     60 & (4 - 1) != 0;

#ifndef CPP_HTMLPARSER_ALLOCATOR_H_

#define CPP_HTMLPARSER_ALLOCATOR_H_

#include <unistd.h>  // For getpagesize()

#include <array>

#include <cstring>

#include <memory>

#include <tuple>

#include <vector>

namespace htmlparser {

template <class T>

class Allocator {

 public:

  explicit Allocator(std::size_t block_size = 0) :

    alignment_(std::alignment_of_v<T>),

    // Rounds the block_size_ to page size multiple.

    // 3000 becomes 4096 and 5000 becomes 8192 for 4k page size OS.

    block_size_(

        ((block_size < 1 ? 0 : block_size - 1) | (getpagesize() - 1)) + 1),

    object_size_(sizeof(T)),

    remaining_(0),

    next_free_(nullptr),

    blocks_allocated_(0),

    block_(nullptr) {}

  ~Allocator() {

    FreeBlocks();

  }

  Allocator(const Allocator&) = delete;

  Allocator& operator=(const Allocator&) = delete;

  // Allocates memory of same size required to construct object of type T.

  // Returns nullptr if alloction failed.

  void* Allocate() {

    // Checks if remaining bytes in block are less than object size, or

    // reamining bytes after alignment is less than object size.

    // Add a new block.

    if (object_size_ > remaining_ || !AlignFreeAddress()) {

      if (!NewBlock()) return nullptr;

    }

    // Get the address for object allocation.

    last_alloc_ = next_free_;

    remaining_ -= object_size_;

    // Move the pointer for next object.

    next_free_ += object_size_;

    return static_cast<void*>(last_alloc_);

  }

  // Allocates memory and constructs the object.

  // Returns nullptr if memory allocation failed.

  template <typename ...Args>

  T* Construct(Args&& ...args) {

    void* mem = Allocate();

    // New object or nullptr if memory allocation failed.

    return mem ? new (mem) T(std::forward<Args>(args)...) : nullptr;

  }

  // Default constructor.

  T* Construct() {

    void* mem = Allocate();

    return mem ? new (mem) T() : nullptr;

  }

  // Deallocates the blocks and restores the allocator for reuse.

  void Reset() {

    FreeBlocks();

    next_free_ = nullptr;

    remaining_ = 0;

  }

  // Used only by test or development environment.

  std::tuple<int /*alignment*/,

             int /*block_size*/,

             int /*object_size*/,

             unsigned char* /*last_alloc*/,

             unsigned char* /*next_free*/,

             std::size_t /*remaining*/,

             uint32_t /*blocks_allocated*/> DebugInfo() const {

    return {alignment_, block_size_, object_size_, last_alloc_, next_free_,

      remaining_, blocks_allocated_};

  }

 private:

  struct Block {

    Block* previous;

    void* buf;

  };

  // Deallocates the blocks.

  void FreeBlocks() {

    Block* current_block = block_;

    bool partial = true;

    while (current_block != nullptr) {

      Block* previous = current_block->previous;

      Destroy(current_block, partial);

      partial = false;

      FreeBlockMemory(current_block);

      delete current_block;

      blocks_allocated_--;

      current_block = previous;

    }

  }

  // Creates a new block.

  bool NewBlock() {

    Block* block = new Block;

    block->previous = block_;

    if (alignment_ <=  __STDCPP_DEFAULT_NEW_ALIGNMENT__) {

      block->buf = ::operator new(block_size_);

    } else {

      block->buf = ::operator new(block_size_, std::align_val_t(alignment_));

    }

    std::memset(block->buf, 0, block_size_);

    // Align the block to alignment boundary.

    //

    // The adjusted space may be lesser than block size.

    std::size_t adjusted_space = block_size_;

    if (alignment_ > 1) {

      if (block->buf = std::align(alignment_, block_size_, block->buf,

                                  adjusted_space);

          block->buf == nullptr) {

        // In case std::align fails, try manual alignment.

        if (!AlignFreeAddress()) {

          return false;

        }

      } else if (adjusted_space < object_size_) {

        return false;

      }

    }

    next_free_ = static_cast<unsigned char*>(block->buf);

    remaining_ = adjusted_space;

    blocks_allocated_++;

    block_ = block;

    return true;

  }

  void FreeBlockMemory(Block* block) {

    if (alignment_ <= __STDCPP_DEFAULT_NEW_ALIGNMENT__) {

      ::operator delete(block->buf, block_size_);

      block->buf = nullptr;

    } else {

      ::operator delete(block->buf, block_size_, std::align_val_t(alignment_));

      block->buf = nullptr;

    }

  }

  // Destroys the T objects allocated and constructed using this block.

  // If the block is only partially consumed, destroys only objects allocated

  // in the partial space.

  void Destroy(Block* block, bool partial_allocation = false) {

    unsigned char* t_ptr = static_cast<unsigned char*>(block->buf);

    unsigned char* block_end = t_ptr + block_size_;

    std::size_t remaining = block_end - t_ptr;

    // All offsets are aligned, so simply increment and destroy.

    if ((object_size_ & (alignment_ - 1)) == 0) {

      while (remaining >= object_size_) {

        reinterpret_cast<T*>(t_ptr)->~T();

        t_ptr += object_size_;

        if (partial_allocation && t_ptr >= next_free_) {

          return;

        }

        remaining -= object_size_;

      }

    }

  }

  // If the block's address is not aligned, moves the pointer to the address

  // that is multiple of aligment_.

  bool AlignFreeAddress() {

    // Checks how many bytes to skip to be at the correct alignment.

    if (const std::size_t skip =

            reinterpret_cast<std::size_t>(next_free_) & (alignment_ - 1);

        skip > 0) {

      auto waste = remaining_ - skip;

      if (waste >= remaining_) return false;

      next_free_ += waste;

      remaining_ -= waste;

    }

    return true;

  }

  const std::size_t alignment_;

  const std::size_t block_size_;

  const std::size_t object_size_;

  std::size_t remaining_;

  unsigned char* last_alloc_;

  unsigned char* next_free_;

  uint32_t blocks_allocated_;

  Block* block_;

};

}  // namespace htmlparser

#endif  // CPP_HTMLPARSER_ALLOCATOR_H_