satsolver
0.17.2
Main Page
Related Pages
Classes
Files
File List
File Members
src
strpool.c
Go to the documentation of this file.
1
/*
2
* Copyright (c) 2007, Novell Inc.
3
*
4
* This program is licensed under the BSD license, read LICENSE.BSD
5
* for further information
6
*/
7
8
#include <string.h>
9
#include "
util.h
"
10
#include "
strpool.h
"
11
12
#define STRING_BLOCK 2047
13
#define STRINGSPACE_BLOCK 65535
14
15
void
16
stringpool_init
(
Stringpool
*ss,
const
char
*strs[])
17
{
18
unsigned
totalsize = 0;
19
unsigned
count;
20
21
memset(ss, 0,
sizeof
(*ss));
22
// count number and total size of predefined strings
23
for
(count = 0; strs[count]; count++)
24
totalsize += strlen(strs[count]) + 1;
25
26
// alloc appropriate space
27
ss->
stringspace
=
sat_extend_resize
(0, totalsize, 1,
STRINGSPACE_BLOCK
);
28
ss->
strings
=
sat_extend_resize
(0, count,
sizeof
(
Offset
),
STRING_BLOCK
);
29
30
// now copy predefined strings into allocated space
31
ss->
sstrings
= 0;
32
for
(count = 0; strs[count]; count++)
33
{
34
strcpy(ss->
stringspace
+ ss->
sstrings
, strs[count]);
35
ss->
strings
[count] = ss->
sstrings
;
36
ss->
sstrings
+= strlen(strs[count]) + 1;
37
}
38
ss->
nstrings
= count;
39
}
40
41
void
42
stringpool_free
(
Stringpool
*ss)
43
{
44
sat_free
(ss->
strings
);
45
sat_free
(ss->
stringspace
);
46
sat_free
(ss->
stringhashtbl
);
47
}
48
49
void
50
stringpool_freehash
(
Stringpool
*ss)
51
{
52
ss->
stringhashtbl
=
sat_free
(ss->
stringhashtbl
);
53
ss->
stringhashmask
= 0;
54
}
55
56
void
57
stringpool_init_empty
(
Stringpool
*ss)
58
{
59
const
char
*emptystrs[] = {
60
"<NULL>"
,
61
""
,
62
0,
63
};
64
stringpool_init
(ss, emptystrs);
65
}
66
67
void
68
stringpool_clone
(
Stringpool
*ss,
Stringpool
*from)
69
{
70
memset(ss, 0,
sizeof
(*ss));
71
ss->
strings
=
sat_extend_resize
(0, from->
nstrings
,
sizeof
(
Offset
),
STRING_BLOCK
);
72
memcpy(ss->
strings
, from->
strings
, from->
nstrings
*
sizeof
(
Offset
));
73
ss->
stringspace
=
sat_extend_resize
(0, from->
sstrings
, 1,
STRINGSPACE_BLOCK
);
74
memcpy(ss->
stringspace
, from->
stringspace
, from->
sstrings
);
75
ss->
nstrings
= from->
nstrings
;
76
ss->
sstrings
= from->
sstrings
;
77
}
78
79
Id
80
stringpool_strn2id
(
Stringpool
*ss,
const
char
*str,
unsigned
int
len,
int
create)
81
{
82
Hashval
h;
83
unsigned
int
hh;
84
Hashmask
hashmask;
85
int
i;
86
Id
id;
87
Hashtable
hashtbl;
88
89
// check string
90
if
(!str)
91
return
STRID_NULL
;
92
if
(!len)
93
return
STRID_EMPTY
;
94
95
hashmask = ss->
stringhashmask
;
96
hashtbl = ss->
stringhashtbl
;
97
98
// expand hashtable if needed
99
if
(ss->
nstrings
* 2 > hashmask)
100
{
101
sat_free
(hashtbl);
102
103
// realloc hash table
104
ss->
stringhashmask
= hashmask =
mkmask
(ss->
nstrings
+
STRING_BLOCK
);
105
ss->
stringhashtbl
= hashtbl = (
Hashtable
)
sat_calloc
(hashmask + 1,
sizeof
(
Id
));
106
107
// rehash all strings into new hashtable
108
for
(i = 1; i < ss->
nstrings
; i++)
109
{
110
h =
strhash
(ss->
stringspace
+ ss->
strings
[i]) & hashmask;
111
hh =
HASHCHAIN_START
;
112
while
(hashtbl[h] != 0)
// follow overflow chain
113
h =
HASHCHAIN_NEXT
(h, hh, hashmask);
114
hashtbl[h] = i;
115
}
116
}
117
118
// compute hash and check for match
119
h =
strnhash
(str, len) & hashmask;
120
hh =
HASHCHAIN_START
;
121
while
((
id
= hashtbl[h]) != 0)
// follow hash overflow chain
122
{
123
// break if string already hashed
124
if
(!memcmp(ss->
stringspace
+ ss->
strings
[
id
], str, len)
125
&& ss->
stringspace
[ss->
strings
[
id
] + len] == 0)
126
break
;
127
h =
HASHCHAIN_NEXT
(h, hh, hashmask);
128
}
129
if
(
id
|| !create)
// exit here if string found
130
return
id;
131
132
// generate next id and save in table
133
id
= ss->
nstrings
++;
134
hashtbl[h] = id;
135
136
ss->
strings
=
sat_extend
(ss->
strings
,
id
, 1,
sizeof
(
Offset
),
STRING_BLOCK
);
137
ss->
strings
[id] = ss->
sstrings
;
/* we will append to the end */
138
139
// append string to stringspace
140
ss->
stringspace
=
sat_extend
(ss->
stringspace
, ss->
sstrings
, len + 1, 1,
STRINGSPACE_BLOCK
);
141
memcpy(ss->
stringspace
+ ss->
sstrings
, str, len);
142
ss->
stringspace
[ss->
sstrings
+ len] = 0;
143
ss->
sstrings
+= len + 1;
144
return
id;
145
}
146
147
Id
148
stringpool_str2id
(
Stringpool
*ss,
const
char
*str,
int
create)
149
{
150
if
(!str)
151
return
STRID_NULL
;
152
if
(!*str)
153
return
STRID_EMPTY
;
154
return
stringpool_strn2id
(ss, str, (
unsigned
int
)strlen(str), create);
155
}
156
157
void
158
stringpool_shrink
(
Stringpool
*ss)
159
{
160
ss->
stringspace
=
sat_extend_resize
(ss->
stringspace
, ss->
sstrings
, 1,
STRINGSPACE_BLOCK
);
161
ss->
strings
=
sat_extend_resize
(ss->
strings
, ss->
nstrings
,
sizeof
(
Offset
),
STRING_BLOCK
);
162
}
Generated by
1.8.4