December 04, 2020, 12:02:39 PM

Author Topic: [bb] Container: hash table by octothorpe [ 1+ years ago ]  (Read 522 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Container: hash table by octothorpe [ 1+ years ago ]
« on: June 29, 2017, 12:28:42 AM »
Title : Container: hash table
Author : octothorpe
Posted : 1+ years ago

Description : This library makes it painless to add many independant hash table containers for many different types of objects. This is done by storing Handle()s to your objects. Each container should hold objects of only one type.  For more information on containers, an example of how to use them, and a tutorial, <a href="../Community/posts8333.html?topic=53352" target="_blank">click here[/url].

A hash table (or map, or dictionary) is similar to an array, but you refer to elements with a key$ instead of an index%.  You also don't have to worry about the size of the container.

This library is dependant upon <a href="codearcs0d6f.html?code=1438" >Container: double-linked list[/url]

For an example of how to use this library, scroll down to the test() function at the very bottom.  This code will run standalone if you uncomment the line at the top which runs the test code.
Please post bugs or feature requests in comments.
Fundamentals

hash_new.hashC()
- create a new hash
hash_destroy(our_hash.hashC)
- delete a hash and all of its elements

Standard Operations

hash_set(our_hash.hashC, key$, value)
- set a key-value pair in a hash
hash_exists(our_hash.hashC, key$)
- check to see if a key exists in a hash
hash_delete(our_hash.hashC, key$)
- delete a key-value pair in a hash, returning the value
hash_get(our_hash.hashC, key$)
- get a value from a hash by its key$
hash_count(our_hash.hashC)
- return the number of elements in the hash

Iterators

Code: [Select]
; for item.type = each our_hash
it.hashC_iter = hash_iterator_begin(our_hash)
while hash_iterator_next(it)
key$      = hash_iterator_get_key$(it)
item.type = object.type(hash_iterator_get_value(it))
; do stuff with key$ and item
wend


Convenience

hash_get_list.listC(our_hash.hashC, key$)
- get a list from a hash by its key$, autovivifying (for hashes-of-lists)
---

The Code [/i]

Code :
Code: BlitzBasic
  1. ;test_hashC()
  2.  
  3. ; ------------------------------------------------------------------------------
  4. ;= TO DO
  5. ; ------------------------------------------------------------------------------
  6. ; iterator sanity checking (try to catch problems which might be caused by deleting elements while iterating)
  7. ; replace hashCucket[] array with a vectorC so hashes aren't all forced to share the same number of buckets?
  8.  
  9. ; ------------------------------------------------------------------------------
  10. ;= CHANGE LOG
  11. ; ------------------------------------------------------------------------------
  12. ; 12/11/2005 - iterator sample usage for quick copying and pasting
  13. ; 06/11/2005 - new() for forwards compatibility
  14. ; 06/11/2005 - dropped humpBack notation in favour of under_score
  15. ; 06/11/2005 - sexy new hash_get_list() function for hashes-of-lists
  16. ; 03/11/2005 - renamed class from hashType
  17. ; 02/11/2005 - iterators now treat null hash objects as empty hashes
  18. ; 02/11/2005 - added hash_destroy, iterators
  19.  
  20. ; ------------------------------------------------------------------------------
  21. ;= INCLUDES
  22. ; ------------------------------------------------------------------------------
  23. include "listC.bb" ; http://blitzbasic.com/codearcs/codearcs.php?code=1438
  24.  
  25. ; ------------------------------------------------------------------------------
  26. ;= CONSTANTS
  27. ; ------------------------------------------------------------------------------
  28. const HASH_MAX_BUCKETS = 512
  29.         ; more buckets will make lookups faster in crowded hashes, but will use more memory
  30.         ; theoretically, overhead memory usage is (buckets * 16 bytes)
  31.  
  32. ; ------------------------------------------------------------------------------
  33. ;= TYPES
  34. ; ------------------------------------------------------------------------------
  35. type hashC
  36.         field bucket.listC[HASH_MAX_BUCKETS-1]          ; a list of hashC_elems
  37.         field elements%
  38. end type
  39.  
  40. type hashC_elem
  41.         field key$
  42.         field value
  43. end type
  44.  
  45. type hashC_iter
  46.         field hash.hashC
  47.         field current_bucket%
  48.         field current_node.listC_node
  49.         field next_node.listC_node                      ; keep track of this so we can safely delete the current_node
  50. end type
  51.  
  52. ; ------------------------------------------------------------------------------
  53. ;= FUNDAMENTAL
  54. ; ------------------------------------------------------------------------------
  55.  
  56. ; ------------------------------------------------------------------------------
  57. function hash_new.hashC()
  58. ; create a new hash
  59.  
  60.         return new hashC
  61. end function
  62.  
  63. ; ------------------------------------------------------------------------------
  64. function hash_destroy(our_hash.hashC)
  65. ; delete a hash and all of its elements
  66.  
  67.         if our_hash = null then runtimeerror("not a valid hashC: null")
  68.  
  69.         ; loop through each bucket
  70.         for bucket_index% = 0 to HASH_MAX_BUCKETS-1
  71.                 local this_element_list.listC = our_hashucket[bucket_index]
  72.  
  73.                 if this_element_list <> null then
  74.                         ; loop through each node in each bucket's list
  75.                         local this_node.listC_node = this_element_listfirst_node
  76.                         while this_node <> null
  77.                                 ; destroy the element
  78.                                 delete object.hashC_elem(this_nodevalue)
  79.                                 ; advance to next node in list
  80.                                 this_node = this_node
  81. ext_node
  82.                         wend
  83.                         ; destroy the bucket
  84.                         list_destroy(this_element_list)
  85.                 endif
  86.         next
  87.         ; destroy the hash
  88.         delete our_hash
  89. end function
  90.  
  91. ; ------------------------------------------------------------------------------
  92. function hash_set(our_hash.hashC, key$, value)
  93. ; set a key-value pair in a hash
  94.  
  95.         if our_hash = null then runtimeerror("not a valid hashC: null")
  96.  
  97.         ; find the appropriate bucket
  98.         local our_element_list.listC = hash_choose_bucket(our_hash, key$)
  99.  
  100.         ; look for an element with a matching key
  101.         local this_node.listC_node = our_element_listfirst_node
  102.         while this_node <> null
  103.                 local this_element.hashC_elem = object.hashC_elem(this_nodevalue)
  104.        
  105.                 ; if the keys match, update the value and return from the function
  106.                 if (this_elementkey$ = key$) then
  107.                         this_elementvalue = value
  108.                         return
  109.                 endif
  110.  
  111.                 ; look at the next node
  112.                 this_node = this_node
  113. ext_node
  114.         wend
  115.  
  116.         ; if we didn't find an element to update, add a new element
  117.         local new_element.hashC_elem = new hashC_elem
  118.         new_elementkey$  = key$
  119.         new_elementvalue = value
  120.         list_push(our_element_list, handle(new_element))
  121.        
  122.         ; update element count
  123.         our_hashelements = our_hashelements + 1
  124.  
  125. end function
  126.  
  127. ; ------------------------------------------------------------------------------
  128. function hash_exists(our_hash.hashC, key$)
  129. ; check to see if a key exists in a hash
  130.  
  131.         if our_hash = null then runtimeerror("not a valid hashC: null")
  132.  
  133.         if (hash_get(our_hash, key$) > 0) then
  134.                 return true
  135.         else
  136.                 return false
  137.         endif
  138.  
  139. end function
  140.  
  141. ; ------------------------------------------------------------------------------
  142. function hash_delete(our_hash.hashC, key$)
  143. ; delete a key-value pair in a hash, returning the value
  144.  
  145.         if our_hash = null then runtimeerror("not a valid hashC: null")
  146.  
  147.         ; find the appropriate bucket
  148.         local our_element_list.listC = hash_choose_bucket(our_hash, key$)
  149.  
  150.         ; look for an element with a matching key
  151.         local this_node.listC_node = our_element_listfirst_node
  152.         while this_node <> null
  153.                 local this_element.hashC_elem = object.hashC_elem(this_nodevalue)
  154.        
  155.                 ; if the keys match, remove this element and return the value
  156.                 if (this_elementkey$ = key$) then
  157.                         local value = this_elementvalue
  158.                         delete this_element
  159.                         list_remove_node(this_node)
  160.  
  161.                         ; update element count
  162.                         our_hashelements = our_hashelements - 1
  163.  
  164.                         return value
  165.                 endif
  166.  
  167.                 ; look at the next node
  168.                 this_node = this_node
  169. ext_node
  170.         wend
  171.  
  172.         ; if we didn't find an element to update, return 0
  173.         return 0
  174.  
  175.  
  176. end function
  177.  
  178. ; ------------------------------------------------------------------------------
  179. function hash_get(our_hash.hashC, key$)
  180. ; get a value from a hash by its key$
  181.  
  182.         if our_hash = null then runtimeerror("not a valid hashC: null")
  183.  
  184.         ; find the appropriate bucket
  185.         local our_element_list.listC = hash_choose_bucket(our_hash, key$)
  186.  
  187.         ; look for an element with a matching key
  188.         local this_node.listC_node = our_element_listfirst_node
  189.         while this_node <> null
  190.                 local this_element.hashC_elem = object.hashC_elem(this_nodevalue)
  191.        
  192.                 ; if the keys match, update the value and return from the function
  193.                 if (this_elementkey$ = key$) then
  194.                         return this_elementvalue
  195.                 endif
  196.  
  197.                 ; look at the next node
  198.                 this_node = this_node
  199. ext_node
  200.         wend
  201.  
  202.         ; we didn't find the key, so return 0
  203.         return 0
  204. end function
  205.  
  206. ; ------------------------------------------------------------------------------
  207. function hash_count(our_hash.hashC)
  208. ; return the number of elements in the hash
  209.  
  210.         if our_hash = null then runtimeerror("not a valid hashC: null")
  211.         return our_hashelements
  212. end function
  213.  
  214. ; ------------------------------------------------------------------------------
  215. ;= INTERNAL
  216. ; ------------------------------------------------------------------------------
  217.  
  218. ; ------------------------------------------------------------------------------
  219. function hash_choose_bucket.listC(our_hash.hashC, key$)
  220. ; return the linked list which corresponds with the key$
  221.  
  222.         ; find the appropriate bucket index
  223.         local bucket_index% = hash_key_to_bucket_index(key$, HASH_MAX_BUCKETS)
  224.  
  225.         ; make sure bucket has been initialized
  226.         if (our_hashucket[bucket_index%] = null) then
  227.                 our_hashucket[bucket_index%] = list_new()
  228.         endif
  229.  
  230.         return our_hashucket[bucket_index%]
  231.  
  232. end function
  233.  
  234. ; ------------------------------------------------------------------------------
  235. function hash_key_to_bucket_index%(key$, modulus%)     
  236. ; come up with an index for any string, dependably coming up with the same index
  237. ; for the same string, and attempting to distribute strings evenly over the
  238. ; available indexes
  239.  
  240.         local bucket_index%
  241.  
  242.         local character_index
  243.         for character_index = 1 to len(key$)
  244.                 local character$ = mid$(key$, character_index, 1)
  245.                 bucket_index% = (bucket_index% * 123) + asc(character)            ; arbitrary math, whee!
  246.         next
  247.  
  248.         ; force the index to be valid (overflows might make the number negative)
  249.         bucket_index% = abs(bucket_index% mod modulus)
  250.  
  251.         return bucket_index%
  252.  
  253. end function
  254.  
  255. ; ------------------------------------------------------------------------------
  256. ;= ITERATORS
  257. ; ------------------------------------------------------------------------------
  258.  
  259. ; sample usage
  260.  
  261. ;       ; for item.type = each hash
  262. ;       it.hashC_iter = hash_iterator_begin(hash)
  263. ;       while hash_iterator_next(it)
  264. ;               key$      = hash_iterator_get_key$(it)
  265. ;               item.type = object.type(hash_iterator_get_value(it))
  266. ;       wend
  267.  
  268. ; ------------------------------------------------------------------------------
  269. function hash_iterator_begin.hashC_iter(our_hash.hashC)
  270. ; create a new iterator for traversing the hash
  271. ; note that elements will be returned in arbitrary order!
  272.  
  273.         it.hashC_iter = new hashC_iter
  274.         if our_hash <> null then
  275.                 ithash = our_hash
  276.                 itcurrent_bucket = -1
  277.                 itcurrent_node = null
  278.                 it
  279. ext_node = null
  280.         endif
  281.         return it
  282. end function
  283.  
  284. ; ------------------------------------------------------------------------------
  285. function hash_iterator_next(it.hashC_iter)
  286. ; advance the iterator to the next item in the hash
  287.  
  288.         ; drop out immediately if this iterator is void
  289.         if ithash = null then return false
  290.         ; if we aren't already going through a bucket's list, advance until we find one
  291.         while (it
  292. ext_node = null)
  293.                 itcurrent_bucket = itcurrent_bucket + 1
  294.                 ; if we've run out of buckets, delete the iterator and return false
  295.                 if itcurrent_bucket >= HASH_MAX_BUCKETS then
  296.                         delete it
  297.                         return false
  298.                 endif
  299.                
  300.                 local bucket_list.listC = ithashucket[itcurrent_bucket]
  301.                 if (bucket_list <> null) then
  302.                         ; try the first node of this bucket
  303.                         ; (if the bucket list is empty, this will be null and the next bucket will be tried,
  304.                         ;  otherwise the last part of this function will advance us onto this node)
  305.                         it
  306. ext_node = bucket_listfirst_node
  307.                 endif
  308.         wend
  309.         ; while we're in a bucket list, simply advance to the next node
  310.         itcurrent_node = it
  311. ext_node
  312.         it
  313. ext_node = itcurrent_node
  314. ext_node
  315.         return true
  316. end function
  317.  
  318. ; ------------------------------------------------------------------------------
  319. function hash_iterator_get_key$(it.hashC_iter)
  320. ; return the key of the element the iterator is currently on
  321.  
  322.         local this_element.hashC_elem = object.hashC_elem(itcurrent_nodevalue)
  323.         return this_elementkey$
  324. end function
  325.  
  326. ; ------------------------------------------------------------------------------
  327. function hash_iterator_get_value(it.hashC_iter)
  328. ; return the key of the element the iterator is currently on
  329.  
  330.         local this_element.hashC_elem = object.hashC_elem(itcurrent_nodevalue)
  331.         return this_elementvalue
  332. end function
  333.  
  334. ; ------------------------------------------------------------------------------
  335. ;= CONVENIENCE
  336. ; ------------------------------------------------------------------------------
  337.  
  338. ; ------------------------------------------------------------------------------
  339. function hash_get_list.listC(our_hash.hashC, key$)
  340. ; get a list from a hash by its key$, autovivifying (for hashes-of-lists)
  341.  
  342.         if our_hash = null then runtimeerror("not a valid hashC: null")
  343.  
  344.         list.listC = object.listC(hash_get(our_hash, key$))
  345.         if list = null then
  346.                 list = list_new()
  347.                 hash_set(our_hash, key$, handle(list))
  348.         endif
  349.         return list
  350. end function
  351.  
  352. ; ------------------------------------------------------------------------------
  353. ;= TESTING
  354. ; ------------------------------------------------------------------------------
  355. type hash_sample_type
  356.         field value$
  357. end type
  358. function hash_sample_type_new.hash_sample_type(value$)
  359.         i.hash_sample_type = new hash_sample_type
  360.         ivalue$ = value$
  361.         return i
  362. end function
  363. function test_hashC()
  364.         print "test_hashC()"
  365.  
  366.         local our_hash.hashC = new hashC
  367.  
  368.         hash_set(our_hash, "apples", 1)
  369.         hash_set(our_hash, "oranges", 2)
  370.         hash_set(our_hash, "bananas", 8)
  371.  
  372.         print "displaying all elements..."
  373.         it.hashC_iter = hash_iterator_begin(our_hash)
  374.         while hash_iterator_next(it)
  375.                 key$ = hash_iterator_get_key$(it)
  376.                 value = hash_iterator_get_value(it)
  377.                 print key$ + " => " + value
  378.         wend
  379.        
  380.         hash_delete(our_hash, "apples")
  381.         hash_delete(our_hash, "bananas")
  382.         hash_delete(our_hash, "grapefruit")
  383.  
  384.         print hash_get(our_hash, "oranges")
  385.         print hash_exists(our_hash, "oranges")
  386.         print hash_delete(our_hash, "oranges")
  387.         print hash_get(our_hash, "oranges")
  388.         print hash_exists(our_hash, "oranges")
  389.  
  390.         print "displaying all elements..."
  391.         it.hashC_iter = hash_iterator_begin(our_hash)
  392.         while hash_iterator_next(it)
  393.                 key$ = hash_iterator_get_key$(it)
  394.                 value = hash_iterator_get_value(it)
  395.                 print key$ + " => " + value
  396.         wend
  397.        
  398.         hash_destroy(our_hash)
  399.  
  400.         ; test new hash_get_list() function
  401.         print "test new hash_get_list() function..."
  402.        
  403.         local HoL.hashC = new hashC
  404.  
  405.         list_push(hash_get_list(HoL, "milk"), handle(hash_sample_type_new("cow")))
  406.         list_push(hash_get_list(HoL, "milk"), handle(hash_sample_type_new("goat")))
  407.         list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("gouda")))
  408.         list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("edam")))
  409.         list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("cheddar")))
  410.  
  411.         it.hashC_iter = hash_iterator_begin(HoL)
  412.         while hash_iterator_next(it)
  413.                 key$ = hash_iterator_get_key$(it)
  414.                 value = hash_iterator_get_value(it)
  415.  
  416.                 print key$ + ":"
  417.  
  418.                 list_it.listC_iter = list_iterator_begin(object.listC(value))
  419.                 while list_iterator_next(list_it)
  420.                         i.hash_sample_type = object.hash_sample_type(list_iterator_get(list_it))
  421.  
  422.                         print "  " + ivalue$
  423.  
  424.                 wend
  425.         wend
  426.  
  427.         print "press any key to exit..."
  428.         waitkey
  429.         end
  430.  
  431. end function


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal