1 | /* Copyright (C) 2000-2019 Free Software Foundation, Inc. |
---|---|

2 | This file is part of the GNU C Library. |

3 | Contributed by Bruno Haible <haible@clisp.cons.org>, 2000. |

4 | |

5 | This program is free software; you can redistribute it and/or modify |

6 | it under the terms of the GNU General Public License as published |

7 | by the Free Software Foundation; version 2 of the License, or |

8 | (at your option) any later version. |

9 | |

10 | This program is distributed in the hope that it will be useful, |

11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |

12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |

13 | GNU General Public License for more details. |

14 | |

15 | You should have received a copy of the GNU General Public License |

16 | along with this program; if not, see <http://www.gnu.org/licenses/>. */ |

17 | |

18 | #include <stdint.h> |

19 | |

20 | /* Construction of sparse 3-level tables. |

21 | See wchar-lookup.h or coll-lookup.h for their structure and the |

22 | meaning of p and q. |

23 | |

24 | Before including this file, set |

25 | TABLE to the name of the structure to be defined |

26 | ELEMENT to the type of every entry |

27 | DEFAULT to the default value for empty entries |

28 | ITERATE if you want the TABLE_iterate function to be defined |

29 | NO_ADD_LOCALE if you don't want the add_locale_TABLE function |

30 | to be defined |

31 | |

32 | This will define |

33 | |

34 | struct TABLE; |

35 | void TABLE_init (struct TABLE *t); |

36 | ELEMENT TABLE_get (struct TABLE *t, uint32_t wc); |

37 | void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value); |

38 | void TABLE_iterate (struct TABLE *t, |

39 | void (*fn) (uint32_t wc, ELEMENT value)); |

40 | void add_locale_TABLE (struct locale_file *file, struct TABLE *t); |

41 | */ |

42 | |

43 | #define CONCAT(a,b) CONCAT1(a,b) |

44 | #define CONCAT1(a,b) a##b |

45 | |

46 | struct TABLE |

47 | { |

48 | /* Parameters. */ |

49 | unsigned int p; |

50 | unsigned int q; |

51 | /* Working representation. */ |

52 | size_t level1_alloc; |

53 | size_t level1_size; |

54 | uint32_t *level1; |

55 | size_t level2_alloc; |

56 | size_t level2_size; |

57 | uint32_t *level2; |

58 | size_t level3_alloc; |

59 | size_t level3_size; |

60 | ELEMENT *level3; |

61 | /* Size of compressed representation. */ |

62 | size_t result_size; |

63 | }; |

64 | |

65 | /* Initialize. Assumes t->p and t->q have already been set. */ |

66 | static inline void |

67 | CONCAT(TABLE,_init) (struct TABLE *t) |

68 | { |

69 | t->level1 = NULL; |

70 | t->level1_alloc = t->level1_size = 0; |

71 | t->level2 = NULL; |

72 | t->level2_alloc = t->level2_size = 0; |

73 | t->level3 = NULL; |

74 | t->level3_alloc = t->level3_size = 0; |

75 | } |

76 | |

77 | /* Marker for an empty slot. This has the value 0xFFFFFFFF, regardless |

78 | whether 'int' is 16 bit, 32 bit, or 64 bit. */ |

79 | #define EMPTY ((uint32_t) ~0) |

80 | |

81 | /* Retrieve an entry. */ |

82 | static inline ELEMENT |

83 | __attribute ((always_inline)) |

84 | CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc) |

85 | { |

86 | uint32_t index1 = wc >> (t->q + t->p); |

87 | if (index1 < t->level1_size) |

88 | { |

89 | uint32_t lookup1 = t->level1[index1]; |

90 | if (lookup1 != EMPTY) |

91 | { |

92 | uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1)) |

93 | + (lookup1 << t->q); |

94 | uint32_t lookup2 = t->level2[index2]; |

95 | if (lookup2 != EMPTY) |

96 | { |

97 | uint32_t index3 = (wc & ((1 << t->p) - 1)) |

98 | + (lookup2 << t->p); |

99 | ELEMENT lookup3 = t->level3[index3]; |

100 | |

101 | return lookup3; |

102 | } |

103 | } |

104 | } |

105 | return DEFAULT; |

106 | } |

107 | |

108 | /* Add one entry. */ |

109 | static void |

110 | CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc, ELEMENT value) |

111 | { |

112 | uint32_t index1 = wc >> (t->q + t->p); |

113 | uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1); |

