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