1 |
/* |
2 |
* shstr.C: Shared string class |
3 |
* |
4 |
* Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team |
5 |
* Rights to this code are as documented in COPYING. |
6 |
*/ |
7 |
|
8 |
static char const rcsid[] = "$Id: string.C,v 1.6 2007-09-05 11:23:15 pippijn Exp $"; |
9 |
|
10 |
#include <ermyth/shstr.h> |
11 |
|
12 |
shstr::shstr (char const * const str) |
13 |
{ |
14 |
insert (str); |
15 |
} |
16 |
|
17 |
shstr::shstr (const shstr &rhs) |
18 |
{ |
19 |
insert (rhs.m_str); |
20 |
} |
21 |
|
22 |
shstr::~shstr () |
23 |
{ |
24 |
erase (); |
25 |
} |
26 |
|
27 |
char const * const |
28 |
shstr::c_str () const |
29 |
{ |
30 |
return m_str; |
31 |
} |
32 |
|
33 |
shstr::size_type |
34 |
shstr::length () const |
35 |
{ |
36 |
return m_len; |
37 |
} |
38 |
|
39 |
shstr & |
40 |
shstr::operator = (char const * const rhs) |
41 |
{ |
42 |
erase (); |
43 |
insert (rhs); |
44 |
|
45 |
return *this; |
46 |
} |
47 |
|
48 |
shstr & |
49 |
shstr::operator = (const shstr &rhs) |
50 |
{ |
51 |
if (m_str == rhs.m_str) |
52 |
return *this; |
53 |
|
54 |
erase (); |
55 |
insert (rhs.m_str); |
56 |
|
57 |
return *this; |
58 |
} |
59 |
|
60 |
bool |
61 |
shstr::operator == (const shstr &rhs) const |
62 |
{ |
63 |
return m_str == rhs.m_str; |
64 |
} |
65 |
|
66 |
bool |
67 |
shstr::operator != (const shstr &rhs) const |
68 |
{ |
69 |
return m_str != rhs.m_str; |
70 |
} |
71 |
|
72 |
// string manager functions |
73 |
shentry * |
74 |
shstr::prepare (char const * const str) |
75 |
{ |
76 |
size_t n = hash (str); |
77 |
pairs::iterator it = find (str, n); |
78 |
|
79 |
shentry *entry; |
80 |
|
81 |
if (it == m_buckets[n].end ()) |
82 |
{ |
83 |
entry = new shentry (str, n); |
84 |
m_buckets[n].push_back (entry); |
85 |
} |
86 |
else |
87 |
entry = *it; |
88 |
|
89 |
return entry; |
90 |
} |
91 |
|
92 |
bool |
93 |
shstr::unref (char const * const str) |
94 |
{ |
95 |
size_t n = hash (str); |
96 |
pairs::iterator it = find (str, n); |
97 |
|
98 |
if (it == m_buckets[n].end ()) |
99 |
return false; |
100 |
else |
101 |
{ |
102 |
shentry *entry = *it; |
103 |
|
104 |
--entry->m_refcnt; |
105 |
|
106 |
if (entry->m_refcnt == 0) |
107 |
{ |
108 |
m_buckets[n].erase (it); |
109 |
delete entry; |
110 |
return true; |
111 |
} |
112 |
else |
113 |
return false; |
114 |
} |
115 |
} |
116 |
|
117 |
const shentry * |
118 |
shstr::get (char const * const str) |
119 |
{ |
120 |
size_t n = hash (str); |
121 |
pairs::iterator it = find (str, n); |
122 |
if (it == m_buckets[n].end ()) |
123 |
return NULL; |
124 |
else |
125 |
return *it; |
126 |
} |
127 |
|
128 |
shstr::pairs::iterator |
129 |
shstr::find (char const * const str, size_t n) |
130 |
{ |
131 |
pairs &bucket = m_buckets[n]; |
132 |
pairs::iterator it = bucket.begin (); |
133 |
pairs::iterator et = bucket.end (); |
134 |
|
135 |
while (it != et) |
136 |
{ |
137 |
/* we first check hash equality, because if the hash is not |
138 |
* equal, then the string most definately is not |
139 |
*/ |
140 |
if (n == (*it)->m_hash && __builtin_expect (!strcmp ((*it)->m_str, str), 0)) |
141 |
return it; |
142 |
++it; |
143 |
} |
144 |
|
145 |
return et; |
146 |
} |
147 |
|
148 |
size_t |
149 |
shstr::hash (char const * const str) |
150 |
{ |
151 |
char const *s = str; |
152 |
unsigned long hash = 0; |
153 |
|
154 |
// use the one-at-a-time hash function |
155 |
// see http://burtleburtle.net/bob/hash/doobs.html |
156 |
while (*s) |
157 |
{ |
158 |
hash += *s++; |
159 |
hash += hash << 10; |
160 |
hash ^= hash >> 6; |
161 |
} |
162 |
|
163 |
hash += hash << 3; |
164 |
hash ^= hash >> 11; |
165 |
hash += hash << 15; |
166 |
|
167 |
return hash % m_bucketcnt; |
168 |
} |
169 |
|
170 |
char const * const |
171 |
shstr::insert (char const * const str, size_t *size) |
172 |
{ |
173 |
shentry *entry = prepare (str); |
174 |
++entry->m_refcnt; |
175 |
|
176 |
if (entry->m_refcnt == 1) |
177 |
++m_cnt; |
178 |
*size = entry->m_len; |
179 |
|
180 |
return entry->m_str; |
181 |
} |
182 |
|
183 |
void |
184 |
shstr::erase (char const * const str) |
185 |
{ |
186 |
bool removed = unref (str); |
187 |
if (removed) |
188 |
--m_cnt; |
189 |
} |
190 |
|
191 |
size_t |
192 |
shstr::refs (char const * const str) |
193 |
{ |
194 |
const shentry *entry = get (str); |
195 |
if (entry == NULL) |
196 |
return 0; |
197 |
else |
198 |
return entry->m_refcnt; |
199 |
} |
200 |
|
201 |
size_t |
202 |
shstr::strcnt () |
203 |
{ |
204 |
return m_cnt; |
205 |
} |
206 |
|
207 |
size_t shstr::m_cnt = 0; |
208 |
size_t shstr::m_bucketcnt = 1024; |
209 |
shstr::pairs *shstr::m_buckets; |