1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
/* ScummVM - Graphic Adventure Engine
*
* ScummVM is the legal property of its developers, whose names
* are too numerous to list here. Please refer to the COPYRIGHT
* file distributed with this source distribution.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* $URL$
* $Id$
*
*/
#ifndef SCI_ENGINE_INTMAP_H
#define SCI_ENGINE_INTMAP_H
#include "common/scummsys.h"
#include "common/serializer.h"
namespace Sci {
// Assumes that the ints are relatively evenly distributed
enum {
DCS_INT_HASH_MAX = 256
};
/**
* Defines a map from arbitrary integers to "small" integers, useable as index
* into small arrays. This class is somewhat like a hashmap, but not quite:
* Unlike a hashmap, it generates the values associated to each key. It does
* not try to be very clever about it, either, e.g. using a linked list of
* values to keep track of what is mapped where.
* Another important feature is that it reclaims unused values when they
* are removed.
*
* All in all, this implementation is not very elegant, and wastes memory.
* But it does the job. Any rewrite of this class would have to provide a
* way to load the old savegames made using the current implementation.
*
* One approach to implement a replacement: Combine a Common::HashMap<int,int>
* with a bitfield which track which low-value integers are in use.
* That way, lookup just invokes the hashmap, and insertion (which requires
* finding an unmapped low-value integer) can still be implemented efficiently.
*/
struct IntMapper : public Common::Serializable {
struct Node {
int key;
int idx;
Node *next;
};
int base_value; // Starts at zero, counts upwards
Node *nodes[DCS_INT_HASH_MAX];
Node *holes; /* List of freed entries to minimize
** memory operations and modifications
** to base_value */
void free_node_recursive(Node *node);
protected:
void insert(int key, int idx); // For loading only
public:
IntMapper();
~IntMapper();
virtual void saveLoadWithSerializer(Common::Serializer &ser);
void clear();
/**
* Checks whether a key is in the map, adds it if neccessary.
* @param key The key to check for/add
* @param add Whether to add the key if it's not in there
* @param was_added Set to non-zero if and only if the key is new, ignored if NULL.
* @return The new (or old) index, or -1 if add was zero and
* the key couldn't be found
*/
int checkKey(int key, bool add, bool *wasAdded = 0);
/**
* Looks up a key in the map
* @parmam key The key to look for
* @return The value or -1 if not found
*/
int lookupKey(int key) const;
/**
* Removes a key from the map.
* @param key The key to remove
* @return The index of the key, or -1 if it wasn't present
*/
int removeKey(int key);
};
} // End of namespace Sci
#endif // SCI_ENGINE_INTMAP_H
|
