[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Sv: Misc

> 2.) PFile
> I now implemented the core PakFile writing stuff using normal search
> trees, not the complete stuff, because I (grr) left my algorithms book
> at home and thus dont know the algo for converting a generic (balanced)
> tree to a minimal complete one (taking up as little space as possible).
> Well, later we can add this.
> Bjarke, you convinced me concerning added hashing. I also think 4byte
> keys are the way to go.
I've already implemented a complete hashed binary search tree based on an
array. If you want to do it again, that's fine, it just seems a bit weird to
do things like that.

Oh yeah, the hashed tree supports pre-hashing the hash value from a key and
then passing that value along with the entry-to-search-for's key whenever
this entry is desired to be searched for in any tree. That way, only one
hashing operation is needed for searching for the same entry in several

Another thing is that I changed the way the hashing is done from what I
originally sketched out. The original idea was to do a XOR operation on a
value for each byte of the string that is being hashed. However, it suddenly
struck me that that algorithm would not make the hashed value fill the
entire possible range of the variable its being stored in, as most filenames
are text, and there are bits that the binary representation of no text
characters has set. I instead changed XOR to +, the addition operator.

Btw, you don't need to convert uncomplete balanced trees to complete trees,
since all the trees you are going to be building will be already complete...