* utils/storage.H: Rework.

	* utils/storage.cc: Likewise.

3 files changed, 177 insertions, 151 deletions

diff --git a/src/utils/Makefile.in b/src/utils/Makefile.in
index 764bda0f..e4211f62 100644
--- a/src/utils/Makefile.in
+++ b/src/utils/Makefile.in
@@ -87,7 +87,7 @@ stamp-headers: $(libOpenAxiom_HEADERS) Makefile
 	done ; \
 	$(STAMP) stamp-headers
 
-hammer$(EXEEXT): $(hammer_OBJECTS) libOpenAxiom.$(LIBEXT)
+hammer$(EXEEXT): $(bin_PROGRAMS) libOpenAxiom.$(LIBEXT)
 	$(CXXLINK) -o $@ $(hammer_OBJECTS)  $(hammer_LDADD) $(LDFLAGS)
 
 libOpenAxiom.$(LIBEXT): $(libOpenAxiom_OBJECTS)
diff --git a/src/utils/storage.H b/src/utils/storage.H
index 29da96eb..ab334abb 100644
--- a/src/utils/storage.H
+++ b/src/utils/storage.H
@@ -1,4 +1,4 @@
-// Copyright (C) 2010, Gabriel Dos Reis.
+// Copyright (C) 2010-2011, Gabriel Dos Reis.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
@@ -52,7 +52,7 @@ namespace OpenAxiom {
    // Objects of (type derived from) this type are used to report
    // error orignating from the OpenAxiom core system.
    struct SystemError {
-      explicit SystemError(std::string);
+      explicit SystemError(const std::string&);
       virtual ~SystemError();
       // Return the text of the diagnostic message.
       virtual const std::string& message() const;
@@ -61,7 +61,7 @@ namespace OpenAxiom {
    };
 
    // Report a file system error
-   void filesystem_error(std::string);
+   void filesystem_error(const std::string&);
    
    namespace Memory {
       // Datatype for the unit of storage.
@@ -99,44 +99,28 @@ namespace OpenAxiom {
       // This class is a low-level abstraction intented for use
       // to implement higher level storage abstraction.
       struct Storage {
-         // Acquire storage chunk of at least `n' bytes, and align
-         // the first allocatable address to `a' boundary.
-         // The result is a pointer to a storage object.  That object
-         // `result' is constructed such that `result->free' points
-         // to the next allocatable address, with alignment `a'.
-         // After allocation, the real capacity of the allocated
-         // object is reported by `result->capacity()'.
-         static Storage* acquire(size_t a, size_t n);
+         // Objects of this sbstract datatype holds storage objects.
+         struct Handle;
          
+         // Acquire storage chunk of at least `n' bytes.
+         // The result is a pointer to a storage object.  That object
+         // `result' is constructed such that `begin(result)' points
+         // to the next allocatable address.
+         static Handle* acquire(size_t n);
+
          // Return the storage pointed to by the operand.  It
          // must be a pointer value previously returned by `acquire'.
          // Otherwise, the result is undefined.
-         static void release(Storage*);
-
-         // Count of bytes that can fit in this storage.
-         size_t capacity() const { return limit_bot - limit_top; }
-
-         // Count of available allocatable bytes in this storage.
-         size_t room() const { return limit_bot - free; }
-
-         // Count of used bytes in this storage.
-         size_t occupancy() const { return free - limit_top; }
-
-         // Align next allocatable address to boundary given by operand.
-         // Return true on success, otherwise false.
-         bool align_to(size_t);
-
-         // Allocate `n' bytes from this storage.  It is assumed that prior
-         // to calling this function, `n' is less than `room()'.
-         // The allocated storage is guaranteed to contain only zeros.
-         void* allocate(size_t);
-
-         // Next unused address
-         void* next_available() { return free; }
-
-         // address at offset `off' from the first allocatable address.
-         void* at_offset(size_t off) {
-            return limit_top + off;
+         static void release(Handle*);
+         
+         // Return the start address of storage area.
+         // Note: this should not be confused with the address of
+         // the handle object.
+         static Pointer begin(Handle*);
+
+         // Courtesy conversion function from pointer to byte address.
+         static Byte* byte_address(Pointer h) {
+            return static_cast<Byte*>(h);
          }
 
          // Round up `n' to a multiple of `a', a power of 2.
@@ -144,35 +128,41 @@ namespace OpenAxiom {
          round_up(size_t n, size_t a) {
             return (n + a - 1) & ~(a - 1);
          }
+      };
 
-         // Next address after `p' in this storage that has alignment `a'.
-         void*
-         round_up(void* p, size_t a) {
-            return base() + round_up(base() - static_cast<Byte*>(p), a);
-         }
+      // -------------------------
+      // -- SinglyLinkedStorage --
+      // -------------------------
+      // This class implements a simple single-linked list of storage
+      // objects.
+      struct SinglyLinkedStorage : Storage {
+         // Same as Storage::acquire, except begin(h) returns an address
+         // that satisfies the alignment requirement `a'.
+         static Handle* acquire(size_t n, size_t a);
          
-      protected:
-         Byte* limit_top;       // first allocatable address
-         Byte* limit_bot;       // one-past-the-end of valid allocatable
-                                // address in this storage.
-         Byte* free;            // first allocatable address suitably
-                                // aligned at boundary specified at
-                                // construction time.
-
-         Storage() { }
-
-         // Address of the host OS page holding this storage.
-         Byte* base() {
-            return reinterpret_cast<Byte*>(this);
-         }
-
-         size_t extent() {
-            return size_t(limit_bot - base());
-         }
+         // Return the previous handle in the link chain.
+         static Handle*& previous(Handle*);
+      };
 
-      private:
-         Storage(const Storage&); // not implemented
-         Storage& operator=(const Storage&); // idem.
+      // ------------------
+      // -- BlockStorage --
+      // ------------------
+      // This class implements a simple single-linked list of block storage.
+      // Each block maintains information about the next allocatable
+      // address within that block.
+      struct BlockStorage : SinglyLinkedStorage {
+         // Same as SinglyLinkedStorage::acquire(); initialize internal
+         // bookkeepking machinery.
+         static Handle* acquire(size_t n, size_t a);
+
+         // Return the next allocatable address within the given block.
+         static Pointer next_address(Handle*);
+
+         // Return the amount of allocatable byte in the given block.
+         static size_t room(Handle*);
+
+         // Set `n' bytes aside with the given storage block.
+         static Pointer book(Handle*, size_t);
       };
 
       // -----------
@@ -184,7 +174,7 @@ namespace OpenAxiom {
       // it is guaranteed that objects allocated in a single call
       // to `allocate()' occupy a contiguous block of storage.
       template<typename T>
-      struct Arena {
+      struct Arena : protected BlockStorage {
          // Acquire storage capable of holding `n' objects of type `T'.
          explicit Arena(size_t);
          // Release all storage acquired by this object, upon end of life.
@@ -196,39 +186,29 @@ namespace OpenAxiom {
 
       protected:
          // Address of the first object of type `T' in a storage.
-         static T* first_object(Storage* s) {
-            return static_cast<T*>
-               (s->round_up(&previous(s) + 1, openaxiom_alignment(T)));
+         static T* first_object(Handle* h) {
+            return static_cast<T*>(BlockStorage::begin(h));
          }
 
          // Address of one-past-the-end object of type `T' in this storage.
-         static T* last_object(Storage* s) {
-            return static_cast<T*>(s->next_available());
+         static T* last_object(Handle* h) {
+            return static_cast<T*>(BlockStorage::next_address(h));
          }
 
          // Number of objects allocated in a storage.
-         static size_t object_count(Storage* s) {
-            return last_object(s) - first_object(s);
-         }
-
-         // The `previous' link in the chain of storage.
-         static Storage*& previous(Storage* s) {
-            return *static_cast<Storage**>(s->at_offset(0));
+         static size_t object_count(Handle* h) {
+            return last_object(h) - first_object(h);
          }
 
-         Storage* store;        // active storage to allocate from
-
-      private:
-         // Acquire storage large enough to hold `n' objects of type `T'.
-         static Storage* acquire(size_t);
+         BlockStorage::Handle* store; // active storage to allocate from
       };
 
       template<typename T>
       size_t
       Arena<T>::population() const {
          size_t n = 0;
-         for (Storage* s = store; s != 0; s = previous(s))
-            n += object_count(s);
+         for (Handle* h = store; h != 0; h = previous(h))
+            n += object_count(h);
          return n;
       }
 
@@ -236,48 +216,41 @@ namespace OpenAxiom {
       T*
       Arena<T>::allocate(size_t n) {
          const size_t sz = n * sizeof(T);
-         if (store->room() < sz) {
-            Storage* s = acquire(std::max(n, object_count(store)));
-            previous(s) = store;
-            store = s;
+         if (BlockStorage::room(store) < sz) {
+            // Not enough room left.  Make sure we allocate storage
+            // at least as big as the current.
+            Handle* h = acquire(std::max(n, object_count(store)),
+                                openaxiom_alignment(T));
+            previous(h) = store;
+            store = h;
          }
-         return static_cast<T*>(store->allocate(sz));
+         return static_cast<T*>(BlockStorage::book(store, sz));
       }
 
       template<typename T>
-      Arena<T>::Arena(size_t n) : store(acquire(n)) { }
+      Arena<T>::Arena(size_t n)
+            : store(BlockStorage::acquire(n * sizeof (T),
+                                          openaxiom_alignment (T)))
+      { }
       
       template<typename T>
       Arena<T>::~Arena() {
          // Release storage in the reverse order of their
          // their allocation.
          while (store != 0) {
-            Storage* current = store;
-            store = previous(store);
-            Storage::release(current);
+            Handle* current = store;
+            store = BlockStorage::previous(store);
+            BlockStorage::release(current);
          }
       }
 
-      template<typename T>
-      Storage*
-      Arena<T>::acquire(size_t n) {
-         // We build single-linked list of Storage objects, so 
-         // don't forget to account for the additional pointer,
-         // and necessary padding.
-         const size_t sz = n * sizeof(T)
-            + Storage::round_up(sizeof(Storage*), openaxiom_alignment(T));
-         Storage* s = Storage::acquire(openaxiom_alignment(Storage*), sz);
-         s->allocate(sizeof(Storage*));
-         previous(s) = 0;
-         s->align_to(openaxiom_alignment(T));
-         return s;
-      }
-
       // -------------
       // -- Factory --
       // -------------
       template<typename T>
       struct Factory : Arena<T> {
+         typedef typename Arena<T>::Handle Handle;
+
          Factory() : Arena<T>(nominal_population()) { }
          ~Factory();
 
@@ -307,21 +280,17 @@ namespace OpenAxiom {
       private:
          // Return 1 or the number of objects that can fit in a page unit.
          static size_t nominal_population() {
-            const size_t overhead =
-               Storage::round_up(sizeof(Storage),
-                                  openaxiom_alignment(Storage*))
-               + Storage::round_up(sizeof(Storage*), openaxiom_alignment(T));
             const size_t psz = page_size();
-            if (overhead + sizeof (T) > psz)
+            if (sizeof (T) > psz)
                return 1;
-            return (psz - overhead) / sizeof(T);
+            return psz / sizeof(T);
          }
       };
 
       // Destroy objects in the reverse order of their construction.
       template<typename T>
       Factory<T>::~Factory() {
-         for (Storage* s = this->store; s != 0; s = Arena<T>::previous(s)) {
+         for (Handle* s = this->store; s != 0; s = Arena<T>::previous(s)) {
             T* last = Arena<T>::last_object(s);
             for (--last; last >= Arena<T>::first_object(s); --last)
                last->~T();
diff --git a/src/utils/storage.cc b/src/utils/storage.cc
index 0bd9265d..f7c2aec3 100644
--- a/src/utils/storage.cc
+++ b/src/utils/storage.cc
@@ -1,4 +1,4 @@
-// Copyright (C) 2010, Gabriel Dos Reis.
+// Copyright (C) 2010-2011, Gabriel Dos Reis.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
@@ -62,7 +62,7 @@ namespace OpenAxiom {
    // ----------------
    // -- SystemError --
    // ----------------
-   SystemError::SystemError(std::string s) : text(s) { }
+   SystemError::SystemError(const std::string& s) : text(s) { }
 
    SystemError::~SystemError() { }
 
@@ -72,7 +72,7 @@ namespace OpenAxiom {
    }
 
    void
-   filesystem_error(std::string s) {
+   filesystem_error(const std::string& s) {
       throw SystemError(s);
    }
 
@@ -130,43 +130,100 @@ namespace OpenAxiom {
       // -------------
       // -- Storage --
       // -------------
-      Storage*
-      Storage::acquire(size_t alignment, size_t byte_count) {
-         // Adjust for overhead, and page boundary.
-         byte_count = round_up(byte_count + sizeof(Storage), page_size());
-         Storage* mem = new(os_acquire_raw_memory(byte_count)) Storage;
-         mem->limit_top = mem->base() + round_up(sizeof(Storage), alignment);
-         mem->limit_bot = mem->base() + byte_count;
-         mem->free = mem->limit_top;
-         return mem;
+      struct Storage::Handle {
+         size_t extent;
+         void* start;
+      };
+
+      static inline Pointer
+      storage_end(Storage::Handle* h) {
+         return Storage::byte_address(h) + h->extent;
+      }
+
+      Storage::Handle*
+      Storage::acquire(size_t n) {
+         // Adjust for overhead, and to page boundary.
+         n = round_up(n + sizeof(Handle), page_size());
+         Handle* h = static_cast<Handle*>(os_acquire_raw_memory(n));
+         h->extent = n;
+         h->start = h + 1;
+         return h;
       }
 
       void
-      Storage::release(Storage* store) {
-         os_release_raw_memory(store, store->extent());
-      }
-
-      void*
-      Storage::allocate(size_t n) {
-         void* result = free;
-         free += n;
-         return memset(result, 0, n);
-      }
-
-      bool
-      Storage::align_to(size_t alignment) {
-         if (alignment == 0)    // protect against nuts
-            return true;
-         if (alignment == 1)    // no preferred alignment at all
-            return true;
-         Byte* b = base();
-         const size_t offset = round_up(free - b, alignment);
-         if (offset < size_t(limit_bot - b)) {
-            free = b + offset;
-            return true;
-         }
-         return false;          // not enough room left
+      Storage::release(Handle* h) {
+         os_release_raw_memory(h, h->extent);
+      }
+
+      Pointer
+      Storage::begin(Handle* h) {
+         return h->start;
+      }
+
+      // -------------------------
+      // -- SinglyLinkedStorage --
+      // -------------------------
+      struct SingleLinkHeader : Storage::Handle {
+         Handle* previous;
+      };
+      
+      SinglyLinkedStorage::Handle*&
+      SinglyLinkedStorage::previous(Handle* h) {
+         return static_cast<SingleLinkHeader*>(h)->previous;
+      }
+
+      SinglyLinkedStorage::Handle*
+      SinglyLinkedStorage::acquire(size_t n, size_t a) {
+         const size_t overhead = round_up(sizeof (SingleLinkHeader), a);
+         Handle* h = Storage::acquire(overhead + n);
+         h->start = byte_address (h) + overhead;
+         previous(h) = 0;
+         return h;
+      }
+
+      // ------------------
+      // -- BlockStorage --
+      // ------------------
+      struct BlockHeader : SingleLinkHeader {
+         Byte* available;
+      };
+
+      static inline BlockHeader*
+      block_header(BlockStorage::Handle* h) {
+         return static_cast<BlockHeader*>(h);
+      }
+
+      BlockStorage::Handle*
+      BlockStorage::acquire(size_t n, size_t a) {
+         const size_t overhead = round_up(sizeof (BlockHeader), a);
+         // Tell SinglyLinkedStorage not to align; we do that here.
+         BlockHeader* h = block_header
+            (SinglyLinkedStorage::acquire(overhead + n, 1));
+         // Remember the next available address to allocate from.
+         h->available = byte_address(h) + overhead;
+         // That is also where the actual object storage starts.
+         h->start = h->available;
+         return h;
+      }
+
+      Pointer
+      BlockStorage::next_address(Handle* h) {
+         return block_header(h)->available;
+      }
+
+      size_t
+      BlockStorage::room(Handle* h) {
+         return byte_address(storage_end(h)) - block_header(h)->available;
+      }
+
+      Pointer
+      BlockStorage::book(Handle* h, size_t n) {
+         BlockHeader* block = block_header(h);
+         void* const p = block->available;
+         block->available += n;
+         return p;
       }
+      
 
       // -----------------
       // -- FileMapping --