In a symbol table of 2^N different symbols, there is a way for a routine to find any given symbol with at most N+1 string comparisons, provided that the table is properly "indexed". (I don't think "hashed" is the right word, but that's unimportant.) If somebody writing an IDE can use it, I could write an applet that does the following. The input is a text file with lines like
IDHELP equ 9
(syntax need not be very rigid) and the output is a file consisting of records each of which contains 4 fields:
field0 = dword = value of the symbol in field3.
field1 = dword = either:
-- the offset, within this table, of the next record to look at if the symbol being sought is "less than" the symbol in field3
-- -1 if the symbol sought is not in the table.
field2 = dword, similar to field1 except that the sought-for symbol is "greater than" this one.
field3 = asciiz string, the symbol itself.
To explain, the string "ABC" is less than "ABCD" and greater than "ABBC", for example.
Once we have that tool, we could make a DLL called e.g. LOOKUP.DLL. That dll contains (or maybe reads from disk) the indexed table above. The dll has a procedure called say
which returns 1 if the symbol is found and zero otherwise.
Anybody got any big use for such tools? I haven't looked into very many IDE's; maybe some of them are ahead of me on this issue :roll:
Posted on 2004-10-31 22:20:20 by LarryH
you can look at FASM sources if you want to see an implementation of an efficient hash table
Posted on 2004-10-31 22:25:57 by comrade
Thx, I just looked into FASM. Their algo looks faster than mine and would not require such a bulky index. But I still like the idea of a lookup dll.
Posted on 2004-11-03 02:29:18 by LarryH
i think fasm uses fnv hash some description is available here

Posted on 2004-11-03 13:36:18 by CodeKnight