GALAHAD HASH package

purpose

The hash package sets up, inserts into, removes from and searches a chained scatter table (Williams, 1959).

Currently only the options and inform dictionaries are exposed; these are provided and used by other GALAHAD packages with Python interfaces. Please contact us if you would like full functionality!

See Section 4 of $GALAHAD/doc/hash.pdf for additional details.

method

To insert a word in the table, the word is first mapped onto an integer value, the entry integer. This mapping is often called hashing. As many words may be mapped to the same value (a collision), a chain of used locations starting from the entry integer is searched until an empty location is found. The word is inserted in the table at this point and the chain extended to the next unoccupied entry. The hashing routine is intended to reduce the number of collisions. Words are located and flagged as deleted from the table in exactly the same way; the word is hashed and the resulting chain searched until the word is matched or the end of the chain reached. Provided there is sufficient space in the table, the expected number of operations needed to perform an insertion, search or removal is \(O(1)\).

reference

The chained scatter table search and insertion method is due to

F. A. Williams (1959), ``Handling identifies as internal symbols in language processors’’, Communications of the ACM 2(6) (1959) 21-24.

parametric real type T

Below, the symbol T refers to a parametric real type that may be Float32 (single precision) or Float64 (double precision).

callable functions

    function hash_initialize(T, nchar, length, data, control, inform)

Set default control values and initialize private data

Parameters:

nchar	is a scalar variable of type Int32 that holds the number of characters permitted in each word in the hash table
length	is a scalar variable of type Int32 that holds the maximum number of words that can be held in the dictionary
data	holds private internal data
control	is a structure containing control information (see hash_control_type)
inform	is a structure containing output information (see hash_inform_type)

    function hash_information(T, data, inform, status)

Provides output information

Parameters:

data	holds private internal data
inform	is a structure containing output information (see hash_inform_type)
status	is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently): 0 The values were recorded successfully

    function hash_terminate(T, data, control, inform)

Deallocate all internal private storage

Parameters:

data	holds private internal data
control	is a structure containing control information (see hash_control_type)
inform	is a structure containing output information (see hash_inform_type)

available structures

hash_control_type structure

    struct hash_control_type
      error::Int32
      out::Int32
      print_level::Int32
      space_critical::Bool
      deallocate_error_fatal::Bool
      prefix::NTuple{31,Cchar}

detailed documentation

control derived type as a Julia structure

components

Int32 error

error and warning diagnostics occur on stream error

Int32 out

general output occurs on stream out

Int32 print_level

the level of output required. Possible values are:

• \(\leq\) 0 no output,

• \(\geq\) 1 debugging

Bool space_critical

if space_critical true, every effort will be made to use as little space as possible. This may result in longer computation time

Bool deallocate_error_fatal

if deallocate_error_fatal is true, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue

NTuple{31,Cchar} prefix

all output lines will be prefixed by prefix(2:LEN(TRIM(prefix))-1) where prefix contains the required string enclosed in quotes, e.g. “string” or ‘string’

hash_inform_type structure

    struct hash_inform_type
      status::Int32
      alloc_status::Int32
      bad_alloc::NTuple{81,Cchar}

detailed documentation

inform derived type as a Julia structure

components

Int32 status

return status. Possible values are:

• 0

  The initialization, insertion or deletion was successful.

• -1

  An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

• -2

  A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

• -99

  The current dictionary is full and should be rebuilt with more space.

Int32 alloc_status

the status of the last attempted allocation/deallocation.

NTuple{81,Cchar} bad_alloc

the name of the array for which an allocation/deallocation error occurred.

Index