Anonymous user
Hash join: Difference between revisions
m
→{{header|Forth}}
Line 519:
include FMS-SILib.f
\ Since the same join attribute, Name, occurs more than once
\ in both tables for this problem we need a hash table that
\ will accept and retrieve multiple identical keys if we want
\ an efficient solution for large tables. We make use
\ of the hash collision handling feature of class hash-table.
\ Subclass hash-table-m allows multiple entries with the same key.
\ After a get: hit one can inspect for additional entries with
\ the same key by using next: until false is returned.
:class hash-table-m <super hash-table
\ called within insert: method in superclass
:m (do-search): ( node hash -- idx hash false )
swap drop idx @ swap false ;m
:m next: ( -- val true | false )
last-node @ dup
if
begin
( node ) next: dup
while
dup key@: @: key-addr @ key-len @ compare 0=
if dup last-node ! val@: true exit then
repeat
;class
\ begin hash phase
: obj ( addr len -- obj )
heap> string+ dup >r !: r> ;
hash-table-m
s"
s"
s"
s"
s"
s" Vampires " obj s" Jonah" r insert:
\ end hash phase
\ create Age Name table S
o{ o{ 27 'Jonah' }
o{ 18 'Alan' }
Line 534 ⟶ 565:
o{ 18 'Popeye' }
o{ 28 'Alan' } } value s
\ Q is a place to store the relation
object-list2 Q
▲ then drop ;
: join \ { obj | list -- }
0 locals| list obj |
1 obj at: @: r get: \ hash the join-attribute and search table r
▲: join
if \ we have a match, so concatenate and save in q
heap> object-list2 to list list q add: \ start a new sub-list in q
0 obj at: copy: list add: \ place age from list s in q
1 obj at: copy: list add: \ place join-attribute (name) from list s in q
( str-obj ) copy: list add: \ place first nemesis in q
begin
r next: \ check for more nemeses
while
( str-obj ) copy: list add: \ place next nemesis in q
repeat
then ;
: probe
begin
s each: \ for each tuple object in s
while
( obj ) join \ pass the object to function join
repeat ;
q p: \ print the saved relation
\ free allocated memory
s <free
r free2:
q free:
</lang>
{{out}}
<pre>
o{
o{ 27 'Jonah' Whales Spiders Vampires }
o{ 18 'Alan' Ghosts Zombies
o{ 28 'Glory' Buffy }
o{ 28 'Alan' Ghosts Zombies
</pre>
| |||