* utils/storage.H (Memory::Storage::acquire): Remove.

	(Memory::SinglyLinkedStorage::acquire): Likewise.
	(Memory::DoublyLinkedStorage): New.
	* utils/storage.cc (acquire_storage_with_header): Rename from
	Storage::acquire.  Make template.
	(OneWayLinkHeader): Rename from SingleLinkHeader.
	(TwoWayLinkHeader): New.

3 files changed, 82 insertions, 32 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index 05e121b9..c6a536ef 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,13 @@
+2011-06-20  Gabriel Dos Reis  <gdr@cs.tamu.edu>
+
+	* utils/storage.H (Memory::Storage::acquire): Remove.
+	(Memory::SinglyLinkedStorage::acquire): Likewise.
+	(Memory::DoublyLinkedStorage): New.
+	* utils/storage.cc (acquire_storage_with_header): Rename from
+	Storage::acquire.  Make template.
+	(OneWayLinkHeader): Rename from SingleLinkHeader.
+	(TwoWayLinkHeader): New.
+
 2011-06-15  Gabriel Dos Reis  <gdr@cs.tamu.edu>
 
 	* lib/fnct_key.c (handle_function_key): Explicitly cast the
diff --git a/src/utils/storage.H b/src/utils/storage.H
index ab334abb..72b9eb1e 100644
--- a/src/utils/storage.H
+++ b/src/utils/storage.H
@@ -77,7 +77,7 @@ namespace OpenAxiom {
       Pointer os_acquire_raw_memory(size_t);
 
       // Release raw storage to the hosting OS.  The first operand must
-      // be a pointer value previous returned by `os_acquire_raw_memory'.
+      // be a pointer value previously returned by `os_acquire_raw_memory'.
       // Otherwise, the result is undefined.
       void os_release_raw_memory(Pointer, size_t);
 
@@ -96,24 +96,20 @@ namespace OpenAxiom {
       // -------------
       // -- Storage --
       // -------------
-      // This class is a low-level abstraction intented for use
-      // to implement higher level storage abstraction.
+      // This class provides low-level abstractions intented for use
+      // to implement higher level storage abstractions.
       struct Storage {
-         // Objects of this sbstract datatype holds storage objects.
+         // Objects of this abstract datatype hold 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(Handle*);
          
-         // Return the start address of storage area.
+         // Return the start address of storage area.  Clients would
+         // want to add padding bytes necessary to accomodate alignment
+         // requirements.  
          // Note: this should not be confused with the address of
          // the handle object.
          static Pointer begin(Handle*);
@@ -134,14 +130,28 @@ namespace OpenAxiom {
       // -- SinglyLinkedStorage --
       // -------------------------
       // This class implements a simple single-linked list of storage
-      // objects.
+      // objects.  Each storage object in the link is created with
+      // a specific starting alignment requirements.
       struct SinglyLinkedStorage : Storage {
-         // Same as Storage::acquire, except begin(h) returns an address
-         // that satisfies the alignment requirement `a'.
+         // Return the previous handle in the link chain.
+         static Handle*& previous(Handle*);
+      };
+
+      // -------------------------
+      // -- DoublyLinkedStorage --
+      // -------------------------
+      // Like SinglyLinkedStorage, except that the chain of storage
+      // object supports bidirectional travervsal.
+      struct DoublyLinkedStorage : Storage {
+         // Same as Storage::acquire, except that begin(h) returns an
+         // address that satisfies the alignment requirement `a'.
          static Handle* acquire(size_t n, size_t a);
          
          // Return the previous handle in the link chain.
          static Handle*& previous(Handle*);
+         
+         // Return the next handle in the link chain.
+         static Handle*& next(Handle*);
       };
 
       // ------------------
diff --git a/src/utils/storage.cc b/src/utils/storage.cc
index f7c2aec3..4f5fc67c 100644
--- a/src/utils/storage.cc
+++ b/src/utils/storage.cc
@@ -131,8 +131,8 @@ namespace OpenAxiom {
       // -- Storage --
       // -------------
       struct Storage::Handle {
-         size_t extent;
-         void* start;
+         size_t extent;         // count of allocated bytes
+         void* start;           // beginning of usable address.
       };
 
       static inline Pointer
@@ -140,11 +140,15 @@ namespace OpenAxiom {
          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));
+      // 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.
+      template<typename T>
+      static T*
+      acquire_storage_with_header(size_t n) {
+         n = Storage::round_up(n, page_size());
+         T* h = static_cast<T*>(os_acquire_raw_memory(n));
          h->extent = n;
          h->start = h + 1;
          return h;
@@ -163,28 +167,54 @@ namespace OpenAxiom {
       // -------------------------
       // -- SinglyLinkedStorage --
       // -------------------------
-      struct SingleLinkHeader : Storage::Handle {
+      struct OneWayLinkHeader : Storage::Handle {
          Handle* previous;
       };
       
       SinglyLinkedStorage::Handle*&
       SinglyLinkedStorage::previous(Handle* h) {
-         return static_cast<SingleLinkHeader*>(h)->previous;
+         return static_cast<OneWayLinkHeader*>(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);
+      // -------------------------
+      // -- DoublyLinkedStorage --
+      // -------------------------
+      struct TwoWayLinkHeader : Storage::Handle {
+         Handle* previous;
+         Handle* next;
+      };
+
+      static inline TwoWayLinkHeader*
+      two_way_link(Storage::Handle* h) {
+         return static_cast<TwoWayLinkHeader*>(h);
+      }
+
+      DoublyLinkedStorage::Handle*&
+      DoublyLinkedStorage::previous(Handle* h) {
+         return two_way_link(h)->previous;
+      }
+
+      DoublyLinkedStorage::Handle*&
+      DoublyLinkedStorage::next(Handle* h) {
+         return two_way_link(h)->next;
+      }
+
+      DoublyLinkedStorage::Handle*
+      DoublyLinkedStorage::acquire(size_t n, size_t a) {
+         // Add enough padding space for specified alignment.
+         const size_t overhead = round_up(sizeof (TwoWayLinkHeader), a);
+         TwoWayLinkHeader* h =
+            acquire_storage_with_header<TwoWayLinkHeader>(overhead + n);
          h->start = byte_address (h) + overhead;
-         previous(h) = 0;
+         h->previous = 0;
+         h->next = 0;
          return h;
       }
 
       // ------------------
       // -- BlockStorage --
       // ------------------
-      struct BlockHeader : SingleLinkHeader {
+      struct BlockHeader : OneWayLinkHeader {
          Byte* available;
       };
 
@@ -196,13 +226,13 @@ namespace OpenAxiom {
       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));
+         BlockHeader* h =
+            acquire_storage_with_header<BlockHeader>(overhead + n);
          // 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;
+         h->previous = 0;
          return h;
       }