Possible to "Redim" Dictionary?

[ReneMiner]

I wonder if it's possible to "redim" the dictionary if I need more keys.

The help warns about:


More than NumberOfKeys keys can be stored into a dictionary but this will slow down all operations.
So I fear to reach the limit but also to use up unnecessary memory if not 5000 keys used...

Now I thought about some "Redim Preserve" in this manner:



Uses "Dictionary"
Dword pDictionary = Dictionary_Create(1000)
' ...
' now discover I have reached limit, 1000 Keys are used...

' copy dictionary to some buffer
Dword pBuffer = Heap_Alloc( Dictionary_MemInfo(pDictionary, %HT_MemInfo_Total) )
Memory_Copy( pDictionary, pBuffer, Heap_Size(pBuffer) )

'kill the old dictionary
Dictionary_Free(pDictionary)

' create a bigger one
pDicitonary = Dictionary_Create(2000)

' put the data back?
Memory_Copy( pBuffer, pDictionary, Heap_Size(pBuffer) )


would this work or corrupt the dictionary-content?

[ErosOlmi]

No, it is not possible to REDIM and you cannot just copy data.
A thinBasic dictionary is like an hash table with separated linked list chaining used for overflow (when two o more keys generate the same hash value)

http://en.wikipedia.org/wiki/Hash_table


8286

The reason why a hash table MUST have a fixed number of buckets is because the hash value calculated over a key MUST give the bucket where to store key/data pair.
If I change the number of pre-defined buckets, all the hash values will change creating a mess.

I need to develop a new function that:

create a new hash table with the new number of keys (buckets)
get all the keys from original dictionary
recalculate the hash
remap data to the new hash table/hash value
delete old hash table


In the meantime you can just double or more the initial number of keys needed.
This will not much increase your memory consumption. Every bucket (even if empty) will just consume 2 DWORD (8 bytes) so 10000 empty buckets will consume 80Kb

Ciao
Eros

[Charles Pegge]

Hi Eros

I use a scheme, whereby a block of keys can be dumped when it falls out of scope. The hash table never has to be rebuilt. Any data links which point beyond the truncated boundary, are automatically nulled whenever they are encountered. I use this facility for disallocating local variables etc at the end of a function, while leaving globals in place.

But the table I use is currently static (100k). though it would be possible to make it stretchable by mapping the table into a dynamic string.

Food for thought?

Charles

[ErosOlmi]

Hi Charles,

I cannot use such a "static" scheme in thinBasic dictionary because every dictionary has its own life.

Anyway, yes: a lot of food for thoughts.

Stanley Durham has posted many interesting variations of data structures and algorithms in Power Basic forum: http://www.powerbasic.com/support/pbforums/forumdisplay.php?f=12 and search for OLIB or HLIB
All is work can be foud here: http://www.deadtheorywalking.com/power_basic_code/power_basic_code.html

Maybe I can "steal" some ideas ;)

Ciao
Eros

[Charles Pegge]

Stealing ideas is good, :) but sometimes it is easier to build from the base.

The compiler entity table I use, is really a cross-breed between a regular hash table and a stack. The table boundary is recorded before entering a function, then restored on leaving the function, chopping off the local data. This technique can be applied to any level of nesting.

[peter]

Stealing ideas is good. :drink:

Is not this a punishable act? Here in my world we have own ideas.

[ErosOlmi]

The compiler entity table I use, is really a cross-breed between a regular hash table and a stack. The table boundary is recorded before entering a function, then restored on leaving the function, chopping off the local data. This technique can be applied to any level of nesting.

Is for sure a clever idea: a common hash table divided into slices.
It is quite easy to manage and very fast because you do not have to de-allocate/allocate every time but just clean a slice.

Looking at the code I use allocate local function variables (an array of hash tables, one for each function stack level, allocated/de-allocated at every function execution) ...
... maybe I will steal something from your suggestion.

Thanks a lot
Eros

[ReneMiner]

Stealing ideas is good. :drink:

Is not this a punishable act? Here in my world we have own ideas.


Let's call it "involuntary sharing" then :D

[peter]

An attack?

I am willing to quitting this forum, for sure.

[ReneMiner]

No attack! we're just doing it for fun - wir machen doch nur:punish: Spaß