1 files changed, 167 insertions, 0 deletions
diff --git a/examples/cxx/hybrid/allocator/arena.cxx b/examples/cxx/hybrid/allocator/arena.cxx
new file mode 100644
index 0000000..facb852
--- /dev/null
+++ b/examples/cxx/hybrid/allocator/arena.cxx
@@ -0,0 +1,167 @@
+// file      : examples/cxx/hybrid/allocator/arena.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : not copyrighted - public domain
+
+#include <stdio.h>
+#include <string.h> // memcpy
+
+#include "arena.hxx"
+
+arena::
+arena (void* memory, size_t size)
+    : alloc_count_ (0),
+      realloc_count_ (0),
+      free_count_ (0),
+      cur_allocated_ (0),
+      max_allocated_ (0)
+{
+  head_ = static_cast<block*> (memory);
+  head_->cap  = size - sizeof (block);
+  head_->next = 0;
+  head_->used = false;
+}
+
+void* arena::
+allocate (size_t size)
+{
+  block* b = head_;
+
+  while (b != 0)
+  {
+    if (!b->used)
+    {
+      if (b->cap >= size)
+      {
+        // See if it makes sense to fragment this block.
+        //
+        if (b->cap - size >= sizeof (block) * 2)
+        {
+          block* b1 = reinterpret_cast<block*> (
+            reinterpret_cast<char*> (b) + sizeof (block) + size);
+
+          b1->cap = b->cap - size - sizeof (block);
+          b1->next = b->next;
+          b1->used = false;
+
+          b->next = b1;
+          b->cap = size;
+        }
+
+        b->used = true;
+        b->size = size;
+
+        alloc_count_++;
+        cur_allocated_ += size;
+
+        if (cur_allocated_ > max_allocated_)
+          max_allocated_ = cur_allocated_;
+
+        return b + 1;
+      }
+
+      // This block is not big enough. See if we can merge it
+      // with the next block.
+      //
+      if (b->next != 0 && !b->next->used)
+      {
+        block* b1 = b->next;
+        b->cap += b1->cap + sizeof (block);
+        b->next = b1->next;
+
+        // Try the merged block again.
+        //
+        continue;
+      }
+    }
+
+    // This block is either in use or not big enough. Continue
+    // searching.
+    //
+    b = b->next;
+  }
+
+  return 0;
+}
+
+void* arena::
+reallocate (void* p, size_t size)
+{
+  // If the passed pointer is NULL, reallocate is equivalent to
+  // allocate.
+  //
+  if (!p)
+    return allocate (size);
+
+  block* b = static_cast<block*> (p) - 1;
+
+  // If the passed size is NULL, reallocate is equivalent to free.
+  //
+  if (size == 0)
+  {
+    free (p);
+    return 0;
+  }
+
+  // If this block is not large enough to satisfy the request, try to
+  // merge it with the next block(s).
+  //
+  while (b->cap < size && b->next != 0 && !b->next->used)
+  {
+    block* b1 = b->next;
+    b->cap += b1->cap + sizeof (block);
+    b->next = b1->next;
+  }
+
+  // If this block is now large enough then we can reuse the same
+  // memory region.
+  //
+  if (b->cap >= size)
+  {
+    realloc_count_++;
+    cur_allocated_ += size - b->size;
+
+    if (cur_allocated_ > max_allocated_)
+      max_allocated_ = cur_allocated_;
+
+    b->size = size;
+    return p;
+  }
+
+  // Otherwise allocate a new block and copy the data over.
+  //
+  void* r = allocate (size);
+
+  if (r)
+  {
+    memcpy (r, p, b->size);
+    free (p);
+  }
+
+  return r;
+}
+
+void arena::
+free (void* p)
+{
+  if (p)
+  {
+    block* b = static_cast<block*> (p) - 1;
+
+    cur_allocated_ -= b->size;
+    free_count_++;
+
+    b->used = false;
+  }
+}
+
+void arena::
+print_statistics ()
+{
+  printf ("\n");
+  printf ("allocations:      %lu\n", alloc_count_);
+  printf ("reallocations:    %lu\n", realloc_count_);
+  printf ("deallocations:    %lu\n", free_count_);
+  printf ("currently in use: %lu bytes\n", cur_allocated_);
+  printf ("maximum in use:   %lu bytes\n", max_allocated_);
+  printf ("\n");
+}