open_address_file_hash_dictionary_handler.c File Reference

#include "open_address_file_hash_dictionary_handler.h"
#include "../../key_value/kv_system.h"
#include "open_address_file_hash.h"
#include "../../file/ion_file.h"

Description

The handler for a hash table using linear probing.

Author

Scott Ronald Fazackerley

Copyright

Copyright 2017 The University of British Columbia, IonDB Project Contributors (see AUTHORS.md)

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are met:

1.Redistributions of source code must retain the above copyright notice,

this list of conditions and the following disclaimer.

2.Redistributions in binary form must reproduce the above copyright notice,

this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3.Neither the name of the copyright holder nor the names of its contributors

may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Definition in file open_address_file_hash_dictionary_handler.c.

Include dependency graph for open_address_file_hash_dictionary_handler.c:

Functions
ion_status_t	oafdict_get (ion_dictionary_t *dictionary, ion_key_t key, ion_value_t value)
	Queries a dictionary instance for the given key and returns the associated value. More...
ion_err_t	oafdict_scan (ion_oafdict_cursor_t *cursor)
	Starts scanning map looking for conditions that match predicate and returns result. More...
ion_cursor_status_t	oafdict_next (ion_dict_cursor_t *cursor, ion_record_t *record)
	Next function to query and retrieve the next <K,V> that stratifies the predicate of the cursor. More...
ion_err_t	oafdict_find (ion_dictionary_t *dictionary, ion_predicate_t *predicate, ion_dict_cursor_t **cursor)
	Finds multiple instances of a keys that satisfy the provided predicate in the dictionary. More...
ion_err_t	oafdict_open_dictionary (ion_dictionary_handler_t *handler, ion_dictionary_t *dictionary, ion_dictionary_config_info_t *config, ion_dictionary_compare_t compare)
	Opens a specific open address file hash instance of a dictionary. More...
ion_err_t	oafdict_close_dictionary (ion_dictionary_t *dictionary)
	Closes an open address file hash instance of a dictionary. More...
void	oafdict_init (ion_dictionary_handler_t *handler)
	Registers a specific handler for a dictionary instance. More...
ion_status_t	oafdict_insert (ion_dictionary_t *dictionary, ion_key_t key, ion_value_t value)
	Inserts a key and value into the dictionary. More...
ion_err_t	oafdict_create_dictionary (ion_dictionary_id_t id, ion_key_type_t key_type, ion_key_size_t key_size, ion_value_size_t value_size, ion_dictionary_size_t dictionary_size, ion_dictionary_compare_t compare, ion_dictionary_handler_t *handler, ion_dictionary_t *dictionary)
	Creates an instance of a dictionary. More...
ion_status_t	oafdict_delete (ion_dictionary_t *dictionary, ion_key_t key)
	Deletes the key and assoicated value from the dictionary instance. More...
ion_err_t	oafdict_delete_dictionary (ion_dictionary_t *dictionary)
	Deletes an instance of the dictionary and associated data. More...
ion_err_t	oafdict_destroy_dictionary (ion_dictionary_id_t id)
	Cleans up all files created by the dictionary, and frees any allocated memory, for an already closed dictionary. More...
ion_status_t	oafdict_update (ion_dictionary_t *dictionary, ion_key_t key, ion_value_t value)
	Updates the value for a given key. More...
ion_boolean_t	oafdict_is_equal (ion_dictionary_t *dict, ion_key_t key1, ion_key_t key2)
	Compares two keys and determines if they are equal assuming that they are equal is length (in size). More...
void	oafdict_destroy_cursor (ion_dict_cursor_t **cursor)
	Next function to query and retrieve the next <K,V> that stratifies the predicate of the cursor. More...

Function Documentation

ion_err_t oafdict_close_dictionary

(

ion_dictionary_t *

dictionary

)

Closes an open address file hash instance of a dictionary.

Parameters

dictionary

A pointer to the specific dictionary instance to be closed.

Returns

The status of closing the dictionary.

