pic_hash_map Module

A hash map from character(len=*) keys to integer(int64) values whose iteration order is a documented, reproducible guarantee rather than an implementation accident.

## The iteration-order guarantee

Iteration is always in insertion order. keys(), values() and at() visit the entries in the exact order in which their keys were first inserted. That order does not depend on the bucket count, on how many times the table has grown and rehashed, on the hash function, or on which other keys were inserted or removed. Two runs performing the same sequence of insert/remove calls observe the same iteration order, on every supported compiler.

The rules that make that guarantee precise:

  • insert on a key that is not present appends the entry at the end of the iteration order.
  • insert on a key that is present overwrites the value and leaves the key exactly where it was in the iteration order. It is an update, not a re-insertion.
  • remove deletes the entry from the iteration order. Every remaining entry keeps its relative position: entries before the removed one are untouched, entries after it shift down by one index.
  • remove followed by insert of the same key is a fresh insertion: the key reappears at the end of the iteration order, not at its old position.
  • Growing the table rehashes the buckets but never reorders entries.

## Key identity

Keys are compared by exact length and exact characters, not with the Fortran == operator. Fortran blank-pads the shorter operand when comparing character values, so "a" == "a " is .true. in the language; in this map "a" and "a " are different keys. Trailing blanks are significant and are stored verbatim.

Beware that a character(len=8) variable holding "a" is the eight character key "a ", because that is what the actual argument contains. Pass trim(name) if trailing blanks are not meant to count.

The zero-length key "" is a perfectly ordinary key.

## Capacity, load factor and growth

The bucket table is a power of two, at least 8 buckets, addressed by open addressing with linear probing. It grows by doubling whenever a new entry would push occupancy above a load factor of 0.75. There are no tombstones: remove compacts the insertion-order table and rebuilds the bucket table from scratch, so remove costs O(size() + bucket_count()) while insert, get and has_key are amortised O(1). This map is built for reproducible iteration and simple, portable code, not for remove-heavy workloads.

## Example

 type(hash_map_t) :: counts
 character(len=:), allocatable :: k
 integer(int64) :: v
 integer(default_int) :: i

 call counts%init(16_default_int)
 call counts%insert("beta", 2_int64)
 call counts%insert("alpha", 1_int64)
 call counts%insert("beta", 20_int64)   ! updates, stays at position 1
 do i = 1, counts%size()
    call counts%at(i, k, v)             ! "beta" then "alpha"
 end do
 call counts%destroy()

Uses

  • module~~pic_hash_map~~UsesGraph module~pic_hash_map pic_hash_map module~pic_error pic_error module~pic_hash_map->module~pic_error module~pic_hash_32bit_fnv pic_hash_32bit_fnv module~pic_hash_map->module~pic_hash_32bit_fnv module~pic_types pic_types module~pic_hash_map->module~pic_types module~pic_error->module~pic_types module~pic_global_definitions pic_global_definitions module~pic_error->module~pic_global_definitions module~pic_hash_32bit_fnv->module~pic_types iso_fortran_env iso_fortran_env module~pic_hash_32bit_fnv->iso_fortran_env iso_c_binding iso_c_binding module~pic_types->iso_c_binding module~pic_types->iso_fortran_env module~pic_global_definitions->module~pic_types

Variables

Type Visibility Attributes Name Initial
integer(kind=default_int), private, parameter :: BUCKET_EMPTY = 0

Sentinel stored in a bucket that does not hold an entry.
integer(kind=default_int), private, parameter :: LOAD_DEN = 4

Denominator of the maximum load factor (3/4).
integer(kind=default_int), private, parameter :: LOAD_NUM = 3

Numerator of the maximum load factor (3/4).
integer(kind=default_int), private, parameter :: MIN_BUCKETS = 8

Smallest bucket table this map will ever allocate.
integer(kind=default_int), private, parameter :: MIN_ENTRIES = 8

Smallest insertion-order table this map will ever allocate.
integer(kind=default_int), private, parameter :: MIN_POOL = 64

Smallest key character pool this map will ever allocate.

Derived Types

type, public ::  hash_map_t

Insertion-ordered hash map: character(len=*) keys, integer(int64) values. Default initialisation yields a valid empty map; the first insert allocates with default capacity if init was never called.

Components

Type Visibility Attributes Name Initial
integer(kind=default_int), private, allocatable :: buckets(:)

Bucket table; BUCKET_EMPTY or an index into the entry table.
integer(kind=default_int), private :: entry_cap = 0

Allocated length of the entry arrays.
integer(kind=int64), private, allocatable :: entry_value(:)

Value of each entry, in insertion order.
character(len=1), private, allocatable :: key_pool(:)

Packed storage for all key characters.
integer(kind=default_int), private, allocatable :: key_size(:)

Length in characters of each key, in insertion order.
integer(kind=default_int), private, allocatable :: key_start(:)

First character of each key inside key_pool, in insertion order.
integer(kind=default_int), private :: n_buckets = 0

Number of buckets, always a power of two, 0 while unallocated.
integer(kind=default_int), private :: n_entries = 0

Number of live entries, i.e. the value returned by size().
integer(kind=default_int), private :: pool_cap = 0

