blob: 875aa26b25b34869e723bf86b0714a2cd2f19877 (
plain)
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
// file : xsde/cxx/hashmap.hxx
// copyright : Copyright (c) 2005-2011 Code Synthesis Tools CC
// license : GNU GPL v2 + exceptions; see accompanying LICENSE file
#ifndef XSDE_CXX_HASHMAP_HXX
#define XSDE_CXX_HASHMAP_HXX
#include <stddef.h> // size_t
#include <xsde/cxx/config.hxx>
namespace xsde
{
namespace cxx
{
class hashmap;
class hashmap_const_iterator
{
public:
hashmap_const_iterator (const hashmap& map, size_t bucket);
// Forward iterator requirements.
//
const void*
operator* () const;
hashmap_const_iterator&
operator++ ();
hashmap_const_iterator
operator++ (int);
friend bool
operator== (const hashmap_const_iterator& i,
const hashmap_const_iterator& j);
private:
const hashmap* map_;
size_t bucket_;
size_t element_;
};
bool
operator!= (const hashmap_const_iterator& i,
const hashmap_const_iterator& j);
// Special-purpose, light-weight C-string to POD hashmap. Some of
// its characteristics:
//
// - number of buckets does not grow (no re-hashing)
// - removal of items is not supported
// - key and value (POD) are not deep-copied
// - empty bucket is cheap (1 pointer)
//
class hashmap
{
public:
#ifndef XSDE_EXCEPTIONS
enum error
{
error_none,
error_no_memory
};
error
_error () const;
#endif
public:
~hashmap ();
hashmap (size_t buckets, size_t element_size);
private:
hashmap (hashmap&);
hashmap& operator= (hashmap&);
public:
void
insert (const char* key, void* value);
const void*
find (const char* key) const;
public:
bool
empty () const;
size_t
size () const;
// Return the maximum number of elements in a single bucket.
//
size_t
max_bucket_size () const;
public:
typedef hashmap_const_iterator const_iterator;
const_iterator
begin () const;
const_iterator
end () const;
public:
static size_t
hash (const char*);
static size_t
hash (const char*, size_t n);
static size_t
hash (size_t hash, const char*);
static size_t
hash (size_t hash, const char*, size_t n);
protected:
// Keep these types POD.
//
struct bucket
{
size_t size_;
size_t capacity_;
};
struct element
{
size_t hash_;
const char* key_;
};
protected:
const bucket*
find (size_t hash) const;
private:
friend class hashmap_const_iterator;
size_t esize_; // element size
size_t ecount_; // element count
size_t bcount_; // bucket count
bucket** buckets_;
#ifndef XSDE_EXCEPTIONS
protected:
error error_;
#endif
};
}
}
#include <xsde/cxx/hashmap.ixx>
#endif // XSDE_CXX_HASHMAP_HXX
|
