Description
Header for a linear hash .
- Copyright
- Copyright 2017 The University of British Columbia, IonDB Project Contributors (see AUTHORS.md)
- 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 linear_hash.h.
Functions | |
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) |
ion_err_t | linear_hash_read_state (linear_hash_table_t *linear_hash) |
Read the state of a linear hash from a .lhs file. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
ion_err_t | linear_hash_update_state (linear_hash_table_t *linear_hash) |
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. More... | |
ion_err_t | split (linear_hash_table_t *linear_hash) |
Performs the split operation on a linear hash instance. More... | |
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. More... | |
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 pointers passed in. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
ion_err_t | create_overflow_bucket (int bucket_idx, ion_fpos_t *overflow_location, linear_hash_table_t *linear_hash) |
Create an overflow bucket and write it to the linear hash's .lhd file. More... | |
ion_fpos_t | get_bucket_records_location (ion_fpos_t bucket_loc) |
ion_err_t | invalidate_buffer_records (ion_byte_t *key, int record_count, ion_byte_t *records, linear_hash_table_t *linear_hash) |
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 greater than or equal to the split pointer. More... | |
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 than the split pointer. More... | |
linear_hash_bucket_t | linear_hash_get_overflow_bucket (ion_fpos_t loc) |
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. More... | |
ion_err_t | linear_hash_increment_next_split (linear_hash_table_t *linear_hash) |
Helper method to increment the split linear hash. More... | |
void | print_linear_hash_bucket (linear_hash_bucket_t bucket) |
void | print_linear_hash_bucket_map (linear_hash_table_t *linear_hash) |
ion_err_t | store_bucket_loc_in_map (int idx, ion_fpos_t bucket_loc, linear_hash_table_t *linear_hash) |
ion_err_t | array_list_init (int init_size, array_list_t *array_list) |
Initialize an array list. More... | |
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. More... | |
ion_fpos_t | array_list_get (int bucket_idx, array_list_t *array_list) |
Retreive a value from an array list. More... | |
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. More... | |
ion_err_t | linear_hash_close (linear_hash_table_t *linear_hash) |
Close a linear hash instance with proper resource clean-up. More... | |
void | print_linear_hash_distribution (linear_hash_table_t *linear_hash) |
Function Documentation
ion_fpos_t array_list_get | ( | int | bucket_idx, |
array_list_t * | array_list | ||
) |
Retreive a value from an array list.
- Parameters
-
[in] bucket_idx The index in the array list to retireve the value from. [in] array_list The array list to retrieve the value from.
- Returns
- An ion_fpos_t if successful, linear_hash_end_of_list if array bucket idx is outside of array list bounds.
Definition at line 1444 of file linear_hash.c.
ion_err_t array_list_init | ( | int | init_size, |
array_list_t * | array_list | ||
) |
Initialize an array list.
- Parameters
-
[in] init_size The number of indexes to initialize the array list with [in] array_list Pointer to the array list location in memory
- Returns
- err_ok if successful, err_out_of_memory if array list cannot be created with init_size.
Definition at line 1377 of file linear_hash.c.
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.
If the index specified for insertion is larger than the size of the table, the array list size is doubled.
- Parameters
-
[in] bucket_idx The index in the array list to insert the value at. [in] bucket_loc The value to insert. [in] array_list The array list to insert the value into.
- Returns
- err_ok if successful, err_out_of_memory if array list cannot be created doubled in size.
Definition at line 1404 of file linear_hash.c.
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.
- Parameters
-
[in] idx Index of the bucket chain to retrieve the location of [in] linear_hash Pointer to a linear hash instance.
- Returns
- An ion_fpos_t file position where the bucket chain specified begins.
Definition at line 1298 of file linear_hash.c.
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.
Create a new overflow bucket and add it to the end of the bucket chain. The location of the overflow bucket is created at is saved in a write back parameter so that the bucket map of the linear hash points to the end of the linked list of overflow buckets. This saves on disk writes as previous tail does not need to be updated. As with write_new_bucket, the new bucket is intialized with empty memory, including space for all its record, and is appended to the end of the .lhd file.
- Parameters
-
[in] bucket_idx Index of the new bucket to be written [in] overflow_loc Pointer to the location the location of the new overflow bucket is written back to. [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1240 of file linear_hash.c.
ion_fpos_t get_bucket_records_location | ( | ion_fpos_t | bucket_loc | ) |
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 greater than or equal to the split pointer.
- Parameters
-
[in] key Pointer to the key to hash [in] linear_hash Pointer to the linear hash instance (required for knowledge of the key-size)
- Returns
- An integer in the address space of the linear hash.
Definition at line 1339 of file linear_hash.c.
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 than the split pointer.
- Parameters
-
[in] key Pointer to the key to hash [in] linear_hash Pointer to the linear hash instance (required for knowledge of the key-size)
- Returns
- An integer in the address space of the linear hash.
Definition at line 1358 of file linear_hash.c.
ion_err_t invalidate_buffer_records | ( | ion_byte_t * | key, |
int | record_count, | ||
ion_byte_t * | records, | ||
linear_hash_table_t * | linear_hash | ||
) |
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.
- Parameters
-
[in] linear_hash Pointer to a linear hash instance.
- Returns
- True if the linear hash's load is above its split threshold.
Definition at line 477 of file linear_hash.c.
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.
- Parameters
-
[in] bucket Pointer to a bucket. [in] linear_hash Pointer to a linear hash instance.
- Returns
- True if the bucket is full, false if it is not.
Definition at line 270 of file linear_hash.c.
ion_err_t linear_hash_close | ( | linear_hash_table_t * | linear_hash | ) |
Close a linear hash instance with proper resource clean-up.
This will free all the references related to the linear hash in memory and writes it state to its associated .lhs file.
- Parameters
-
[in] linear_hash The linear hash instance to close.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1466 of file linear_hash.c.
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.
- Parameters
-
[in] linear_hash Pointer to a linear hash instance.
- Returns
- err_ok.
Definition at line 313 of file linear_hash.c.
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.
The delete operation of this implementation deletes all records with keys matching the key specified. To improve the overall performance of the linear hash, particularly the insert method, a swap-on-delete strategy is used. When a record is deleted, the last record in the terminal bucket of the bucket moved from its current location to the now empty location where the record just deleted was previously. This garuantees that if there is empty space in a bucket chain, it will be in the terminal bucket.
- Parameters
-
[in] key Pointer to the key of the record to insert. [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 867 of file linear_hash.c.
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.
- Parameters
-
[in] linear_hash The linear hash instance to close.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1507 of file linear_hash.c.
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 pointers passed in.
- Parameters
-
[in] key Pointer where the key of the record is written back to. [in] value Pointer where the value of the record is written back to. [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 673 of file linear_hash.c.
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.
- Parameters
-
[in] bucket_loc Location to read the bucket from [in] bucket Pointer to the location the bucket is written back to [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1163 of file linear_hash.c.
linear_hash_bucket_t linear_hash_get_overflow_bucket | ( | ion_fpos_t | loc | ) |
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.
- Parameters
-
[in] loc Location of the record in the linear hash's data file. [in] key Pointer where the key of the record is written back to. [in] value Pointer where the value of the record is written back to. [in] status Pointer where the status of the record is written back to. [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1017 of file linear_hash.c.
ion_err_t linear_hash_increment_next_split | ( | linear_hash_table_t * | linear_hash | ) |
Helper method to increment the split linear hash.
The new bucket is written to the end of the .lhd file associated with the linear hash. When a bucket is added to a linear hash, the inital_size parameter used in the hash functions is doubled and the pointer is reset to the first bucket. This helps the linear hash's distribution remains constant over time.
- Parameters
-
[in] linear_hash Pointer to a linear hash instance.
- Returns
- err_ok.
Definition at line 349 of file linear_hash.c.
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.
The new bucket is written to the end of the .lhd file associated with the linear hash. When a bucket is added to a linear hash, the inital_size parameter used in the hash functions is doubled and the pointer is reset to the first bucket. This helps the linear hash's distribution remains constant over time.
- Parameters
-
[in] linear_hash Pointer to a linear hash instance.
- Returns
- err_ok.
Definition at line 328 of file linear_hash.c.
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.
When a record is inserted into a linear hash, the load of the linear hash increases. If this pushes the load above the split threshold, then a new bucket is created and a split is performed.
- Parameters
-
[in] linear_hash Pointer to a linear hash instance.
- Returns
- err_ok or the resulting status of the several file operations used to create a new bucket.
Definition at line 285 of file linear_hash.c.
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 at line 47 of file linear_hash.c.
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.
Insert a new record into the linear hash table. If the bucket at hash_bucket_idx is full, a new bucket is written and the record is inserted there. If inserting the record pushes the load of the linear hash above the split threshold, a split is performed.
- Parameters
-
[in] key Pointer to the key of the record to insert. [in] value Pointer to the value of the record to insert. [in] hash_bucket_idx Index of the bucket to insert the record to. [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 573 of file linear_hash.c.
ion_err_t linear_hash_read_state | ( | linear_hash_table_t * | linear_hash | ) |
Read the state of a linear hash from a .lhs file.
Each instance of a linear hash has an associated .lhs file which stores its state in non-volatile storage. The name of a linear hash's .lhs file is the id of linear hash in the master table. This is the file the state is read from.
- Parameters
-
[in] linear_hash Pointer to a linear hash instance to read the data to.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 219 of file linear_hash.c.
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.
- Parameters
-
[in] key Pointer to the key of the record to update. [in] value Pointer to the value to set this record to. [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 774 of file linear_hash.c.
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.
- Parameters
-
[in] bucket_loc Location to write the bucket to [in] bucket Pointer to the bucket data to write to the file [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1205 of file linear_hash.c.
ion_err_t linear_hash_update_state | ( | linear_hash_table_t * | linear_hash | ) |
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.
- Parameters
-
[in] record_loc Location to write the record data in the linear hash's data file. [in] key Pointer to the key to be written. [in] value Pointer to the value to be written. [in] status Pointer to the status to be written. [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1059 of file linear_hash.c.
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.
Each instace of a linear hash has an associated .lhs file which stores its state in non-volatile storage. The name of a linear hash's .lhs file is the id of linear hash in the master table. This is the file the state is written to.
- Parameters
-
[in] linear_hash Which linear hash instance to write.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 168 of file linear_hash.c.
void print_linear_hash_bucket | ( | linear_hash_bucket_t | bucket | ) |
void print_linear_hash_bucket_map | ( | linear_hash_table_t * | linear_hash | ) |
void print_linear_hash_distribution | ( | linear_hash_table_t * | linear_hash | ) |
ion_err_t split | ( | linear_hash_table_t * | linear_hash | ) |
Performs the split operation on a linear hash instance.
A split is triggered when the load of the linear hash surpasses the split_threshold. A new bucket is created and the bucket currently pointed to by the split pointer has all of its records checked against a condition. If this condition passes, the record is deleted from the current bucket and inserted to the new bucket. This operation may require several several calls to linear_hash_insert and linear_hash_delete methods. To avoid data loss caused by the swap-on-delete strategy used in the linear_hash_delete deleting multiple records per call potentially, a cache is used to store the values associated with records which are deleted.
- Parameters
-
[in] linear_hash Pointer to a linear hash instance.
- Returns
- err_ok.
Definition at line 364 of file linear_hash.c.
ion_err_t store_bucket_loc_in_map | ( | int | idx, |
ion_fpos_t | bucket_loc, | ||
linear_hash_table_t * | linear_hash | ||
) |
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.
The new bucket is intialized with empty memory, including space for all its record. The bucket is appended to the end of the .lhd file.
- Parameters
-
[in] idx Index of the new bucket to be written [in] linear_hash Pointer to a linear hash instance.
- Returns
- Resulting status of the several file operations used to commit the write.
Definition at line 1099 of file linear_hash.c.