Dictionary Class
Dictionary Class
Below is a link to a Dictionary class that I just uploaded to my GitHub repo:
https://github.com/glasyalabolas/fb-dictionary
Dictionaries (aka hash tables) map key-value pairs, and are super useful for a lot of tasks: databases, operating systems, compilers and interpreters, and any other sort of task that require fast indexing on a huge dataset; they all use some sort of hash table. The one provided here can be classified as a separate chaining, array hash table, and it's fully dynamic (it grows or shrinks automatically) unless one specifies otherwise.
Here are some nice and easy string hashing functions to try, if you feel like it:
String hashing functions
EDIT: revamped the repository a little, and made minor changes to the code. Thanks to D.J.Peters, MrSwiss and srvaldez for miscelaneous comments and suggestions.
EDIT: exposed a previously forgotten property. Thanks to Makoto WATANABE for reminding me.
EDIT: added support for atomic operations (multithread safety). Thanks to fxm for some useful info.
EDIT: fixed a small leak, caused by a constructor being incorrectly called.
https://github.com/glasyalabolas/fb-dictionary
Dictionaries (aka hash tables) map key-value pairs, and are super useful for a lot of tasks: databases, operating systems, compilers and interpreters, and any other sort of task that require fast indexing on a huge dataset; they all use some sort of hash table. The one provided here can be classified as a separate chaining, array hash table, and it's fully dynamic (it grows or shrinks automatically) unless one specifies otherwise.
Here are some nice and easy string hashing functions to try, if you feel like it:
String hashing functions
EDIT: revamped the repository a little, and made minor changes to the code. Thanks to D.J.Peters, MrSwiss and srvaldez for miscelaneous comments and suggestions.
EDIT: exposed a previously forgotten property. Thanks to Makoto WATANABE for reminding me.
EDIT: added support for atomic operations (multithread safety). Thanks to fxm for some useful info.
EDIT: fixed a small leak, caused by a constructor being incorrectly called.
Last edited by paul doe on May 12, 2018 0:51, edited 12 times in total.
Re: Dictionary Class
Ok, I finished revamping it. It's more flexible now, albeit a little more difficult to use, but that's of no consecuence since nobody but me will use it =D
There's some examples and a stress test included in the package. If there's any questions about the usage, I'll post some examples here. It might be useful for someone. Later.
There's some examples and a stress test included in the package. If there's any questions about the usage, I'll post some examples here. It might be useful for someone. Later.
Re: Dictionary Class
could you use your dictionary class to call function pointers by name?
Re: Dictionary Class
Yep. That's one of the uses (for implementing a compiler/interpreter, for example). How do you plan to manage the functions signature? Or the signature is always the same?srvaldez wrote:could you use your dictionary class to call function pointers by name?
Re: Dictionary Class
Trivial example (for subs/functions without parameters):
Code uses the reference implementation found in the package. Hope it helps.
Code: Select all
#include once "fb-dictionary.bi"
#include once "fb-dict-reference.bas"
sub f1()
? "Function 1 called"
end sub
sub f2()
? "Function 2 called"
end sub
sub f3()
? "Function 3 called"
end sub
sub f4()
? "Function 4 called"
end sub
sub f5()
? "Function 5 called"
end sub
function dispatch( byref funcName as const string, byval dic as Dictionary ptr ) as boolean
dim disp as sub()
disp = dic->item( funcName )
if( disp <> 0 ) then
disp()
return( true )
end if
'' Function not found
return( false )
end function
dim as Dictionary ptr dic = new Dictionary()
'' Add the entries
dic->add( "f1", @f1 )
dic->add( "f2", @f2 )
dic->add( "f3", @f3 )
dic->add( "f4", @f4 )
dic->add( "f5", @f5 )
dim as string cmd
? "Enter command (exit to finish)"
do
input">> ", cmd
if( dispatch( cmd, dic ) = false ) then
? "Unknown command"
end if
loop until( lcase( cmd ) = "exit" )
delete( dic )
Re: Dictionary Class
Another example, showing the dictionary implemented to deal with integer keys:
The code is admittedly stupid, and sort of works in a reverse way than the previous example. The only application that I can think of is for bar code readers (so you map some standard bar code format to an article name). If you can think of any other use, I'm all ears and will change the example asap =D
Code: Select all
#include once "fb-dictionary.bi"
using collections
type IntegerKey extends IDictionaryKey
public:
declare constructor( byval as integer )
declare function equals( byval as IDictionaryKey ptr ) as boolean override
declare function hash() as uinteger override
declare property value() as integer
private:
m_value as integer
end type
constructor IntegerKey( byval pValue as integer )
m_value = pValue
end constructor
property IntegerKey.value() as integer
return( m_value )
end property
function IntegerKey.equals( byval entry as IDictionaryKey ptr ) as boolean
if( *entry is IntegerKey ) then
return( iif( _
m_value = cast( IntegerKey ptr, entry )->value, true, false ) )
else
return( false )
end if
end function
function IntegerKey.hash() as uinteger
dim as integer key = m_value
key = ( key xor ( key shr 30 ) ) * &hbf58476d1ce4e5b9ull
key = ( key xor ( key shr 27 ) ) * &h94d049bb133111ebull
key = key xor ( key shr 31 )
return( key )
end function
type Dictionary extends IDictionary
public:
declare constructor()
declare constructor( byval as uinteger )
declare destructor() override
declare function add( _
byval as integer, _
byval as any ptr, _
byval as sub( byval as any ptr ) = 0 ) as boolean
declare function item( byval as integer ) as string
protected:
declare constructor( byref as Dictionary )
declare operator let( byref as Dictionary )
end type
constructor Dictionary()
base()
end constructor
constructor Dictionary( byval pSize as uinteger )
base( pSize )
end constructor
constructor Dictionary( byref rhs as Dictionary )
end constructor
operator Dictionary.let( byref rhs as Dictionary )
end operator
destructor Dictionary()
end destructor
function Dictionary.add( _
byval key as integer, _
byval value as any ptr, _
byval disposeCallback as sub( byval as any ptr ) = 0 ) as boolean
return( addEntry( new IntegerKey( key ), value, disposeCallback ) )
end function
function Dictionary.item( byval key as integer ) as string
dim as DictionaryEntry ptr entry = getEntry( @IntegerKey( key ) )
if( entry <> 0 ) then
return( *cast( string ptr, entry->value ) )
else
return( "" )
end if
end function
/'
Example of a dictionary implementation that accepts integers as keys
While the example is utterly useless, it shows that the underlying dictionary
can deal with any kind of key, not just strings. This could be most useful,
for example, with bar code readers, where you receive a code that maps to some
article, or some other uses for an integer key.
As it stands, the dictionary is more or less an array, but as of today, I'm out
of imagination.
'/
dim as string strings( 0 to 3 ) = { "File", "Edit", "View", "Options" }
dim as Dictionary ptr intDic = new Dictionary()
for i as integer = 0 to 3
intDic->add( i, @strings( i ) )
next
for i as integer = 0 to 3
? intDic->item( i )
next
sleep()
delete( intDic )
Re: Dictionary Class
thanks a million paul doe :-)
my apologies for the late reply, your examples are exactly what I was looking for.
my apologies for the late reply, your examples are exactly what I was looking for.
I don't understand your questions, probably because I don't know much about dictionaries except that you can store/retrieve values by keys.paul doe wrote:How do you plan to manage the functions signature? Or the signature is always the same?
Re: Dictionary Class
You're welcome =Dsrvaldez wrote:thanks a million paul doe :-)
As you can see, in the example I posted it is trivial to code a dispatcher for parameterless sub/function calls. The thing complicates when the signature of the function changes. Suppose you need to call a function like this by name:srvaldez wrote:I don't understand your questions, probably because I don't know much about dictionaries except that you can store/retrieve values by keys.
Code: Select all
declare function myFunc( byval as integer, byref as const string, byval as ulong ptr )
In that case, the dispatcher is definitely non trivial, and has to deal with issues like calling conventions, type/scope of parameters, and many other minutiae.
However, if you can somehow get away with parameterless functions, then you shouldn't have any troubles. By the way, ever had a look at Forth? I implemented a compiler/interpreter for it a while ago (mainly for scripting purposes), and the dispatcher looked pretty much like the one in the example above ;)
Re: Dictionary Class
By the way, does the code of the library runs on your Mac (I'll assume you're using one, as per some older posts)? Or does it need some other 'salt' for it to run correctly?
Re: Dictionary Class
have not tried it on macOS yet but as long as there are no Windows or Linux specific code it should work, don't have time at the moment, will try later.
btw, I run other OS on my Mac via VM's
btw, I run other OS on my Mac via VM's
Re: Dictionary Class
That's ok, it doesn't use any OS-dependent code, so you should be able to run it natively. I will add the thread-safe version soon, and be done with it (sans bug fixes). Glad to be of help.srvaldez wrote:have not tried it on macOS yet but as long as there are no Windows or Linux specific code it should work, don't have time at the moment, will try later.
Re: Dictionary Class
@Paul doe
would you please include a make file or a batch file to build the library?
as it is I am unable to build the lib because the *.bas files in the src directory don't have any #include in it and I don't know if there's particular order of precedence for the include files.
would you please include a make file or a batch file to build the library?
as it is I am unable to build the lib because the *.bas files in the src directory don't have any #include in it and I don't know if there's particular order of precedence for the include files.
Re: Dictionary Class
Sure. I updated the repo with a makefile. To compile the lib, use:srvaldez wrote:would you please include a make file or a batch file to build the library?
Code: Select all
fbc @makelib
Re: Dictionary Class
thank you :-)
Re: Dictionary Class
You're welcome =Dsrvaldez wrote:thank you :-)
Feel free to report any issues/questions you may have. I'll try to answer as soon as I can. Have fun!