Allocated length of key_pool.
integer(kind=default_int), private :: pool_used = 0

Number of characters currently used in key_pool.

Type-Bound Procedures

procedure, public :: at => hash_map_at
procedure, public :: bucket_count => hash_map_bucket_count
procedure, public :: clear => hash_map_clear
procedure, public :: destroy => hash_map_destroy
procedure, public :: get => hash_map_get
procedure, public :: has_key => hash_map_has_key
procedure, public :: init => hash_map_init
procedure, public :: insert => hash_map_insert
procedure, public :: is_empty => hash_map_is_empty
procedure, public :: keys => hash_map_keys
procedure, public :: remove => hash_map_remove
procedure, public :: size => hash_map_size
procedure, public :: values => hash_map_values

Functions

private function entry_key(this, entry) result(key)

Rebuild the key of an entry from the packed character pool.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
integer(kind=default_int), intent(in) :: entry

Return Value character(len=:), allocatable

private function find_entry(this, key) result(entry)

Index of key in the insertion-order table, or 0 when absent.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
character(len=*), intent(in) :: key

Return Value integer(kind=default_int)

private pure function hash_map_bucket_count(this) result(n)

Current number of buckets, 0 while the map is unallocated. Exposed so that callers and tests can observe growth; it never affects iteration order.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this

Return Value integer(kind=default_int)

private function hash_map_has_key(this, key) result(present_in_map)

.true. when key is stored in the map.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
character(len=*), intent(in) :: key

Return Value logical

private pure function hash_map_is_empty(this) result(empty)

.true. when the map holds no entries.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this

Return Value logical

private function hash_map_keys(this) result(res)

All keys, in insertion order.

Read more…

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this

Return Value character(len=:), allocatable, (:)

private pure function hash_map_size(this) result(n)

Number of entries currently stored.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this

Return Value integer(kind=default_int)

private function hash_map_values(this) result(res)

All values, in insertion order. values() and keys() are index aligned: values(i) belongs to keys(i). Zero-sized for an empty map.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this

Return Value integer(kind=int64), allocatable, (:)

private function home_bucket(this, key) result(bucket)

Bucket a key hashes to before probing.

Read more…

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
character(len=*), intent(in) :: key

Return Value integer(kind=default_int)

private function key_matches(this, entry, key) result(same)

Exact key comparison: same length and same characters. Deliberately not the Fortran == operator, which blank-pads the shorter operand.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
integer(kind=default_int), intent(in) :: entry
character(len=*), intent(in) :: key

Return Value logical

private function probe_free(this, key) result(bucket)

First empty bucket in the probe sequence of key. The load factor keeps at least one bucket empty at all times, so this always finds one.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
character(len=*), intent(in) :: key

Return Value integer(kind=default_int)


Subroutines

private subroutine grow_buckets(this)

Double the bucket table and rehash. Entry storage is never moved.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this

private subroutine hash_map_at(this, position, key, value, err)

Fetch the entry at position in the iteration order, counting from 1. This is the exact-fidelity iteration accessor: key comes back with the key’s true length, trailing blanks included.

Read more…

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
integer(kind=default_int), intent(in) :: position
character(len=:), intent(out), allocatable :: key
integer(kind=int64), intent(out) :: value
type(error_t), intent(out), optional :: err

private subroutine hash_map_clear(this)

Remove every entry but keep the allocated capacity, so that refilling the map does not have to reallocate. A cleared map iterates as empty and the next insert starts a fresh insertion order at position 1.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this

private subroutine hash_map_destroy(this)

Release every buffer and return the map to the unallocated state.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this

private subroutine hash_map_get(this, key, value, found)

Look up key. A missing key is an ordinary outcome, not an error: found comes back .false. and value is set to 0.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(in) :: this
character(len=*), intent(in) :: key
integer(kind=int64), intent(out) :: value
logical, intent(out) :: found

private subroutine hash_map_init(this, initial_capacity)

Allocate the map, discarding any entries it already held.

Read more…

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this
integer(kind=default_int), intent(in), optional :: initial_capacity

private subroutine hash_map_insert(this, key, value)

Insert key with value, or overwrite the value of an existing key.

Read more…

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this
character(len=*), intent(in) :: key

Stored verbatim; trailing blanks are part of the key.
integer(kind=int64), intent(in) :: value

private subroutine hash_map_remove(this, key, err)

Remove key from the map.

Read more…

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this
character(len=*), intent(in) :: key
type(error_t), intent(out), optional :: err

private subroutine rebuild_buckets(this)

Re-index every entry into the bucket table. Touches buckets only, so the insertion order is untouched by construction.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this

private subroutine reserve_entries(this, needed)

Ensure the insertion-order arrays hold at least needed entries. Explicit allocate/copy/move_alloc rather than reallocation-on-assignment, which is shaky on some supported compilers.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this
integer(kind=default_int), intent(in) :: needed

private subroutine reserve_pool(this, needed)

Ensure the packed key pool holds at least needed characters.

Arguments

Type IntentOptional Attributes Name
class(hash_map_t), intent(inout) :: this
integer(kind=default_int), intent(in) :: needed