]> git.saurik.com Git - apt.git/blame - triehash/tests/test-multi-byte-level
projects / apt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
The entire concept of PendingError() is flawed :/.
[apt.git] / triehash / tests / test-multi-byte-level
CommitLineData
e2073b02
JAK		 1#!/bin/sh
2. $(dirname $(readlink -f $0))/framework.sh
3
4# Check that building a single-byte trie works
5testsuccessequal "\
6┌────────────────────────────────────────────────────┐
7│ Initial trie │
8└────────────────────────────────────────────────────┘
9
10├── V
11│ ├── e
12│ │ ├── r
13│ │ │ ├── y
14│ │ │ │ ├── L
15│ │ │ │ │ ├── o
16│ │ │ │ │ │ ├── n
17│ │ │ │ │ │ │ ├── g
18│ │ │ │ │ │ │ │ ├── W
19│ │ │ │ │ │ │ │ │ ├── o
20│ │ │ │ │ │ │ │ │ │ ├── r
21│ │ │ │ │ │ │ │ │ │ │ ├── d → VeryLongWord
22├── W
23│ ├── o
24│ │ ├── r
25│ │ │ ├── d → Word
26│ │ │ │ ├── -
27│ │ │ │ │ ├── _
28│ │ │ │ │ │ ├── 0 → Word-_0
29│ │ │ │ ├── 2 → Label
30┌────────────────────────────────────────────────────┐
31│ Rebuilt trie │
32└────────────────────────────────────────────────────┘
33
34├── V
35│ ├── e
36│ │ ├── r
37│ │ │ ├── y
38│ │ │ │ ├── L
39│ │ │ │ │ ├── o
40│ │ │ │ │ │ ├── n
41│ │ │ │ │ │ │ ├── g
42│ │ │ │ │ │ │ │ ├── W
43│ │ │ │ │ │ │ │ │ ├── o
44│ │ │ │ │ │ │ │ │ │ ├── r
45│ │ │ │ │ │ │ │ │ │ │ ├── d → VeryLongWord
46├── W
47│ ├── o
48│ │ ├── r
49│ │ │ ├── d → Word
50│ │ │ │ ├── -
51│ │ │ │ │ ├── _
52│ │ │ │ │ │ ├── 0 → Word-_0
53│ │ │ │ ├── 2 → Label
54┌────────────────────────────────────────────────────┐
55│ Trie for words of length 4 │
56└────────────────────────────────────────────────────┘
57
58├── W
59│ ├── o
60│ │ ├── r
61│ │ │ ├── d → Word
62┌────────────────────────────────────────────────────┐
63│ Trie for words of length 5 │
64└────────────────────────────────────────────────────┘
65
66├── W
67│ ├── o
68│ │ ├── r
69│ │ │ ├── d
70│ │ │ │ ├── 2 → Label
71┌────────────────────────────────────────────────────┐
72│ Trie for words of length 7 │
73└────────────────────────────────────────────────────┘
74
75├── W
76│ ├── o
77│ │ ├── r
78│ │ │ ├── d
79│ │ │ │ ├── -
80│ │ │ │ │ ├── _
81│ │ │ │ │ │ ├── 0 → Word-_0
82┌────────────────────────────────────────────────────┐
83│ Trie for words of length 12 │
84└────────────────────────────────────────────────────┘
85
86├── V
87│ ├── e
88│ │ ├── r
89│ │ │ ├── y
90│ │ │ │ ├── L
91│ │ │ │ │ ├── o
92│ │ │ │ │ │ ├── n
93│ │ │ │ │ │ │ ├── g
94│ │ │ │ │ │ │ │ ├── W
95│ │ │ │ │ │ │ │ │ ├── o
96│ │ │ │ │ │ │ │ │ │ ├── r
97│ │ │ │ │ │ │ │ │ │ │ ├── d → VeryLongWord" triehash --multi-byte=0 -l tree /dev/stdin
98
99# Two byte optimization
100testsuccessequal "\
101┌────────────────────────────────────────────────────┐
102│ Initial trie │
103└────────────────────────────────────────────────────┘
104
105├── Ve
106│ ├── ry
107│ │ ├── Lo
108│ │ │ ├── ng
109│ │ │ │ ├── Wo
110│ │ │ │ │ ├── rd → VeryLongWord
111├── Wo
112│ ├── rd → Word
113│ │ ├── -_
114│ │ │ ├── 0 → Word-_0
115│ │ ├── 2 → Label
116┌────────────────────────────────────────────────────┐
117│ Rebuilt trie │
118└────────────────────────────────────────────────────┘
119
120├── Ve
121│ ├── ry
122│ │ ├── Lo
123│ │ │ ├── ng
124│ │ │ │ ├── Wo
125│ │ │ │ │ ├── rd → VeryLongWord
126├── Wo
127│ ├── rd → Word
128│ │ ├── -
129│ │ │ ├── _0 → Word-_0
130│ │ ├── 2 → Label
131┌────────────────────────────────────────────────────┐
132│ Trie for words of length 4 │
133└────────────────────────────────────────────────────┘
134
135├── Wo
136│ ├── rd → Word
137┌────────────────────────────────────────────────────┐
138│ Trie for words of length 5 │
139└────────────────────────────────────────────────────┘
140
141├── Wo
142│ ├── rd
143│ │ ├── 2 → Label
144┌────────────────────────────────────────────────────┐
145│ Trie for words of length 7 │
146└────────────────────────────────────────────────────┘
147
148├── Wo
149│ ├── rd
150│ │ ├── -_
151│ │ │ ├── 0 → Word-_0
152┌────────────────────────────────────────────────────┐
153│ Trie for words of length 12 │
154└────────────────────────────────────────────────────┘
155
156├── Ve
157│ ├── ry
158│ │ ├── Lo
159│ │ │ ├── ng
160│ │ │ │ ├── Wo
161│ │ │ │ │ ├── rd → VeryLongWord" triehash --multi-byte=1 -l tree /dev/stdin
162# Four byte optimization
163testsuccessequal "\
164┌────────────────────────────────────────────────────┐
165│ Initial trie │
166└────────────────────────────────────────────────────┘
167
168├── Very
169│ ├── Long
170│ │ ├── Word → VeryLongWord
171├── Word → Word
172│ ├── -
173│ │ ├── _
174│ │ │ ├── 0 → Word-_0
175│ ├── 2 → Label
176┌────────────────────────────────────────────────────┐
177│ Rebuilt trie │
178└────────────────────────────────────────────────────┘
179
180├── Very
181│ ├── Long
182│ │ ├── Word → VeryLongWord
183├── Word → Word
184│ ├── -
185│ │ ├── _
186│ │ │ ├── 0 → Word-_0
187│ ├── 2 → Label
188┌────────────────────────────────────────────────────┐
189│ Trie for words of length 4 │
190└────────────────────────────────────────────────────┘
191
192├── Word → Word
193┌────────────────────────────────────────────────────┐
194│ Trie for words of length 5 │
195└────────────────────────────────────────────────────┘
196
197├── Word
198│ ├── 2 → Label
199┌────────────────────────────────────────────────────┐
200│ Trie for words of length 7 │
201└────────────────────────────────────────────────────┘
202
203├── Word
204│ ├── -
205│ │ ├── _
206│ │ │ ├── 0 → Word-_0
207┌────────────────────────────────────────────────────┐
208│ Trie for words of length 12 │
209└────────────────────────────────────────────────────┘
210
211├── Very
212│ ├── Long
213│ │ ├── Word → VeryLongWord" triehash --multi-byte=2 -l tree /dev/stdin
214# Eigh byte optimization
215testsuccessequal "\
216┌────────────────────────────────────────────────────┐
217│ Initial trie │
218└────────────────────────────────────────────────────┘
219
220├── VeryLong
221│ ├── W
222│ │ ├── o
223│ │ │ ├── r
224│ │ │ │ ├── d → VeryLongWord
225├── W
226│ ├── o
227│ │ ├── r
228│ │ │ ├── d → Word
229│ │ │ │ ├── -
230│ │ │ │ │ ├── _
231│ │ │ │ │ │ ├── 0 → Word-_0
232│ │ │ │ ├── 2 → Label
233┌────────────────────────────────────────────────────┐
234│ Rebuilt trie │
235└────────────────────────────────────────────────────┘
236
237├── V
238│ ├── eryLongW
239│ │ ├── o
240│ │ │ ├── r
241│ │ │ │ ├── d → VeryLongWord
242├── W
243│ ├── o
244│ │ ├── r
245│ │ │ ├── d → Word
246│ │ │ │ ├── -
247│ │ │ │ │ ├── _
248│ │ │ │ │ │ ├── 0 → Word-_0
249│ │ │ │ ├── 2 → Label
250┌────────────────────────────────────────────────────┐
251│ Trie for words of length 4 │
252└────────────────────────────────────────────────────┘
253
254├── W
255│ ├── o
256│ │ ├── r
257│ │ │ ├── d → Word
258┌────────────────────────────────────────────────────┐
259│ Trie for words of length 5 │
260└────────────────────────────────────────────────────┘
261
262├── W
263│ ├── o
264│ │ ├── r
265│ │ │ ├── d
266│ │ │ │ ├── 2 → Label
267┌────────────────────────────────────────────────────┐
268│ Trie for words of length 7 │
269└────────────────────────────────────────────────────┘
270
271├── W
272│ ├── o
273│ │ ├── r
274│ │ │ ├── d
275│ │ │ │ ├── -
276│ │ │ │ │ ├── _
277│ │ │ │ │ │ ├── 0 → Word-_0
278┌────────────────────────────────────────────────────┐
279│ Trie for words of length 12 │
280└────────────────────────────────────────────────────┘
281
282├── VeryLong
283│ ├── W
284│ │ ├── o
285│ │ │ ├── r
286│ │ │ │ ├── d → VeryLongWord" triehash --multi-byte=3 -l tree /dev/stdin
287
288
289# Check that building a multi-byte trie works
290testsuccessequal "\
291┌────────────────────────────────────────────────────┐
292│ Initial trie │
293└────────────────────────────────────────────────────┘
294
295├── VeryLong
296│ ├── Word → VeryLongWord
297├── Word → Word
298│ ├── -
299│ │ ├── _
300│ │ │ ├── 0 → Word-_0
301│ ├── 2 → Label
302┌────────────────────────────────────────────────────┐
303│ Rebuilt trie │
304└────────────────────────────────────────────────────┘
305
306├── Very
307│ ├── LongWord → VeryLongWord
308├── Word → Word
309│ ├── -
310│ │ ├── _
311│ │ │ ├── 0 → Word-_0
312│ ├── 2 → Label
313┌────────────────────────────────────────────────────┐
314│ Trie for words of length 4 │
315└────────────────────────────────────────────────────┘
316
317├── Word → Word
318┌────────────────────────────────────────────────────┐
319│ Trie for words of length 5 │
320└────────────────────────────────────────────────────┘
321
322├── Word
323│ ├── 2 → Label
324┌────────────────────────────────────────────────────┐
325│ Trie for words of length 7 │
326└────────────────────────────────────────────────────┘
327
328├── Word
329│ ├── -
330│ │ ├── _
331│ │ │ ├── 0 → Word-_0
332┌────────────────────────────────────────────────────┐
333│ Trie for words of length 12 │
334└────────────────────────────────────────────────────┘
335
336├── VeryLong
337│ ├── Word → VeryLongWord" triehash -l tree /dev/stdin
338
339
340###### CHANGE THE WORDS FOR THE FOLLOWING TESTS #######
341WORDS="Word"
342
343# Check that we are generating the proper multi-byte and fallback sessions
344testsuccessequal "#include \"/dev/null\"
345#ifdef __GNUC__
346typedef uint16_t __attribute__((aligned (1))) triehash_uu16;
347typedef char static_assert16[__alignof__(triehash_uu16) == 1 ? 1 : -1];
348typedef uint32_t __attribute__((aligned (1))) triehash_uu32;
349typedef char static_assert32[__alignof__(triehash_uu32) == 1 ? 1 : -1];
350typedef uint64_t __attribute__((aligned (1))) triehash_uu64;
351typedef char static_assert64[__alignof__(triehash_uu64) == 1 ? 1 : -1];
352#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
353#define onechar(c, s, l) (((uint64_t)(c)) << (s))
354#else
355#define onechar(c, s, l) (((uint64_t)(c)) << (l-8-s))
356#endif
357#if (!defined(__ARM_ARCH) || defined(__ARM_FEATURE_UNALIGNED)) && !defined(TRIE_HASH_NO_MULTI_BYTE)
358#define TRIE_HASH_MULTI_BYTE
359#endif
360#endif /*GNUC */
361#ifdef TRIE_HASH_MULTI_BYTE
362static enum PerfectKey PerfectHash4(const char *string)
363{
364 switch(*((triehash_uu32*) &string[0])) {
365 case 0| onechar('W', 0, 32)| onechar('o', 8, 32)| onechar('r', 16, 32)| onechar('d', 24, 32):
366 return Word;
367 }
368 return Unknown;
369}
370#else
371static enum PerfectKey PerfectHash4(const char *string)
372{
373 switch(string[0]) {
374 case 'W':
375 switch(string[1]) {
376 case 'o':
377 switch(string[2]) {
378 case 'r':
379 switch(string[3]) {
380 case 'd':
381 return Word;
382 }
383 }
384 }
385 }
386 return Unknown;
387}
388#endif /* TRIE_HASH_MULTI_BYTE */
389 enum PerfectKey PerfectHash(const char *string, size_t length)
390{
391 switch (length) {
392 case 4:
393 return PerfectHash4(string);
394 default:
395 return Unknown;
396 }
397}" triehash -H /dev/null /dev/stdin
398
399
400# Check that we are generating no multi-byte session
401testsuccessequal "#include \"/dev/null\"
402static enum PerfectKey PerfectHash4(const char *string)
403{
404 switch(string[0]) {
405 case 'W':
406 switch(string[1]) {
407 case 'o':
408 switch(string[2]) {
409 case 'r':
410 switch(string[3]) {
411 case 'd':
412 return Word;
413 }
414 }
415 }
416 }
417 return Unknown;
418}
419 enum PerfectKey PerfectHash(const char *string, size_t length)
420{
421 switch (length) {
422 case 4:
423 return PerfectHash4(string);
424 default:
425 return Unknown;
426 }
427}" triehash --multi-byte=0 -H /dev/null /dev/stdin
APT (for Cydia)