source: proto/SymbolTable/README_SymbolTable @ 1228

Last change on this file since 1228 was 1228, checked in by vla24, 8 years ago

Integrated symbol table with xmlwf. There are various implementations for the symbol table, please read /proto/SymbolTable/README_SymbolTable for more information.

File size: 1.8 KB
Line 
1STANDARD LIBRARY LENGTH SORTING
2
3A symbol table using STL C library.
4To compile      : make symtab_stl
5Data structure  : lib/symtab/symtab.*
6
7---------------------------------
8
9LENGTH SORTING
10
11This is Ken's implementation. We are using mask-equal-and/or method
12To compile      : make symtab_ls
13Data structure  : lib/symtab/ls_symbol_table*.*
14
15---------------------------------
16
17HASH TABLE (Jestress)
18
19This symbol table uses Jestress hashing function.
20To compile      : make symtab_hash
21Data structure  : lib/symtab/hash_symbol_table.*
22
23---------------------------------
24
25PARALLEL BITSTREAM-BASED LENGTH SORTING
26
271. USE_IDENTITY_SORT    f(L) = L
28Data structure          : lib/symtab/pbgs_identity_symbol_table.h
29There are 2 different implementations:
30  a. We evaluate the bitstreams using interpose32 and advance32. This implementation is slower than the other one.
31     To compile         : make symtab_pbgs_adv
32  b. We evaluate the bitstreams using one shift right for each bitutil.advance call
33     To compile         : make symtab_pbgs
34
352. USE_LOG_SORT         f(L) = log(L)
36To compile              : make symtab_pbgs_log
37Data structure          : lib/symtab/pbgs_log_symbol_table.h
38
393. USE_DIV_SORT         f(L) = L/4
40NOTE: This implementation is not ready yet
41To compile              : make symtab_pbgs_div
42Data structure          : lib/symtab/pbgs_div_symbol_table.h
43
44
45HASH TABLE IMPLEMENTATION NOTES:
46- All the 3 strategies are using the same hash table implementation (bitstream_hash_table.h) and the same comparison implementation (equal_compare.h).
47
48
49XMLWF IMPLEMENTATION NOTES:
50- XMLWF makes use of overlapping buffer so that the system could look ahead or look back as needed.
51  - For string buffer implementation, the system can look 32 bytes back/ahead (1 byte = 1 character)
52  - For hash value implementation, the system can look 128 bits back/ahead (1 bit = 1 character/position)
Note: See TracBrowser for help on using the repository browser.