114 | uint32_t index3 = wc & ((1 << t->p) - 1); |

115 | size_t i, i1, i2; |

116 | |

117 | if (value == CONCAT(TABLE,_get) (t, wc)) |

118 | return; |

119 | |

120 | if (index1 >= t->level1_size) |

121 | { |

122 | if (index1 >= t->level1_alloc) |

123 | { |

124 | size_t alloc = 2 * t->level1_alloc; |

125 | if (alloc <= index1) |

126 | alloc = index1 + 1; |

127 | t->level1 = (uint32_t *) xrealloc ((char *) t->level1, |

128 | alloc * sizeof (uint32_t)); |

129 | t->level1_alloc = alloc; |

130 | } |

131 | while (index1 >= t->level1_size) |

132 | t->level1[t->level1_size++] = EMPTY; |

133 | } |

134 | |

135 | if (t->level1[index1] == EMPTY) |

136 | { |

137 | if (t->level2_size == t->level2_alloc) |

138 | { |

139 | size_t alloc = 2 * t->level2_alloc + 1; |

140 | t->level2 = (uint32_t *) xrealloc ((char *) t->level2, |

141 | (alloc << t->q) * sizeof (uint32_t)); |

142 | t->level2_alloc = alloc; |

143 | } |

144 | i1 = t->level2_size << t->q; |

145 | i2 = (t->level2_size + 1) << t->q; |

146 | for (i = i1; i < i2; i++) |

147 | t->level2[i] = EMPTY; |

148 | t->level1[index1] = t->level2_size++; |

149 | } |

150 | |

151 | index2 += t->level1[index1] << t->q; |

152 | |

153 | if (t->level2[index2] == EMPTY) |

154 | { |

155 | if (t->level3_size == t->level3_alloc) |

156 | { |

157 | size_t alloc = 2 * t->level3_alloc + 1; |

158 | t->level3 = (ELEMENT *) xrealloc ((char *) t->level3, |

159 | (alloc << t->p) * sizeof (ELEMENT)); |

160 | t->level3_alloc = alloc; |

161 | } |

162 | i1 = t->level3_size << t->p; |

163 | i2 = (t->level3_size + 1) << t->p; |

164 | for (i = i1; i < i2; i++) |

165 | t->level3[i] = DEFAULT; |

166 | t->level2[index2] = t->level3_size++; |

167 | } |

168 | |

169 | index3 += t->level2[index2] << t->p; |

170 | |

171 | t->level3[index3] = value; |

172 | } |

173 | |

174 | #ifdef ITERATE |

175 | /* Apply a function to all entries in the table. */ |

176 | static void |

177 | CONCAT(TABLE,_iterate) (struct TABLE *t, |

178 | void (*fn) (uint32_t wc, ELEMENT value)) |

179 | { |

180 | uint32_t index1; |

181 | for (index1 = 0; index1 < t->level1_size; index1++) |

182 | { |

183 | uint32_t lookup1 = t->level1[index1]; |

184 | if (lookup1 != EMPTY) |

185 | { |

186 | uint32_t lookup1_shifted = lookup1 << t->q; |

187 | uint32_t index2; |

188 | for (index2 = 0; index2 < (1 << t->q); index2++) |

189 | { |

190 | uint32_t lookup2 = t->level2[index2 + lookup1_shifted]; |

191 | if (lookup2 != EMPTY) |

192 | { |

193 | uint32_t lookup2_shifted = lookup2 << t->p; |

194 | uint32_t index3; |

195 | for (index3 = 0; index3 < (1 << t->p); index3++) |

196 | { |

197 | ELEMENT lookup3 = t->level3[index3 + lookup2_shifted]; |

198 | if (lookup3 != DEFAULT) |

199 | fn ((((index1 << t->q) + index2) << t->p) + index3, |

200 | lookup3); |

201 | } |

202 | } |

203 | } |

204 | } |

205 | } |

206 | } |

207 | #endif |

208 | |

209 | #ifndef NO_ADD_LOCALE |

210 | /* Finalize and shrink. */ |

211 | static void |

212 | CONCAT(add_locale_,TABLE) (struct locale_file *file, struct TABLE *t) |

213 | { |

214 | size_t i, j, k; |

215 | uint32_t reorder3[t->level3_size]; |

216 | uint32_t reorder2[t->level2_size]; |

217 | uint32_t level2_offset, level3_offset, last_offset; |

218 | |

219 | /* Uniquify level3 blocks. */ |

220 | k = 0; |

221 | for (j = 0; j < t->level3_size; j++) |

222 | { |

223 | for (i = 0; i < k; i++) |

224 | if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p], |

225 | (1 << t->p) * sizeof (ELEMENT)) == 0) |

