(::
: hash.arg -- hash table manipulations
:
: Copyright (C) 2009,2010,2011,2014 the Argile authors
:
: This file is part of libargrt -- Argile runtime library.
:
: This software is provided 'as-is', without any express or implied
: warranty. In no event will the authors be held liable for any damages
: arising from the use of this software.
:
: Permission is granted to anyone to use this software for any purpose,
: including commercial applications, and to alter it and redistribute it
: freely, subject to the following restrictions:
:
: 1. The origin of this software must not be misrepresented; you must not
: claim that you wrote the original software. If you use this software
: in a product, an acknowledgment in the product documentation would be
: appreciated but is not required.
:
: 2. Altered source versions must be plainly marked as such, and must not
: be misrepresented as being the original software.
:
: 3. This notice may not be removed or altered from any source
: distribution.
:)
use std, list, array
class argrt_pair
text key
argrt_poly value (: union defined in list.arg :)
function(any) del
=:pair (of ):= -> type {argrt_pair.prefix ; argrt_pair.suffix}
autocast pair -> argrt_pair
=:.key:= -> text& {p the argrt_pair.key}
=:.value:= -> p.t& {p the argrt_pair.value as p.t&}
..: => :. -> pair
let p = new argrt_pair as pair
p.key = text
p.value = any
p
class argrt_hash
array of list of pair buckets
int nbuckets
function(any) del
=:hash (of ):= -> type {argrt_hash.prefix ; argrt_hash.suffix}
autocast hash -> argrt_hash
=:.nbuckets:= -> int& {h the argrt_hash.nbuckets}
=:.buckets:= -> (array of list of pair of h.t)&
h the argrt_hash .buckets as (array of list of pair of h.t)&
=:.del:= -> (function(any))& {h the argrt_hash.del}
=:for each in ```
:=
let int for_each_iterator (: avoid C-identifier collisions :)
for each for_each_iterator from 0 to hash.nbuckets - 1
let list of pair for_each_pairlist (: avoid C-identifier collisions :)
for each for_each_pairlist in hash.buckets[for_each_iterator]
p = for_each_pairlist.data
call code
=:new hash of ():= -> hash of t
new hash size as hash of t
=:new hash ():= -> hash
argrt_hash_new size
.:argrt_hash_new :. -> hash
let x = new argrt_hash as hash
x.nbuckets = size as int
x.buckets = new array of size list of pair
x
=:del hash := {argrt_hash_del hash}
.:argrt_hash_del :.
let int i = 0
while i < hash.nbuckets
delete all hash.buckets[i++]
del hash.buckets
del hash
(:
: Bob Jenkins' one at a time hash function
: (http://en.wikipedia.org/wiki/Jenkins_hash_function)
:)
..:hash :. -> nat
let nat h = 0
while *t != 0
h += *(t++) as nat
h += h << 10
h ^= h >> 6
h += h << 3
h ^= h >> 11
h += h << 15
return h
=:find in := -> pair of h.t
argrt_hash_find h text as pair of h.t
.:argrt_hash_find :. -> pair
let nat h = hash text % hash.nbuckets
let cur = hash.buckets[h]
until cur is nil
let p = cur.data
return p if p.key == text
next cur
nil as pair
=:\[]:= -> any& {argrt_hash_get_set hash text}
=:\[]:= -> h.t& {h the argrt_hash [text] as h.t&}
.:argrt_hash_get_set:. -> any&
let nat h = hash text % hash.nbuckets
let pair p
let first = hash.buckets[h]
let cur = first
until cur is nil
p = cur.data
return p.value if p.key == text
next cur
p = strdup text => nil
p.del = hash.del
let new = new list of pair p sub
let p = %% as pair
del p.key
unless p.del is nil
call p.del with p.value
del p
new <-> first
hash.buckets[h] = new
p.value
=:\[]:= -> any {argrt_hash_get hash text}
=:\[]:= -> h.t {h the argrt_hash [text] as h.t}
.:argrt_hash_get :. -> any
let found be find text in hash as hash
return found.value unless found is nil
nil
=:delete \[]:= -> bool {argrt_hash_remove hash text}
.:argrt_hash_remove :. -> bool
let nat h = hash text % hash.nbuckets
let cur = hash.buckets[h]
until cur is nil
break if cur.data.key == text
next cur
if cur??
rm cur from hash.buckets[h]
delete cur
return true
false
```