basis/persistent/hashtables/nodes/full/full.factor

   1 ! Based on Clojure's PersistentHashMap by Rich Hickey.
   2
   3 USING: math accessors kernel arrays sequences sequences.private
   4 locals
   5 persistent.sequences
   6 persistent.hashtables.config
   7 persistent.hashtables.nodes ;
   8 IN: persistent.hashtables.nodes.full
   9
  10 M:: full-node (new-at) ( shift value key hashcode full-node -- node' added-leaf )
  11     [let* | nodes [ full-node nodes>> ]
  12             idx [ hashcode full-node shift>> mask ]
  13             n [ idx nodes nth-unsafe ] |
  14         shift radix-bits + value key hashcode n (new-at)
  15         [let | new-leaf [ ] n' [ ] |
  16             n n' eq? [
  17                 full-node
  18             ] [
  19                 n' idx nodes new-nth shift <full-node>
  20             ] if
  21             new-leaf
  22         ]
  23     ] ;
  24
  25 M:: full-node (pluck-at) ( key hashcode full-node -- node' )
  26     [let* | idx [ hashcode full-node shift>> mask ]
  27             n [ idx full-node nodes>> nth ]
  28             n' [ key hashcode n (pluck-at) ] |
  29         n n' eq? [
  30             full-node
  31         ] [
  32             n' [
  33                 n' idx full-node nodes>> new-nth
  34                 full-node shift>>
  35                 <full-node>
  36             ] [
  37                 hashcode full-node shift>> bitpos bitnot full-bitmap-mask bitand
  38                 idx full-node nodes>> remove-nth
  39                 full-node shift>>
  40                 <bitmap-node>
  41             ] if
  42         ] if
  43     ] ;
  44
  45 M:: full-node (entry-at) ( key hashcode full-node -- node' )
  46     key hashcode
  47     hashcode full-node shift>> mask
  48     full-node nodes>> nth-unsafe
  49     (entry-at) ;
  50
  51 M: full-node >alist% nodes>> >alist-each% ;