open_address_file_hash.c File Reference

Description

Open Address Hash Map.

Author
Scott Ronald Fazackerley

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.

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.

Include dependency graph for open_address_file_hash.c:

Macros

#define ION_TEST_FILE   "file.bin"
 

Functions

ion_err_t oafh_close (ion_file_hashmap_t *hash_map)
 This function closes a hashmap dictionary. More...
 
ion_err_t oafh_initialize (ion_file_hashmap_t *hashmap, ion_hash_t(*hashing_function)(ion_file_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, ion_dictionary_id_t id)
 This function initializes an open address in memory hash map. More...
 
int oafh_get_location (ion_hash_t num, int size)
 Returns the theoretical location of item in hashmap. More...
 
ion_err_t oafh_destroy (ion_file_hashmap_t *hash_map)
 Destroys the map in memory. More...
 
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. More...
 
ion_status_t oafh_insert (ion_file_hashmap_t *hash_map, ion_key_t key, ion_value_t value)
 Insert record into hashmap. More...
 
ion_err_t oafh_find_item_loc (ion_file_hashmap_t *hash_map, ion_key_t key, int *location)
 Locates item in map. More...
 
ion_status_t oafh_delete (ion_file_hashmap_t *hash_map, ion_key_t key)
 Deletes item from map. More...
 
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. More...
 
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. More...
 

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

50  {
51  if (NULL != hash_map->file) {
52  /* check to ensure that you are not freeing something already free */
53  fclose(hash_map->file);
54  free(hash_map);
55  return err_ok;
56  }
57  else {
58  return err_file_close_error;
59  }
60 }

Here is the caller graph for this function:

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
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 414 of file open_address_file_hash.c.

418  {
419  UNUSED(size_of_key);
420 
421  /* convert to a hashable value */
422  ion_hash_t hash = (ion_hash_t) (((*(int *) key) % hashmap->map_size) + hashmap->map_size) % hashmap->map_size;
423 
424  return hash;
425 }
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 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_mapThe map into which the data is going to be inserted.
keyThe key for the record that is being searched for.

Definition at line 339 of file open_address_file_hash.c.

342  {
343  int loc;
344 
345  if (oafh_find_item_loc(hash_map, key, &loc) == err_item_not_found) {
346 #if ION_DEBUG
347  printf("Item not found when trying to oah_delete.\n");
348 #endif
350  }
351  else {
352  /* locate item */
353  ion_hash_bucket_t *item;
354 
355  int record_size = hash_map->super.record.key_size + hash_map->super.record.value_size + SIZEOF(STATUS);
356 
357  item = malloc(record_size);
358 
359  /* set file position */
360  fseek(hash_map->file, loc * record_size, SEEK_SET);
361 
362  fread(&item->status, SIZEOF(STATUS), 1, hash_map->file);
363  fread(item->data, record_size - SIZEOF(STATUS), 1, hash_map->file);
364 
365  item->status = ION_DELETED; /* delete item */
366 
367  /* backup */
368  fseek(hash_map->file, -record_size, SEEK_CUR);
369  fwrite(&item->status, SIZEOF(STATUS), 1, hash_map->file);
370  fwrite(item->data, record_size - SIZEOF(STATUS), 1, hash_map->file);
371 
372  free(item);
373 #if ION_DEBUG
374  printf("Item deleted at location %d\n", loc);
375 #endif
376  return ION_STATUS_OK(1);
377  }
378 }
#define ION_DELETED
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
ion_dictionary_parent_t super
ion_byte_t data[]
#define ION_STATUS_OK(count)
Definition: kv_system.h:113
#define key(k)
Definition: bpp_tree.c:75
#define printf(format,...)
ion_err_t oafh_find_item_loc(ion_file_hashmap_t *hash_map, ion_key_t key, int *location)
Locates item in map.
Struct used to maintain individual records in the hashmap.
ion_key_size_t key_size
Definition: kv_system.h:307
#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 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_mapThe 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.

143  {
144  hash_map->compute_hash = NULL;
145  hash_map->map_size = 0;
146  hash_map->super.record.key_size = 0;
147  hash_map->super.record.value_size = 0;
148 
149  char addr_filename[ION_MAX_FILENAME_LENGTH];
150 
151  int actual_filename_length = dictionary_get_filename(hash_map->super.id, "oaf", addr_filename);
152 
153  if (actual_filename_length >= ION_MAX_FILENAME_LENGTH) {
155  }
156 
157  if (hash_map->file != NULL) {
158  /* check to ensure that you are not freeing something already free */
159  fclose(hash_map->file);
160  fremove(addr_filename);
161  hash_map->file = NULL;
162  return err_ok;
163  }
164  else {
166  }
167 }
ion_record_info_t record
ion_dictionary_parent_t super
#define fremove(x)
Definition: kv_system.h:56
int dictionary_get_filename(ion_dictionary_id_t id, char *ext, char *filename)
Given the ID, implementation specific extension, and a buffer to write to, writes back the formatted ...
Definition: dictionary.c:41
int(* compute_hash)(ion_file_hashmap_t *, ion_key_t, int)
ion_dictionary_id_t id
#define ION_MAX_FILENAME_LENGTH
Since the arduino conforms to 8.3 syntax, that's 8 + 3 = 11 + 1 (null terminator) characters...
Definition: kv_system.h:73
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 call graph for this function:

Here is the caller graph for this function:

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_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 279 of file open_address_file_hash.c.

283  {
284  ion_hash_t hash = hash_map->compute_hash(hash_map, key, hash_map->super.record.key_size);
285  /* compute hash value for given key */
286 
287  int loc = oafh_get_location(hash, hash_map->map_size);
288  /* determine bucket based on hash */
289 
290  int count = 0;
291 
292  ion_hash_bucket_t *item;
293 
294  int record_size = hash_map->super.record.key_size + hash_map->super.record.value_size + SIZEOF(STATUS);
295 
296  item = malloc(record_size);
297 
298  /* set file position */
299  fseek(hash_map->file, loc * record_size, SEEK_SET);
300 
301  /* needs to traverse file again */
302  while (count != hash_map->map_size) {
303  fread(&item->status, SIZEOF(STATUS), 1, hash_map->file);
304  fread(item->data, record_size - SIZEOF(STATUS), 1, hash_map->file);
305 
306  if (item->status == ION_EMPTY) {
307  free(item);
308  return err_item_not_found; /* if you hit an empty cell, exit */
309  }
310  else {
311  /* calculate if there is a match */
312 
313  if (item->status != ION_DELETED) {
314  int key_is_equal = hash_map->super.compare(item->data, key, hash_map->super.record.key_size);
315 
316  if (ION_IS_EQUAL == key_is_equal) {
317  (*location) = loc;
318  free(item);
319  return err_ok;
320  }
321  }
322 
323  loc++;
324  count++;
325 
326  if (loc >= hash_map->map_size) {
327  /* Perform wrapping */
328  loc = 0;
329  frewind(hash_map->file);
330  }
331  }
332  }
333 
334  free(item);
335  return err_item_not_found; /* key have not been found */
336 }
int ion_hash_t
The position in the hashmap.
#define ION_DELETED
ion_record_info_t record
#define ION_EMPTY
ion_dictionary_parent_t super
#define frewind(x)
Definition: kv_system.h:57
ion_byte_t data[]
#define key(k)
Definition: bpp_tree.c:75
int(* compute_hash)(ion_file_hashmap_t *, ion_key_t, int)
Struct used to maintain individual records in the hashmap.
ion_key_size_t key_size
Definition: kv_system.h:307
#define SIZEOF(STATUS)
int oafh_get_location(ion_hash_t num, int size)
Returns the theoretical location of item in hashmap.
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 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_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 381 of file open_address_file_hash.c.

385  {
386  int loc;
387 
388  if (oafh_find_item_loc(hash_map, key, &loc) == err_ok) {
389 #if ION_DEBUG
390  printf("Item found at location %d\n", loc);
391 #endif
392 
393  int record_size = hash_map->super.record.key_size + hash_map->super.record.value_size + SIZEOF(STATUS);
394 
395  /* set file position */
396  fseek(hash_map->file, (loc * record_size) + SIZEOF(STATUS) + hash_map->super.record.key_size, SEEK_SET);
397 #if ION_DEBUG
398  printf("seeking %i\n", (loc * record_size) + SIZEOF(STATUS) + hash_map->super.record.key_size);
399 #endif
400  fread(value, hash_map->super.record.value_size, 1, hash_map->file);
401 
402  return ION_STATUS_OK(1);
403  }
404  else {
405 #if ION_DEBUG
406  printf("Item not found in hash table.\n");
407 #endif
408  value = NULL; /*et the number of bytes to 0 */
410  }
411 }
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
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,...)
ion_err_t oafh_find_item_loc(ion_file_hashmap_t *hash_map, ion_key_t key, int *location)
Locates item in map.
ion_key_size_t key_size
Definition: kv_system.h:307
#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 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
numThe key.
sizeThe 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.

