#include "open_address_file_hash.h"
Description
Open Address Hash Map.
The open address hash map allows non-colliding entries into a hash table
- Todo:
capture size of map
prevent duplicate insertions
When creating the hash-map, need to know something about what is going in it. What we need to know if the the size of the key and the size of the data. That is all. Nothing else.
- 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.c.
Macros | |
#define | ION_TEST_FILE "file.bin" |
Macro Definition Documentation
#define ION_TEST_FILE "file.bin" |
Definition at line 45 of file open_address_file_hash.c.
Function Documentation
ion_err_t oafh_close | ( | ion_file_hashmap_t * | hash_map | ) |
This function closes a hashmap dictionary.
- Parameters
-
hash_map Pointer to the hashmap instance to close.
- Returns
- The status describing the result of closing the dictionary.
Definition at line 48 of file open_address_file_hash.c.
ion_hash_t oafh_compute_simple_hash | ( | ion_file_hashmap_t * | hashmap, |
ion_key_t | key, | ||
int | size_of_key | ||
) |
A simple hashing algorithm implementation.
- Parameters
-
hashmap The hash function is associated with. key The original key value to find hash value for. size_of_key The size of the key in bytes.
- Returns
- The hashed value for the key.
Definition at line 414 of file open_address_file_hash.c.
ion_status_t oafh_delete | ( | ion_file_hashmap_t * | hash_map, |
ion_key_t | key | ||
) |
Deletes item from map.
Deletes item from map based on key. If key does not exist error is returned
- Parameters
-
hash_map The map into which the data is going to be inserted. key The key for the record that is being searched for.
Definition at line 339 of file open_address_file_hash.c.
ion_err_t oafh_destroy | ( | ion_file_hashmap_t * | hash_map | ) |
Destroys the map in memory.
Destroys the map in memory and frees the underlying memory.
- Parameters
-
hash_map The map into which the data is going to be inserted
- Returns
- The status describing the result of the destruction
Definition at line 141 of file open_address_file_hash.c.
ion_err_t oafh_find_item_loc | ( | ion_file_hashmap_t * | hash_map, |
ion_key_t | key, | ||
int * | location | ||
) |
Locates item in map.
Based on a key, function locates the record in the map.
- Parameters
-
hash_map The map into which the data is going to be inserted. key The key for the record that is being searched for. location Pointer to the location variable
- Returns
- The status of the find
Definition at line 279 of file open_address_file_hash.c.
ion_status_t oafh_get | ( | ion_file_hashmap_t * | hash_map, |
ion_key_t | key, | ||
ion_value_t | value | ||
) |
Locates the record if it exists.
Locates the record based on key match is it exists and returns a pointer to the record that has been materialized in memory. This presents a significant issue as both the key and value could be modified, causing issues with map.
- Parameters
-
hash_map The map into which the data is going to be inserted. key The key for the record that is being searched for. value The value associated in the map.
Definition at line 381 of file open_address_file_hash.c.
int oafh_get_location | ( | ion_hash_t | num, |
int | size | ||
) |
Returns the theoretical location of item in hashmap.
Determines which bucket a record is to be placed based on the hash function used.
- Parameters
-
num The key. size The possible number of buckets in the map.
- Returns
- The index position to start probing at.
Definition at line 133 of file open_address_file_hash.c.
ion_err_t oafh_initialize | ( | ion_file_hashmap_t * | hashmap, |
ion_hash_t(*)(ion_file_hashmap_t *, ion_key_t, int) | hashing_function, | ||
ion_key_type_t | key_type, | ||
ion_key_size_t | key_size, | ||
ion_value_size_t | value_size, | ||
int | size, | ||
ion_dictionary_id_t | id | ||
) |
This function initializes an open address in memory hash map.
- Parameters
-
hashmap Pointer to the hashmap instance to initialize. hashing_function Function pointer to the hashing function for the instance. key_type The type of key that is being stored in the dictionary instance. key_size The size of the key in bytes. value_size The size of the value in bytes. size The size of the hashmap in item ( key_size
+value_size
+1
)id The id of hashmap.
- Returns
- The status describing the result of the initialization.
Definition at line 63 of file open_address_file_hash.c.
ion_status_t oafh_insert | ( | ion_file_hashmap_t * | hash_map, |
ion_key_t | key, | ||
ion_value_t | value | ||
) |
Insert record into hashmap.
Attempts to insert data of a given structure as dictated by record into the provided hashmap. The record is used to determine the structure of the data <K,V> so that the key can be extracted. The function will return the status of the insert. If the record has been successfully inserted, the status will reflect success. If the record can not be successfully inserted the error code will reflect failure. Will only allow for insertion of unique records.
- Parameters
-
hash_map The map into which the data is going to be inserted. key The key that is being used to locate the position of the data. value The value that is being inserted.
- Returns
- The status of the insert.
Definition at line 186 of file open_address_file_hash.c.
ion_status_t oafh_update | ( | ion_file_hashmap_t * | hash_map, |
ion_key_t | key, | ||
ion_value_t | value | ||
) |
Updates a value in the map.
Updates a value in the map. If the value does not exist, it will insert the value.
- Parameters
-
hash_map The map into which the data is going to be inserted. key The key that is being used to locate the position of the data. value The value that is being inserted.
- Returns
- The status of the update
Definition at line 170 of file open_address_file_hash.c.