226 | break; |

227 | /* Relocate block j to block i. */ |

228 | reorder3[j] = i; |

229 | if (i == k) |

230 | { |

231 | if (i != j) |

232 | memcpy (&t->level3[i << t->p], &t->level3[j << t->p], |

233 | (1 << t->p) * sizeof (ELEMENT)); |

234 | k++; |

235 | } |

236 | } |

237 | t->level3_size = k; |

238 | |

239 | for (i = 0; i < (t->level2_size << t->q); i++) |

240 | if (t->level2[i] != EMPTY) |

241 | t->level2[i] = reorder3[t->level2[i]]; |

242 | |

243 | /* Uniquify level2 blocks. */ |

244 | k = 0; |

245 | for (j = 0; j < t->level2_size; j++) |

246 | { |

247 | for (i = 0; i < k; i++) |

248 | if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q], |

249 | (1 << t->q) * sizeof (uint32_t)) == 0) |

250 | break; |

251 | /* Relocate block j to block i. */ |

252 | reorder2[j] = i; |

253 | if (i == k) |

254 | { |

255 | if (i != j) |

256 | memcpy (&t->level2[i << t->q], &t->level2[j << t->q], |

257 | (1 << t->q) * sizeof (uint32_t)); |

258 | k++; |

259 | } |

260 | } |

261 | t->level2_size = k; |

262 | |

263 | for (i = 0; i < t->level1_size; i++) |

264 | if (t->level1[i] != EMPTY) |

265 | t->level1[i] = reorder2[t->level1[i]]; |

266 | |

267 | /* Create and fill the resulting compressed representation. */ |

268 | last_offset = |

269 | 5 * sizeof (uint32_t) |

270 | + t->level1_size * sizeof (uint32_t) |

271 | + (t->level2_size << t->q) * sizeof (uint32_t) |

272 | + (t->level3_size << t->p) * sizeof (ELEMENT); |

273 | t->result_size = LOCFILE_ALIGN_UP (last_offset); |

274 | |

275 | level2_offset = |

276 | 5 * sizeof (uint32_t) |

277 | + t->level1_size * sizeof (uint32_t); |

278 | level3_offset = |

279 | 5 * sizeof (uint32_t) |

280 | + t->level1_size * sizeof (uint32_t) |

281 | + (t->level2_size << t->q) * sizeof (uint32_t); |

282 | |

283 | start_locale_structure (file); |

284 | add_locale_uint32 (file, t->q + t->p); |

285 | add_locale_uint32 (file, t->level1_size); |

286 | add_locale_uint32 (file, t->p); |

287 | add_locale_uint32 (file, (1 << t->q) - 1); |

288 | add_locale_uint32 (file, (1 << t->p) - 1); |

289 | |

290 | for (i = 0; i < t->level1_size; i++) |

291 | add_locale_uint32 |

292 | (file, |

293 | t->level1[i] == EMPTY |

294 | ? 0 |

295 | : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset); |

296 | |

297 | for (i = 0; i < (t->level2_size << t->q); i++) |

298 | add_locale_uint32 |

299 | (file, |

300 | t->level2[i] == EMPTY |

301 | ? 0 |

302 | : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset); |

303 | |

304 | if (sizeof (ELEMENT) == 1) |

305 | add_locale_raw_data (file, t->level3, t->level3_size << t->p); |

306 | else if (sizeof (ELEMENT) == sizeof (uint32_t)) |

307 | add_locale_uint32_array (file, (uint32_t *) t->level3, |

308 | t->level3_size << t->p); |

309 | else |

310 | abort (); |

311 | align_locale_data (file, LOCFILE_ALIGN); |

312 | end_locale_structure (file); |

313 | |

314 | if (t->level1_alloc > 0) |

315 | free (t->level1); |

316 | if (t->level2_alloc > 0) |

317 | free (t->level2); |

318 | if (t->level3_alloc > 0) |

319 | free (t->level3); |

320 | } |

321 | #endif |

322 | |

323 | #undef EMPTY |

324 | #undef TABLE |

325 | #undef ELEMENT |

326 | #undef DEFAULT |

327 | #undef ITERATE |

328 | #undef NO_ADD_LOCALE |

329 |