← Back to branch summary

~ubuntu-branches/debian/squeeze/openttd/squeeze

« back to all changes in this revision

Viewing changes to src/misc/hashtable.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Jordi Mallach, Matthijs Kooijman, Jordi Mallach
  • Date: 2009-04-15 18:22:10 UTC
  • mfrom: (1.1.6 upstream) (2.1.3 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090415182210-22ktb8kdbp2tf3bm
[ Matthijs Kooijman ]
* New upstream release.
* Remove Debian specific desktop file, upstream provides one now. 
* Add debian/watch file.

[ Jordi Mallach ]
* Bump Standards-Version to 3.8.1, with no changes required.
* Move to debhelper compat 7. Bump Build-Depends accordingly.
* Use dh_prep.
* Add "set -e" to config script.
* Remove a few extra doc files that get installed by upstream Makefile.
* Add more complete copyright information.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/misc/hashtable.hpp
1
 
/* $Id: hashtable.hpp 9662 2007-04-17 20:23:13Z belugas $ */
 
1
/* $Id: hashtable.hpp 15718 2009-03-15 00:32:18Z rubidium $ */
2
2
 
3
 
/** @file hashtable.hpp */
 
3
/** @file hashtable.hpp Hash table support. */
4
4
 
5
5
#ifndef  HASHTABLE_HPP
6
6
#define  HASHTABLE_HPP
10
10
{
11
11
        typedef typename Titem_::Key Key;          // make Titem_::Key a property of HashTable
12
12
 
13
 
        Titem_*    m_pFirst;
 
13
        Titem_ *m_pFirst;
14
14
 
15
15
        CHashTableSlotT() : m_pFirst(NULL) {}
16
16
 
18
18
        FORCEINLINE void Clear() {m_pFirst = NULL;}
19
19
 
20
20
        /** hash table slot helper - linear search for item with given key through the given blob - const version */
21
 
        FORCEINLINE const Titem_* Find(const Key& key) const
 
21
        FORCEINLINE const Titem_ *Find(const Key& key) const
22
22
        {
23
 
                for (const Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
 
23
                for (const Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
24
24
                        if (pItem->GetKey() == key) {
25
 
                                // we have found the item, return it
 
25
                                /* we have found the item, return it */
26
26
                                return pItem;
27
27
                        }
28
28
                }
30
30
        }
31
31
 
32
32
        /** hash table slot helper - linear search for item with given key through the given blob - non-const version */
33
 
        FORCEINLINE Titem_* Find(const Key& key)
 
33
        FORCEINLINE Titem_ *Find(const Key& key)
34
34
        {
35
 
                for (Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
 
35
                for (Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
36
36
                        if (pItem->GetKey() == key) {
37
 
                                // we have found the item, return it
 
37
                                /* we have found the item, return it */
38
38
                                return pItem;
39
39
                        }
40
40
                }
57
57
                        item_to_remove.SetHashNext(NULL);
58
58
                        return true;
59
59
                }
60
 
                Titem_* pItem = m_pFirst;
 
60
                Titem_ *pItem = m_pFirst;
61
61
                while (true) {
62
62
                        if (pItem == NULL) {
63
63
                                return false;
64
64
                        }
65
 
                        Titem_* pNextItem = pItem->GetHashNext();
 
65
                        Titem_ *pNextItem = pItem->GetHashNext();
66
66
                        if (pNextItem == &item_to_remove) break;
67
67
                        pItem = pNextItem;
68
68
                }
72
72
        }
73
73
 
74
74
        /** hash table slot helper - remove and return item from a slot */
75
 
        FORCEINLINE Titem_* Detach(const Key& key)
 
75
        FORCEINLINE Titem_ *Detach(const Key& key)
76
76
        {
77
 
                // do we have any items?
 
77
                /* do we have any items? */
78
78
                if (m_pFirst == NULL) {
79
79
                        return NULL;
80
80
                }
81
 
                // is it our first item?
 
81
                /* is it our first item? */
82
82
                if (m_pFirst->GetKey() == key) {
83
83
                        Titem_& ret_item = *m_pFirst;
84
84
                        m_pFirst = m_pFirst->GetHashNext();
85
85
                        ret_item.SetHashNext(NULL);
86
86
                        return &ret_item;
87
87
                }
88
 
                // find it in the following items
89
 
                Titem_* pPrev = m_pFirst;
90
 
                for (Titem_* pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) {
 
88
                /* find it in the following items */
 
89
                Titem_ *pPrev = m_pFirst;
 
90
                for (Titem_ *pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) {
91
91
                        if (pItem->GetKey() == key) {
92
 
                                // we have found the item, unlink and return it
 
92
                                /* we have found the item, unlink and return it */
93
93
                                pPrev->SetHashNext(pItem->GetHashNext());
94
94
                                pItem->SetHashNext(NULL);
95
95
                                return pItem;
133
133
         *  Titem contains pointer to the next item - GetHashNext(), SetHashNext() */
134
134
        typedef CHashTableSlotT<Titem_> Slot;
135
135
 
136
 
        Slot*  m_slots;     // here we store our data (array of blobs)
137
 
        int    m_num_items; // item counter
 
136
        Slot *m_slots;     // here we store our data (array of blobs)
 
137
        int   m_num_items; // item counter
138
138
 
139
139
public:
140
 
        // default constructor
 
140
        /* default constructor */
141
141
        FORCEINLINE CHashTableT()
142
142
        {
143
 
                // construct all slots
 
143
                /* construct all slots */
144
144
                m_slots = new Slot[Tcapacity];
145
145
                m_num_items = 0;
146
146
        }
171
171
        FORCEINLINE void Clear() const {for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();}
172
172
 
173
173
        /** const item search */
174
 
        const Titem_* Find(const Tkey& key) const
 
174
        const Titem_ *Find(const Tkey& key) const
175
175
        {
176
176
                int hash = CalcHash(key);
177
177
                const Slot& slot = m_slots[hash];
178
 
                const Titem_* item = slot.Find(key);
 
178
                const Titem_ *item = slot.Find(key);
179
179
                return item;
180
180
        }
181
181
 
182
182
        /** non-const item search */
183
 
        Titem_* Find(const Tkey& key)
 
183
        Titem_ *Find(const Tkey& key)
184
184
        {
185
185
                int hash = CalcHash(key);
186
186
                Slot& slot = m_slots[hash];
187
 
                Titem_* item = slot.Find(key);
 
187
                Titem_ *item = slot.Find(key);
188
188
                return item;
189
189
        }
190
190
 
191
191
        /** non-const item search & optional removal (if found) */
192
 
        Titem_* TryPop(const Tkey& key)
 
192
        Titem_ *TryPop(const Tkey& key)
193
193
        {
194
194
                int hash = CalcHash(key);
195
195
                Slot& slot = m_slots[hash];
196
 
                Titem_* item = slot.Detach(key);
 
196
                Titem_ *item = slot.Detach(key);
197
197
                if (item != NULL) {
198
198
                        m_num_items--;
199
199
                }
203
203
        /** non-const item search & removal */
204
204
        Titem_& Pop(const Tkey& key)
205
205
        {
206
 
                Titem_* item = TryPop(key);
 
206
                Titem_ *item = TryPop(key);
207
207
                assert(item != NULL);
208
208
                return *item;
209
209
        }