json_hash_table Derived Type

type, public :: json_hash_table

Hash table type.

The keys are the member names of a JSON object and the values are pointers to the associated JSON values.

This can be used to speed up lookups of JSON object members by name, since the JSON library itself uses linked lists to store the members of a JSON object, which can lead to O(n) lookup time for n members. By creating a hash table for the members of a JSON object, we can achieve O(1) average case lookup time.


Inherits

type~~json_hash_table~~InheritsGraph type~json_hash_table json_hash_table type~hash_node_t hash_node_t type~json_hash_table->type~hash_node_t buckets type~json_core json_core type~json_hash_table->type~json_core json type~hash_node_t->type~hash_node_t next type~json_value json_value type~hash_node_t->type~json_value value type~json_value->type~json_value previous, next, parent, children, tail

Inherited by

type~~json_hash_table~~InheritedByGraph type~json_hash_table json_hash_table type~json_file json_file type~json_file->type~json_hash_table hash

Components

Type Visibility Attributes Name Initial
type(hash_node_t), private, dimension(:), allocatable :: buckets

array of buckets for the hash table. Each bucket is a linked list of hash_node_t to handle collisions.
integer(kind=IK), private :: capacity = 16_IK

Number of buckets in the table
logical(kind=LK), private :: case_sensitive_keys = .true.

Case-sensitive key comparison
type(json_core), private :: json

The instance of the json_core factory used for this table.
real(kind=RK), private :: load_factor = 0.75_RK

Resize threshold that determines when the hash table should automatically resize to maintain optimal performance.
integer(kind=IK), private :: size = 0_IK

Number of elements in the table
logical(kind=LK), private :: trailing_spaces_significant = .false.

Whether trailing spaces in keys are significant for comparison

Finalization Procedures

final :: hash_table_finalize

  • private subroutine hash_table_finalize(me)

    Finalizer - automatically clean up when hash table goes out of scope.

    Arguments

    Type IntentOptional Attributes Name
    type(json_hash_table), intent(inout) :: me

Type-Bound Procedures

procedure, public :: create => hash_table_create_from_value

  • private subroutine hash_table_create_from_value(me, json, p, status_ok, initial_capacity)

    Create a hash table from the children of an existing JSON object. The keys are the object member names and the values are pointers to the associated JSON values.

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(out) :: me
    type(json_core), intent(in) :: json

    the JSON core factory to use for this hash table. a copy of this will be made and stored in the table.
    type(json_value), pointer :: p

    the JSON value whose children will be used to populate the hash table. This must be a JSON object.
    logical(kind=LK), intent(out) :: status_ok

    true if no problems.
    integer(kind=IK), intent(in), optional :: initial_capacity

    initial capacity of the hash table (number of buckets). If not provided, it will be set based on the number of members divided by the load factor to minimize the number of resizes needed as members are inserted

procedure, public :: destroy => hash_table_destroy

  • private subroutine hash_table_destroy(me)

    Destroy hash table and free all memory

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(inout) :: me

procedure, public :: get => hash_table_get

  • private subroutine hash_table_get(me, key, value, found)

    Get value for a given key

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(in) :: me
    character(kind=CK, len=*), intent(in) :: key

    key to look up.
    type(json_value), pointer :: value

    pointer to the value associated with the key. This will be set to null() if the key is not found.
    logical(kind=LK), intent(out), optional :: found

    flag indicating whether the key was found in the table (true) or not (false).

procedure, private :: hash => hash_table_hash

  • private function hash_table_hash(me, key) result(hash_value)

    DJB hash algorithm for a string.

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(in) :: me
    character(kind=CK, len=*), intent(in) :: key

    Return Value integer(kind=IK)

procedure, private :: insert => hash_table_insert

  • private subroutine hash_table_insert(me, key, value)

    Insert or update a key-value pair

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(inout) :: me
    character(kind=CK, len=*), intent(in) :: key

    key to insert. This will be preprocessed (trimmed and/or lowercased) according to the settings of the hash table.
    type(json_value), pointer :: value

    value to associate with the key. This is a pointer to a JSON value.

procedure, private :: keys_equal

  • private function keys_equal(me, key1, key2) result(equal)

    Compare two keys for equality, taking into account the setting for trailing spaces.

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(in) :: me
    character(kind=CK, len=*), intent(in) :: key1
    character(kind=CK, len=*), intent(in) :: key2

    Return Value logical(kind=LK)

procedure, private :: preprocess_key

  • private function preprocess_key(me, key) result(proc_key)

    Preprocess key for saving in the hash table, as well as for insertion and lookup (handle trim and case-sensitivity).

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(in) :: me
    character(kind=CK, len=*), intent(in) :: key

    the key to preprocess

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

    the preprocessed key to use for storage and comparison in the hash table.

procedure, private :: resize => hash_table_resize

  • private subroutine hash_table_resize(me, new_capacity)

    Resize the hash table (internal method)

    Arguments

    Type IntentOptional Attributes Name
    class(json_hash_table), intent(inout) :: me
    integer(kind=IK), intent(in) :: new_capacity

Source Code

    type, public :: json_hash_table
        !! Hash table type.
        !!
        !! The keys are the member names of a JSON object and the
        !! values are pointers to the associated JSON values.
        !!
        !! This can be used to speed up lookups of JSON object members by name,
        !! since the JSON library itself uses linked lists to store the members
        !! of a JSON object, which can lead to `O(n)` lookup time for `n` members.
        !! By creating a hash table for the members of a JSON object,
        !! we can achieve `O(1)` average case lookup time.

        private

        type(json_core) :: json !! The instance of the [[json_core(type)]]
                                !! factory used for this table.

        type(hash_node_t), dimension(:), allocatable :: buckets !! array of buckets for the hash table.
                                                                !! Each bucket is a linked list of `hash_node_t`
                                                                !! to handle collisions.
        integer(IK) :: size = 0_IK        !! Number of elements in the table
        integer(IK) :: capacity = 16_IK   !! Number of buckets in the table
        real(RK) :: load_factor = 0.75_RK !! Resize threshold that determines when the
                                          !! hash table should automatically resize to
                                          !! maintain optimal performance.

        ! these are obtained from `json`:
        logical(LK) :: case_sensitive_keys = .true. !! Case-sensitive key comparison
        logical(LK) :: trailing_spaces_significant = .false. !! Whether trailing spaces in keys
                                                             !! are significant for comparison

        contains

        private

        procedure,public :: create  => hash_table_create_from_value
        procedure,public :: destroy => hash_table_destroy
        procedure,public :: get     => hash_table_get

        procedure :: insert => hash_table_insert
        procedure :: hash => hash_table_hash
        procedure :: resize => hash_table_resize
        procedure :: preprocess_key
        procedure :: keys_equal

        final :: hash_table_finalize

    end type json_hash_table