1                 : #ifndef __ATERM_MAP_H
       2                 : #define __ATERM_MAP_H
       3                 : 
       4                 : typedef struct _ATerm * ATerm;
       5                 : 
       6                 : #include <assert.h>
       7                 : 
       8                 : 
       9                 : namespace nix {
      10                 : 
      11                 : 
      12                 : class ATermMap
      13                 : {
      14                 : public:
      15                 : 
      16                 :     struct KeyValue
      17                 :     {
      18                 :         ATerm key;
      19                 :         ATerm value;
      20                 :     };
      21                 : 
      22                 : private:
      23                 : 
      24                 :     /* Hash table for the map.  We use open addressing, i.e., all
      25                 :        key/value pairs are stored directly in the table, and there are
      26                 :        no pointers.  Collisions are resolved through probing. */
      27                 :     KeyValue * hashTable;
      28                 : 
      29                 :     /* Current size of the hash table. */
      30                 :     unsigned int capacity;
      31                 : 
      32                 :     /* Number of elements in the hash table. */
      33                 :     unsigned int count;
      34                 : 
      35                 :     /* Maximum number of elements in the hash table.  If `count'
      36                 :        exceeds this number, the hash table is expanded. */
      37                 :     unsigned int maxCount;
      38                 :     
      39                 : public:
      40                 : 
      41                 :     /* Create a map.  `expectedCount' is the number of elements the
      42                 :        map is expected to hold. */
      43                 :     ATermMap(unsigned int expectedCount = 16);
      44                 :     
      45                 :     ATermMap(const ATermMap & map);
      46                 :     
      47                 :     ~ATermMap();
      48                 : 
      49                 :     ATermMap & operator = (const ATermMap & map);
      50                 :         
      51                 :     void set(ATerm key, ATerm value);
      52                 : 
      53                 :     ATerm get(ATerm key) const;
      54                 : 
      55             352 :     ATerm operator [](ATerm key) const
      56                 :     {
      57             352 :         return get(key);
      58                 :     }
      59                 : 
      60                 :     void remove(ATerm key);
      61                 : 
      62                 :     unsigned int size();
      63                 : 
      64                 :     struct const_iterator
      65                 :     {
      66                 :         const ATermMap & map;
      67                 :         unsigned int pos;
      68           13597 :         const_iterator(const ATermMap & map, int pos) : map(map)
      69                 :         {
      70           13597 :             this->pos = pos;
      71           13597 :         }
      72           12005 :         bool operator !=(const const_iterator & i)
      73                 :         {
      74           12005 :             return pos != i.pos;
      75                 :         }
      76           10414 :         void operator ++()
      77                 :         {
      78           10414 :             if (pos == map.capacity) return;
      79           73824 :             do { ++pos; 
      80                 :             } while (pos < map.capacity && map.hashTable[pos].value == 0);
      81                 :         }
      82                 :         const KeyValue & operator *()
      83                 :         {
      84                 :             assert(pos < map.capacity);
      85                 :             return map.hashTable[pos];
      86                 :         }
      87           20469 :         const KeyValue * operator ->()
      88                 :         {
      89           20469 :             assert(pos < map.capacity);
      90           20469 :             return &map.hashTable[pos];
      91                 :         }
      92                 :     };
      93                 : 
      94                 :     friend class ATermMap::const_iterator;
      95                 :     
      96            1592 :     const_iterator begin() const
      97                 :     {
      98            1592 :         unsigned int i = 0;
      99            1592 :         while (i < capacity && hashTable[i].value == 0) ++i;
     100            1592 :         return const_iterator(*this, i);
     101                 :     }
     102                 :     
     103           12005 :     const_iterator end() const
     104                 :     {
     105           12005 :         return const_iterator(*this, capacity);
     106                 :     }
     107                 : 
     108                 : private:
     109                 :     
     110                 :     void init(unsigned int expectedCount);
     111                 : 
     112                 :     void free();
     113                 : 
     114                 :     void resizeTable(unsigned int expectedCount);
     115                 : 
     116                 :     void copy(KeyValue * elements, unsigned int capacity);
     117                 :     
     118                 :     inline unsigned long hash1(ATerm key) const;
     119                 :     inline unsigned long hash2(ATerm key) const;
     120                 : };
     121                 : 
     122                 : 
     123                 : /* Hack. */
     124                 : void printATermMapStats();
     125                 : 
     126                 :  
     127                 : }
     128                 : 
     129                 : 
     130                 : #endif /* !__ATERM_MAP_H */