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