42 use,
intrinsic :: iso_c_binding, only : c_ptr, c_associated
48 logical :: valid = .false.
49 logical :: skip = .false.
50 class(*),
allocatable :: key
51 class(*),
allocatable :: data
56 integer,
private :: size
57 integer,
private :: entries
71 class(*),
intent(in) :: k
157 integer,
private :: n
239 class(
htable_t),
intent(inout) :: this
240 integer,
value :: size
241 class(*),
target,
intent(in) :: key
242 class(*),
target,
intent(in),
optional :: data
243 class(*),
pointer :: dp
249 if (
size .lt. 4)
then
253 size = ishft(1, ceiling(log(dble(size)) /
neko_m_ln2))
255 allocate(this%t(0:size))
256 this%t(:)%valid = .false.
261 if (
present(data))
then
266 allocate(this%t(i)%key, source=key)
267 allocate(this%t(i)%data, source=dp)
273 class(
htable_t),
intent(inout) :: this
276 if (
allocated(this%t))
then
278 deallocate(this%t(i)%key)
279 deallocate(this%t(i)%data)
291 class(
htable_t),
intent(inout) :: this
293 if (
allocated(this%t))
then
294 this%t(:)%valid = .false.
306 entries = this%entries
319 class(
htable_t),
intent(inout) :: this
320 class(*),
intent(inout) :: key
321 class(*),
intent(inout) :: data
326 i = log(1.0/this%size)/log(0.6)
331 index = this%hash(key, c**2)
332 if (index .lt. 0)
then
336 if ((.not. this%t(index)%valid) .or. &
340 if (.not. this%t(index)%valid)
then
341 this%entries = this%entries + 1
343 this%t(index)%valid = .true.
344 this%t(index)%skip = .false.
354 type is (
integer(
i8))
356 type is (double precision)
370 call htable_init(tmp, ishft(this%size, 1), key, data)
372 do i = 0, this%size - 1
373 if (this%t(i)%valid)
then
374 call htable_set(tmp, this%t(i)%key, this%t(i)%data)
378 call move_alloc(tmp%t, this%t)
386 class(
htable_t),
intent(inout) :: this
387 class(*),
intent(inout) :: key
388 class(*),
intent(inout) :: data
390 integer :: index, i, c
396 index = this%hash(key, c**2)
397 if (index .lt. 0)
then
401 if (.not. this%t(index)%valid .and. &
402 .not. this%t(index)%skip)
then
405 else if ((this%t(index)%valid) .and. &
419 class(
htable_t),
intent(inout) :: this
420 class(*),
intent(inout) :: key
421 integer :: index, i, c
427 index = this%hash(key, c**2)
428 if (index .lt. 0)
then
432 if ((this%t(index)%valid) .and. &
434 this%t(index)%valid = .false.
435 this%t(index)%skip = .true.
436 this%entries = this%entries - 1
446 class(
htable_t),
target,
intent(inout) :: this
447 integer,
intent(in) :: idx
448 class(*),
intent(in) :: data
449 class(*),
pointer :: hdp
451 hdp => this%t(idx)%data
458 type is (
integer(i8))
460 type is (
integer(i8))
463 type is (double precision)
465 type is (double precision)
493 integer,
intent(in) :: idx
494 class(*),
intent(inout) :: data
496 select type (hdp=>this%t(idx)%data)
502 type is (
integer(i8))
504 type is (
integer(i8))
507 type is (double precision)
509 type is (double precision)
537 integer,
intent(in) :: idx
538 class(*),
intent(in) :: key
542 select type (kp=>this%t(idx)%key)
548 type is (
integer(
i8))
550 type is (
integer(
i8))
553 type is (double precision)
555 type is (double precision)
573 res = c_associated(kp%ptr, key%ptr)
580 class(
htable_t),
target,
intent(inout) :: this
581 integer,
intent(in) :: idx
582 class(*),
intent(in) :: key
583 class(*),
pointer :: kp
585 kp => this%t(idx)%key
592 type is (
integer(i8))
594 type is (
integer(i8))
597 type is (double precision)
599 type is (double precision)
630 do while ((.not. this%t%t(this%n)%valid) .and. (this%n .lt. this%t%size))
634 valid = (this%n .lt. this%t%size)
635 if (.not. valid) this%n = -1
651 class(*),
intent(inout) :: data
652 class(*),
pointer :: hdp
654 hdp => this%t%t(this%n)%data
661 type is (
integer(i8))
663 type is (
integer(i8))
666 type is (double precision)
668 type is (double precision)
700 integer,
value :: size
701 class(*),
intent(inout),
optional :: data
704 if (
present(data))
then
715 integer,
intent(inout) :: key
716 class(*),
intent(inout) :: data
725 integer,
intent(inout) :: key
726 class(*),
intent(inout) :: data
736 class(*),
intent(in) :: k
739 integer(kind=i8) :: tmp
740 integer(kind=i8),
parameter :: m1 = int(z
'7ed55d15',
i8)
741 integer(kind=i8),
parameter :: m2 = int(z
'c761c23c',
i8)
742 integer(kind=i8),
parameter :: m3 = int(z
'165667b1',
i8)
743 integer(kind=i8),
parameter :: m4 = int(z
'd3a2646c',
i8)
744 integer(kind=i8),
parameter :: m5 = int(z
'fd7046c5',
i8)
745 integer(kind=i8),
parameter :: m6 = int(z
'b55a4f09',
i8)
750 tmp = (k + m1) + ishft(k, 12)
751 tmp = ieor(ieor(tmp, m2), ishft(tmp, -19))
752 tmp = (tmp + m3) + ishft(tmp, 5)
753 tmp = ieor((tmp + m4), ishft(tmp, 9))
754 tmp = (tmp + m5) + ishft(tmp, 3)
755 tmp = ieor(ieor(tmp, m6), ishft(tmp, -16))
756 tmp = modulo(tmp + int(c,
i8), int(this%size,
i8))
766 integer,
intent(inout) :: key
791 integer,
pointer :: value
793 select type (hdp => this%t%t(this%n)%data)
797 call neko_error(
'Key and data of different kind (i4)')
805 integer,
pointer :: key
807 select type (kp => this%t%t(this%n)%key)
822 integer,
value :: size
823 class(*),
intent(inout),
optional :: data
824 integer(kind=i8) :: key
826 if (
present(data))
then
837 integer(kind=i8),
intent(inout) :: key
838 class(*),
intent(inout) :: data
847 integer(kind=i8),
intent(inout) :: key
848 class(*),
intent(inout) :: data
858 class(*),
intent(in) :: k
861 integer(kind=i8) :: tmp
862 integer(kind=i8),
parameter :: m1 = int(z
'7ed55d15',
i8)
863 integer(kind=i8),
parameter :: m2 = int(z
'c761c23c',
i8)
864 integer(kind=i8),
parameter :: m3 = int(z
'165667b1',
i8)
865 integer(kind=i8),
parameter :: m4 = int(z
'd3a2646c',
i8)
866 integer(kind=i8),
parameter :: m5 = int(z
'fd7046c5',
i8)
867 integer(kind=i8),
parameter :: m6 = int(z
'b55a4f09',
i8)
870 type is (
integer(
i8))
871 tmp = (k + m1) + ishft(k, 12)
872 tmp = ieor(ieor(tmp, m2), ishft(tmp, -19))
873 tmp = (tmp + m3) + ishft(tmp, 5)
874 tmp = ieor((tmp + m4), ishft(tmp, 9))
875 tmp = (tmp + m5) + ishft(tmp, 3)
876 tmp = ieor(ieor(tmp, m6), ishft(tmp, -16))
877 hash = int(modulo(tmp, int(this%size,
i8)),
i4)
879 hash = int(modulo((k * 2654435761_i8) + int(c,
i8), &
880 int(this%size,
i8)),
i4)
889 integer(kind=i8),
intent(inout) :: key
914 integer(kind=i8),
pointer :: value
917 select type (hdp => this%t%t(this%n)%data)
918 type is (
integer(
i8))
921 call neko_error(
'Key and data of different kind (i8)')
929 integer(kind=i8),
pointer :: key
934 select type(hti => this)
936 select type (kp => hti%t%t(this%n)%key)
937 type is (
integer(
i8))
955 integer,
value :: size
956 class(*),
intent(inout),
optional :: data
959 if (
present(data))
then
970 real(kind=
dp),
intent(inout) :: key
971 class(*),
intent(inout) :: data
980 real(kind=
dp),
intent(inout) :: key
981 class(*),
intent(inout) :: data
991 class(*),
intent(in) :: k
995 type is (double precision)
996 hash = modulo(floor((2d0 * abs(fraction(k)) - 1d0) * 2**16) + c, this%size)
1005 real(kind=
dp),
intent(inout) :: key
1031 real(kind=
dp),
pointer ::
value
1033 select type (hdp => this%t%t(this%n)%data)
1034 type is (double precision)
1037 call neko_error(
'Key and data of different kind (r8)')
1045 real(kind=
dp),
pointer :: key
1047 select type (kp => this%t%t(this%n)%key)
1048 type is (double precision)
1062 integer,
value :: size
1063 class(*),
intent(inout),
optional :: data
1066 if (
present(data))
then
1077 type(
point_t),
intent(inout) :: key
1078 class(*),
intent(inout) :: data
1087 type(
point_t),
intent(inout) :: key
1088 class(*),
intent(inout) :: data
1098 class(*),
intent(in) :: k
1101 integer(kind=i8) :: hash2, tmp, mult
1102 integer(kind=i8),
parameter :: m1 = int(z
'7ed55d15',
i8)
1103 integer(kind=i8),
parameter :: m2 = int(z
'c761c23c',
i8)
1104 integer(kind=i8),
parameter :: m3 = int(z
'165667b1',
i8)
1105 integer(kind=i8),
parameter :: m4 = int(z
'd3a2646c',
i8)
1106 integer(kind=i8),
parameter :: m5 = int(z
'fd7046c5',
i8)
1107 integer(kind=i8),
parameter :: m6 = int(z
'b55a4f09',
i8)
1112 hash2 = int(z
'345678')
1114 tmp = transfer(k%x(i), tmp)
1115 tmp = (tmp + m1) + ishft(tmp, 12)
1116 tmp = ieor(ieor(tmp, m2), ishft(tmp, -19))
1117 tmp = (tmp + m3) + ishft(tmp, 5)
1118 tmp = ieor((tmp + m4), ishft(tmp, 9))
1119 tmp = (tmp + m5) + ishft(tmp, 3)
1120 tmp = ieor(ieor(tmp, m6), ishft(tmp, -16))
1121 hash2 = ieor(hash2, tmp) * mult
1122 mult = mult + 82520 + 8
1124 hash2 = hash2 + 97531
1125 hash2 = modulo(hash2 + int(c,
i8), int(this%size,
i8))
1126 hash = int(hash2,
i4)
1136 type(
point_t),
intent(inout) :: key
1162 type(
point_t),
pointer :: value
1164 select type (hdp => this%t%t(this%n)%data)
1168 call neko_error(
'Key and data of different kind (pt)')
1178 select type (kp => this%t%t(this%n)%key)
1193 integer,
value :: size
1194 class(*),
intent(inout),
optional :: data
1197 if (
present(data))
then
1209 class(*),
intent(inout) :: data
1219 class(*),
intent(inout) :: data
1229 class(*),
intent(in) :: k
1232 integer(kind=i8) :: tmp, hash2, mult
1233 integer(kind=i8),
parameter :: m1 = int(z
'7ed55d15',
i8)
1234 integer(kind=i8),
parameter :: m2 = int(z
'c761c23c',
i8)
1235 integer(kind=i8),
parameter :: m3 = int(z
'165667b1',
i8)
1236 integer(kind=i8),
parameter :: m4 = int(z
'd3a2646c',
i8)
1237 integer(kind=i8),
parameter :: m5 = int(z
'fd7046c5',
i8)
1238 integer(kind=i8),
parameter :: m6 = int(z
'b55a4f09',
i8)
1242 mult = int(1000003,
i8)
1243 hash2 = int(z
'345678',
i8)
1245 tmp = int(k%x(i),
i8)
1246 tmp = (tmp + m1) + ishft(tmp, 12)
1247 tmp = ieor(ieor(tmp, m2), ishft(tmp, -19))
1248 tmp = (tmp + m3) + ishft(tmp, 5)
1249 tmp = ieor((tmp + m4), ishft(tmp, 9))
1250 tmp = (tmp + m5) + ishft(tmp, 3)
1251 tmp = ieor(ieor(tmp, m6), ishft(tmp, -16))
1252 hash2 = ieor(hash2, tmp) * mult
1253 mult = mult + 82520_i8 + 4_i8
1255 hash2 = hash2 + 97531_i8
1256 hash2 = modulo(hash2 + int(c,
i8), int(this%size,
i8))
1257 hash = int(hash2,
i4)
1293 select type (hdp => this%t%t(this%n)%data)
1297 call neko_error(
'Key and data of different kind (i4t2)')
1307 select type (kp => this%t%t(this%n)%key)
1322 integer,
value :: size
1323 class(*),
intent(inout),
optional :: data
1326 if (
present(data))
then
1338 class(*),
intent(inout) :: data
1348 class(*),
intent(inout) :: data
1358 class(*),
intent(in) :: k
1361 integer(kind=i8) :: tmp, hash2, mult
1362 integer(kind=i8),
parameter :: m1 = int(z
'7ed55d15',
i8)
1363 integer(kind=i8),
parameter :: m2 = int(z
'c761c23c',
i8)
1364 integer(kind=i8),
parameter :: m3 = int(z
'165667b1',
i8)
1365 integer(kind=i8),
parameter :: m4 = int(z
'd3a2646c',
i8)
1366 integer(kind=i8),
parameter :: m5 = int(z
'fd7046c5',
i8)
1367 integer(kind=i8),
parameter :: m6 = int(z
'b55a4f09',
i8)
1371 mult = int(1000003,
i8)
1372 hash2 = int(z
'345678',
i8)
1374 tmp = int(k%x(i),
i8)
1375 tmp = (tmp + m1) + ishft(tmp, 12)
1376 tmp = ieor(ieor(tmp, m2), ishft(tmp, -19))
1377 tmp = (tmp + m3) + ishft(tmp, 5)
1378 tmp = ieor((tmp + m4), ishft(tmp, 9))
1379 tmp = (tmp + m5) + ishft(tmp, 3)
1380 tmp = ieor(ieor(tmp, m6), ishft(tmp, -16))
1381 hash2 = ieor(hash2, tmp) * mult
1382 mult = mult + 82520_i8 + 8_i8
1384 hash2 = hash2 + 97531_i8
1385 hash2 = modulo(hash2 + int(c,
i8), int(this%size,
i8))
1386 hash = int(hash2,
i4)
1422 select type (hdp => this%t%t(this%n)%data)
1426 call neko_error(
'Key and data of different kind (i4t4)')
1439 select type(hti => this)
1441 select type (kp => hti%t%t(this%n)%key)
1448 call neko_error(
'Corrupt htable iter. (i4t4)')
1459 integer,
value :: size
1460 class(*),
intent(inout),
optional :: data
1463 if (
present(data))
then
1474 type(
h_cptr_t),
intent(inout) :: key
1475 class(*),
intent(inout) :: data
1484 type(
h_cptr_t),
intent(inout) :: key
1485 class(*),
intent(inout) :: data
1495 class(*),
intent(in) :: k
1498 integer(kind=i8) :: k_int
1502 k_int = transfer(k%ptr, k_int)
1503 hash = int(modulo(k_int * 2654435761_i8 + int(c,
i8),&
1504 int(this%size,
i8)),
i4)
1513 type(
h_cptr_t),
intent(inout) :: key
1538 class(*),
pointer :: hdp
1541 hdp => this%t%t(this%n)%data
1546 call neko_error(
'Key and data of different kind (cptr)')
1554 class(*),
pointer :: kp
1557 kp => this%t%t(this%n)%key
Implements a hash table ADT.
subroutine htable_i4t4_init(this, size, data)
Initialize an integer 4-tuple hash table.
subroutine htable_iter_r8_init(this, t)
Initialize a double precision based hash table iterator.
subroutine htable_clear(this)
Clear all entries in a hash table.
subroutine htable_pt_init(this, size, data)
Initialize a point based hash table.
type(tuple_i4_t) function, pointer htable_iter_i4t2_key(this)
Return the current key of integer based 2-tuple hash table iterator.
subroutine htable_iter_i8_free(this)
Destroy an integer*8 based hash table iterator.
subroutine htable_i4_set(this, key, data)
Insert an integer into the hash table.
type(tuple4_i4_t) function, pointer htable_iter_i4t4_value(this)
Return the current value of integer based 4-tuple hash table iterator.
integer function, pointer htable_iter_i4_value(this)
Return the current value of the integer based hash table iterator.
subroutine htable_r8_init(this, size, data)
Initialize a double precision based hash table.
integer(kind=i8) function, pointer htable_iter_i8_key(this)
Return the current key of the integer*8 based hash table iterator.
type(point_t) function, pointer htable_iter_pt_key(this)
Return the current key of the point based hash table iterator.
pure integer function htable_r8_hash(this, k, c)
Hash function for a double precision based hash table.
subroutine htable_cptr_init(this, size, data)
Initialize a C pointer based hash table.
pure integer function htable_i4_hash(this, k, c)
Hash function for an integer based hash table.
subroutine htable_iter_cptr_free(this)
Destroy a C pointer based hash table iterator.
subroutine htable_iter_pt_free(this)
Destroy a point based hash table iterator.
subroutine htable_i4t4_set(this, key, data)
Insert an integer 4-tuple into the hash table.
subroutine htable_i8_init(this, size, data)
Initialize an integer*8 based hash table.
subroutine htable_pt_remove(this, key)
Remove a point with key key from the hash table.
subroutine htable_cptr_remove(this, key)
Remove a C pointer with key key from the hash table.
subroutine htable_free(this)
Destroy a hash table.
subroutine htable_iter_data(this, data)
Return the data at the current iterator position.
pure integer function htable_size(this)
Return total size of htable.
subroutine htable_get_data(this, idx, data)
Return data at idx in value.
integer function htable_r8_get(this, key, data)
Retrive a double precision float with key key from the hash table.
pure integer function htable_i8_hash(this, k, c)
Hash function for an integer*8 based hash table.
subroutine htable_i4t4_remove(this, key)
Remove an integer 4-tuple with key key from the hash table.
integer function htable_get(this, key, data)
Retrieve data associated with key into the hash table.
integer function htable_i8_get(this, key, data)
Retrive an integer*8 with key key from the hash table.
integer function htable_pt_get(this, key, data)
Retrive a point with key key from the hash table.
subroutine htable_remove(this, key)
Remove a key from the hash table.
subroutine htable_set_data(this, idx, data)
Set data at idx to value.
real(kind=dp) function, pointer htable_iter_r8_key(this)
Return the current key of the double precision based hash table iterator.
subroutine htable_iter_pt_init(this, t)
Initialize a point based hash table iterator.
integer function htable_i4_get(this, key, data)
Retrive an integer with key key from the hash table.
type(h_cptr_t) function, pointer htable_iter_cptr_value(this)
Return the current value of C pointer based hash table iterator.
type(tuple_i4_t) function, pointer htable_iter_i4t2_value(this)
Return the current value of integer based 2-tuple hash table iterator.
logical function htable_iter_next(this)
Advance the iterator to the next valid table entry.
integer function htable_cptr_get(this, key, data)
Retrive a C pointer with key key from the hash table.
subroutine htable_i8_set(this, key, data)
Insert an integer*8 into the hash table.
subroutine htable_r8_remove(this, key)
Remove a double precision key key from the hash table.
subroutine htable_iter_i4t2_free(this)
Destroy an integer 2-tuple based hash table iterator.
subroutine htable_r8_set(this, key, data)
Insert a double precision key (with data) into the hash table.
type(point_t) function, pointer htable_iter_pt_value(this)
Return the current value of the point based hash table iterator.
integer function htable_i4t4_get(this, key, data)
Retrive an integer 4-tuple with key key from the hash table.
subroutine htable_i4t2_set(this, key, data)
Insert an integer 2-tuple into the hash table.
pure integer function htable_num_entries(this)
Return number of entries in the table.
type(tuple4_i4_t) function, pointer htable_iter_i4t4_key(this)
Return the current key of integer based 4-tuple hash table iterator.
recursive subroutine htable_set(this, key, data)
Insert tuple (key, value) into the hash table.
pure logical function htable_eq_key(this, idx, key)
Compare key at idx to key.
subroutine htable_i4t2_remove(this, key)
Remove an integer 2-tuple with key key from the hash table.
subroutine htable_set_key(this, idx, key)
Set key at idx to key.
subroutine htable_iter_i8_init(this, t)
Initialize an integer*8 based hash table iterator.
pure integer function htable_i4t4_hash(this, k, c)
Hash function for an integer 4-tuple hash table.
pure integer function htable_pt_hash(this, k, c)
Hash function for a point based hash table.
integer function, pointer htable_iter_i4_key(this)
Return the current key of the integer based hash table iterator.
subroutine htable_iter_i4_init(this, t)
Initialize an integer based hash table iterator.
subroutine htable_init(this, size, key, data)
Initialize a hash table of type data.
subroutine htable_i4t2_init(this, size, data)
Initialize an integer 2-tuple hash table.
subroutine htable_cptr_set(this, key, data)
Insert a C pointer into the hash table.
subroutine htable_iter_i4t4_free(this)
Destroy an integer 4-tuple based hash table iterator.
subroutine htable_i4_remove(this, key)
Remove an integer with key key from the hash table.
subroutine htable_iter_cptr_init(this, t)
Initialize a C pointer based hash table iterator.
integer(kind=i8) function, pointer htable_iter_i8_value(this)
Return the current value of the integer*8 based hash table iterator.
integer function htable_i4t2_get(this, key, data)
Retrive an integer 2-tuple with key key from the hash table.
subroutine htable_iter_i4t4_init(this, t)
Initialize an integer 4-tuple based hash table iterator.
subroutine htable_i8_remove(this, key)
Remove an integer*8 with key key from the hash table.
subroutine htable_i4_init(this, size, data)
Initialize an integer based hash table.
pure integer function htable_cptr_hash(this, k, c)
Hash function for an integer 4-tuple hash table.
subroutine htable_pt_set(this, key, data)
Insert a point key (with data) into the hash table.
subroutine htable_iter_reset(this)
Reset an iterator.
subroutine htable_iter_i4_free(this)
Destroy an integer based hash table iterator.
type(h_cptr_t) function, pointer htable_iter_cptr_key(this)
Return the current key of a C pointer based hash table iterator.
subroutine htable_iter_r8_free(this)
Destroy a double precision based hash table iterator.
pure integer function htable_i4t2_hash(this, k, c)
Hash function for an integer 2-tuple hash table.
subroutine htable_iter_i4t2_init(this, t)
Initialize an integer 2-tuple based hash table iterator.
real(kind=dp) function, pointer htable_iter_r8_value(this)
Return the current value of the double precision based hash table iterator.
real(kind=rp), parameter, public neko_m_ln2
integer, parameter, public i8
integer, parameter, public i4
integer, parameter, public dp
Hash table entry, tuple (key, data)
C pointer based hash table.
Integer based hash table.
Integer 2-tuple based hash table.
Integer 4-tuple based hash table.
Integer*8 based hash table.
Iterator for a C pointer based hash table.
Iterator for an integer based hash table.
Iterator for an integer based 2-tuple hash table.
Iterator for an integer based 4-tuple hash table.
Iterator for an integer*8 based hash table.
Iterator for a point based hash table.
Iterator for a double precision based hash table.
Base type for a hash table iterator.
Double precision based hash table.
Base type for a hash table.
A point in with coordinates .
Base type for an n-tuple.