Definition at line 372 of file open_address_file_hash_dictionary_handler.c.

  {
    ion_file_hashmap_t  *hash_map;
    ion_err_t           err;

    hash_map    = (ion_file_hashmap_t *) dictionary->instance;
    err         = oafh_close(hash_map);

    /* The following line creates an allocation error. Will not including it create a memory leak? */
/*  free(dictionary->instance); */

    dictionary->instance = NULL;

    if (err_ok != err) {
        return err_dictionary_destruction_error;
    }

    return err_ok;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_err_t oafdict_create_dictionary	(	ion_dictionary_id_t	id,
		ion_key_type_t	key_type,
		ion_key_size_t	key_size,
		ion_value_size_t	value_size,
		ion_dictionary_size_t	dictionary_size,
		ion_dictionary_compare_t	compare,
		ion_dictionary_handler_t *	handler,
		ion_dictionary_t *	dictionary
	)

Creates an instance of a dictionary.

Creates as instance of a dictionary given a key_size and value_size, in bytes as well as the dictionary size which is the number of buckets available in the hashmap.

Parameters

id
key_type
key_size	The size of the key in bytes.
value_size	The size of the value in bytes.
dictionary_size	The size of the hashmap in discrete units
compare	Function pointer for the comparison function for the dictionary instance.
handler	THe handler for the specific dictionary being created.
dictionary	The pointer declared by the caller that will reference the instance of the dictionary created.

Returns

The status of the creation of the dictionary.

Definition at line 419 of file open_address_file_hash_dictionary_handler.c.

  {
    UNUSED(id);
    /* this is the instance of the hashmap */
    dictionary->instance            = malloc(sizeof(ion_file_hashmap_t));

    dictionary->instance->compare   = compare;
    dictionary->instance->type      = dictionary_type_open_address_file_hash_t;

    /* this registers the dictionary the dictionary */
    oafh_initialize((ion_file_hashmap_t *) dictionary->instance, oafh_compute_simple_hash, key_type, key_size, value_size, dictionary_size, id);/* just pick an arbitary size for testing atm */

    /*TODO The correct comparison operator needs to be bound at run time
     * based on the type of key defined
    */

    if (NULL == handler) {
        return err_uninitialized;
    }

    /* register the correct handler */
    dictionary->handler = handler;

    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_status_t oafdict_delete	(	ion_dictionary_t *	dictionary,
		ion_key_t	key
	)

Deletes the key and assoicated value from the dictionary instance.

Parameters

dictionary	The instance of the dictionary to delete from.
key	The key that is to be deleted.

Returns

The status of the deletion

Definition at line 454 of file open_address_file_hash_dictionary_handler.c.

  {
    return oafh_delete((ion_file_hashmap_t *) dictionary->instance, key);
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_err_t oafdict_delete_dictionary

(

ion_dictionary_t *

dictionary

)

Deletes an instance of the dictionary and associated data.

Parameters

dictionary

The instance of the dictionary to delete.

Returns

The status of the dictionary deletion.

Definition at line 462 of file open_address_file_hash_dictionary_handler.c.

  {
    ion_err_t result = oafh_destroy((ion_file_hashmap_t *) dictionary->instance);

    free(dictionary->instance);
    dictionary->instance = NULL;/* When releasing memory, set pointer to NULL */
    return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void oafdict_destroy_cursor

(

ion_dict_cursor_t **

cursor

)

Next function to query and retrieve the next <K,V> that stratifies the predicate of the cursor.

Parameters

cursor

The cursor to iterate over the results.

Returns

The status of the cursor. Destroys the cursor.

Destroys the cursor when the user is finished with it. The destroy function will free up internally allocated memory as well as freeing up any reference to the cursor itself. Cursor pointers will be set to NULL as per ION_DB specification for de-allocated pointers.

Parameters

cursor

pointer to cursor.

Definition at line 525 of file open_address_file_hash_dictionary_handler.c.

  {
    (*cursor)->predicate->destroy(&(*cursor)->predicate);
    free(*cursor);
    *cursor = NULL;
}

Here is the caller graph for this function:

ion_err_t oafdict_destroy_dictionary

(

ion_dictionary_id_t

id

)

Cleans up all files created by the dictionary, and frees any allocated memory, for an already closed dictionary.

Parameters

id	The identifier identifying the dictionary to delete.

Returns

The resulting status of the operation.

Definition at line 473 of file open_address_file_hash_dictionary_handler.c.

  {
    char addr_filename[ION_MAX_FILENAME_LENGTH];

    int actual_filename_length = dictionary_get_filename(id, "oaf", addr_filename);

    if (actual_filename_length >= ION_MAX_FILENAME_LENGTH) {
        return err_dictionary_destruction_error;
    }

    fremove(addr_filename);

    return err_ok;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_err_t oafdict_find	(	ion_dictionary_t *	dictionary,
		ion_predicate_t *	predicate,
		ion_dict_cursor_t **	cursor
	)

Finds multiple instances of a keys that satisfy the provided predicate in the dictionary.

Generates a cursor that allows the traversal of items where the items key satisfies the predicate (if the underlying implementation allows it).

Parameters

dictionary	The instance of the dictionary to search.
predicate	The predicate to be used as the condition for matching.
cursor	The pointer to a cursor which is caller declared but callee is responsible for populating.

Returns

The status of the operation.

Definition at line 223 of file open_address_file_hash_dictionary_handler.c.

  {
    /* allocate memory for cursor */
    if ((*cursor = malloc(sizeof(ion_oafdict_cursor_t))) == NULL) {
        return err_out_of_memory;
    }

    (*cursor)->dictionary           = dictionary;
    (*cursor)->status               = cs_cursor_uninitialized;

    /* bind destroy method for cursor */
    (*cursor)->destroy              = oafdict_destroy_cursor;

    /* bind correct next function */
    (*cursor)->next                 = oafdict_next; /* this will use the correct value */

    /* allocate predicate */
    (*cursor)->predicate            = malloc(sizeof(ion_predicate_t));
    (*cursor)->predicate->type      = predicate->type;
    (*cursor)->predicate->destroy   = predicate->destroy;

    /* based on the type of predicate that is being used, need to create the correct cursor */
    switch (predicate->type) {
        case predicate_equality: {
            /* as this is an equality, need to malloc for key as well */
            if (((*cursor)->predicate->statement.equality.equality_value = malloc((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
                free((*cursor)->predicate);
                free(*cursor);  /* cleanup */
                return err_out_of_memory;
            }

            /* copy across the key value as the predicate may be destroyed */
            memcpy((*cursor)->predicate->statement.equality.equality_value, predicate->statement.equality.equality_value, ((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size)));

            /* find the location of the first element as this is a straight equality */
            int location = cs_invalid_index;

            if (oafh_find_item_loc((ion_file_hashmap_t *) dictionary->instance, (*cursor)->predicate->statement.equality.equality_value, &location) == err_item_not_found) {
                (*cursor)->status = cs_end_of_results;
                return err_ok;
            }
            else {
                (*cursor)->status = cs_cursor_initialized;

                /* cast to specific instance type for conveniences of setup */
                ion_oafdict_cursor_t *oadict_cursor = (ion_oafdict_cursor_t *) (*cursor);

                /* the cursor is ready to be consumed */
                oadict_cursor->first    = location;

                oadict_cursor->current  = location;
                return err_ok;
            }

            break;
        }

        case predicate_range: {
            /* as this is a range, need to malloc lower bound key */
            if (((*cursor)->predicate->statement.range.lower_bound = malloc((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
                free((*cursor)->predicate);
                free(*cursor);  /* cleanup */
                return err_out_of_memory;
            }

            /* copy across the key value as the predicate may be destroyed */
            memcpy((*cursor)->predicate->statement.range.lower_bound, predicate->statement.range.lower_bound, (((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size));

            /* as this is a range, need to malloc upper bound key */
            if (((*cursor)->predicate->statement.range.upper_bound = malloc((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
                free((*cursor)->predicate->statement.range.lower_bound);
                free((*cursor)->predicate);
                free(*cursor);  /* cleanup */
                return err_out_of_memory;
            }

            /* copy across the key value as the predicate may be destroyed */
            memcpy((*cursor)->predicate->statement.range.upper_bound, predicate->statement.range.upper_bound, (((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size));
        }

        /* Range query will intentionally continue to all record code to get rid of duplicate statements. */
        case predicate_all_records: {
            ion_oafdict_cursor_t    *oafdict_cursor = (ion_oafdict_cursor_t *) (*cursor);
            ion_file_hashmap_t      *hash_map       = ((ion_file_hashmap_t *) dictionary->instance);

            (*cursor)->status       = cs_cursor_initialized;
            oafdict_cursor->first   = (hash_map->map_size) - 1;
            oafdict_cursor->current = -1;

            ion_err_t err = oafdict_scan(oafdict_cursor);

            if (cs_end_of_results == err) {
                (*cursor)->status = cs_end_of_results;
            }

            return err_ok;
            break;
        }

        case predicate_predicate: {
            break;
        }

        default: {
            return err_invalid_predicate;   /* * Invalid predicate supplied */
            break;
        }
    }

    return err_ok;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_status_t oafdict_get	(	ion_dictionary_t *	dictionary,
		ion_key_t	key,
		ion_value_t	value
	)

Queries a dictionary instance for the given key and returns the associated value.

Queries a dictionary instance for the given key and returns the associated value. If the write_concern is set to wc_insert_unique then if the key exists already, an error will be generated as duplicate keys are prevented. If the write_concern is set to wc_update, the updates are allowed. In this case, if the key exists in the hashmap, the value will be updated. If the key does not exist, then a new item will be inserted to hashmap.

Parameters

dictionary	The instance of the dictionary to query.
key	The key to search for.
value	A pointer that is used to return the value associated with the provided key. The function will malloc memory for the value and it is up to the consumer the free the associated memory.

Returns

The status of the query.

Definition at line 67 of file open_address_file_hash_dictionary_handler.c.

  {
    return oafh_get((ion_file_hashmap_t *) dictionary->instance, key, value);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void oafdict_init

(

ion_dictionary_handler_t *

handler

)

Registers a specific handler for a dictionary instance.

Registers functions for handlers. This only needs to be called once for each type of dictionary that is present.

Parameters

handler

The handler for the dictionary instance that is to be initialized.

Definition at line 394 of file open_address_file_hash_dictionary_handler.c.

  {
    handler->insert             = oafdict_insert;
    handler->create_dictionary  = oafdict_create_dictionary;
    handler->get                = oafdict_get;
    handler->update             = oafdict_update;
    handler->find               = oafdict_find;
    handler->remove             = oafdict_delete;
    handler->delete_dictionary  = oafdict_delete_dictionary;
    handler->destroy_dictionary = oafdict_destroy_dictionary;
    handler->open_dictionary    = oafdict_open_dictionary;
    handler->close_dictionary   = oafdict_close_dictionary;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_status_t oafdict_insert	(	ion_dictionary_t *	dictionary,
		ion_key_t	key,
		ion_value_t	value
	)

Inserts a key and value into the dictionary.

Parameters

dictionary	The dictionary instance to insert the value into.
key	The key to use.
value	The value to use.

Returns

The status on the insertion of the record.

Definition at line 410 of file open_address_file_hash_dictionary_handler.c.

  {
    return oafh_insert((ion_file_hashmap_t *) dictionary->instance, key, value);
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_boolean_t oafdict_is_equal	(	ion_dictionary_t *	dict,
		ion_key_t	key1,
		ion_key_t	key2
	)

Compares two keys and determines if they are equal assuming that they are equal is length (in size).

Parameters

dict	The map the keys are associated with.
key1	The first key for comparison.
key2	The second key for comparison.

Returns

If the keys are equal.

Definition at line 511 of file open_address_file_hash_dictionary_handler.c.

  {
    if (memcmp(key1, key2, (((ion_file_hashmap_t *) dict->instance)->super.record.key_size)) == ION_IS_EQUAL) {
        return boolean_true;
    }
    else {
        return boolean_false;
    }
}

ion_cursor_status_t oafdict_next	(	ion_dict_cursor_t *	cursor,
		ion_record_t *	record
	)

Next function to query and retrieve the next <K,V> that stratifies the predicate of the cursor.

Parameters

cursor	The cursor to iterate over the results.
record

Returns

The status of the cursor.

Definition at line 151 of file open_address_file_hash_dictionary_handler.c.

  {
    ion_oafdict_cursor_t *oafdict_cursor = (ion_oafdict_cursor_t *) cursor;

    /* check the status of the cursor and if it is not valid or at the end, just exit */
    if (cursor->status == cs_cursor_uninitialized) {
        return cursor->status;
    }
    else if (cursor->status == cs_end_of_results) {
        return cursor->status;
    }
    else if ((cursor->status == cs_cursor_initialized) || (cursor->status == cs_cursor_active)) {
        /* cursor is active and results have never been accessed */
        /* extract reference to map */
        ion_file_hashmap_t *hash_map = ((ion_file_hashmap_t *) cursor->dictionary->instance);

        /* assume that the value has been pre-allocated */
        /* compute length of data record stored in map */
        int data_length = hash_map->super.record.key_size + hash_map->super.record.value_size;

        if (cursor->status == cs_cursor_active) {
            /* find the next valid entry */

            /* scan and determine what to do? */
            if (cs_end_of_results == oafdict_scan(oafdict_cursor)) {
                /* Then this is the end and there are no more results */
                cursor->status = cs_end_of_results;
                return cursor->status;
            }
        }
        else {
            /* if the cursor is initialized but not active, then just read the data and set cursor active */
            cursor->status = cs_cursor_active;
        }

        /* the results are now ready //reference item at given position */

        /* set position in file to read value */
        fseek(hash_map->file, (SIZEOF(STATUS) + data_length) * oafdict_cursor->current  /* position is based on indexes (not abs file pos) */
            + SIZEOF(STATUS), SEEK_SET);

        fread(record->key, hash_map->super.record.key_size, 1, hash_map->file);
        fread(record->value, hash_map->super.record.value_size, 1, hash_map->file);

        /* and update current cursor position */
        return cursor->status;
    }

    /* and if you get this far, the cursor is invalid */
    return cs_invalid_cursor;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_err_t oafdict_open_dictionary	(	ion_dictionary_handler_t *	handler,
		ion_dictionary_t *	dictionary,
		ion_dictionary_config_info_t *	config,
		ion_dictionary_compare_t	compare
	)

Opens a specific open address file hash instance of a dictionary.

Parameters

handler	A pointer to the handler for the specific dictionary being opened.
dictionary	The pointer declared by the caller that will reference the instance of the dictionary opened.
config	The configuration info of the specific dictionary to be opened.
compare	Function pointer for the comparison function for the dictionary.

Returns

The status of opening the dictionary.

Definition at line 354 of file open_address_file_hash_dictionary_handler.c.

  {
    return oafdict_create_dictionary(config->id, config->type, config->key_size, config->value_size, config->dictionary_size, compare, handler, dictionary);
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_err_t oafdict_scan

(

ion_oafdict_cursor_t *

cursor

)

Starts scanning map looking for conditions that match predicate and returns result.

Scans that map looking for the next value that satisfies the predicate. The next valid index is returned through the cursor

Parameters

cursor

A pointer to the cursor that is operating on the map.

Returns

The status of the scan.

Definition at line 88 of file open_address_file_hash_dictionary_handler.c.

  {
    /* need to scan hashmap fully looking for values that satisfy - need to think about */
    ion_file_hashmap_t *hash_map    = (ion_file_hashmap_t *) (cursor->super.dictionary->instance);

    int loc                         = (cursor->current + 1) % hash_map->map_size;
    /* this is the current position of the cursor */
    /* and start scanning 1 ahead */

    int record_size = SIZEOF(STATUS) + hash_map->super.record.key_size + hash_map->super.record.value_size;

    /* move to the correct position in the fie */
    fseek(hash_map->file, loc * record_size, SEEK_SET);

    ion_hash_bucket_t *item;

    item = malloc(record_size);

    /* start at the current position, scan forward */
    while (loc != cursor->first) {
        fread(item, record_size, 1, hash_map->file);

        if ((item->status == ION_EMPTY) || (item->status == ION_DELETED)) {
            /* if empty, just skip to next cell */
            loc++;
        }
        else {
            /* check to see if the current key value satisfies the predicate */

            ion_boolean_t key_satisfies_predicate = test_predicate(&(cursor->super), item->data);   /* assumes that the key is first */

            if (key_satisfies_predicate == boolean_true) {
                cursor->current = loc;  /* this is the next index for value */
                free(item);
                return cs_cursor_active;
            }

            /* If valid bucket is not found, advance current position. */
            loc++;
        }

        if (loc >= hash_map->map_size) {
            /* Perform wrapping */
            loc = 0;
        }
    }

    /* if you end up here, you've wrapped the entire data structure and not found a value */
    free(item);
    return cs_end_of_results;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ion_status_t oafdict_update	(	ion_dictionary_t *	dictionary,
		ion_key_t	key,
		ion_value_t	value
	)

Updates the value for a given key.

Updates the value for a given key. If the key does not currently exist in the hashmap, it will be created and the value sorted.

Parameters

dictionary	The instance of the dictionary to be updated.
key	The key that is to be updated.
value	The value that is to be updated.

Returns

The status of the update.

Definition at line 490 of file open_address_file_hash_dictionary_handler.c.

  {
    return oafh_update((ion_file_hashmap_t *) dictionary->instance, key, value);
}

Here is the call graph for this function:

Here is the caller graph for this function: