Dictionary Class

[paul doe]

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.

[paul doe]

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.

[srvaldez]

could you use your dictionary class to call function pointers by name?

[paul doe]

could you use your dictionary class to call function pointers by name?

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?

[paul doe]

Trivial example (for subs/functions without parameters):

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 )

Code uses the reference implementation found in the package. Hope it helps.

[paul doe]

Another example, showing the dictionary implemented to deal with integer keys:

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 )

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

[srvaldez]

thanks a million paul doe :-)
my apologies for the late reply, your examples are exactly what I was looking for.

How do you plan to manage the functions signature? Or the signature is always the same?

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]

thanks a million paul doe :-)

You're welcome =D

I don't understand your questions, probably because I don't know much about dictionaries except that you can store/retrieve values by keys.

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:

Code: Select all

declare function myFunc( byval as integer, byref as const string, byval as ulong ptr )

That means you're in trouble ;)

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 ;)

[paul doe]

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?

[srvaldez]

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

[paul doe]

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.

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]

@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.

[paul doe]

would you please include a make file or a batch file to build the library?

Sure. I updated the repo with a makefile. To compile the lib, use:

Code: Select all

fbc @makelib

The 'fb-dict-make.bas' file can also be included directly into your sources, to avoid the lib altogether. Hope it helps.

[srvaldez]

thank you :-)

[paul doe]

thank you :-)

You're welcome =D

Feel free to report any issues/questions you may have. I'll try to answer as soon as I can. Have fun!