about summary refs log tree commit diff
path: root/table/aterm-map.cc
diff options
context:
space:
mode:
authorEelco Dolstra <e.dolstra@tudelft.nl>2006-05-04T09·22+0000
committerEelco Dolstra <e.dolstra@tudelft.nl>2006-05-04T09·22+0000
commit9840368cad6088e4221fb323202861c97d70bb37 (patch)
tree5ad08cbf44f735fa3d830a47755582be10eb9758 /table/aterm-map.cc
parent6980544467b42aaefc5b588d8be2f1d7a2badef3 (diff)
* Iterators.
Diffstat (limited to 'table/aterm-map.cc')
-rw-r--r--table/aterm-map.cc79
1 files changed, 73 insertions, 6 deletions
diff --git a/table/aterm-map.cc b/table/aterm-map.cc
index df013359263e..b619ead3668a 100644
--- a/table/aterm-map.cc
+++ b/table/aterm-map.cc
@@ -9,7 +9,7 @@ using namespace std;
 
 class ATermMap
 {
-private:
+public:
 
     struct KeyValue
     {
@@ -17,6 +17,8 @@ private:
         ATerm value;
     };
 
+private:
+
     /* Hash table for the map.  We use open addressing, i.e., all
        key/value pairs are stored directly in the table, and there are
        no pointers.  Collisions are resolved through probing. */
@@ -33,6 +35,7 @@ private:
     unsigned int maxCount;
     
 public:
+
     /* Create a map.  `expectedCount' is the number of elements the
        map is expected to hold. */
     ATermMap(unsigned int expectedCount);
@@ -51,7 +54,50 @@ public:
 
     unsigned int size();
 
+    struct const_iterator
+    {
+        const ATermMap & map;
+        unsigned int pos;
+        const_iterator(const ATermMap & map, int pos) : map(map)
+        {
+            this->pos = pos;
+        }
+        bool operator !=(const const_iterator & i)
+        {
+            return pos != i.pos;
+        }
+        void operator ++()
+        {
+            if (pos == map.capacity) return;
+            do { ++pos; 
+            } while (pos < map.capacity && map.hashTable[pos].value == 0);
+        }
+        const KeyValue & operator *()
+        {
+            assert(pos < map.capacity);
+            return map.hashTable[pos];
+        }
+        const KeyValue * operator ->()
+        {
+            assert(pos < map.capacity);
+            return &map.hashTable[pos];
+        }
+    };
+
+    const_iterator begin() const
+    {
+        unsigned int i = 0;
+        while (i < capacity && hashTable[i].value == 0) ++i;
+        return const_iterator(*this, i);
+    }
+    
+    const_iterator end() const
+    {
+        return const_iterator(*this, capacity);
+    }
+
 private:
+    
     void init(unsigned int expectedCount);
 
     void free();
@@ -305,7 +351,7 @@ int main(int argc, char * * argv)
 
 
     for (int test = 0; test < 100000; ++test) {
-        // cerr << test << endl;
+        //cerr << test << endl;
         unsigned int n = 300;
         ATermMap map(300);
         ATerm keys[n], values[n];
@@ -313,24 +359,45 @@ int main(int argc, char * * argv)
             keys[i] = someTerm();
             values[i] = someTerm();
             map.set(keys[i], values[i]);
-            // cerr << "INSERT: " << keys[i] << " " << values[i] << endl;
+            //cerr << "INSERT: " << keys[i] << " " << values[i] << endl;
         }
+
         unsigned int size = map.size();
         assert(size <= n);
         values[n - 1] = 0;
         map.remove(keys[n - 1]);
         assert(map.size() == size - 1);
+
+        unsigned int checksum;
+        unsigned int count = 0;
+        for (ATermMap::const_iterator i = map.begin(); i != map.end(); ++i, ++count) {
+            assert(i->key);
+            assert(i->value);
+            checksum += (unsigned int) (*i).key;
+            checksum += (unsigned int) (*i).value;
+            // cout << (*i).key << " " << (*i).value << endl;
+        }
+        assert(count == size - 1);
+
         for (unsigned int i = 0; i < n; ++i) {
+            for (unsigned int j = i + 1; j < n; ++j)
+                if (keys[i] == keys[j]) goto x;
             if (map.get(keys[i]) != values[i]) {
-                for (unsigned int j = i + 1; j < n; ++j)
-                    if (keys[i] == keys[j]) goto x;
                 cerr << "MISMATCH: " << keys[i] << " " << values[i] << " " << map.get(keys[i]) << " " << i << endl;
                 abort();
-            x: ;
             }
+            if (values[i] != 0) {
+                checksum -= (unsigned int) keys[i];
+                checksum -= (unsigned int) values[i];
+            }
+        x:  ;
         }
+
+        assert(checksum == 0);
+        
         for (unsigned int i = 0; i < 100; ++i)
             map.get(someTerm());
+        
     }
 
     cout << "RESIZES: " << nrResizes << " "