open_address_hash.h File Reference
#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.

Author
Scott Ronald Fazackerley
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.

Include dependency graph for open_address_hash.h:
This graph shows which files directly or indirectly include this file:

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
hashmapThe hash function is associated with.
keyThe original key value to find hash value for.
size_of_keyThe size of the key in bytes.
Returns
The hashed value for the key.

Definition at line 337 of file open_address_hash.c.

341  {
342  UNUSED(size_of_key);
343 
344  ion_hash_t hash = (ion_hash_t) (((*(int *) key) % hashmap->map_size) + hashmap->map_size) % hashmap->map_size;
345 
346  return hash;
347 }
int ion_hash_t
The position in the hashmap.
#define key(k)
Definition: bpp_tree.c:75
#define UNUSED(x)
Definition: kv_system.h:102

Here is the caller graph for this function:

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_mapThe map into which the data is going to be inserted.
keyThe key for the record that is being searched for.

Definition at line 241 of file open_address_hash.c.

244  {
245  int loc = -1;
246 
247  if (oah_find_item_loc(hash_map, key, &loc) == err_item_not_found) {
248 #if ION_DEBUG
249  printf("Item not found when trying to oah_delete.\n");
250 #endif
252  }
253  else {
254  /* locate item */
255  ion_hash_bucket_t *item = (((ion_hash_bucket_t *) ((hash_map->entry + (hash_map->super.record.key_size + hash_map->super.record.value_size + SIZEOF(STATUS)) * loc))));
256 
257  item->status = ION_DELETED; /* delete item */
258 
259 #if ION_DEBUG
260  printf("Item deleted at location %d\n", loc);
261 #endif
262  return ION_STATUS_OK(1);
263  }
264 }
#define ION_DELETED
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
char * entry
ion_dictionary_parent_t super
#define ION_STATUS_OK(count)
Definition: kv_system.h:113
#define key(k)
Definition: bpp_tree.c:75
#define printf(format,...)
Struct used to maintain individual records in the hashmap.
ion_key_size_t key_size
Definition: kv_system.h:307
ion_err_t oah_find_item_loc(ion_hashmap_t *hash_map, ion_key_t key, int *location)
Locates item in map.
#define SIZEOF(STATUS)
ion_value_size_t value_size
Definition: kv_system.h:309

Here is the call graph for this function:

Here is the caller graph for this function:

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

96  {
97  hash_map->compute_hash = NULL;
98  hash_map->map_size = 0;
99  hash_map->super.record.key_size = 0;
100  hash_map->super.record.value_size = 0;
101 
102  if (hash_map->entry != NULL) {
103  /* check to ensure that you are not freeing something already free */
104  free(hash_map->entry);
105  hash_map->entry = NULL; /* */
106  return err_ok;
107  }
108  else {
110  }
111 }
int(* compute_hash)(ion_hashmap_t *, ion_key_t, int)
ion_record_info_t record
char * entry
ion_dictionary_parent_t super
ion_key_size_t key_size
Definition: kv_system.h:307
ion_value_size_t value_size
Definition: kv_system.h:309

Here is the caller graph for this function:

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_mapThe map into which the data is going to be inserted.
keyThe key for the record that is being searched for.
locationPointer to the location variable
Returns
The status of the find

Definition at line 194 of file open_address_hash.c.

198  {
199  /* compute hash value for given key */
200  ion_hash_t hash = hash_map->compute_hash(hash_map, key, hash_map->super.record.key_size);
201 
202  int loc = oah_get_location(hash, hash_map->map_size);
203  /* determine bucket based on hash */
204 
205  int count = 0;
206 
207  while (count != hash_map->map_size) {
208  /* check to see if current item is a match based on key */
209  /* locate first item */
210  ion_hash_bucket_t *item = (((ion_hash_bucket_t *) ((hash_map->entry + (hash_map->super.record.key_size + hash_map->super.record.value_size + SIZEOF(STATUS)) * loc))));
211 
212  if (item->status == ION_EMPTY) {
213  return err_item_not_found; /* if you hit an empty cell, exit */
214  }
215  else {
216  /* calculate if there is a match */
217 
218  if (item->status != ION_DELETED) {
219  int key_is_equal = hash_map->super.compare(item->data, key, hash_map->super.record.key_size);
220 
221  if (ION_IS_EQUAL == key_is_equal) {
222  (*location) = loc;
223  return err_ok;
224  }
225  }
226 
227  count++;
228  loc++;
229 
230  if (loc >= hash_map->map_size) {
231  /* Perform wrapping */
232  loc = 0;
233  }
234  }
235  }
236 
237  return err_item_not_found; /* key have not been found */
238 }
int ion_hash_t
The position in the hashmap.
int(* compute_hash)(ion_hashmap_t *, ion_key_t, int)
#define ION_DELETED
ion_record_info_t record
char * entry
#define ION_EMPTY
ion_byte_t data[]
ion_dictionary_parent_t super
#define key(k)
Definition: bpp_tree.c:75
int oah_get_location(ion_hash_t num, int size)
Returns the theoretical location of item in hashmap.
Struct used to maintain individual records in the hashmap.
ion_key_size_t key_size
Definition: kv_system.h:307
#define SIZEOF(STATUS)
ion_dictionary_compare_t compare
ion_value_size_t value_size
Definition: kv_system.h:309
#define ION_IS_EQUAL
Definition: kv_system.h:64

Here is the call graph for this function:

Here is the caller graph for this function:

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_mapThe map into which the data is going to be inserted.
keyThe key for the record that is being searched for.
valueThe value associated in the map.

Definition at line 267 of file open_address_hash.c.

271  {
272  int loc;
273 
274  if (oah_find_item_loc(hash_map, key, &loc) == err_ok) {
275 #if ION_DEBUG
276  printf("Item found at location %d\n", loc);
277 #endif
278 
279  int data_length = hash_map->super.record.key_size + hash_map->super.record.value_size;
280  ion_hash_bucket_t *item = (((ion_hash_bucket_t *) ((hash_map->entry + (data_length + SIZEOF(STATUS)) * loc))));
281 
282  /* *value = malloc(sizeof(char) * (hash_map->super.record.value_size)); */
283  memcpy(value, (item->data + hash_map->super.record.key_size), hash_map->super.record.value_size);
284  return ION_STATUS_OK(1);
285  }
286  else {
287 #if ION_DEBUG
288  printf("Item not found in hash table.\n");
289 #endif
291  }
292 }
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
char * entry
ion_byte_t data[]
ion_dictionary_parent_t super
#define ION_STATUS_OK(count)
Definition: kv_system.h:113
#define key(k)
Definition: bpp_tree.c:75
#define printf(format,...)
Struct used to maintain individual records in the hashmap.
ion_key_size_t key_size
Definition: kv_system.h:307
ion_err_t oah_find_item_loc(ion_hashmap_t *hash_map, ion_key_t key, int *location)
Locates item in map.
#define SIZEOF(STATUS)
ion_value_size_t value_size
Definition: kv_system.h:309

Here is the call graph for this function:

Here is the caller graph for this function:

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
numThe key.
sizeThe 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.

89  {
90  return num % size;
91 }

Here is the caller graph for this function:

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
hashmapPointer to the hashmap instance to initialize.
hashing_functionFunction pointer to the hashing function for the instance.
key_typeThe type of key that is being stored in the dictionary instance.
key_sizeThe size of the key in bytes.
value_sizeThe size of the value in bytes.
sizeThe 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.

53  {
54  int i;
55 
56  hashmap->write_concern = wc_insert_unique; /* By default allow unique inserts only */
57  hashmap->super.record.key_size = key_size;
58  hashmap->super.record.value_size = value_size;
59  hashmap->super.key_type = key_type;
60 
61 /* hashmap->compare = compare;*/
62 
63  /* The hash map is allocated as a single contiguous array*/
64  hashmap->map_size = size;
65  hashmap->entry = malloc((hashmap->super.record.key_size + hashmap->super.record.value_size + 1) * hashmap->map_size);
66  /* Allows for binding of different hash function depending on requirements. */
67  hashmap->compute_hash = (*hashing_function);
68 
69  if (NULL == hashmap->entry) {
70  return 1;
71  }
72 
73 #if ION_DEBUG
74  printf("Initializing hash table\n");
75 #endif
76 
77  /* Initialize hash table */
78  for (i = 0; i < size; i++) {
79  ((ion_hash_bucket_t *) (hashmap->entry + ((hashmap->super.record.key_size + hashmap->super.record.value_size + SIZEOF(STATUS)) * i)))->status = ION_EMPTY;
80  }
81 
82  return 0;
83 }
int(* compute_hash)(ion_hashmap_t *, ion_key_t, int)
ion_record_info_t record
char * entry
#define ION_EMPTY
ion_dictionary_parent_t super
#define printf(format,...)
Struct used to maintain individual records in the hashmap.
ion_key_size_t key_size
Definition: kv_system.h:307
#define SIZEOF(STATUS)
ion_key_type_t key_type
ion_write_concern_t write_concern
ion_value_size_t value_size
Definition: kv_system.h:309

