[Assorted-commits] SF.net SVN: assorted:[1267] cpp-commons/trunk/src

[<yan...@us...>]

Revision: 1267
          http://assorted.svn.sourceforge.net/assorted/?rev=1267&view=rev
Author:   yangzhang
Date:     2009-03-07 21:18:08 +0000 (Sat, 07 Mar 2009)

Log Message:
-----------
- added iterators and a bunch of other standards-conforming features to
  fast_map
- added fast_map tests

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/fast_map.h

Added Paths:
-----------
    cpp-commons/trunk/src/test/fast_map.cc

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:15:20 UTC (rev 1266)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:18:08 UTC (rev 1267)
@@ -1,16 +1,120 @@
 #ifndef COMMONS_DENSE_HASH_MAP_H
 #define COMMONS_DENSE_HASH_MAP_H
 
-#include <backward/hash_fun.h>
+#include <boost/functional/hash.hpp>
 #include <cassert>
 #include <commons/array.h>
+#include <commons/exceptions.h>
 #include <utility>
 
 namespace commons {
 
+  using namespace boost;
   using namespace std;
-  using namespace __gnu_cxx;
 
+  // TODO write unit tests
+
+  template<typename Key, typename Data> class fast_map;
+  template<typename map_traits> class fast_map_iterator;
+  template<typename map_traits> class fast_map_const_iterator;
+
+  template<typename Key, typename Data>
+  struct fast_map_traits
+  {
+    typedef fast_map<Key, Data> map_type;
+    typedef Key key_type;
+    typedef Data data_type;
+    typedef pair<key_type, data_type> value_type;
+    typedef fast_map_traits<Key, Data> traits;
+
+    typedef value_type &reference;
+    typedef const value_type &const_reference;
+    typedef value_type *pointer;
+    typedef const value_type *const_pointer;
+    typedef fast_map_iterator<traits> iterator;
+    typedef fast_map_const_iterator<traits> const_iterator;
+    typedef size_t size_type;
+    typedef ptrdiff_t difference_type;
+  };
+
+  template<typename map_traits>
+  class fast_map_const_iterator
+  {
+  public:
+    typedef typename map_traits::map_type map_type;
+    typedef typename map_traits::iterator iterator;
+    typedef typename map_traits::const_iterator const_iterator;
+    typedef typename map_traits::value_type value_type;
+    typedef typename map_traits::reference reference;
+    typedef typename map_traits::const_reference const_reference;
+    typedef typename map_traits::pointer pointer;
+    typedef typename map_traits::const_pointer const_pointer;
+    typedef typename map_traits::size_type size_type;
+    typedef typename map_traits::difference_type difference_type;
+    typedef forward_iterator_tag iterator_category;
+  private:
+    const map_type &m;
+    const value_type *p;
+    const value_type *end;
+  public:
+    fast_map_const_iterator(const map_type &m, const value_type *p)
+      : m(m), p(p), end(m.get_table().end()) { increment(); }
+    void increment() { for (; p != end && m.empty_or_deleted(p->first); ++p) {} }
+    const_iterator &operator++() {
+      ++p;
+      increment();
+      return *this;
+    }
+    const_iterator operator++(int) {
+      fast_map_const_iterator copy = *this;
+      ++*this;
+      return copy;
+    }
+    const_reference operator*() const { return *p; }
+    const_pointer operator->() const { return p; }
+    bool operator==(const const_iterator &it) const { return p == it.p; }
+    bool operator!=(const const_iterator &it) const { return p != it.p; }
+  };
+
+  template<typename map_traits>
+  class fast_map_iterator
+  {
+  public:
+    typedef typename map_traits::map_type map_type;
+    typedef typename map_traits::iterator iterator;
+    typedef typename map_traits::const_iterator const_iterator;
+    typedef typename map_traits::value_type value_type;
+    typedef typename map_traits::reference reference;
+    typedef typename map_traits::const_reference const_reference;
+    typedef typename map_traits::pointer pointer;
+    typedef typename map_traits::const_pointer const_pointer;
+    typedef typename map_traits::size_type size_type;
+    typedef typename map_traits::difference_type difference_type;
+    typedef forward_iterator_tag iterator_category;
+  private:
+    map_type &m;
+    value_type *p;
+    value_type *end;
+  public:
+    fast_map_iterator(map_type &m, value_type *p)
+      : m(m), p(p), end(m.get_table().end()) { increment(); }
+    void increment() { for (; p != end && m.empty_or_deleted(p->first); ++p) {} }
+    iterator &operator++() {
+      ++p;
+      increment();
+      return *this;
+    }
+    iterator operator++(int) {
+      fast_map_iterator copy = *this;
+      ++*this;
+      return copy;
+    }
+    reference operator*() const { return *p; }
+    pointer operator->() const { return p; }
+    bool operator==(const iterator &it) const { return p == it.p; }
+    bool operator!=(const iterator &it) const { return p != it.p; }
+  };
+
   /**
    * Quadratic internal probing with triangular numbers, a la
    * google::dense_hash_map.  Took the overall design from
@@ -24,66 +128,147 @@
    * ability to serialize just a certain range of the fast_map is also
    * important.
    */
-  // TODO someday: template <typename K, typename V>
+  template <typename Key, typename Data>
   class fast_map
   {
+    public:
+      typedef fast_map_traits<Key, Data> traits;
+      typedef typename traits::map_type map_type;
+      typedef typename traits::iterator iterator;
+      typedef typename traits::const_iterator const_iterator;
+      typedef typename traits::key_type key_type;
+      typedef typename traits::data_type data_type;
+      typedef typename traits::value_type value_type;
+      typedef typename traits::reference reference;
+      typedef typename traits::const_reference const_reference;
+      typedef typename traits::pointer pointer;
+      typedef typename traits::const_pointer const_pointer;
+
     private:
-      static const size_t initsize = 1<<20;
-      typedef pair<int, int> entry;
-      commons::array<entry> table;
-      int empty_key, deleted_key;
+      static const size_t initsize = 1 << 20;
+      commons::array<value_type> table;
+      key_type empty_key, deleted_key;
       size_t count;
-      hash<int> hasher;
+      boost::hash<key_type> hasher;
+      bool has_empty_key, has_deleted_key;
+
       void resize(size_t size) {
-        commons::array<entry> tmp(size);
-        // TODO faster?
+        commons::array<value_type> newtab(0);
+        newtab.reset(reinterpret_cast<value_type*>(new char[size * sizeof(value_type)]), size);
         for (size_t i = 0; i < size; ++i)
-          tmp[i].first = empty_key;
-        swap(table, tmp);
+          newtab[i].first = empty_key;
         // Rehash old values over into new table.
-        size_t mask = table.size() - 1;
-        for (size_t i = 0; i < tmp.size(); ++i) {
-          if (tmp[i].first != empty_key && tmp[i].first != deleted_key) {
+        size_t mask = newtab.size() - 1;
+        for (size_t i = 0; i < table.size(); ++i) {
+          if (table[i].first != empty_key && table[i].first != deleted_key) {
             // Don't want to simply reuse the general lookup, since we know
             // we're starting with a blank slate.
-            size_t pos = hasher(tmp[i].first) & mask;
+            size_t pos = hasher(table[i].first) & mask;
             for (size_t probe = 0;
-                 table[pos].first != empty_key;
-                 ++probe, pos = (pos + probe) & mask) {
-              assert(probe < table.size());
+                 newtab[pos].first != empty_key;
+                 pos = (pos + ++probe) & mask) {
+              assert(probe < newtab.size());
             }
-            table[pos] = tmp[pos];
+            newtab[pos] = table[pos];
           }
         }
+        swap(newtab, table);
       }
+
       void grow() { resize(table.size() << 1); }
       void shrink() { resize(table.size() >> 1); }
+      void assert_init() const { assert(has_empty_key && has_deleted_key); }
+
     public:
-      fast_map() : table(0), empty_key(0), deleted_key(0), count(0) {}
-      void set_empty_key(int k) { empty_key = k; resize(initsize); }
-      void set_deleted_key(int k) { deleted_key = k; resize(initsize); }
+      fast_map() :
+        table(0), empty_key(0), deleted_key(0), count(0), has_empty_key(false),
+        has_deleted_key(false) {}
+      void set_empty_key(key_type k) {
+        has_empty_key = true;
+        empty_key = k;
+        resize(initsize);
+      }
+      void set_deleted_key(key_type k) {
+        has_deleted_key = true;
+        deleted_key = k;
+        resize(initsize);
+      }
       size_t size() const { return count; }
-      int &operator[](int k) {
-        size_t mask = table.size() - 1;
-        size_t probe, pos = hasher(k) & mask; // , unset = -1, first_deleted = unset;
+      void erase(iterator) { throw_not_implemented(); }
+      array<value_type> &get_table() { return table; }
+      const array<value_type> &get_table() const { return table; }
+      bool empty_or_deleted(key_type k) const { return k == empty_key || k == deleted_key; }
+
+      iterator begin() {
+        assert_init();
+        if (count == 0) return end();
+        else return iterator(*this, table.begin());
+      }
+      const_iterator begin() const {
+        assert_init();
+        if (count == 0) return end();
+        else return const_iterator(*this, table.begin());
+      }
+
+      iterator end() {
+        assert_init();
+        return iterator(*this, table.end());
+      }
+      const_iterator end() const {
+        assert_init();
+        return const_iterator(*this, table.end());
+      }
+
+      const_iterator find(key_type k) const {
+        assert_init();
+        size_t probe = 0, mask = table.size() - 1, pos = hasher(k) & mask;
+        while (true) {
+          if (table[pos].first == empty_key) return end();
+          if (table[pos].first == k) return const_iterator(*this, &table[pos]);
+          pos = (pos + ++probe) & mask;
+        }
+      }
+
+      iterator find(key_type k) {
+        assert_init();
+        size_t probe = 0, mask = table.size() - 1, pos = hasher(k) & mask;
+        while (true) {
+          if (table[pos].first == empty_key) return end();
+          if (table[pos].first == k) return iterator(*this, &table[pos]);
+          pos = (pos + ++probe) & mask;
+        }
+#if 0
+        for (;
+             table[pos].first != empty_key && table[pos].first != k;
+             pos = (pos + ++probe) & mask) {
+          assert(probe < table.size());
+        }
+        if (table[pos].first == empty_key) return end();
+        else return &table[pos];
+#endif
+      }
+
+      data_type &operator[](key_type k) {
+        assert_init();
+        size_t probe = 0, mask = table.size() - 1, pos = hasher(k) & mask;
         // Lookup.  Skip over deleted entries (but remembering the first one
         // seen as an open slot if we later decide to insert).  If we find an
         // empty spot, try returning the earlier deleted spot first.  If we
         // find the key, return that.
-        for (probe = 0;
+        for (;
              table[pos].first != deleted_key && table[pos].first != empty_key && table[pos].first != k;
-             ++probe, pos = (pos + probe) & mask) {
+             pos = (pos + ++probe) & mask) {
           assert(probe < table.size());
         }
         if (table[pos].first == deleted_key) {
           size_t first_deleted = pos;
           for (;
                table[pos].first != empty_key && table[pos].first != k;
-               ++probe, pos = (pos + probe) & mask) {
+               pos = (pos + ++probe) & mask) {
             assert(probe < table.size());
           }
           if (table[pos].first == empty_key) {
-            // Inserting new entry.  Grow table if necessary.
+            // Inserting new value_type.  Grow table if necessary.
             if (++count > table.size() * 3 / 4) {
               --count;
               grow();
@@ -93,7 +278,7 @@
             table[pos].first = k;
           }
         } else if (table[pos].first == empty_key) {
-          // Inserting new entry.  Grow table if necessary.
+          // Inserting new value_type.  Grow table if necessary.
           if (++count > table.size() * 3 / 4) {
             --count;
             grow();

Added: cpp-commons/trunk/src/test/fast_map.cc
===================================================================
--- cpp-commons/trunk/src/test/fast_map.cc	                        (rev 0)
+++ cpp-commons/trunk/src/test/fast_map.cc	2009-03-07 21:18:08 UTC (rev 1267)
@@ -0,0 +1,83 @@
+#include <commons/fast_map.h>
+#include <boost/foreach.hpp>
+#include "test.h"
+
+static const char *unset_key_string = "Assertion `has_empty_key && has_deleted_key' failed.";
+
+template<typename T>
+void const_uninit_tests(T &fm) {
+  ASSERT_DEATH(fm.begin(), unset_key_string);
+  ASSERT_DEATH(fm.end(), unset_key_string);
+  ASSERT_DEATH(fm.find(0), unset_key_string);
+}
+
+template<typename T>
+void const_empty_tests(T &fm) {
+  EXPECT_EQ(0, fm.size());
+  EXPECT_TRUE(fm.begin() == fm.end());
+  EXPECT_TRUE(fm.find(0) == fm.end());
+  EXPECT_FALSE(fm.begin() != fm.end());
+  EXPECT_FALSE(fm.find(0) != fm.end());
+}
+
+template<typename T>
+void const_nonempty_tests(T &fm) {
+  EXPECT_EQ(10, fm.size());
+  EXPECT_TRUE(fm.begin() != fm.end());
+  EXPECT_TRUE(fm.find(0) != fm.end());
+  EXPECT_FALSE(fm.begin() == fm.end());
+  EXPECT_FALSE(fm.find(0) == fm.end());
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(2*i, fm.find(2*i)->first);
+    EXPECT_EQ(2*i, (*fm.find(2*i)).first);
+    EXPECT_EQ(4*i, fm.find(2*i)->second);
+    EXPECT_EQ(4*i, (*fm.find(2*i)).second);
+  }
+  EXPECT_TRUE(fm.begin() == fm.find(0));
+  EXPECT_TRUE(fm.end() == fm.find(1));
+
+  typedef pair<int, int> pii;
+  size_t counter = 0;
+  vector<int> xs(20);
+  for (typeof(fm.begin()) it = fm.begin();
+       it != fm.end();
+       ++it) {
+    const pii &p = *it;
+    ++counter;
+    xs[p.first] = p.second;
+  }
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(4 * i, xs[2 * i]);
+  }
+  EXPECT_EQ(10, counter);
+}
+
+TEST(fast_map, basics) {
+  typedef fast_map<int, int> map_t;
+  map_t fm;
+
+  // Uninitialized tests.
+  const_uninit_tests(fm);
+  const_uninit_tests<const map_t>(fm);
+  ASSERT_DEATH(fm[0], unset_key_string);
+
+  // Initialize, leave empty.
+  fm.set_empty_key(-1);
+  fm.set_deleted_key(-2);
+
+  // Empty tests.
+  const_empty_tests(fm);
+  const_empty_tests<const map_t>(fm);
+
+  // Fill.
+  for (int i = 0; i < 10; ++i) {
+    fm[2*i] = 4*i;
+  }
+
+  // Filled tests.
+  const_nonempty_tests(fm);
+  const_nonempty_tests<const map_t>(fm);
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(4*i, fm[2*i]);
+  }
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.