hashtablemodule Module Reference

A chaining hash map for integers. More...

Data Types
type	nodetype
type	buckettype
type	hashtabletype

Functions/Subroutines
subroutine, public	hash_table_cr (map)
	Create a hash table. More...
subroutine, public	hash_table_da (map)
	Deallocate the hash table. More...
subroutine	ht_add (this, k, v)
	Associate the given key and value. More...
type(nodetype) function, pointer	find_node (this, k)
	Find the node containing the given key. More...
integer(i4b) function	ht_get (this, k)
	Get the value for the given key if it exists, otherwise return zero. More...
subroutine	list_cr (list, k, v)
	Create a list with the given key/value pair. More...
subroutine	list_add (this, k, v)
	Add a key/value pair to the list. More...
subroutine	list_da (list)
	Deallocate the list. More...
integer(i4b) function	hash (k)
	Map a character string to an integer. More...

Variables
integer, parameter, private	hash_size = 4993
integer, parameter, private	multiplier = 31

Detailed Description

Convenient for use as an index into arrays of arbitrary data type. The implementation is based on Arjen Markus' dictionary in the Flibs collection of Fortran utilities.

Function/Subroutine Documentation

find_node()

type(nodetype) function, pointer hashtablemodule::find_node ( class(hashtabletype)  this, character(len=*), intent(in)  k  )

private

Parameters

	this	the hash map
[in]	k	the key

Definition at line 111 of file HashTable.f90.

    ! -- dummy
    class(HashTableType) :: this !< the hash map
    character(len=*), intent(in) :: k !< the key
    ! -- local
    type(NodeType), pointer :: node
    integer(I4B) :: h
 
    h = hash(trim(k))
    node => this%buckets(h)%list
 
    ! -- search bucket for node with matching key
    do while (associated(node))
      if (node%key == k) then
        exit
      else
        node => node%next
      end if
    end do
 

Here is the call graph for this function:

hash()

integer(i4b) function hashtablemodule::hash ( character(len=*), intent(in)  k )

private

Parameters

[in]

k

the key

Definition at line 201 of file HashTable.f90.

    ! -- dummy
    character(len=*), intent(in) :: k !< the key
    ! -- local
    integer(I4B) :: h
    integer(I4B) :: i
 
    h = 0
    do i = 1, len(k)
      h = modulo(multiplier * h + ichar(k(i:i)), hash_size)
    end do
    h = 1 + modulo(h - 1, hash_size)
 

Here is the caller graph for this function:

hash_table_cr()

subroutine, public hashtablemodule::hash_table_cr

(

type(hashtabletype), pointer

map

)

Definition at line 45 of file HashTable.f90.

    ! -- dummy
    type(HashTableType), pointer :: map
    ! -- local
    integer(I4B) :: i
 
    ! -- allocate
    allocate (map)
    allocate (map%buckets(hash_size))
 
    ! -- initialize nul buckets
    do i = 1, hash_size
      map%buckets(i)%list => null()
    end do
 

Here is the caller graph for this function:

hash_table_da()

subroutine, public hashtablemodule::hash_table_da

(

type(hashtabletype), pointer

map

)

Definition at line 63 of file HashTable.f90.

    ! -- dummy
    type(HashTableType), pointer :: map
    ! -- local
    integer(I4B) :: i
 
    ! -- deallocate each bucket
    do i = 1, size(map%buckets)
      if (associated(map%buckets(i)%list)) then
        call list_da(map%buckets(i)%list)
      end if
    end do
 
    ! -- deallocate bucket array and hash table
    deallocate (map%buckets)
    deallocate (map)
 

Here is the call graph for this function:

Here is the caller graph for this function:

ht_add()

subroutine hashtablemodule::ht_add ( class(hashtabletype)  this, character(len=*), intent(in)  k, integer(i4b), intent(in)  v  )

private

Definition at line 83 of file HashTable.f90.

    ! -- dummy
    class(HashTableType) :: this
    character(len=*), intent(in) :: k
    integer(I4B), intent(in) :: v
    ! -- local
    type(NodeType), pointer :: node
    integer(I4B) :: h
 
    ! -- find the element corresponding to this key and replace index or
    !    get an unassociated elem that corresponds to this key
    node => this%find_node(k)
 
    ! -- replace index or create new entry
    if (associated(node)) then
      node%value = v
    else
      h = hash(trim(k))
      if (associated(this%buckets(h)%list)) then
        call this%buckets(h)%list%add(k, v)
      else
        call list_cr(this%buckets(h)%list, k, v)
      end if
    end if
 

Here is the call graph for this function:

ht_get()

integer(i4b) function hashtablemodule::ht_get ( class(hashtabletype)  this, character(len=*), intent(in)  k  )

private

Parameters

	this	the hash map
[in]	k	the key

Definition at line 134 of file HashTable.f90.

    ! -- dummy
    class(HashTableType) :: this !< the hash map
    character(len=*), intent(in) :: k !< the key
    ! -- return
    integer(I4B) :: v
    ! -- local
    type(NodeType), pointer :: node
 
    node => this%find_node(k)
    if (associated(node)) then
      v = node%value
    else
      v = 0
    end if
 

list_add()

subroutine hashtablemodule::list_add ( class(nodetype)  this, character(len=*), intent(in)  k, integer(i4b), intent(in)  v  )

private

Parameters

	this	the list
[in]	k	the key
[in]	v	the value

Definition at line 167 of file HashTable.f90.

    ! -- dummy
    class(NodeType) :: this !< the list
    character(len=*), intent(in) :: k !< the key
    integer(I4B), intent(in) :: v !< the value
    ! -- local
    type(NodeType), pointer :: next
 
    allocate (next)
    next%key = k
    next%value = v
    next%next => this%next
    this%next => next
 

list_cr()

subroutine hashtablemodule::list_cr ( type(nodetype), pointer  list, character(len=*), intent(in)  k, integer(i4b), intent(in)  v  )

private

Parameters

	list	pointer to the list
[in]	k	the first key
[in]	v	the first value

Definition at line 153 of file HashTable.f90.

    ! -- dummy
    type(NodeType), pointer :: list !< pointer to the list
    character(len=*), intent(in) :: k !< the first key
    integer(I4B), intent(in) :: v !< the first value
 
    allocate (list)
    list%next => null()
    list%key = k
    list%value = v
 

Here is the caller graph for this function:

list_da()

subroutine hashtablemodule::list_da ( type(nodetype), intent(in), pointer  list )

private

Parameters

[in]

list

the list

Definition at line 184 of file HashTable.f90.

    ! -- dummy
    type(NodeType), pointer, intent(in) :: list !< the list
    ! -- local
    type(NodeType), pointer :: curr
    type(NodeType), pointer :: node
 
    node => list
    do while (associated(node))
      curr => node
      node => curr%next
      deallocate (curr)
    end do
 

Here is the caller graph for this function:

Variable Documentation

hash_size

integer, parameter, private hashtablemodule::hash_size = 4993

private

Definition at line 18 of file HashTable.f90.

  integer, parameter, private :: HASH_SIZE = 4993

multiplier

integer, parameter, private hashtablemodule::multiplier = 31

private

Definition at line 19 of file HashTable.f90.

  integer, parameter, private :: MULTIPLIER = 31