136  {
137  return num % size;
138 }

Here is the caller graph for this function:

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
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)
idThe id of hashmap.
Returns
The status describing the result of the initialization.

Definition at line 63 of file open_address_file_hash.c.

71  {
72  hashmap->write_concern = wc_insert_unique; /* By default allow unique inserts only */
73  hashmap->super.record.key_size = key_size;
74  hashmap->super.record.value_size = value_size;
75  hashmap->super.key_type = key_type;
76 
77  /* The hash map is allocated as a single contiguous file*/
78  hashmap->map_size = size;
79 
80  hashmap->compute_hash = (*hashing_function); /* Allows for binding of different hash functions
81  depending on requirements */
82 
83  char addr_filename[ION_MAX_FILENAME_LENGTH];
84 
85  /* open the file */
86  int actual_filename_length = dictionary_get_filename(id, "oaf", addr_filename);
87 
88  if (actual_filename_length >= ION_MAX_FILENAME_LENGTH) {
89  return err_uninitialized;
90  }
91 
92  hashmap->file = fopen(addr_filename, "r+b");
93 
94  if (NULL != hashmap->file) {
95  return err_ok;
96  }
97 
98  /* open the file */
99  hashmap->file = fopen(addr_filename, "w+b");
100 
101  ion_hash_bucket_t *file_record;
102 
103  int record_size = SIZEOF(STATUS) + hashmap->super.record.key_size + hashmap->super.record.value_size;
104 
105  file_record = calloc(record_size, 1);
106  file_record->status = ION_EMPTY;
107 
108  /* write out the records to disk to prep */
109 #if ION_DEBUG
110  printf("Initializing hash table\n");
111 #endif
112 
113  int i, writes = 0;
114 
115  for (i = 0; i < hashmap->map_size; i++) {
116  writes += fwrite(&file_record->status, SIZEOF(STATUS), 1, hashmap->file);
117  writes += fwrite(file_record->data, record_size - SIZEOF(STATUS), 1, hashmap->file);
118  }
119 
120  fflush(hashmap->file);
121 
122  if (writes / 2 != hashmap->map_size) {
123  fclose(hashmap->file);
124  return err_file_write_error;
125  }
126 
127  free(file_record);
128 
129  return err_ok;
130 }
ion_record_info_t record
#define ION_EMPTY
ion_dictionary_parent_t super
ion_byte_t data[]
#define printf(format,...)
int dictionary_get_filename(ion_dictionary_id_t id, char *ext, char *filename)
Given the ID, implementation specific extension, and a buffer to write to, writes back the formatted ...
Definition: dictionary.c:41
int(* compute_hash)(ion_file_hashmap_t *, ion_key_t, int)
Struct used to maintain individual records in the hashmap.
#define ION_MAX_FILENAME_LENGTH
Since the arduino conforms to 8.3 syntax, that&#39;s 8 + 3 = 11 + 1 (null terminator) characters...
Definition: kv_system.h:73
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 call graph for this function:

