TABLE OF CONTENTS
ABINIT/m_hashtable [ Modules ]
NAME
m_hashtable
FUNCTION
A dictionary like structure for integers
COPYRIGHT
Copyright (C) 2010-2024 ABINIT group (HM) This file is distributed under the terms of the GNU General Public License, see ~abinit/COPYING or http://www.gnu.org/copyleft/gpl.txt .
SOURCE
16 #if defined HAVE_CONFIG_H 17 #include "config.h" 18 #endif 19 20 #include "abi_common.h" 21 22 module m_hashtable 23 24 use defs_basis 25 use m_abicore 26 implicit none 27 28 type :: hashbucket 29 integer :: nitems 30 integer,allocatable :: items(:,:) 31 end type hashbucket 32 33 type :: hashtable_t 34 integer :: bucketsize 35 integer :: bucketstep 36 integer :: nbuckets 37 type(hashbucket),allocatable :: buckets(:) 38 end type hashtable_t 39 40 public :: hashtable_init 41 public :: hashtable_add 42 public :: hashtable_get 43 public :: hashtable_cleanup 44 public :: hashtable_items 45 public :: hashtable_free 46 47 contains 48 type(hashtable_t) function hashtable_init(nbuckets,bucketsize,bucketstep) result(new) 49 ! Create the hashtable structure 50 integer,intent(in) :: bucketsize, bucketstep, nbuckets 51 integer :: ibucket 52 53 new%nbuckets = nbuckets 54 new%bucketsize = bucketsize 55 new%bucketstep = bucketstep 56 ABI_MALLOC(new%buckets,(nbuckets)) 57 do ibucket=1,nbuckets 58 ABI_MALLOC(new%buckets(ibucket)%items,(2,new%bucketsize)) 59 new%buckets(ibucket)%nitems = 0 60 end do 61 end function hashtable_init 62 63 pure function compute_hash(self,key) result(ihash) 64 type(hashtable_t),intent(in) :: self 65 integer,intent(in) :: key 66 integer :: ihash 67 ihash = mod(key-1,self%nbuckets)+1 68 end function compute_hash 69 70 subroutine hashtable_add(self, key, val) 71 ! Add a key to the hashtable structure 72 type(hashtable_t) :: self 73 integer,intent(in) :: key, val 74 integer :: ihash, item, nitems 75 integer,allocatable :: new_items(:,:) 76 ! Compute bucket for this element 77 ihash = compute_hash(self,key) 78 nitems = self%buckets(ihash)%nitems 79 ! Check if the element already exists in the bucket 80 do item=1,nitems 81 if (self%buckets(ihash)%items(1,item) /= key) cycle 82 ! Replace value 83 self%buckets(ihash)%items(2,item) = val 84 return 85 end do 86 ! Check if the buckets are full 87 if (size(self%buckets(ihash)%items,2)==nitems) then 88 ABI_MALLOC(new_items,(2,nitems+self%bucketstep)) 89 new_items(:,:nitems) = self%buckets(ihash)%items(:,:nitems) 90 new_items(:,nitems+1:) = 0 91 ABI_MOVE_ALLOC(new_items,self%buckets(ihash)%items) 92 end if 93 ! Add the element to the bucket 94 nitems = nitems + 1 95 self%buckets(ihash)%items(:,nitems) = [key,val] 96 self%buckets(ihash)%nitems = nitems 97 end subroutine hashtable_add 98 99 subroutine hashtable_print(self,iunit) 100 ! Print the hashtable data 101 type(hashtable_t),intent(in) :: self 102 integer,intent(in) :: iunit 103 integer :: ibucket,item 104 do ibucket=1,self%nbuckets 105 do item=1,self%buckets(ibucket)%nitems 106 write(iunit,*) ibucket, self%buckets(ibucket)%items(:,item) 107 end do 108 end do 109 end subroutine hashtable_print 110 111 subroutine hashtable_get(self,key,val,ierr) 112 ! Get the value of a key in the hashtable 113 type(hashtable_t) :: self 114 integer,intent(in) :: key 115 integer,intent(out) :: val,ierr 116 integer :: item, ihash 117 ierr = 0 118 ihash = compute_hash(self,key) 119 do item=1,self%buckets(ihash)%nitems 120 if (self%buckets(ihash)%items(1,item) /= key) cycle 121 val = self%buckets(ihash)%items(2,item) 122 return 123 end do 124 ierr = 1 125 end subroutine hashtable_get 126 127 subroutine hashtable_items(self,items) 128 ! Get an array with all the keys in hashtable 129 type(hashtable_t) :: self 130 integer :: item,ibucket,idx 131 integer,allocatable :: items(:,:) 132 ABI_MALLOC(items,(2,sum(self%buckets(:)%nitems))) 133 idx = 0 134 do ibucket=1,self%nbuckets 135 do item=1,self%buckets(ibucket)%nitems 136 idx = idx + 1 137 items(:,idx) = self%buckets(ibucket)%items(:,item) 138 end do 139 end do 140 end subroutine hashtable_items 141 142 subroutine hashtable_cleanup(self) 143 ! Free up memory in all the buckets 144 ! this should be done only after all the add operations are finished 145 type(hashtable_t) :: self 146 integer :: ibucket,nitems 147 integer,allocatable :: new_items(:,:) 148 do ibucket=1,self%nbuckets 149 ! get size of buckets and free unecessary memory 150 nitems = self%buckets(ibucket)%nitems 151 ABI_MALLOC(new_items,(2,nitems)) 152 new_items = self%buckets(ibucket)%items(:,:nitems) 153 ABI_MOVE_ALLOC(new_items,self%buckets(ibucket)%items) 154 end do 155 end subroutine hashtable_cleanup 156 157 integer function hashtable_size(self) result(bsize) 158 type(hashtable_t) :: self 159 integer :: ibucket 160 ! Return the size of the hashtable in bytes 161 bsize = storage_size(self%buckets)*self%nbuckets 162 do ibucket=1,self%nbuckets 163 bsize = bsize + storage_size(self%buckets(ibucket)%items)*size(self%buckets(ibucket)%items,2)*2 164 end do 165 bsize = bsize/8 166 end function hashtable_size 167 168 subroutine hashtable_free(self) 169 type(hashtable_t) :: self 170 integer :: ibucket 171 if (allocated(self%buckets)) then 172 do ibucket=1,self%nbuckets 173 ABI_FREE(self%buckets(ibucket)%items) 174 end do 175 ABI_FREE(self%buckets) 176 end if 177 end subroutine hashtable_free 178 179 end module m_hashtable