open_address_file_hash_dictionary_handler.c
Go to the documentation of this file.
1 /******************************************************************************/
35 /******************************************************************************/
36 
38 #include "../../key_value/kv_system.h"
39 #include "open_address_file_hash.h"
40 #include "../../file/ion_file.h"
41 
69  ion_key_t key,
70  ion_value_t value
71 ) {
72  return oafh_get((ion_file_hashmap_t *) dictionary->instance, key, value);
73 }
74 
89  ion_oafdict_cursor_t *cursor/* don't need to pass in the cursor */
90 ) {
91  /* need to scan hashmap fully looking for values that satisfy - need to think about */
93 
94  int loc = (cursor->current + 1) % hash_map->map_size;
95  /* this is the current position of the cursor */
96  /* and start scanning 1 ahead */
97 
98  int record_size = SIZEOF(STATUS) + hash_map->super.record.key_size + hash_map->super.record.value_size;
99 
100  /* move to the correct position in the fie */
101  fseek(hash_map->file, loc * record_size, SEEK_SET);
102 
103  ion_hash_bucket_t *item;
104 
105  item = malloc(record_size);
106 
107  /* start at the current position, scan forward */
108  while (loc != cursor->first) {
109  fread(item, record_size, 1, hash_map->file);
110 
111  if ((item->status == ION_EMPTY) || (item->status == ION_DELETED)) {
112  /* if empty, just skip to next cell */
113  loc++;
114  }
115  else {
116  /* check to see if the current key value satisfies the predicate */
117 
118  ion_boolean_t key_satisfies_predicate = test_predicate(&(cursor->super), item->data); /* assumes that the key is first */
119 
120  if (key_satisfies_predicate == boolean_true) {
121  cursor->current = loc; /* this is the next index for value */
122  free(item);
123  return cs_cursor_active;
124  }
125 
126  /* If valid bucket is not found, advance current position. */
127  loc++;
128  }
129 
130  if (loc >= hash_map->map_size) {
131  /* Perform wrapping */
132  loc = 0;
133  }
134  }
135 
136  /* if you end up here, you've wrapped the entire data structure and not found a value */
137  free(item);
138  return cs_end_of_results;
139 }
140 
152  ion_dict_cursor_t *cursor,
153  ion_record_t *record
154 ) {
156 
157  /* check the status of the cursor and if it is not valid or at the end, just exit */
158  if (cursor->status == cs_cursor_uninitialized) {
159  return cursor->status;
160  }
161  else if (cursor->status == cs_end_of_results) {
162  return cursor->status;
163  }
164  else if ((cursor->status == cs_cursor_initialized) || (cursor->status == cs_cursor_active)) {
165  /* cursor is active and results have never been accessed */
166  /* extract reference to map */
167  ion_file_hashmap_t *hash_map = ((ion_file_hashmap_t *) cursor->dictionary->instance);
168 
169  /* assume that the value has been pre-allocated */
170  /* compute length of data record stored in map */
171  int data_length = hash_map->super.record.key_size + hash_map->super.record.value_size;
172 
173  if (cursor->status == cs_cursor_active) {
174  /* find the next valid entry */
175 
176  /* scan and determine what to do? */
177  if (cs_end_of_results == oafdict_scan(oafdict_cursor)) {
178  /* Then this is the end and there are no more results */
179  cursor->status = cs_end_of_results;
180  return cursor->status;
181  }
182  }
183  else {
184  /* if the cursor is initialized but not active, then just read the data and set cursor active */
185  cursor->status = cs_cursor_active;
186  }
187 
188  /* the results are now ready //reference item at given position */
189 
190  /* set position in file to read value */
191  fseek(hash_map->file, (SIZEOF(STATUS) + data_length) * oafdict_cursor->current /* position is based on indexes (not abs file pos) */
192  + SIZEOF(STATUS), SEEK_SET);
193 
194  fread(record->key, hash_map->super.record.key_size, 1, hash_map->file);
195  fread(record->value, hash_map->super.record.value_size, 1, hash_map->file);
196 
197  /* and update current cursor position */
198  return cursor->status;
199  }
200 
201  /* and if you get this far, the cursor is invalid */
202  return cs_invalid_cursor;
203 }
204 
222 ion_err_t
226  ion_dict_cursor_t **cursor
227 ) {
228  /* allocate memory for cursor */
229  if ((*cursor = malloc(sizeof(ion_oafdict_cursor_t))) == NULL) {
230  return err_out_of_memory;
231  }
232 
233  (*cursor)->dictionary = dictionary;
234  (*cursor)->status = cs_cursor_uninitialized;
235 
236  /* bind destroy method for cursor */
237  (*cursor)->destroy = oafdict_destroy_cursor;
238 
239  /* bind correct next function */
240  (*cursor)->next = oafdict_next; /* this will use the correct value */
241 
242  /* allocate predicate */
243  (*cursor)->predicate = malloc(sizeof(ion_predicate_t));
244  (*cursor)->predicate->type = predicate->type;
245  (*cursor)->predicate->destroy = predicate->destroy;
246 
247  /* based on the type of predicate that is being used, need to create the correct cursor */
248  switch (predicate->type) {
249  case predicate_equality: {
250  /* as this is an equality, need to malloc for key as well */
251  if (((*cursor)->predicate->statement.equality.equality_value = malloc((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
252  free((*cursor)->predicate);
253  free(*cursor); /* cleanup */
254  return err_out_of_memory;
255  }
256 
257  /* copy across the key value as the predicate may be destroyed */
258  memcpy((*cursor)->predicate->statement.equality.equality_value, predicate->statement.equality.equality_value, ((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size)));
259 
260  /* find the location of the first element as this is a straight equality */
261  int location = cs_invalid_index;
262 
263  if (oafh_find_item_loc((ion_file_hashmap_t *) dictionary->instance, (*cursor)->predicate->statement.equality.equality_value, &location) == err_item_not_found) {
264  (*cursor)->status = cs_end_of_results;
265  return err_ok;
266  }
267  else {
268  (*cursor)->status = cs_cursor_initialized;
269 
270  /* cast to specific instance type for conveniences of setup */
272 
273  /* the cursor is ready to be consumed */
274  oadict_cursor->first = location;
275 
276  oadict_cursor->current = location;
277  return err_ok;
278  }
279 
280  break;
281  }
282 
283  case predicate_range: {
284  /* as this is a range, need to malloc lower bound key */
285  if (((*cursor)->predicate->statement.range.lower_bound = malloc((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
286  free((*cursor)->predicate);
287  free(*cursor); /* cleanup */
288  return err_out_of_memory;
289  }
290 
291  /* copy across the key value as the predicate may be destroyed */
292  memcpy((*cursor)->predicate->statement.range.lower_bound, predicate->statement.range.lower_bound, (((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size));
293 
294  /* as this is a range, need to malloc upper bound key */
295  if (((*cursor)->predicate->statement.range.upper_bound = malloc((((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
296  free((*cursor)->predicate->statement.range.lower_bound);
297  free((*cursor)->predicate);
298  free(*cursor); /* cleanup */
299  return err_out_of_memory;
300  }
301 
302  /* copy across the key value as the predicate may be destroyed */
303  memcpy((*cursor)->predicate->statement.range.upper_bound, predicate->statement.range.upper_bound, (((ion_file_hashmap_t *) dictionary->instance)->super.record.key_size));
304  }
305 
306  /* Range query will intentionally continue to all record code to get rid of duplicate statements. */
307  case predicate_all_records: {
309  ion_file_hashmap_t *hash_map = ((ion_file_hashmap_t *) dictionary->instance);
310 
311  (*cursor)->status = cs_cursor_initialized;
312  oafdict_cursor->first = (hash_map->map_size) - 1;
313  oafdict_cursor->current = -1;
314 
315  ion_err_t err = oafdict_scan(oafdict_cursor);
316 
317  if (cs_end_of_results == err) {
318  (*cursor)->status = cs_end_of_results;
319  }
320 
321  return err_ok;
322  break;
323  }
324 
325  case predicate_predicate: {
326  break;
327  }
328 
329  default: {
330  return err_invalid_predicate; /* * Invalid predicate supplied */
331  break;
332  }
333  }
334 
335  return err_ok;
336 }
337 
353 ion_err_t
355  ion_dictionary_handler_t *handler,
359 ) {
360  return oafdict_create_dictionary(config->id, config->type, config->key_size, config->value_size, config->dictionary_size, compare, handler, dictionary);
361 }
362 
371 ion_err_t
374 ) {
375  ion_file_hashmap_t *hash_map;
376  ion_err_t err;
377 
378  hash_map = (ion_file_hashmap_t *) dictionary->instance;
379  err = oafh_close(hash_map);
380 
381  /* The following line creates an allocation error. Will not including it create a memory leak? */
382 /* free(dictionary->instance); */
383 
384  dictionary->instance = NULL;
385 
386  if (err_ok != err) {
388  }
389 
390  return err_ok;
391 }
392 
393 void
395  ion_dictionary_handler_t *handler
396 ) {
397  handler->insert = oafdict_insert;
399  handler->get = oafdict_get;
400  handler->update = oafdict_update;
401  handler->find = oafdict_find;
402  handler->remove = oafdict_delete;
407 }
408 
412  ion_key_t key,
413  ion_value_t value
414 ) {
415  return oafh_insert((ion_file_hashmap_t *) dictionary->instance, key, value);
416 }
417 
418 ion_err_t
421  ion_key_type_t key_type,
422  ion_key_size_t key_size,
423  ion_value_size_t value_size,
424  ion_dictionary_size_t dictionary_size,
425  ion_dictionary_compare_t compare,
426  ion_dictionary_handler_t *handler,
428 ) {
429  UNUSED(id);
430  /* this is the instance of the hashmap */
431  dictionary->instance = malloc(sizeof(ion_file_hashmap_t));
432 
433  dictionary->instance->compare = compare;
435 
436  /* this registers the dictionary the dictionary */
437  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 */
438 
439  /*TODO The correct comparison operator needs to be bound at run time
440  * based on the type of key defined
441  */
442 
443  if (NULL == handler) {
444  return err_uninitialized;
445  }
446 
447  /* register the correct handler */
448  dictionary->handler = handler;
449 
450  return 0;
451 }
452 
456  ion_key_t key
457 ) {
458  return oafh_delete((ion_file_hashmap_t *) dictionary->instance, key);
459 }
460 
461 ion_err_t
464 ) {
465  ion_err_t result = oafh_destroy((ion_file_hashmap_t *) dictionary->instance);
466 
467  free(dictionary->instance);
468  dictionary->instance = NULL;/* When releasing memory, set pointer to NULL */
469  return result;
470 }
471 
472 ion_err_t
475 ) {
476  char addr_filename[ION_MAX_FILENAME_LENGTH];
477 
478  int actual_filename_length = dictionary_get_filename(id, "oaf", addr_filename);
479 
480  if (actual_filename_length >= ION_MAX_FILENAME_LENGTH) {
482  }
483 
484  fremove(addr_filename);
485 
486  return err_ok;
487 }
488 
492  ion_key_t key,
493  ion_value_t value
494 ) {
495  return oafh_update((ion_file_hashmap_t *) dictionary->instance, key, value);
496 }
497 
512  ion_dictionary_t *dict,
513  ion_key_t key1,
514  ion_key_t key2
515 ) {
516  if (memcmp(key1, key2, (((ion_file_hashmap_t *) dict->instance)->super.record.key_size)) == ION_IS_EQUAL) {
517  return boolean_true;
518  }
519  else {
520  return boolean_false;
521  }
522 }
523 
524 void
526  ion_dict_cursor_t **cursor
527 ) {
528  (*cursor)->predicate->destroy(&(*cursor)->predicate);
529  free(*cursor);
530  *cursor = NULL;
531 }
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.
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.
ion_status_t oafdict_update(ion_dictionary_t *dictionary, ion_key_t key, ion_value_t value)
Updates the value for a given key.
#define ION_DELETED
ion_status_t(* insert)(ion_dictionary_t *, ion_key_t, ion_value_t)
enum ION_KEY_TYPE ion_key_type_t
This is the available key types for ION_DB. All types will be based on system defines.
ion_record_info_t record
ion_status_t oafh_delete(ion_file_hashmap_t *hash_map, ion_key_t key)
Deletes item from map.
#define ION_EMPTY
int ion_value_size_t
The size (length) of a dictionary value in bytes.
Definition: kv_system.h:256
ion_dictionary_parent_t super
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.
ion_predicate_statement_t statement
ion_dictionary_handler_t * handler
ion_dictionary_parent_t * instance
The handler for a hash table using linear probing.
ion_value_t value
Definition: kv_system.h:318
ion_status_t(* remove)(ion_dictionary_t *, ion_key_t)
ion_dictionary_t * dictionary
ion_err_t(* destroy_dictionary)(ion_dictionary_id_t id)
Struct used to maintain key and value.
Definition: kv_system.h:315
unsigned int ion_dictionary_id_t
A type used to identify dictionaries, specifically in the master table.
unsigned int ion_dictionary_size_t
The implementation specific size of the dictionary.
Definition: kv_system.h:264
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.
Struct containing details for opening a dictionary previously created.
ion_byte_t data[]
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 ...
ion_cursor_status_t status
#define key(k)
Definition: bpp_tree.c:75
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)...
ion_boolean_t test_predicate(ion_dict_cursor_t *cursor, ion_key_t key)
Tests the supplied key against the predicate registered in the cursor. If the supplied cursor if of t...
Definition: dictionary.c:571
#define fremove(x)
Definition: kv_system.h:56
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.
ion_key_t key
Definition: kv_system.h:316
char(* ion_dictionary_compare_t)(ion_key_t, ion_key_t, ion_key_size_t)
Function pointer type for dictionary comparison methods.
char ion_err_t
The error type used to store error codes.
Definition: kv_system.h:226
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
ion_err_t oafh_find_item_loc(ion_file_hashmap_t *hash_map, ion_key_t key, int *location)
Locates item in map.
void * ion_key_t
A dictionary key.
Definition: kv_system.h:241
void(* destroy)(ion_predicate_t **)
ion_status_t(* update)(ion_dictionary_t *, ion_key_t, ion_value_t)
ion_equality_statement_t equality
void * ion_value_t
A dictionary value.
Definition: kv_system.h:246
Struct used to maintain individual records in the hashmap.
A dictionary contains information regarding an instance of the storage element and the associated han...
ion_predicate_type_t type
A supertype for dictionary cursor objects.
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.
ion_err_t(* close_dictionary)(ion_dictionary_t *)
#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_err_t(* open_dictionary)(ion_dictionary_handler_t *, ion_dictionary_t *, ion_dictionary_config_info_t *, ion_dictionary_compare_t)
ion_err_t oafh_close(ion_file_hashmap_t *hash_map)
This function closes a hashmap dictionary.
ion_err_t(* create_dictionary)(ion_dictionary_id_t, ion_key_type_t, ion_key_size_t, ion_value_size_t, ion_dictionary_size_t, ion_dictionary_compare_t, ion_dictionary_handler_t *, ion_dictionary_t *)
ion_err_t oafdict_close_dictionary(ion_dictionary_t *dictionary)
Closes an open address file hash instance of a dictionary.
ion_err_t(* delete_dictionary)(ion_dictionary_t *)
void oafdict_init(ion_dictionary_handler_t *handler)
Registers a specific handler for a dictionary instance.
ion_key_size_t key_size
Definition: kv_system.h:307
A supertype for cursor predicate objects.
A hash table using linear probing. Designed for in memory use.
ion_dictionary_type_t type
ion_err_t oafdict_delete_dictionary(ion_dictionary_t *dictionary)
Deletes an instance of the dictionary and associated data.
ion_err_t(* find)(ion_dictionary_t *, ion_predicate_t *, ion_dict_cursor_t **)
#define UNUSED(x)
Definition: kv_system.h:102
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.
ion_status_t oafh_insert(ion_file_hashmap_t *hash_map, ion_key_t key, ion_value_t value)
Insert record into hashmap.
#define SIZEOF(STATUS)
ion_err_t oafdict_scan(ion_oafdict_cursor_t *cursor)
Starts scanning map looking for conditions that match predicate and returns result.
ion_dictionary_compare_t compare
ion_dictionary_size_t dictionary_size
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...
int ion_key_size_t
The size (length) of a dictionary key in bytes.
Definition: kv_system.h:251
char ion_boolean_t
A boolean type.
Definition: kv_system.h:269
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...
ion_status_t oafdict_delete(ion_dictionary_t *dictionary, ion_key_t key)
Deletes the key and assoicated value from the dictionary instance.
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. ...
ion_range_statement_t range
Struct used to maintain an instance of an in memory hashmap.
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.
ion_dictionary_status_t status
ion_err_t oafh_destroy(ion_file_hashmap_t *hash_map)
Destroys the map in memory.
ion_value_size_t value_size
Definition: kv_system.h:309
#define ION_IS_EQUAL
Definition: kv_system.h:64
ion_status_t(* get)(ion_dictionary_t *, ion_key_t, ion_value_t)
A dictionary_handler is responsible for dealing with the specific interface for an underlying diction...
char ion_cursor_status_t
A type for the status of a cursor.
A status object that describes the result of a dictionary operation.
Definition: kv_system.h:290