FrontISTR 5.2.0
Large-scale structural analysis program with finit element method
Loading...
Searching...
No Matches
dictionary.f90
Go to the documentation of this file.
1!-------------------------------------------------------------------------------
2! Copyright (c) 2019 FrontISTR Commons
3! This software is released under the MIT License, see LICENSE.txt
4!-------------------------------------------------------------------------------
5! dictionary.f90 --
6! Include file for defining dictionaries:
7! a mapping of strings to some data
8!
9! See the example/test program for the way to use this
10!
11! Note:
12! Use is made of a hash table. This should speed up most
13! operations. The algorithm for determining the hashkey
14! is taken from Kernighan and Pike: The Practice of Programming
15!
16! Note:
17! - Define the length of the strings as
18! parameter "DICT_KEY_LENGTH"
19! - Define a derived type for the data
20! to be stored
21! - Also define a "null" value - DICT_NULL
22! of type DICT_DATA, for use when the
23! key is not found.
24! - Put both in a separate module, that
25! will be used.
26!
27! $Id: dictionary.f90,v 1.3 2007/01/26 09:56:43 arjenmarkus Exp $
28!
29! Following is modified by Xi YUAN( AdvanceSoft )
30! - In function dict_hashkey, there would be value of dict_hashkey
31! exceeds max integer value. It maybe avoided by extending the max
32! value of this integer or use small value of multiplier. Take care!
33! It hasn't be solved completely.
34!
35
36type list_data
37 character(len=DICT_KEY_LENGTH) :: key
38 type(DICT_DATA) :: value
39end type list_data
40
41type hash_list
42 type(LINKED_LIST), pointer :: list
43end type hash_list
44
45type dict_struct
46 private
47 type(HASH_LIST), pointer, dimension(:) :: table
48end type dict_struct
49
50!
51! We do not want everything to be public
52!
53private :: list_data
54private :: hash_list
55private :: linked_list
56private :: list_create
57private :: list_destroy
58private :: list_count
59private :: list_next
60private :: list_insert
61private :: list_insert_head
62private :: list_delete_element
63private :: list_get_data
64private :: list_put_data
65private :: dict_get_elem
66private :: dict_hashkey
67
68integer, parameter, private :: hash_size = 499
69integer, parameter, private :: multiplier = 1
70
71include 'linkedlist.f90'
72
73!
74! Routines and functions specific to dictionaries
75!
76
77! dict_create --
78! Create and initialise a dictionary
79! Arguments:
80! dict Pointer to new dictionary
81! key Key for the first element
82! value Value for the first element
83! Note:
84! This version assumes a shallow copy is enough
85! (that is, there are no pointers within the data
86! to be stored)
87! It also assumes the argument list does not already
88! refer to a list. Use dict_destroy first to
89! destroy up an old list.
90!
91subroutine dict_create( dict, key, value )
92 type(DICT_STRUCT), pointer :: dict
93 character(len=*), intent(in) :: key
94 type(DICT_DATA), intent(in) :: value
95
96 type(LIST_DATA) :: data
97 integer :: i
98 integer :: hash
99
100 allocate( dict )
101 allocate( dict%table(hash_size) )
102
103 do i = 1,hash_size
104 dict%table(i)%list => null()
105 enddo
106
107 data%key = key
108 data%value = value
109
110 hash = dict_hashkey( trim(key ) )
111 call list_create( dict%table(hash)%list, data )
112
113end subroutine dict_create
114
115! dict_destroy --
116! Destroy an entire dictionary
117! Arguments:
118! dict Pointer to the dictionary to be destroyed
119! Note:
120! This version assumes that there are no
121! pointers within the data that need deallocation
122!
123subroutine dict_destroy( dict )
124 type(DICT_STRUCT), pointer :: dict
125
126 integer :: i
127
128 do i = 1,size(dict%table)
129 if ( associated( dict%table(i)%list ) ) then
130 call list_destroy( dict%table(i)%list )
131 endif
132 enddo
133 deallocate( dict%table )
134 deallocate( dict )
135
136end subroutine dict_destroy
137
138! dict_add_key
139! Add a new key
140! Arguments:
141! dict Pointer to the dictionary
142! key Key for the new element
143! value Value for the new element
144! Note:
145! If the key already exists, the
146! key's value is simply replaced
147!
148subroutine dict_add_key( dict, key, value )
149 type(DICT_STRUCT), pointer :: dict
150 character(len=*), intent(in) :: key
151 type(DICT_DATA), intent(in) :: value
152
153 type(LIST_DATA) :: data
154 type(LINKED_LIST), pointer :: elem
155 integer :: hash
156
157 elem => dict_get_elem( dict, key )
158
159 if ( associated(elem) ) then
160 elem%data%value = value
161 else
162 data%key = key
163 data%value = value
164 hash = dict_hashkey( trim(key) )
165 if ( associated( dict%table(hash)%list ) ) then
166 call list_insert( dict%table(hash)%list, data )
167 else
168 call list_create( dict%table(hash)%list, data )
169 endif
170 endif
171
172end subroutine dict_add_key
173
174! dict_delete_key
175! Delete a key-value pair from the dictionary
176! Arguments:
177! dict Dictionary in question
178! key Key to be removed
179!
180subroutine dict_delete_key( dict, key )
181 type(DICT_STRUCT), pointer :: dict
182 character(len=*), intent(in) :: key
183
184 type(LINKED_LIST), pointer :: elem
185 integer :: hash
186
187 elem => dict_get_elem( dict, key )
188
189 if ( associated(elem) ) then
190 hash = dict_hashkey( trim(key) )
191 call list_delete_element( dict%table(hash)%list, elem )
192 endif
193end subroutine dict_delete_key
194
195! dict_get_key
196! Get the value belonging to a key
197! Arguments:
198! dict Pointer to the dictionary
199! key Key for which the values are sought
200!
201function dict_get_key( dict, key ) result(value)
202 type(DICT_STRUCT), pointer :: dict
203 character(len=*), intent(in) :: key
204 type(DICT_DATA), pointer :: value
205
206 type(LINKED_LIST), pointer :: elem
207
208 elem => dict_get_elem( dict, key )
209
210 if ( associated(elem) ) then
211 value => elem%data%value
212 else
213 nullify(value)
214 endif
215end function dict_get_key
216
217! dict_has_key
218! Check if the dictionary has a particular key
219! Arguments:
220! dict Pointer to the dictionary
221! key Key to be sought
222!
223function dict_has_key( dict, key ) result(has)
224 type(DICT_STRUCT), pointer :: dict
225 character(len=*), intent(in) :: key
226 logical :: has
227
228 type(LINKED_LIST), pointer :: elem
229
230 elem => dict_get_elem( dict, key )
231
232 has = associated(elem)
233end function dict_has_key
234
235! dict_get_elem
236! Find the element with a particular key
237! Arguments:
238! dict Pointer to the dictionary
239! key Key to be sought
240!
241function dict_get_elem( dict, key ) result(elem)
242 type(DICT_STRUCT), pointer :: dict
243 character(len=*), intent(in) :: key
244
245 type(LINKED_LIST), pointer :: elem
246 integer :: hash
247
248 hash = dict_hashkey( trim(key) )
249
250 elem => dict%table(hash)%list
251 do while ( associated(elem) )
252 if ( elem%data%key .eq. key ) then
253 exit
254 else
255 elem => list_next( elem )
256 endif
257 enddo
258end function dict_get_elem
259
260! dict_hashkey
261! Determine the hash value from the string
262! Arguments:
263! key String to be examined
264!
265integer function dict_hashkey( key )
266 character(len=*), intent(in) :: key
267
268! integer :: hash
269 integer :: i
270
271 dict_hashkey = 0
272
273 do i = 1,len(key)
274 dict_hashkey = multiplier * dict_hashkey + ichar(key(i:i))
275 enddo
276
277 dict_hashkey = 1 + mod( dict_hashkey-1, hash_size )
278end function dict_hashkey
279