hash_map_t Derived Type

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

  • 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

procedure, public :: bucket_count => hash_map_bucket_count

  • 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)

procedure, public :: clear => hash_map_clear

  • 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

procedure, public :: destroy => hash_map_destroy

  • 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

procedure, public :: get => hash_map_get

  • 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

procedure, public :: has_key => hash_map_has_key

  • 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

procedure, public :: init => hash_map_init

  • 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

procedure, public :: insert => hash_map_insert

  • 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

procedure, public :: is_empty => hash_map_is_empty

  • 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

procedure, public :: keys => hash_map_keys

  • 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, (:)

procedure, public :: remove => hash_map_remove

  • 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

procedure, public :: size => hash_map_size

  • 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)

procedure, public :: values => hash_map_values

  • 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, (:)

Source Code

   type :: 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.
      private
      integer(default_int) :: n_buckets = 0
         !! Number of buckets, always a power of two, 0 while unallocated.
      integer(default_int), allocatable :: buckets(:)
         !! Bucket table; `BUCKET_EMPTY` or an index into the entry table.
      integer(default_int) :: n_entries = 0
         !! Number of live entries, i.e. the value returned by `size()`.
      integer(default_int) :: entry_cap = 0
         !! Allocated length of the entry arrays.
      integer(default_int), allocatable :: key_start(:)
         !! First character of each key inside `key_pool`, in insertion order.
      integer(default_int), allocatable :: key_size(:)
         !! Length in characters of each key, in insertion order.
      integer(int64), allocatable :: entry_value(:)
         !! Value of each entry, in insertion order.
      character(len=1), allocatable :: key_pool(:)
         !! Packed storage for all key characters.
      integer(default_int) :: pool_used = 0
         !! Number of characters currently used in `key_pool`.
      integer(default_int) :: pool_cap = 0
         !! Allocated length of `key_pool`.
   contains
      procedure :: init => hash_map_init
      procedure :: destroy => hash_map_destroy
      procedure :: clear => hash_map_clear
      procedure :: size => hash_map_size
      procedure :: is_empty => hash_map_is_empty
      procedure :: bucket_count => hash_map_bucket_count
      procedure :: insert => hash_map_insert
      procedure :: get => hash_map_get
      procedure :: has_key => hash_map_has_key
      procedure :: remove => hash_map_remove
      procedure :: keys => hash_map_keys
      procedure :: values => hash_map_values
      procedure :: at => hash_map_at
   end type hash_map_t