Here is the caller graph for this function:

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_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 186 of file open_address_file_hash.c.

190  {
191  ion_hash_t hash = hash_map->compute_hash(hash_map, key, hash_map->super.record.key_size); /* compute hash value for given key */
192 
193  int loc = oafh_get_location(hash, hash_map->map_size);
194 
195  /* Scan until find an empty location - oah_insert if found */
196  int count = 0;
197 
198  ion_hash_bucket_t *item;
199 
200  int record_size = hash_map->super.record.key_size + hash_map->super.record.value_size + SIZEOF(STATUS);
201 
202  item = malloc(record_size);
203 
204  /* set file position */
205  fseek(hash_map->file, loc * record_size, SEEK_SET);
206 
207  while (count != hash_map->map_size) {
208  fread(item, record_size, 1, hash_map->file);
209 #if ION_DEBUG
210  DUMP((int) ftell(hash_map->file), "%i");
211 #endif
212 
213  if (item->status == ION_IN_USE) {
214  /* if a cell is in use, need to key to */
215 
216  if (hash_map->super.compare(item->data, key, hash_map->super.record.key_size) == ION_IS_EQUAL) {
217  if (hash_map->write_concern == wc_insert_unique) {
218  /* allow unique entries only */
219  free(item);
221  }
222  else if (hash_map->write_concern == wc_update) {
223  /* allows for values to be updated // */
224  /* backup and write */
225  fseek(hash_map->file, SIZEOF(STATUS) + hash_map->super.record.key_size - record_size, SEEK_CUR);
226 #if ION_DEBUG
227  DUMP((int) ftell(hash_map->file), "%i");
228  DUMP(value, "%s");
229 #endif
230  fwrite(value, hash_map->super.record.value_size, 1, hash_map->file);
231  free(item);
232  return ION_STATUS_OK(1);
233  }
234  else {
235  free(item);
236  return ION_STATUS_ERROR(err_file_write_error); /* there is a configuration issue with write concern */
237  }
238  }
239  }
240  else if ((item->status == ION_EMPTY) || (item->status == ION_DELETED)) {
241  /* problem is here with base types as it is just an array of data. Need better way */
242  /* printf("empty\n"); */
243  fseek(hash_map->file, -record_size, SEEK_CUR);
244 #if ION_DEBUG
245  DUMP((int) ftell(hash_map->file), "%i");
246 #endif
247  item->status = ION_IN_USE;
248  memcpy(item->data, key, (hash_map->super.record.key_size));
249  memcpy(item->data + hash_map->super.record.key_size, value, (hash_map->super.record.value_size));
250  fwrite(item, record_size, 1, hash_map->file);
251  free(item);
252 
253  return ION_STATUS_OK(1);
254  }
255 
256  loc++;
257 
258  if (loc >= hash_map->map_size) {
259  /* Perform wrapping */
260  loc = 0;
261  /* rewind the file */
262  frewind(hash_map->file);
263  }
264 
265 #if ION_DEBUG
266  printf("checking location %i\n", loc);
267 #endif
268  count++;
269  }
270 
271 #if ION_DEBUG
272  printf("Hash table full. Insert not done");
273 #endif
274  free(item);
276 }
int ion_hash_t
The position in the hashmap.
#define ION_DELETED
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
#define ION_EMPTY
ion_dictionary_parent_t super
#define frewind(x)
Definition: kv_system.h:57
ion_byte_t data[]
#define ION_STATUS_OK(count)
Definition: kv_system.h:113
#define key(k)
Definition: bpp_tree.c:75
#define printf(format,...)
int(* compute_hash)(ion_file_hashmap_t *, ion_key_t, int)
#define DUMP(varname, format)
Definition: kv_system.h:78
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)
int oafh_get_location(ion_hash_t num, int size)
Returns the theoretical location of item in hashmap.
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 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_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 170 of file open_address_file_hash.c.

174  {
175  ion_write_concern_t current_write_concern = hash_map->write_concern;
176 
177  hash_map->write_concern = wc_update;/* change write concern to allow update */
178 
179  ion_status_t result = oafh_insert(hash_map, key, value);
180 
181  hash_map->write_concern = current_write_concern;
182  return result;
183 }
#define key(k)
Definition: bpp_tree.c:75
ion_status_t oafh_insert(ion_file_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: