#include <string.h>
#include <stdio.h>
#include "../dictionary_types.h"
#include "./../dictionary.h"
#include "open_address_hash_dictionary.h"
#include "../../key_value/kv_system.h"
Description
A hash table using linear probing. Designed for in memory use.
- 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_hash.h.
Classes | |
struct | hashmap |
Struct used to maintain an instance of an in memory hashmap. More... | |
Macros | |
#define | ION_EMPTY -1 |
#define | ION_DELETED -2 |
#define | ION_IN_USE -3 |
#define | SIZEOF(STATUS) 1 |
Typedefs | |
typedef struct hashmap | ion_hashmap_t |
Prototype declaration for hashmap. More... | |
Functions | |
ion_err_t | oah_initialize (ion_hashmap_t *hashmap, ion_hash_t(*hashing_function)(ion_hashmap_t *, ion_key_t, int), ion_key_type_t key_type, ion_key_size_t key_size, ion_value_size_t value_size, int size) |
This function initializes an open address in memory hash map. More... | |
ion_err_t | oah_destroy (ion_hashmap_t *hash_map) |
Destroys the map in memory. More... | |
int | oah_get_location (ion_hash_t num, int size) |
Returns the theoretical location of item in hashmap. More... | |
ion_status_t | oah_insert (ion_hashmap_t *hash_map, ion_key_t key, ion_value_t value) |
Insert record into hashmap. More... | |
ion_status_t | oah_update (ion_hashmap_t *hash_map, ion_key_t key, ion_value_t value) |
Updates a value in the map. More... | |
ion_err_t | oah_find_item_loc (ion_hashmap_t *hash_map, ion_key_t key, int *location) |
Locates item in map. More... | |
ion_status_t | oah_delete (ion_hashmap_t *hash_map, ion_key_t key) |
Deletes item from map. More... | |
ion_status_t | oah_get (ion_hashmap_t *hash_map, ion_key_t key, ion_value_t value) |
Locates the record if it exists. More... | |
ion_hash_t | oah_compute_simple_hash (ion_hashmap_t *hashmap, ion_key_t key, int size_of_key) |
A simple hashing algorithm implementation. More... | |
Macro Definition Documentation
#define ION_DELETED -2 |
Definition at line 58 of file open_address_hash.h.
#define ION_EMPTY -1 |
Definition at line 57 of file open_address_hash.h.
#define ION_IN_USE -3 |
Definition at line 59 of file open_address_hash.h.
#define SIZEOF | ( | STATUS | ) | 1 |
Definition at line 60 of file open_address_hash.h.
Typedef Documentation
typedef struct hashmap ion_hashmap_t |
Prototype declaration for hashmap.
Definition at line 65 of file open_address_hash.h.
Function Documentation
ion_hash_t oah_compute_simple_hash | ( | ion_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 337 of file open_address_hash.c.
ion_status_t oah_delete | ( | ion_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 241 of file open_address_hash.c.
ion_err_t oah_destroy | ( | ion_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 94 of file open_address_hash.c.
ion_err_t oah_find_item_loc | ( | ion_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 194 of file open_address_hash.c.
ion_status_t oah_get | ( | ion_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 267 of file open_address_hash.c.
int oah_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 86 of file open_address_hash.c.
ion_err_t oah_initialize | ( | ion_hashmap_t * | hashmap, |
ion_hash_t(*)(ion_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 | ||
) |
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
)
- Returns
- The status describing the result of the initialization.
Definition at line 46 of file open_address_hash.c.
ion_status_t oah_insert | ( | ion_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 130 of file open_address_hash.c.
ion_status_t oah_update | ( | ion_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 114 of file open_address_hash.c.