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.

callable functions

overview of functions provided

// namespaces

namespace conf;

// typedefs

typedef float spc_;
typedef double rpc_;
typedef int ipc_;

// structs

struct hash_control_type;
struct hash_inform_type;

// global functions

void hash_initialize(
    ipc_ nchar,
    ipc_ length,
    void **data,
    struct hash_control_type* control,
    struct hash_inform_type* inform
);

void hash_information(void **data, struct hash_inform_type* inform, ipc_ *status);

void hash_terminate(
    void **data,
    struct hash_control_type* control,
    struct hash_inform_type* inform
);

typedefs

typedef float spc_

spc_ is real single precision

typedef double rpc_

rpc_ is the real working precision used, but may be changed to float by defining the preprocessor variable REAL_32 or (if supported) to __real128 using the variable REAL_128.

typedef int ipc_

ipc_ is the default integer word length used, but may be changed to int64_t by defining the preprocessor variable INTEGER_64.

function calls

void hash_initialize(
    ipc_ nchar,
    ipc_ length,
    void **data,
    struct hash_control_type* control,
    struct hash_inform_type* inform
)

Set default control values and initialize private data

Parameters:

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

void hash_information(void **data, struct hash_inform_type* inform, ipc_ *status)

Provides output information

Parameters:

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

void hash_terminate(
    void **data,
    struct hash_control_type* control,
    struct hash_inform_type* inform
)

Deallocate all internal private storage

Parameters:

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

available structures

hash_control_type structure

#include <galahad_hash.h>

struct hash_control_type {
    // fields

    ipc_ error;
    ipc_ out;
    ipc_ print_level;
    bool space_critical;
    bool deallocate_error_fatal;
    char prefix[31];
};

detailed documentation

control derived type as a C struct

components

ipc_ error

error and warning diagnostics occur on stream error

ipc_ out

general output occurs on stream out

ipc_ 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

char prefix[31]

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

#include <galahad_hash.h>

struct hash_inform_type {
    // fields

    ipc_ status;
    ipc_ alloc_status;
    char bad_alloc[81];
};

detailed documentation

inform derived type as a C struct

components

ipc_ 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.

ipc_ alloc_status

the status of the last attempted allocation/deallocation.

char bad_alloc[81]

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

Index