Dictionary Class

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
srvaldez
Posts: 2110
Joined: Sep 25, 2005 21:54

Re: Dictionary Class

Postby srvaldez » May 03, 2018 19:57

@Paul doe
if I rebuild the library using makelib and then try to compile your first example (post #5) then I get an undefined symbol

Code: Select all

fb-dict-test.o:fake:(.text+0x3e): undefined reference to `COLLECTIONS::IDICTIONARYKEY::~IDICTIONARYKEY()'

it compiles OK with your lib, I was unable to compile the example when including fb-dict-make.bas
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 03, 2018 20:42

srvaldez wrote:it compiles OK with your lib, I was unable to compile the example when including fb-dict-make.bas

There, try it now. It complies and links ok here.

If you're using the source code directly, be sure that you don't also include 'fb-dictionary.bi' as that is intended to be the header for the lib version. Just tick (rem) the lines that contain the include and they should work fine...
srvaldez
Posts: 2110
Joined: Sep 25, 2005 21:54

Re: Dictionary Class

Postby srvaldez » May 03, 2018 21:40

thank you paul doe :-)
the lib now compiles on macOS and the example compiles and runs OK, before your last change it would give a number of undefined symbols.
thanks again :-)
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 03, 2018 21:57

srvaldez wrote:...the lib now compiles on macOS and the example compiles and runs OK...

That's really cool, glad it worked. I hope you can find an use for it ;)
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 04, 2018 1:12

Well then, just finished adding thread safety. Link to the code is in the first post, of course. An example can be found in the package in the 'fb-dict-example-5.bas' file. Here's the example in question:

Code: Select all

#include once "fb-dictionary.bi"
#include once "fb-dict-reference.bas"
/'
   Example 5: multithreading
   
   This example shows the atomicity of the operations of the dictionary.
   
   It works like this:
   Two threads are spawned that add and remove items to the same dictionary.
   At the same time, the main thread simply queries for a key, and display
   the key value and the dictionary count and the current size.
   
   The trick here is that the two threads that perform the additions and
   removals are set to work at different times that nonetheless converge
   eventually, so they'll eventually create racing conditions. Since the
   dictionary is fully dynamic, this can cause a rehash at any given moment,
   and screw the internal tables completely. So, on the next operation, the
   internal hash table is corrupted and the app may crash, or you can get
   wrong results when querying.
   
   As can be seen, the queried item remains the same, even after rehashings
   (evidenced with an increase in table size), thus showing how two different
   threads can safely work asynchronously with the same instance of the
   dictionary.
'/
'' A pair of utility functions
function rndRange( byval mn as integer, byval mx as integer ) as integer
  return int( rnd() * ( mx + 1 - mn ) + mn )
end function

function createRandomKey( byval length as uinteger ) as string
   '' Creates a random key
   dim as string ret
   
   for i as integer = 0 to length - 1
      ret &= chr( rndRange( 97, 122 ) )
   next
   
   return( ret )   
end function

'' Some common state shared by all threads
type threadState
   running          as boolean
   dictInstance   as Dictionary ptr
end type

'' This thread will add an entry to the dictionary every 0.125 seconds
sub addThread( byval pThreadState as any ptr )
   dim as threadState ptr state = pThreadState
   
   dim as double interval = 0.125
   dim as double startTime, currentTime
   
   startTime = timer()
   
   do while( state->running = true )
      currentTime = timer() - startTime
      
      if( currentTime > interval ) then
         state->dictInstance->add( createRandomKey( 3 ), cptr( any ptr, 9876 ) )
         startTime = timer()
      end if
      
      sleep( 1, 1 )
   loop
end sub

'' This thread will remove an item from the dictionay every 0.25 seconds.
sub removeThread( byval pThreadState as any ptr )
   dim as threadState ptr state = pThreadState
   
   dim as double interval = 0.25
   dim as double startTime, currentTime
   
   startTime = timer()
   
   do while( state->running = true )
      currentTime = timer() - startTime
      
      if( currentTime > interval ) then
         state->dictInstance->remove( createRandomKey( 3 ) )
         startTime = timer()
      end if
      
      sleep( 1, 1 )
   loop
end sub

''   Main code body   

'' Create a common state var and a dictionary instance
dim as threadState ptr state = new threadState
dim as Dictionary ptr dic = new Dictionary( 12 )

'' Allow duplicates in the dictionary to simplify the test
dic->allowDuplicates = true

'' Add the reference item
dic->add( "reference", cptr( any ptr, 1234 ) )

'' Set up the state for the threads...
state->dictInstance = dic
state->running = true

'' ...and spawn them
var addThreadID = threadCreate( @addThread, state )
var removeThreadID = threadCreate( @removeThread, state )

'' Main loop. Simply query for a reference key and show some stats
do while( state->running = true )
   locate 1, 1
   ? "Dictionary entry count: "; dic->count; ", size: "; dic->size
   ? "Reference item value: "; dic->item( "reference" )
   
   if( inkey() <> "" ) then
      state->running = false
   end if
   
   sleep( 1, 1 )
loop

'' Detach threads
threadWait( addThreadID )
threadWait( removeThreadID )

'' And cleanup
delete( dic )
delete( state )


Many thanks to fxm for this wonderful thread:
How to manage a critical section of code of a thread in FB
Last edited by paul doe on May 12, 2018 0:58, edited 1 time in total.
fxm
Posts: 9182
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dictionary Class

Postby fxm » May 04, 2018 5:11

Happy that this thread finally seems to serve someone :-)
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 04, 2018 5:37

fxm wrote:Happy that this thread finally seems to serve someone :-)

Hahaha don't fret, it's a great thread/tutorial =D

I used it as a reference, so perhaps it'll be better served in the FB Wiki, no? Things posted here in the forum have a tendency to get buried very soon, and there are some things one should rather not forget, or have something to be used as a quick reference without having to skim through a lot of info...
fxm
Posts: 9182
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dictionary Class

Postby fxm » May 04, 2018 11:42

paul doe wrote:
fxm wrote:Things posted here in the forum have a tendency to get buried very soon

An interesting question IMHO:
How did you find it or rediscover it?
(search from the forum, or search from google, or other way?)
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 04, 2018 11:50

fxm wrote:... How did you find it or rediscover it? Search from the forum, or search from google, or other way?)

I searched in the forum. But I already saw that thread back when you wrote it (even downloaded it for reference, but I lost many of my old files recently), so I knew it was here somewhere. I this case, the search function of the forum was actually useful for a change. I searched for "manage threads" and "fxm" as author.

There was already some work in this area, but it's lost, unfortunately: Fast multi-threading synchronization constructs
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 04, 2018 13:26

A punctualization of the inner workings of the IDictionary interface. The default behavior at creation is to not allow duplicate keys. However, this can be changed using the allowDuplicates() property provided by the IDictionary interface:

Code: Select all

#include once "fb-dictionary.bi"
#include once "fb-dict-reference.bas"

'' Create a dictionary
dim as Dictionary ptr dic = new Dictionary()

'' Allow duplicates
dic->allowDuplicates = true

'' Add two items with the same key but different values
dic->add( "Paul Doe", cptr( any ptr, 1234 ) )
dic->add( "Paul Doe", cptr( any ptr, 5678 ) )

'' Retrieves the LAST duplicated item added to the dictionary
? dic->item( "Paul Doe" )

'' Removes the LAST duplicated item added
dic->remove( "Paul Doe" )

'' The other entry is still there, however
? dic->item( "Paul Doe" )

'' Now, don't allow duplicates
dic->allowDuplicates = false

'' As you can see, if you check if the entry has been added, it returns false
if( dic->add( "Paul Doe", cptr( any ptr, 5678 ) ) = false ) then
   ? "No duplicates, please"
end if

'' The dictionary is, thus, unchanged
? dic->item( "Paul Doe" )

sleep()

delete( dic )

As you can see, the way it handles duplicates is by retrieving the last duplicated entry that was added. In a sense, the buckets are treated like they were LIFO (Last In First Out) lists. This design trait allows one to implement some things (using the example given on a previous post) like symbol shadowing/var scoping without too much hassle.
Last edited by paul doe on May 04, 2018 15:54, edited 1 time in total.
fxm
Posts: 9182
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dictionary Class

Postby fxm » May 04, 2018 15:03

paul doe wrote:I used it (How to manage a critical section of code of a thread in FB) as a reference, so perhaps it'll be better served in the FB Wiki, no? Things posted here in the forum have a tendency to get buried very soon, and there are some things one should rather not forget, or have something to be used as a quick reference without having to skim through a lot of info...

I think this kind of thread goes beyond the classic tutorial, and that it would find better place in rather the "Programmer's Guide" but creating in my opinion a new topic which would be for example "Advanced programming techniques" where experienced users could record their own knowledge in their favorite areas. I could probably myself add other topics such as "Dynamic allocation of memory", "Advanced UDT (with constructors / operators / destructor)", "Inheritance and polymorphism", ...
But it's already a lot of work to write such threads in the forum that it would be even more in the documentation, because having in addition to respect the formatting of the pages and if possible in a good English concise and precise at the same time.
And maybe all this work will interest only a few other users?
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 04, 2018 15:23

fxm wrote:... But it's already a lot of work to write such threads in the forum that it would be even more in the documentation, because having in addition to respect the formatting of the pages and if possible in a good English concise and precise at the same time.
And maybe all this work to interest only a few other users?

Yeah, I understand how you feel. However, in their transition to a more evolved state of know-how, some FB users will invariably start to look for this kind of information, so it could also prove invaluable for the future of FB. Right now, we are doomed to address the same issues over and over again, in a cyclic basis, because there's not a centralized 'hub' where one could look at the needed info in an indexed way. So, we dump things here, perhaps one day somebody will find an use for them ;)
Roland Chastain
Posts: 851
Joined: Nov 24, 2011 19:49
Location: Dakar, Senegal
Contact:

Re: Dictionary Class

Postby Roland Chastain » May 04, 2018 15:25

Hello!

@Paul

Thank you for the new edition of your library.

fxm wrote:And maybe all this work to interest only a few other users?


I have many of your code examples on my disk, and often (as Paul) I search something with "fxm" as author. So don't believe that your contributions are not much appreciated.

viewtopic.php?p=246202#p246202
Last edited by Roland Chastain on May 05, 2018 9:52, edited 1 time in total.
fxm
Posts: 9182
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dictionary Class

Postby fxm » May 04, 2018 16:53

fxm wrote:
paul doe wrote:I used it (How to manage a critical section of code of a thread in FB) as a reference, so perhaps it'll be better served in the FB Wiki, no? Things posted here in the forum have a tendency to get buried very soon, and there are some things one should rather not forget, or have something to be used as a quick reference without having to skim through a lot of info...

I think this kind of thread goes beyond the classic tutorial, and that it would find better place in rather the "Programmer's Guide" but creating in my opinion a new topic which would be for example "Advanced programming techniques" where experienced users could record their own knowledge in their favorite areas. I could probably myself add other topics such as "Dynamic allocation of memory", "Advanced UDT (with constructors / operators / destructor)", "Inheritance and polymorphism", ...
But it's already a lot of work to write such threads in the forum that it would be even more in the documentation, because having in addition to respect the formatting of the pages and if possible in a good English concise and precise at the same time.
And maybe all this work will interest only a few other users?

Administrators, perhaps we could first move these such threads (that have a pedagogic vocation) to the documentation forum, and by ensuring that their titles contain relevant key words for a easy search.
Last edited by fxm on May 04, 2018 21:51, edited 1 time in total.
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 04, 2018 20:05

Roland Chastain wrote:Thank you for the new edition of your library.

You're welcome. I'm glad that you find it useful =D

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 27 guests