#include "skip_list_types.h"
Description
Implementation of a Skiplist data store.
- 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 skip_list.h.
Functions | |
ion_err_t | sl_initialize (ion_skiplist_t *skiplist, ion_key_type_t key_type, int key_size, int value_size, int maxheight, int pnum, int pden) |
Initializes an in-memory skiplist. More... | |
ion_err_t | sl_destroy (ion_skiplist_t *skiplist) |
Destroys the skiplist in memory. More... | |
ion_status_t | sl_insert (ion_skiplist_t *skiplist, ion_key_t key, ion_value_t value) |
Inserts a key value pair into the skiplist. More... | |
ion_status_t | sl_get (ion_skiplist_t *skiplist, ion_key_t key, ion_value_t value) |
Requests the value stored at the given key . More... | |
ion_status_t | sl_update (ion_skiplist_t *skiplist, ion_key_t key, ion_value_t value) |
Updates the value stored at key with the new value . More... | |
ion_status_t | sl_delete (ion_skiplist_t *skiplist, ion_key_t key) |
Attempts to delete all key/value pairs stored at the given key . More... | |
ion_sl_node_t * | sl_find_node (ion_skiplist_t *skiplist, ion_key_t key) |
Searches for a node with the given key . Used in conjunction with sl_query to perform key lookups. More... | |
void | print_skiplist (ion_skiplist_t *skiplist) |
Iterates through each level of a skiplist and prints out the content of each node in a meaningful way. Intended for debug use only. More... | |
ion_sl_level_t | sl_gen_level (ion_skiplist_t *skiplist) |
Generates a psuedo-random height, bounded within [0, maxheight). The generator is seeded using the current epoch time when the skiplist is initialized. More... | |
Function Documentation
void print_skiplist | ( | ion_skiplist_t * | skiplist | ) |
Iterates through each level of a skiplist and prints out the content of each node in a meaningful way. Intended for debug use only.
- Parameters
-
skiplist The skiplist to print
Definition at line 353 of file skip_list.c.
ion_status_t sl_delete | ( | ion_skiplist_t * | skiplist, |
ion_key_t | key | ||
) |
Attempts to delete all key/value pairs stored at the given key
.
Attempts to delete all key/value pairs stored at the given key
. Returns "err_item_not_found" if the requested key
is not in the skiplist, and "err_ok" if the deletion was successful. Any memory previously used for the deleted key/value pair(s) is freed.
- Parameters
-
skiplist The skiplist in which to delete from key The key to delete
- Returns
- Status of deletion.
Definition at line 261 of file skip_list.c.
ion_err_t sl_destroy | ( | ion_skiplist_t * | skiplist | ) |
Destroys the skiplist in memory.
Destroys the skiplist in memory and frees the underlying structures.
- Parameters
-
skiplist The skiplist to be destroyed
- Returns
- Status of destruction.
Definition at line 95 of file skip_list.c.
ion_sl_node_t* sl_find_node | ( | ion_skiplist_t * | skiplist, |
ion_key_t | key | ||
) |
Searches for a node with the given key
. Used in conjunction with sl_query to perform key lookups.
Searches for a node with the given key
. Used in conjunction with sl_query to perform key lookups. Returns the first node containing the target key (if it exists), or the closest node less than the target key if it does not exist.
Definition at line 317 of file skip_list.c.
ion_sl_level_t sl_gen_level | ( | ion_skiplist_t * | skiplist | ) |
Generates a psuedo-random height, bounded within [0, maxheight). The generator is seeded using the current epoch time when the skiplist is initialized.
- Parameters
-
skiplist The skiplist to read level generation parameters from
- Returns
- A height.
Definition at line 340 of file skip_list.c.
ion_status_t sl_get | ( | ion_skiplist_t * | skiplist, |
ion_key_t | key, | ||
ion_value_t | value | ||
) |
Requests the value
stored at the given key
.
Requests the value
stored at the given key
. The resultant value is then copied into the pointer provided by the user.
- Parameters
-
skiplist The skiplist in which to query key The key to be found value The container in which to put the resultant data
- Returns
- Status of query.
Definition at line 206 of file skip_list.c.
ion_err_t sl_initialize | ( | ion_skiplist_t * | skiplist, |
ion_key_type_t | key_type, | ||
int | key_size, | ||
int | value_size, | ||
int | maxheight, | ||
int | pnum, | ||
int | pden | ||
) |
Initializes an in-memory skiplist.
- Parameters
-
skiplist Pointer to a skiplist instance to initialize key_type Type of key used in this instance of a skiplist. key_size Size of key in bytes. value_size Size of value in bytes. maxheight Maximum number of levels the skiplist will have. pnum The numerator portion of the p value. pden The denominator portion of the p value.
- Returns
- Status of initialization.
Definition at line 41 of file skip_list.c.
ion_status_t sl_insert | ( | ion_skiplist_t * | skiplist, |
ion_key_t | key, | ||
ion_value_t | value | ||
) |
Inserts a key
value
pair into the skiplist.
Inserts a key
value
pair into the skiplist. The key and value are copied byte-for-byte as passed by the user. Duplicate inserts are implicitly supported.
- Parameters
-
skiplist The skiplist in which to insert key The key to be insert value The value to be insert
- Returns
- Status of insertion.
Definition at line 115 of file skip_list.c.
ion_status_t sl_update | ( | ion_skiplist_t * | skiplist, |
ion_key_t | key, | ||
ion_value_t | value | ||
) |
Updates the value stored at key
with the new value
.
Updates the value stored at key
with the new value
. The given value is copied byte-for-byte into the malloc'd memory already stored at the key. If the key
does not exist within the skiplist, the key/value pair is inserted into the skiplist instead.
- Parameters
-
skiplist The skiplist in which to update key The key to find and update value The new value to be updated to
- Returns
- Status of updating.
Definition at line 225 of file skip_list.c.