open_address_hash_dictionary_handler.c
Go to the documentation of this file.
1 /******************************************************************************/
35 /******************************************************************************/
36 
38 
66  ion_key_t key,
67  ion_value_t value
68 ) {
69  return oah_get((ion_hashmap_t *) dictionary->instance, key, value);
70 }
71 
87  ion_oadict_cursor_t *cursor /* don't need to pass in the cursor */
88 ) {
89  /* need to scan hashmap fully looking for values that satisfy - need to think about */
90  ion_hashmap_t *hash_map = (ion_hashmap_t *) (cursor->super.dictionary->instance);
91 
92  int loc = (cursor->current + 1) % hash_map->map_size;
93 
94  /* this is the current position of the cursor */
95  /* and start scanning 1 ahead */
96 
97  /* start at the current position, scan forward */
98  while (loc != cursor->first) {
99  /* check to see if current item is a match based on key */
100  /* locate first item */
101  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))));
102 
103  if ((item->status == ION_EMPTY) || (item->status == ION_DELETED)) {
104  /* if empty, just skip to next cell */
105  loc++;
106  }
107  else {
108  /* check to see if the current key value satisfies the predicate */
109 
110  ion_boolean_t key_satisfies_predicate = test_predicate(&(cursor->super), item->data); /* assumes that the key is first */
111 
112  if (key_satisfies_predicate == boolean_true) {
113  cursor->current = loc; /* this is the next index for value */
114  return cs_cursor_active;
115  }
116 
117  /* If valid bucket is not found, advance current position. */
118  loc++;
119  }
120 
121  if (loc >= hash_map->map_size) {
122  /* Perform wrapping */
123  loc = 0;
124  }
125  }
126 
127  /* if you end up here, you've wrapped the entire data structure and not found a value */
128  return cs_end_of_results;
129 }
130 
148 ion_err_t
152  ion_dict_cursor_t **cursor
153 ) {
154  /* allocate memory for cursor */
155  if ((*cursor = malloc(sizeof(ion_oadict_cursor_t))) == NULL) {
156  return err_out_of_memory;
157  }
158 
159  (*cursor)->dictionary = dictionary;
160  (*cursor)->status = cs_cursor_uninitialized;
161 
162  /* bind destroy method for cursor */
163  (*cursor)->destroy = oadict_destroy_cursor;
164 
165  /* bind correct next function */
166  (*cursor)->next = oadict_next; /* this will use the correct value */
167 
168  /* allocate predicate */
169  (*cursor)->predicate = malloc(sizeof(ion_predicate_t));
170  (*cursor)->predicate->type = predicate->type;
171  (*cursor)->predicate->destroy = predicate->destroy;
172 
173  /* based on the type of predicate that is being used, need to create the correct cursor */
174  switch (predicate->type) {
175  case predicate_equality: {
176  /* as this is an equality, need to malloc for key as well */
177  if (((*cursor)->predicate->statement.equality.equality_value = malloc((((ion_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
178  free((*cursor)->predicate);
179  free(*cursor); /* cleanup */
180  return err_out_of_memory;
181  }
182 
183  /* copy across the key value as the predicate may be destroyed */
184  memcpy((*cursor)->predicate->statement.equality.equality_value, predicate->statement.equality.equality_value, ((((ion_hashmap_t *) dictionary->instance)->super.record.key_size)));
185 
186  /* find the location of the first element as this is a straight equality */
187  int location = cs_invalid_index;
188 
189  if (oah_find_item_loc((ion_hashmap_t *) dictionary->instance, (*cursor)->predicate->statement.equality.equality_value, &location) == err_item_not_found) {
190  (*cursor)->status = cs_end_of_results;
191  return err_ok;
192  }
193  else {
194  (*cursor)->status = cs_cursor_initialized;
195 
196  /* cast to specific instance type for conveniences of setup */
198 
199  /* the cursor is ready to be consumed */
200  oadict_cursor->first = location;
201 
202  oadict_cursor->current = location;
203  return err_ok;
204  }
205 
206  break;
207  }
208 
209  case predicate_range: {
210  if (((*cursor)->predicate->statement.range.lower_bound = malloc((((ion_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
211  free((*cursor)->predicate);
212  free(*cursor); /* cleanup */
213  return err_out_of_memory;
214  }
215 
216  /* copy across the key value as the predicate may be destroyed */
217  memcpy((*cursor)->predicate->statement.range.lower_bound, predicate->statement.range.lower_bound, (((ion_hashmap_t *) dictionary->instance)->super.record.key_size));
218 
219  /* as this is a range, need to malloc upper bound key */
220  if (((*cursor)->predicate->statement.range.upper_bound = malloc((((ion_hashmap_t *) dictionary->instance)->super.record.key_size))) == NULL) {
221  free((*cursor)->predicate->statement.range.lower_bound);
222  free((*cursor)->predicate);
223  free(*cursor); /* cleanup */
224  return err_out_of_memory;
225  }
226 
227  /* copy across the key value as the predicate may be destroyed */
228  memcpy((*cursor)->predicate->statement.range.upper_bound, predicate->statement.range.upper_bound, (((ion_hashmap_t *) dictionary->instance)->super.record.key_size));
229 
231  ion_hashmap_t *hash_map = ((ion_hashmap_t *) dictionary->instance);
232 
233  (*cursor)->status = cs_cursor_initialized;
234  oadict_cursor->first = (hash_map->map_size) - 1;
235  oadict_cursor->current = -1;
236 
237  ion_err_t err = oadict_scan(oadict_cursor);
238 
239  if (cs_end_of_results == err) {
240  (*cursor)->status = cs_cursor_uninitialized;
241  }
242 
243  return err_ok;
244  break;
245  }
246 
247  case predicate_all_records: {
249  ion_hashmap_t *hash_map = ((ion_hashmap_t *) dictionary->instance);
250 
251  (*cursor)->status = cs_cursor_initialized;
252  oadict_cursor->first = (hash_map->map_size) - 1;
253  oadict_cursor->current = -1;
254 
255  ion_err_t err = oadict_scan(oadict_cursor);
256 
257  if (cs_end_of_results == err) {
258  (*cursor)->status = cs_cursor_uninitialized;
259  }
260 
261  return err_ok;
262  break;
263  }
264 
265  case predicate_predicate: {
266  break;
267  }
268 
269  default: {
270  return err_invalid_predicate; /* * Invalid predicate supplied */
271  break;
272  }
273  }
274 
275  return err_ok;
276 }
277 
293 ion_err_t
295  ion_dictionary_handler_t *handler,
299 ) {
300  UNUSED(handler);
301  UNUSED(dictionary);
302  UNUSED(config);
303  UNUSED(compare);
304  return err_not_implemented;
305 }
306 
315 ion_err_t
318 ) {
319  UNUSED(dictionary);
320  return err_not_implemented;
321 }
322 
323 void
325  ion_dictionary_handler_t *handler
326 ) {
327  handler->insert = oadict_insert;
329  handler->get = oadict_get;
330  handler->update = oadict_update;
331  handler->find = oadict_find;
332  handler->remove = oadict_delete;
337 }
338 
342  ion_key_t key,
343  ion_value_t value
344 ) {
345  return oah_insert((ion_hashmap_t *) dictionary->instance, key, value);
346 }
347 
348 ion_err_t
351  ion_key_type_t key_type,
352  ion_key_size_t key_size,
353  ion_value_size_t value_size,
354  ion_dictionary_size_t dictionary_size,
355  ion_dictionary_compare_t compare,
356  ion_dictionary_handler_t *handler,
358 ) {
359  UNUSED(id);
360  /* this is the instance of the hashmap */
361  dictionary->instance = malloc(sizeof(ion_hashmap_t));
362 
363  dictionary->instance->compare = compare;
365 
366  /* this registers the dictionary the dictionary */
367  oah_initialize((ion_hashmap_t *) dictionary->instance, oah_compute_simple_hash, key_type, key_size, value_size, dictionary_size); /* just pick an arbitary size for testing atm */
368 
369  /*TODO The correct comparison operator needs to be bound at run time
370  * based on the type of key defined
371  */
372 
373  if (NULL == handler) {
374  return err_uninitialized;
375  }
376 
377  /* register the correct handler */
378  dictionary->handler = handler;
379 
380  return 0;
381 }
382 
386  ion_key_t key
387 ) {
388  return oah_delete((ion_hashmap_t *) dictionary->instance, key);
389 }
390 
391 ion_err_t
394 ) {
395  ion_err_t result = oah_destroy((ion_hashmap_t *) dictionary->instance);
396 
397  free(dictionary->instance);
398  dictionary->instance = NULL;/* When releasing memory, set pointer to NULL */
399  return result;
400 }
401 
402 ion_err_t
405 ) {
406  UNUSED(id);
407  return err_not_implemented;
408 }
409 
413  ion_key_t key,
414  ion_value_t value
415 ) {
416  return oah_update((ion_hashmap_t *) dictionary->instance, key, value);
417 }
418 
421  ion_dict_cursor_t *cursor,
422  ion_record_t *record
423 ) {
425 
426  /* check the status of the cursor and if it is not valid or at the end, just exit */
427  if (cursor->status == cs_cursor_uninitialized) {
428  return cursor->status;
429  }
430  else if (cursor->status == cs_end_of_results) {
431  return cursor->status;
432  }
433  else if ((cursor->status == cs_cursor_initialized) || (cursor->status == cs_cursor_active)) {
434  /* cursor is active and results have never been accessed */
435  /* extract reference to map */
436  ion_hashmap_t *hash_map = ((ion_hashmap_t *) cursor->dictionary->instance);
437 
438  /* assume that the value has been pre-allocated */
439  /* compute length of data record stored in map */
440  int data_length = hash_map->super.record.key_size + hash_map->super.record.value_size;
441 
442  if (cursor->status == cs_cursor_active) {
443  /* find the next valid entry */
444 
445  /* scan and determine what to do? */
446  if (cs_end_of_results == oadict_scan(oadict_cursor)) {
447  /* Then this is the end and there are no more results */
448  cursor->status = cs_end_of_results;
449  return cursor->status;
450  }
451  }
452  else {
453  /* if the cursor is initialized but not active, then just read the data and set cursor active */
454  cursor->status = cs_cursor_active;
455  }
456 
457  /* the results are now ready //reference item at given position */
458  ion_hash_bucket_t *item = (((ion_hash_bucket_t *) ((hash_map->entry + (data_length + SIZEOF(STATUS)) * oadict_cursor->current /*idx*/))));
459 
460  memcpy(record->key, (item->data), hash_map->super.record.key_size);
461 
462  memcpy(record->value, (item->data + hash_map->super.record.key_size), hash_map->super.record.value_size);
463 
464  /* and update current cursor position */
465  return cursor->status;
466  }
467 
468  /* and if you get this far, the cursor is invalid */
469  return cs_invalid_cursor;
470 }
471 
474  ion_dictionary_t *dict,
475  ion_key_t key1,
476  ion_key_t key2
477 ) {
478  if (memcmp(key1, key2, (((ion_hashmap_t *) dict->instance)->super.record.key_size)) == ION_IS_EQUAL) {
479  return boolean_true;
480  }
481  else {
482  return boolean_false;
483  }
484 }
485 
486 void
488  ion_dict_cursor_t **cursor
489 ) {
490  (*cursor)->predicate->destroy(&(*cursor)->predicate);
491  free(*cursor);
492  *cursor = NULL;
493 }
#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_err_t oadict_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 hash instance of a dictionary.
ion_cursor_status_t oadict_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...
char * entry
Struct used to maintain an instance of an in memory hashmap.
void oadict_destroy_cursor(ion_dict_cursor_t **cursor)
Destroys the cursor.
#define ION_EMPTY
int ion_value_size_t
The size (length) of a dictionary value in bytes.
Definition: kv_system.h:256
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.
ion_status_t oadict_update(ion_dictionary_t *dictionary, ion_key_t key, ion_value_t value)
Updates the value for a given key.
ion_predicate_statement_t statement
ion_dictionary_handler_t * handler
ion_dictionary_parent_t * instance
ion_err_t oah_destroy(ion_hashmap_t *hash_map)
Destroys the map in memory.
ion_err_t oadict_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_status_t oah_get(ion_hashmap_t *hash_map, ion_key_t key, ion_value_t value)
Locates the record if it exists.
ion_value_t value
Definition: kv_system.h:318
ion_status_t(* remove)(ion_dictionary_t *, ion_key_t)
ion_status_t oadict_delete(ion_dictionary_t *dictionary, ion_key_t key)
Deletes the key and assoicated value from the dictionary instance.
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
Struct containing details for opening a dictionary previously created.
void oadict_init(ion_dictionary_handler_t *handler)
Registers a specific handler for a dictionary instance.
ion_byte_t data[]
ion_dictionary_parent_t super
ion_cursor_status_t status
#define key(k)
Definition: bpp_tree.c:75
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
ion_status_t oah_delete(ion_hashmap_t *hash_map, ion_key_t key)
Deletes item from 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
ion_hash_t oah_compute_simple_hash(ion_hashmap_t *hashmap, ion_key_t key, int size_of_key)
A simple hashing algorithm implementation.
ion_err_t oadict_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 oah_update(ion_hashmap_t *hash_map, ion_key_t key, ion_value_t value)
Updates a value in the map.
void * ion_key_t
A dictionary key.
Definition: kv_system.h:241
The handler for a hash table using linear probing.
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_boolean_t oadict_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_predicate_type_t type
A supertype for dictionary cursor objects.
ion_err_t oadict_delete_dictionary(ion_dictionary_t *dictionary)
Deletes an instance of the dictionary and associated data.
ion_err_t(* close_dictionary)(ion_dictionary_t *)
ion_err_t(* open_dictionary)(ion_dictionary_handler_t *, ion_dictionary_t *, ion_dictionary_config_info_t *, ion_dictionary_compare_t)
ion_err_t oadict_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_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(* delete_dictionary)(ion_dictionary_t *)
ion_key_size_t key_size
Definition: kv_system.h:307
A supertype for cursor predicate objects.
ion_status_t oadict_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_dictionary_type_t type
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 oah_find_item_loc(ion_hashmap_t *hash_map, ion_key_t key, int *location)
Locates item in map.
ion_err_t oadict_close_dictionary(ion_dictionary_t *dictionary)
Closes an open address hash instance of a dictionary.
#define SIZEOF(STATUS)
ion_err_t oadict_scan(ion_oadict_cursor_t *cursor)
Starts scanning map looking for conditions that match predicate and returns result.
ion_status_t oah_insert(ion_hashmap_t *hash_map, ion_key_t key, ion_value_t value)
Insert record into hashmap.
ion_dictionary_compare_t compare
int ion_key_size_t
The size (length) of a dictionary key in bytes.
Definition: kv_system.h:251
ion_status_t oadict_insert(ion_dictionary_t *dictionary, ion_key_t key, ion_value_t value)
Inserts a key and value into the dictionary.
char ion_boolean_t
A boolean type.
Definition: kv_system.h:269
ion_range_statement_t range
ion_dictionary_status_t status
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