intern/container/CTR_Map.h

   1 /**
   2  * $Id$
   3  * ***** BEGIN GPL LICENSE BLOCK *****
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  *
  19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  20  * All rights reserved.
  21  *
  22  * The Original Code is: all of this file.
  23  *
  24  * Contributor(s): none yet.
  25  *
  26  * ***** END GPL LICENSE BLOCK *****
  27  */
  28
  29 #ifndef CTR_MAP_H
  30 #define CTR_MAP_H
  31
  32 template <class Key, class Value>
  33 class CTR_Map {
  34 private:
  35     struct Entry {
  36         Entry (Entry *next, Key key, Value value) :
  37             m_next(next),
  38             m_key(key),
  39             m_value(value) {}
  40
  41         Entry *m_next;
  42         Key    m_key;
  43         Value  m_value;
  44     };
  45
  46 public:
  47     CTR_Map(int num_buckets = 100) : m_num_buckets(num_buckets) {
  48         m_buckets = new Entry *[num_buckets];
  49         for (int i = 0; i < num_buckets; ++i) {
  50             m_buckets[i] = 0;
  51         }
  52     }
  53
  54     int size() {
  55         int count=0;
  56         for (int i=0;i<m_num_buckets;i++)
  57         {
  58             Entry* bucket = m_buckets[i];
  59             while(bucket)
  60             {
  61                 bucket = bucket->m_next;
  62                 count++;
  63             }
  64         }
  65         return count;
  66     }
  67
  68     Value* at(int index) {
  69         int count=0;
  70         for (int i=0;i<m_num_buckets;i++)
  71         {
  72             Entry* bucket = m_buckets[i];
  73             while(bucket)
  74             {
  75                 if (count==index)
  76                 {
  77                     return &bucket->m_value;
  78                 }
  79                 bucket = bucket->m_next;
  80                 count++;
  81             }
  82         }
  83         return 0;
  84     }
  85
  86     void clear() {
  87         for (int i = 0; i < m_num_buckets; ++i) {
  88             Entry *entry_ptr = m_buckets[i];
  89
  90             while (entry_ptr != 0) {
  91                 Entry *tmp_ptr = entry_ptr->m_next;
  92                 delete entry_ptr;
  93                 entry_ptr = tmp_ptr;
  94             }
  95             m_buckets[i] = 0;
  96         }
  97     }
  98
  99     ~CTR_Map() {
 100         clear();
 101         delete [] m_buckets;
 102     }
 103
 104     void insert(const Key& key, const Value& value) {
 105         Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
 106         while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
 107             entry_ptr = entry_ptr->m_next;
 108         }
 109
 110         if (entry_ptr != 0) {
 111             entry_ptr->m_value = value;
 112         }
 113         else {
 114             Entry **bucket = &m_buckets[key.hash() % m_num_buckets];
 115             *bucket = new Entry(*bucket, key, value);
 116         }
 117     }
 118
 119     void remove(const Key& key) {
 120         Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
 121         while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
 122             entry_ptr = &(*entry_ptr)->m_next;
 123         }
 124
 125         if (*entry_ptr != 0) {
 126             Entry *tmp_ptr = (*entry_ptr)->m_next;
 127             delete *entry_ptr;
 128             *entry_ptr = tmp_ptr;
 129         }
 130     }
 131
 132     Value *operator[](Key key) {
 133         Entry *bucket = m_buckets[key.hash() % m_num_buckets];
 134         while ((bucket != 0) && !(key == bucket->m_key)) {
 135             bucket = bucket->m_next;
 136         }
 137         return bucket != 0 ? &bucket->m_value : 0;
 138     }
 139
 140 private:
 141     int     m_num_buckets;
 142     Entry **m_buckets;
 143 };
 144
 145 #endif
 146