Implement an s-expression C++ library.

	* utils/hash-table.H: New.
	* utils/sexpr.H: Likewise.
	* utils/sexpr.cc: Likewise.
	* utils/string-pool.H: Likewise.
	* utils/string-pool.cc: Likewise.
	* utils/storage.H: Include openaxiom-c-macros.h
	(Memory::Storage): New.
	(Memory::Arena): Likewise.
	* utils/storage.cc: Implement member functions of new class.
	* utils/Makefile.in (libOpenAxiom_HEADERS): Include hash-table.H,
	string-pool.H, and sexpr.H
	(libOpenAxiom_SOURCES): Include string-pool.cc and sexpr.cc

1 files changed, 82 insertions, 0 deletions

diff --git a/src/utils/hash-table.H b/src/utils/hash-table.H
new file mode 100644
index 00000000..75b485ff
--- /dev/null
+++ b/src/utils/hash-table.H
@@ -0,0 +1,82 @@
+// Copyright (C) 2010, Gabriel Dos Reis.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     - Redistributions of source code must retain the above copyright
+//       notice, this list of conditions and the following disclaimer.
+//
+//     - Redistributions in binary form must reproduce the above copyright
+//       notice, this list of conditions and the following disclaimer in
+//       the documentation and/or other materials provided with the
+//       distribution.
+//
+//     - Neither the name of The Numerical Algorithms Group Ltd. nor the
+//       names of its contributors may be used to endorse or promote products
+//       derived from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef OPENAXIOM_HASH_TABLE_INCLUDED
+#define OPENAXIOM_HASH_TABLE_INCLUDED
+
+// --% Author: Gabriel Dos Reis.
+// --% Description:
+// --%   Simple hash table facility.  To be replaced by C++0x
+// --%   hash tables when C++0x compilers become common place.
+
+#include "storage.H"
+
+namespace OpenAxiom {
+   // --------------------
+   // -- HashTableEntry --
+   // --------------------
+   // Datatype for entries in a parameterized hash table.
+   // The type parameter is required to be a value-construcitble datatype.
+   template<typename T>
+   struct HashTableEntry : T {
+      HashTableEntry* chain;   // previous item in the same bucket chain
+      size_t hash;             // hash code of stored data
+   };
+
+   // --------------------
+   // -- BasicHashTable --
+   // --------------------
+   // A simple hash table data structure.  Ideally, we would like to use
+   // standard C++ types, but hash tables were only in a C++ 2003 TR,
+   // officially part of C++0x standard library.  We still don't have
+   // wide-spread C++0x compilers.
+   template<typename T>
+   struct BasicHashTable : private Memory::Arena<HashTableEntry<T> > {
+      typedef HashTableEntry<T> EntryType;
+      explicit BasicHashTable(size_t n)
+            : Memory::Arena<HashTableEntry<T> >(n),
+              buckets(this->allocate(n)), nbuckets(n) { }
+
+      EntryType* hash_chain(size_t h) const {
+         return buckets + (h % nbuckets);
+      }
+
+      EntryType* new_bucket() {
+         return this->allocate(1);
+      }
+
+   private:
+      HashTableEntry<T>* const buckets;
+      const size_t nbuckets;
+   };
+}
+
+#endif  // OPENAXIOM_HASH_TABLE_INCLUDED