linear_hash.c
Go to the documentation of this file.
171 if (1 != fwrite(&linear_hash->initial_size, sizeof(linear_hash->initial_size), 1, linear_hash->state)) {
175 if (1 != fwrite(&linear_hash->next_split, sizeof(linear_hash->next_split), 1, linear_hash->state)) {
179 if (1 != fwrite(&linear_hash->split_threshold, sizeof(linear_hash->split_threshold), 1, linear_hash->state)) {
183 if (1 != fwrite(&linear_hash->num_buckets, sizeof(linear_hash->num_buckets), 1, linear_hash->state)) {
187 if (1 != fwrite(&linear_hash->num_records, sizeof(linear_hash->num_records), 1, linear_hash->state)) {
191 if (1 != fwrite(&linear_hash->records_per_bucket, sizeof(linear_hash->records_per_bucket), 1, linear_hash->state)) {
199 ion_byte_t *cached_bucket_map = alloca(sizeof(ion_fpos_t) * linear_hash->bucket_map->current_size);
202 memcpy(cached_bucket_map, linear_hash->bucket_map->data, linear_hash->num_buckets * sizeof(ion_fpos_t));
204 if (1 != fwrite(cached_bucket_map, sizeof(linear_hash->bucket_map->data), 1, linear_hash->state)) {
226 if (1 != fread(&(linear_hash->initial_size), sizeof(linear_hash->initial_size), 1, linear_hash->state)) {
230 if (1 != fread(&linear_hash->next_split, sizeof(linear_hash->next_split), 1, linear_hash->state)) {
234 if (1 != fread(&linear_hash->split_threshold, sizeof(linear_hash->split_threshold), 1, linear_hash->state)) {
238 if (1 != fread(&linear_hash->num_buckets, sizeof(linear_hash->num_buckets), 1, linear_hash->state)) {
242 if (1 != fread(&linear_hash->num_records, sizeof(linear_hash->num_records), 1, linear_hash->state)) {
246 if (1 != fread(&linear_hash->records_per_bucket, sizeof(linear_hash->records_per_bucket), 1, linear_hash->state)) {
254 if (1 != fwrite(&linear_hash->bucket_map->data, sizeof(ion_fpos_t) * linear_hash->num_buckets, 1, linear_hash->state)) {
401 fread(records, linear_hash->record_total_size, linear_hash->records_per_bucket, linear_hash->database);
406 memcpy(record_key, records + record_offset + sizeof(record_status), linear_hash->super.record.key_size);
407 memcpy(record_value, records + record_offset + sizeof(record_status) + linear_hash->super.record.key_size, linear_hash->super.record.value_size);
428 memcpy(record_value, linear_hash->cache + linear_hash->last_cache_idx * linear_hash->super.record.value_size, linear_hash->super.record.value_size);
431 status = linear_hash_insert(record_key, record_value, hash_to_bucket(record_key, linear_hash), linear_hash);
440 fread(records, linear_hash->record_total_size, linear_hash->records_per_bucket, linear_hash->database);
521 ion_fpos_t swap_record_loc = bucket_loc + sizeof(linear_hash_bucket_t) + ((bucket.record_count - 1) * linear_hash->record_total_size);
542 /* garuntee the bucket in the bucket map has records in it - THIS LEAVES EMPTY BUCKETS FLOATING ABOUT */
614 /* Get location of overflow bucket and update the tail record for the linked list of buckets storing
635 record_loc = bucket_loc + sizeof(linear_hash_bucket_t) + bucket.record_count * linear_hash->record_total_size;
640 status.error = linear_hash_write_record(record_loc, record_key, record_value, &record_status, linear_hash);
716 fread(records, linear_hash->record_total_size, linear_hash->records_per_bucket, linear_hash->database);
720 memcpy(record_key, records + record_offset + sizeof(record_status), linear_hash->super.record.key_size);
721 memcpy(record_value, records + record_offset + sizeof(record_status) + linear_hash->super.record.key_size, linear_hash->super.record.value_size);
811 status.error = linear_hash_get_record(record_loc, record_key, record_value, &record_status, linear_hash);
819 status.error = linear_hash_write_record(record_loc, record_key, value, &record_status, linear_hash);
916 fread(records, linear_hash->record_total_size, linear_hash->records_per_bucket, linear_hash->database);
921 memcpy(record_key, records + record_offset + sizeof(record_status), linear_hash->super.record.key_size);
922 memcpy(record_value, records + record_offset + sizeof(record_status) + linear_hash->super.record.key_size, linear_hash->super.record.value_size);
928 memcpy(linear_hash->cache + linear_hash->last_cache_idx * linear_hash->super.record.value_size, record_value, linear_hash->super.record.value_size);
935 linear_hash_get_bucket_swap_record(bucket_idx, &swap_record_loc, terminal_record_key, terminal_record_value, &terminal_record_status, linear_hash);
938 while (linear_hash->super.compare(terminal_record_key, key, linear_hash->super.record.key_size) == 0) {
939 memcpy(linear_hash->cache + linear_hash->last_cache_idx * linear_hash->super.record.value_size, terminal_record_value, linear_hash->super.record.value_size);
948 linear_hash_get_bucket_swap_record(bucket_idx, &swap_record_loc, terminal_record_key, terminal_record_value, &terminal_record_status, linear_hash);
960 linear_hash_write_record(record_loc, terminal_record_key, terminal_record_value, &terminal_record_status, linear_hash);
1039 memcpy(value, record + sizeof(*status) + linear_hash->super.record.key_size, linear_hash->super.record.value_size);
1080 memcpy(record + linear_hash->super.record.key_size + sizeof(*status), value, linear_hash->super.record.value_size);
1129 ion_byte_t record_blank[linear_hash->super.record.key_size + linear_hash->super.record.value_size + sizeof(linear_hash_record_status_empty)];
1131 memset(record_blank, 0, linear_hash->super.record.key_size + linear_hash->super.record.value_size);
1136 if (1 != fwrite(record_blank, linear_hash->super.record.key_size + linear_hash->super.record.value_size + sizeof(linear_hash_record_status_empty), 1, linear_hash->database)) {
1274 ion_byte_t record_blank[linear_hash->super.record.key_size + linear_hash->super.record.value_size + sizeof(linear_hash_record_status_empty)];
1276 memset(record_blank, 0, linear_hash->super.record.key_size + linear_hash->super.record.value_size);
1281 if (1 != fwrite(record_blank, linear_hash->super.record.key_size + linear_hash->super.record.value_size + sizeof(linear_hash_record_status_empty), 1, linear_hash->database)) {
1343 /* Case the record we are looking for was in a bucket that has already been split and h1 was used */
ion_status_t linear_hash_get(ion_byte_t *key, ion_byte_t *value, linear_hash_table_t *linear_hash)
Retrieve a record from the linear hash. The key and value will be written to the key and value pointe...
Definition: linear_hash.c:673
ion_err_t linear_hash_destroy(linear_hash_table_t *linear_hash)
Close a linear hash instance and delete its associated .lhs and .lhd files.
Definition: linear_hash.c:1507
Definition: kv_system.h:276
Definition: kv_system.h:160
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_err_t linear_hash_get_record(ion_fpos_t loc, ion_byte_t *key, ion_byte_t *value, ion_byte_t *status, linear_hash_table_t *linear_hash)
Read the record data at the location specified from the linear hash's .lhd file.
Definition: linear_hash.c:1017
ion_err_t linear_hash_write_state(linear_hash_table_t *linear_hash)
Writes the current state of the linear hash to a .lhs file.
Definition: linear_hash.c:168
ion_err_t linear_hash_get_bucket_swap_record(int bucket_idx, ion_fpos_t *record_loc, ion_byte_t *key, ion_byte_t *value, ion_byte_t *status, linear_hash_table_t *linear_hash)
Obtains the data associated with the last record the bucket chain associated with bucket_idx and dele...
Definition: linear_hash.c:507
ion_err_t array_list_insert(int bucket_idx, ion_fpos_t bucket_loc, array_list_t *array_list)
Insert a value into an array list.
Definition: linear_hash.c:1404
int linear_hash_bucket_is_full(linear_hash_bucket_t bucket, linear_hash_table_t *linear_hash)
Helper method to check if a linear hash bucket is full.
Definition: linear_hash.c:270
ion_err_t write_new_bucket(int idx, linear_hash_table_t *linear_hash)
Write a new bucket to the linear hash's .lhd file.
Definition: linear_hash.c:1099
ion_fpos_t array_list_get(int bucket_idx, array_list_t *array_list)
Retreive a value from an array list.
Definition: linear_hash.c:1444
unsigned int ion_dictionary_id_t
A type used to identify dictionaries, specifically in the master table.
Definition: dictionary_types.h:51
unsigned int ion_dictionary_size_t
The implementation specific size of the dictionary.
Definition: kv_system.h:264
ion_dictionary_size_t dictionary_size
Definition: linear_hash_types.h:72
ion_err_t linear_hash_close(linear_hash_table_t *linear_hash)
Close a linear hash instance with proper resource clean-up.
Definition: linear_hash.c:1466
ion_err_t split(linear_hash_table_t *linear_hash)
Performs the split operation on a linear hash instance.
Definition: linear_hash.c:364
Definition: kv_system.h:188
ion_fpos_t bucket_idx_to_ion_fpos_t(int idx, linear_hash_table_t *linear_hash)
Helper method to get the location of a bucket chain from the linear hash's bucket map...
Definition: linear_hash.c:1298
int insert_hash_to_bucket(ion_byte_t *key, linear_hash_table_t *linear_hash)
Map a key to the address space of the linear hash. Used to map records to buckets with an index less ...
Definition: linear_hash.c:1358
ion_status_t linear_hash_update(ion_key_t key, ion_value_t value, linear_hash_table_t *linear_hash)
Update the value of the first record matching the key specified in the linear hash.
Definition: linear_hash.c:774
ion_boolean_t linear_hash_above_threshold(linear_hash_table_t *linear_hash)
Helper method to increment check if a linear hash's load is above its split threshold.
Definition: linear_hash.c:477
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_fpos_t overflow_location
Definition: linear_hash_types.h:64
ion_err_t linear_hash_increment_next_split(linear_hash_table_t *linear_hash)
Helper method to increment the split linear hash.
Definition: linear_hash.c:349
Definition: kv_system.h:176
Definition: kv_system.h:278
ion_fpos_t record_total_size
Definition: linear_hash_types.h:79
ion_err_t linear_hash_decrement_num_records(linear_hash_table_t *linear_hash)
Helper method to decrement the number of records in the linear hash.
Definition: linear_hash.c:313
int hash_to_bucket(ion_byte_t *key, linear_hash_table_t *linear_hash)
Map a key to the address space of the linear hash. Used to map records to buckets with an index great...
Definition: linear_hash.c:1339
Header for a linear hash .
ion_err_t linear_hash_init(ion_dictionary_id_t id, ion_dictionary_size_t dictionary_size, ion_key_type_t key_type, ion_key_size_t key_size, ion_value_size_t value_size, int initial_size, int split_threshold, int records_per_bucket, linear_hash_table_t *linear_hash)
Definition: linear_hash.c:47
#define linear_hash_record_status_full
Definition: linear_hash_types.h:46
Definition: kv_system.h:185
#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
Definition: kv_system.h:179
Definition: linear_hash_types.h:49
Definition: linear_hash_types.h:69
ion_status_t linear_hash_delete(ion_byte_t *key, linear_hash_table_t *linear_hash)
Delete all records with keys matching the key specified in the linear hash.
Definition: linear_hash.c:867
ion_err_t array_list_init(int init_size, array_list_t *array_list)
Initialize an array list.
Definition: linear_hash.c:1377
Definition: kv_system.h:197
Definition: kv_system.h:162
ion_err_t linear_hash_get_bucket(ion_fpos_t bucket_loc, linear_hash_bucket_t *bucket, linear_hash_table_t *linear_hash)
Read the bucket at the location specified from the linear hash's .lhd file.
Definition: linear_hash.c:1163
Definition: kv_system.h:182
ion_err_t linear_hash_increment_num_records(linear_hash_table_t *linear_hash)
Helper method to increment the number of records in the linear hash.
Definition: linear_hash.c:285
ion_err_t linear_hash_increment_num_buckets(linear_hash_table_t *linear_hash)
Helper method to increment the number of buckets in the linear hash.
Definition: linear_hash.c:328
ion_err_t linear_hash_update_bucket(ion_fpos_t bucket_loc, linear_hash_bucket_t *bucket, linear_hash_table_t *linear_hash)
Write the bucket provided at the location specified from in linear hash's .lhd file.
Definition: linear_hash.c:1205
#define linear_hash_record_status_empty
Definition: linear_hash_types.h:45
Definition: kv_system.h:212
int key_bytes_to_int(ion_byte_t *key, linear_hash_table_t *linear_hash)
Transform a key to an integer.
Definition: linear_hash.c:1315
Definition: kv_system.h:191
Definition: linear_hash_types.h:61
ion_err_t create_overflow_bucket(int bucket_idx, ion_fpos_t *overflow_loc, linear_hash_table_t *linear_hash)
Create an overflow bucket and write it to the linear hash's .lhd file.
Definition: linear_hash.c:1240
ion_status_t linear_hash_insert(ion_key_t key, ion_value_t value, int hash_bucket_idx, linear_hash_table_t *linear_hash)
Insert a record into the linear hash.
Definition: linear_hash.c:573
ion_err_t linear_hash_write_record(ion_fpos_t record_loc, ion_byte_t *key, ion_byte_t *value, ion_byte_t *status, linear_hash_table_t *linear_hash)
Write record data to the location specified from the linear hash's .lhd file.
Definition: linear_hash.c:1059
ion_err_t linear_hash_read_state(linear_hash_table_t *linear_hash)
Read the state of a linear hash from a .lhs file.
Definition: linear_hash.c:219
A status object that describes the result of a dictionary operation.
Definition: kv_system.h:290