WPS/geogrid/src/hash_module.f90

   1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   2 ! MODULE HASH_MODULE
   3 !
   4 ! Purpose: This module provides a dictionary/hashtable with insert, search, and
   5 !   remove routines.
   6 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   7 module hash_module
   8
   9    ! Parameters
  10    integer, parameter :: TABLESIZE=53     ! Number of spaces in the table (the
  11                                           !   number of linked lists)
  12
  13    type hashnode
  14       character (len=256) :: entry         ! The actual string to be stored
  15       type (hashnode), pointer :: next
  16    end type hashnode
  17
  18    type hashnode_ptr
  19       type (hashnode), pointer :: p        ! Pointer to a list of entries
  20    end type hashnode_ptr
  21
  22    type hashtable
  23       type (hashnode_ptr), dimension(TABLESIZE) :: table ! The hashtable array
  24    end type hashtable
  25
  26    contains
  27
  28
  29    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  30    ! Name: hash_init
  31    !
  32    ! Purpose: To initialize a hashtable
  33    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  34    subroutine hash_init(h)
  35
  36      implicit none
  37
  38      ! Arguments
  39      type (hashtable), intent(inout) :: h
  40
  41      ! Local variables
  42      integer :: i
  43
  44      do i=1,TABLESIZE
  45         nullify(h%table(i)%p)
  46      end do
  47
  48    end subroutine hash_init
  49
  50
  51    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  52    ! Name: hash_insert
  53    !
  54    ! Purpose: Given a hashtable h and a string to be inserted into the hashtable,
  55    !   this routine adds string to the table.
  56    !
  57    ! NOTE: If the string already exists in the table, a second copy of the
  58    !   string is added to the table
  59    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  60    subroutine hash_insert(h, string)
  61
  62      implicit none
  63
  64      ! Arguments
  65      character (len=256), intent(in) :: string
  66      type (hashtable), intent(inout) :: h
  67
  68      ! Local variables
  69      integer :: hashval, i
  70      type (hashnode), pointer :: hn
  71
  72      hashval = 0
  73      do i=1,len(string)
  74         hashval = hashval + iachar(string(i:i))
  75      end do
  76      hashval = mod(hashval, TABLESIZE) + 1
  77
  78      allocate(hn)
  79      hn%entry = string
  80      hn%next => h%table(hashval)%p
  81      h%table(hashval)%p => hn
  82
  83    end subroutine hash_insert
  84
  85
  86    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  87    ! Name: hash_search
  88    !
  89    ! Purpose: This function returns TRUE if the specified string was found in the
  90    !   hashtable h, and FALSE otherwise.
  91    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  92    function hash_search(h, string)
  93
  94       implicit none
  95
  96       ! Arguments
  97       character (len=256), intent(in) :: string
  98       type (hashtable), intent(inout) :: h
  99
 100       ! Return value
 101       logical :: hash_search
 102
 103       ! Local variables
 104       integer :: hashval, i
 105       type (hashnode), pointer :: cursor
 106
 107       hash_search = .false.
 108
 109       hashval = 0
 110       do i=1,len(string)
 111          hashval = hashval + iachar(string(i:i))
 112       end do
 113       hashval = mod(hashval, TABLESIZE) + 1
 114
 115       cursor => h%table(hashval)%p
 116       do while(associated(cursor))
 117          if (cursor%entry == string) then
 118             hash_search = .true.
 119             return
 120          else
 121             cursor => cursor%next
 122          end if
 123       end do
 124
 125       return
 126
 127    end function hash_search
 128
 129
 130    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 131    ! Name: hash_destroy
 132    !
 133    ! Purpose: Frees all memory associated with hashtable h. This routine may be
 134    !   used to remove all entries from a hashtable.
 135    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 136    subroutine hash_destroy(h)
 137
 138       implicit none
 139
 140       ! Arguments
 141       type (hashtable), intent(inout) :: h
 142
 143       ! Local variables
 144       integer :: i
 145       type (hashnode), pointer :: cursor, cursor_prev
 146
 147       do i=1,TABLESIZE
 148          cursor => h%table(i)%p
 149          do while(associated(cursor))
 150             cursor_prev => cursor
 151             cursor => cursor%next
 152             deallocate(cursor_prev)
 153          end do
 154          nullify(h%table(i)%p)
 155       end do
 156
 157    end subroutine hash_destroy
 158
 159 end module hash_module