Here is the caller graph for this function:

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_mapThe map into which the data is going to be inserted.
keyThe key that is being used to locate the position of the data.
valueThe value that is being inserted.
Returns
The status of the insert.

Definition at line 130 of file open_address_hash.c.

134  {
135  ion_hash_t hash = hash_map->compute_hash(hash_map, key, hash_map->super.record.key_size); /* compute hash value for given key */
136 
137  int loc = oah_get_location(hash, hash_map->map_size);
138 
139  /* Scan until find an empty location - oah_insert if found */
140  int count = 0;
141 
142  ion_hash_bucket_t *item;
143 
144  while (count != hash_map->map_size) {
145  item = ((ion_hash_bucket_t *) ((hash_map->entry + (hash_map->super.record.key_size + hash_map->super.record.value_size + SIZEOF(STATUS)) * loc)));
146 
147  if (item->status == ION_IN_USE) {
148  /* if a cell is in use, need to key to */
149 
150  if (hash_map->super.compare(item->data, key, hash_map->super.record.key_size) == ION_IS_EQUAL) {
151  if (hash_map->write_concern == wc_insert_unique) {
152  /* allow unique entries only */
154  }
155  else if (hash_map->write_concern == wc_update) {
156  /* allows for values to be updated */
157  memcpy(item->data + hash_map->super.record.key_size, value, (hash_map->super.record.value_size));
158  return ION_STATUS_OK(1);
159  }
160  else {
161  return ION_STATUS_ERROR(err_file_write_error); /* there is a configuration issue with write concern */
162  }
163  }
164  }
165  else if ((item->status == ION_EMPTY) || (item->status == ION_DELETED)) {
166  /* problem is here with base types as it is just an array of data. Need better way */
167  item->status = ION_IN_USE;
168  memcpy(item->data, key, (hash_map->super.record.key_size));
169  memcpy(item->data + hash_map->super.record.key_size, value, (hash_map->super.record.value_size));
170  return ION_STATUS_OK(1);
171  }
172 
173  loc++;
174 
175  if (loc >= hash_map->map_size) {
176  /* Perform wrapping */
177  loc = 0;
178  }
179 
180 #if ION_DEBUG
181  printf("checking location %i\n", loc);
182 #endif
183  count++;
184  }
185 
186 #if ION_DEBUG
187  printf("Hash table full. Insert not done");
188 #endif
189 
191 }
int ion_hash_t
The position in the hashmap.
int(* compute_hash)(ion_hashmap_t *, ion_key_t, int)
#define ION_DELETED
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
char * entry
#define ION_EMPTY
ion_byte_t data[]
ion_dictionary_parent_t super
#define ION_STATUS_OK(count)
Definition: kv_system.h:113
#define key(k)
Definition: bpp_tree.c:75
#define printf(format,...)
int oah_get_location(ion_hash_t num, int size)
Returns the theoretical location of item in hashmap.
Struct used to maintain individual records in the hashmap.
#define ION_IN_USE
ion_key_size_t key_size
Definition: kv_system.h:307
#define SIZEOF(STATUS)
ion_dictionary_compare_t compare
ion_write_concern_t write_concern
ion_value_size_t value_size
Definition: kv_system.h:309
#define ION_IS_EQUAL
Definition: kv_system.h:64

Here is the call graph for this function:

Here is the caller graph for this function:

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_mapThe map into which the data is going to be inserted.
keyThe key that is being used to locate the position of the data.
valueThe value that is being inserted.
Returns
The status of the update

Definition at line 114 of file open_address_hash.c.

118  {
119  ion_write_concern_t current_write_concern = hash_map->write_concern;
120 
121  hash_map->write_concern = wc_update;/* change write concern to allow update */
122 
123  ion_status_t status = oah_insert(hash_map, key, value);
124 
125  hash_map->write_concern = current_write_concern;
126  return status;
127 }
#define key(k)
Definition: bpp_tree.c:75
ion_status_t oah_insert(ion_hashmap_t *hash_map, ion_key_t key, ion_value_t value)
Insert record into hashmap.
char ion_write_concern_t
A type for write concern information used by hash table based dictionaries which limit insert/update ...
ion_write_concern_t write_concern
A status object that describes the result of a dictionary operation.
Definition: kv_system.h:290

Here is the call graph for this function:

Here is the caller graph for this function: