skip_list.h File Reference
#include "skip_list_types.h"

Description

Implementation of a Skiplist data store.

Author
Eric Huang
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.

Include dependency graph for skip_list.h:
This graph shows which files directly or indirectly include this file:

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_tsl_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
skiplistThe skiplist to print

Definition at line 353 of file skip_list.c.

355  {
356  ion_sl_node_t *cursor = skiplist->head;
357 
358  while (NULL != cursor->next[0]) {
359  ion_sl_level_t level = cursor->next[0]->height + 1;
360 
361  if (key_type_numeric_signed == skiplist->super.key_type) {
362  int key = *((int *) cursor->next[0]->key);
363  int value = *(int *) cursor->next[0]->value;
364 
365  printf("k: '%d' (v: '%d') [l: %d] -- ", key, value, level);
366  }
367  else if (key_type_null_terminated_string == skiplist->super.key_type) {
368  char *key = cursor->next[0]->key;
369  int value = *(int *) cursor->next[0]->value;
370 
371  printf("k: '%s' (v: '%d') [l: %d] -- ", key, value, level);
372  }
373 
374  cursor = cursor->next[0];
375  }
376 
377  printf("%s", "END\n\n");
378 }
ion_value_t value
ion_sl_level_t height
int ion_sl_level_t
struct sl_node ** next
ion_dictionary_parent_t super
#define key(k)
Definition: bpp_tree.c:75
ion_sl_node_t * head
#define printf(format,...)
Struct of a node in the skiplist.
ion_key_t key
ion_key_type_t key_type
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
skiplistThe skiplist in which to delete from
keyThe key to delete
Returns
Status of deletion.

Definition at line 261 of file skip_list.c.

264  {
265  ion_key_size_t key_size = skiplist->super.record.key_size;
266  /* Default return is no item */
267  ion_status_t status;
268 
269  status = ION_STATUS_INITIALIZE;
270  /* If we fall through, then we didn't find what we were looking for. */
271  status.error = err_item_not_found;
272 
273  ion_sl_node_t *cursor = skiplist->head;
274  ion_sl_level_t h;
275 
276  for (h = skiplist->head->height; h >= 0; --h) {
277  while (NULL != cursor->next[h] && skiplist->super.compare(cursor->next[h]->key, key, key_size) < 0) {
278  cursor = cursor->next[h];
279  }
280 
281  if ((NULL != cursor->next[h]) && (skiplist->super.compare(cursor->next[h]->key, key, key_size) == 0)) {
282  ion_sl_node_t *oldcursor = cursor;
283 
284  while (NULL != cursor->next[h] && skiplist->super.compare(cursor->next[h]->key, key, key_size) == 0) {
285  ion_sl_node_t *tofree = cursor->next[h];
286  ion_sl_node_t *relink = cursor->next[h];
287  ion_sl_level_t link_h = relink->height;
288 
289  while (link_h >= 0) {
290  while (cursor->next[link_h] != relink) {
291  cursor = cursor->next[link_h];
292  }
293 
294  ion_sl_node_t *jump = relink->next[link_h];
295 
296  cursor->next[link_h] = jump;
297  link_h--;
298  }
299 
300  free(tofree->key);
301  free(tofree->value);
302  free(tofree->next);
303  free(tofree);
304 
305  cursor = oldcursor;
306  status.count++;
307  }
308 
309  status.error = err_ok;
310  }
311  }
312 
313  return status;
314 }
ion_value_t value
ion_record_info_t record
ion_sl_level_t height
int ion_sl_level_t
struct sl_node ** next
ion_dictionary_parent_t super
#define key(k)
Definition: bpp_tree.c:75
ion_err_t error
Definition: kv_system.h:291
ion_sl_node_t * head
Struct of a node in the skiplist.
ion_key_t key
ion_result_count_t count
Definition: kv_system.h:293
ion_key_size_t key_size
Definition: kv_system.h:307
ion_dictionary_compare_t compare
int ion_key_size_t
The size (length) of a dictionary key in bytes.
Definition: kv_system.h:251
#define ION_STATUS_INITIALIZE
Definition: kv_system.h:107
A status object that describes the result of a dictionary operation.
Definition: kv_system.h:290

Here is the caller graph for this function:

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
skiplistThe skiplist to be destroyed
Returns
Status of destruction.

Definition at line 95 of file skip_list.c.

97  {
98  ion_sl_node_t *cursor = skiplist->head, *tofree;
99 
100  while (cursor != NULL) {
101  tofree = cursor;
102  cursor = cursor->next[0];
103  free(tofree->key);
104  free(tofree->value);
105  free(tofree->next);
106  free(tofree);
107  }
108 
109  skiplist->head = NULL;
110 
111  return err_ok;
112 }
struct sl_node ** next
ion_sl_node_t * head
Struct of a node in the skiplist.

Here is the caller graph for this function:

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.

320  {
321  int key_size = skiplist->super.record.key_size;
322  ion_sl_node_t *cursor = skiplist->head;
323  ion_sl_level_t h;
324 
325  for (h = skiplist->head->height; h >= 0; h--) {
326  while (NULL != cursor->next[h] && skiplist->super.compare(cursor->next[h]->key, key, key_size) <= 0) {
327  if ((NULL != cursor->next[h]) && (skiplist->super.compare(cursor->next[h]->key, key, key_size) == 0)) {
328  return cursor->next[h];
329  }
330 
331  cursor = cursor->next[h];
332  }
333  }
334 
335  /* Key was not found, so return closest thing to that key */
336  return cursor;
337 }
ion_record_info_t record
ion_sl_level_t height
int ion_sl_level_t
struct sl_node ** next
ion_dictionary_parent_t super
#define key(k)
Definition: bpp_tree.c:75
ion_sl_node_t * head
Struct of a node in the skiplist.
ion_key_t key
ion_key_size_t key_size
Definition: kv_system.h:307
ion_dictionary_compare_t compare

Here is the caller graph for this function:

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
skiplistThe skiplist to read level generation parameters from
Returns
A height.

Definition at line 340 of file skip_list.c.

342  {
343  ion_sl_level_t level = 1;
344 
345  while ((rand() < skiplist->pnum * (RAND_MAX / skiplist->pden)) && level < skiplist->maxheight) {
346  level++;
347  }
348 
349  return level - 1;
350 }
int ion_sl_level_t

Here is the caller graph for this function:

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
skiplistThe skiplist in which to query
keyThe key to be found
valueThe container in which to put the resultant data
Returns
Status of query.

Definition at line 206 of file skip_list.c.

210  {
211  ion_key_size_t key_size = skiplist->super.record.key_size;
212  ion_value_size_t value_size = skiplist->super.record.value_size;
213  ion_sl_node_t *cursor = sl_find_node(skiplist, key);
214 
215  if ((NULL == cursor->key) || (skiplist->super.compare(cursor->key, key, key_size) != 0)) {
217  }
218 
219  memcpy(value, cursor->value, value_size);
220 
221  return ION_STATUS_OK(1);
222 }
ion_value_t value
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
int ion_value_size_t
The size (length) of a dictionary value in bytes.
Definition: kv_system.h:256
ion_dictionary_parent_t super
#define ION_STATUS_OK(count)
Definition: kv_system.h:113
#define key(k)
Definition: bpp_tree.c:75
Struct of a node in the skiplist.
ion_key_t key
ion_key_size_t key_size
Definition: kv_system.h:307
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...
Definition: skip_list.c:317
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_value_size_t value_size
Definition: kv_system.h:309

Here is the call graph for this function:

Here is the caller graph for this function:

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
skiplistPointer to a skiplist instance to initialize
key_typeType of key used in this instance of a skiplist.
key_sizeSize of key in bytes.
value_sizeSize of value in bytes.
maxheightMaximum number of levels the skiplist will have.
pnumThe numerator portion of the p value.
pdenThe denominator portion of the p value.
Returns
Status of initialization.

Definition at line 41 of file skip_list.c.

49  {
50  /* srand(time(NULL)); */
51 
52  skiplist->super.key_type = key_type;
53  skiplist->super.record.key_size = key_size;
54  skiplist->super.record.value_size = value_size;
55  skiplist->maxheight = maxheight;
56 
57  skiplist->pden = pden;
58  skiplist->pnum = pnum;
59 
60 #if ION_DEBUG
61  DUMP(skip_list->super.record.key_size, "%d");
62  DUMP(skip_list->super.record.value_size, "%d");
63  DUMP(skip_list->maxheight, "%d");
64  DUMP(skip_list->pnum, "%d");
65  DUMP(skip_list->pden, "%d");
66  printf("%s", "\n");
67 #endif
68 
69  skiplist->head = malloc(sizeof(ion_sl_node_t));
70 
71  if (NULL == skiplist->head) {
72  return err_out_of_memory;
73  }
74 
75  skiplist->head->next = malloc(sizeof(ion_sl_node_t) * skiplist->maxheight);
76 
77  if (NULL == skiplist->head->next) {
78  free(skiplist->head);
79  skiplist->head = NULL;
80  return err_out_of_memory;
81  }
82 
83  skiplist->head->height = maxheight - 1;
84  skiplist->head->key = NULL;
85  skiplist->head->value = NULL;
86 
87  while (--maxheight >= 0) {
88  skiplist->head->next[maxheight] = NULL;
89  }
90 
91  return err_ok;
92 }
ion_value_t value
ion_record_info_t record
ion_sl_level_t height
struct sl_node ** next
ion_dictionary_parent_t super
ion_sl_node_t * head
#define printf(format,...)
Struct of a node in the skiplist.
#define DUMP(varname, format)
Definition: kv_system.h:78
ion_sl_level_t maxheight
ion_key_t key
ion_key_size_t key_size
Definition: kv_system.h:307
ion_key_type_t key_type
ion_value_size_t value_size
Definition: kv_system.h:309

Here is the caller graph for this function:

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
skiplistThe skiplist in which to insert
keyThe key to be insert
valueThe value to be insert
Returns
Status of insertion.

Definition at line 115 of file skip_list.c.

119  {
120  ion_key_size_t key_size = skiplist->super.record.key_size;
121  ion_value_size_t value_size = skiplist->super.record.value_size;
122 
123  ion_sl_node_t *newnode = malloc(sizeof(ion_sl_node_t));
124 
125  if (NULL == newnode) {
127  }
128 
129  newnode->key = malloc((size_t) key_size);
130 
131  if (NULL == newnode->key) {
132  free(newnode);
134  }
135 
136  newnode->value = malloc((size_t) value_size);
137 
138  if (NULL == newnode->value) {
139  free(newnode->key);
140  free(newnode);
142  }
143 
144  memcpy(newnode->key, key, key_size);
145  memcpy(newnode->value, value, value_size);
146 
147  /* First we check if there's already a duplicate node. If there is, we're
148  going to do a modified insert instead. */
149  ion_sl_node_t *duplicate = sl_find_node(skiplist, key);
150 
151  if ((NULL != duplicate->key) && (skiplist->super.compare(duplicate->key, key, key_size) == 0)) {
152  /* Child duplicate nodes have no height (which is effectively 1). */
153  newnode->height = 0;
154  newnode->next = malloc(sizeof(ion_sl_node_t *) * (newnode->height + 1));
155 
156  if (NULL == newnode->next) {
157  free(newnode->value);
158  free(newnode->key);
159  free(newnode);
161  }
162 
163  /* We want duplicate to be the last node in the block of duplicate
164  * nodes, so we traverse along the bottom until we get there.
165  */
166  while (NULL != duplicate->next[0] && skiplist->super.compare(duplicate->next[0]->key, key, key_size) == 0) {
167  duplicate = duplicate->next[0];
168  }
169 
170  /* Only one height to worry about */
171  newnode->next[0] = duplicate->next[0];
172  duplicate->next[0] = newnode;
173  }
174  else {
175  /* If there's no duplicate node, we do a vanilla insert instead */
176  newnode->height = sl_gen_level(skiplist);
177  newnode->next = malloc(sizeof(ion_sl_node_t *) * (newnode->height + 1));
178 
179  if (NULL == newnode->next) {
180  free(newnode->value);
181  free(newnode->key);
182  free(newnode);
184  }
185 
186  ion_sl_node_t *cursor = skiplist->head;
187  ion_sl_level_t h;
188 
189  for (h = skiplist->head->height; h >= 0; --h) {
190  /* The memcmp will return -1 if key is smaller, 0 if equal, 1 if greater. */
191  while (NULL != cursor->next[h] && skiplist->super.compare(key, cursor->next[h]->key, key_size) >= 0) {
192  cursor = cursor->next[h];
193  }
194 
195  if (h <= newnode->height) {
196  newnode->next[h] = cursor->next[h];
197  cursor->next[h] = newnode;
198  }
199  }
200  }
201 
202  return ION_STATUS_OK(1);
203 }
ion_value_t value
#define ION_STATUS_ERROR(error)
Definition: kv_system.h:110
ion_record_info_t record
int ion_value_size_t
The size (length) of a dictionary value in bytes.
Definition: kv_system.h:256
ion_sl_level_t height
int ion_sl_level_t
struct sl_node ** next
ion_dictionary_parent_t super
#define ION_STATUS_OK(count)
Definition: kv_system.h:113
#define key(k)
Definition: bpp_tree.c:75
ion_sl_node_t * head
Struct of a node in the skiplist.
ion_key_t key
ion_key_size_t key_size
Definition: kv_system.h:307
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...
Definition: skip_list.c:317
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 cu...
Definition: skip_list.c:340
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_value_size_t value_size
Definition: kv_system.h:309

Here is the call graph for this function:

Here is the caller graph for this function:

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
skiplistThe skiplist in which to update
keyThe key to find and update
valueThe new value to be updated to
Returns
Status of updating.

Definition at line 225 of file skip_list.c.

229  {
230  ion_status_t status;
231 
232  status = ION_STATUS_INITIALIZE;
233 
234  ion_key_size_t key_size = skiplist->super.record.key_size;
235  ion_value_size_t value_size = skiplist->super.record.value_size;
236  ion_sl_node_t *cursor = sl_find_node(skiplist, key);
237 
238  /* If the key doesn't exist in the skiplist... */
239  if ((NULL == cursor->key) || (skiplist->super.compare(cursor->key, key, key_size) != 0)) {
240  /* Insert it. */
241  status.error = sl_insert(skiplist, key, value).error;
242  status.count = 1;
243  return status;
244  }
245 
246  /* Otherwise, the key exists and now we have the node to update. */
247 
248  /* While the cursor still has the same key as the target key... */
249  while (NULL != cursor && skiplist->super.compare(cursor->key, key, skiplist->super.record.key_size) == 0) {
250  /* Update the value, and then move on to the next node. */
251  memcpy(cursor->value, value, value_size);
252  cursor = cursor->next[0];
253  status.count++;
254  }
255 
256  status.error = err_ok;
257  return status;
258 }
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.
Definition: skip_list.c:115
ion_value_t value
ion_record_info_t record
int ion_value_size_t
The size (length) of a dictionary value in bytes.
Definition: kv_system.h:256
struct sl_node ** next
ion_dictionary_parent_t super
#define key(k)
Definition: bpp_tree.c:75
ion_err_t error
Definition: kv_system.h:291
Struct of a node in the skiplist.
ion_key_t key
ion_result_count_t count
Definition: kv_system.h:293
ion_key_size_t key_size
Definition: kv_system.h:307
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...
Definition: skip_list.c:317
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_value_size_t value_size
Definition: kv_system.h:309
#define ION_STATUS_INITIALIZE
Definition: kv_system.h:107
A status object that describes the result of a dictionary operation.
Definition: kv_system.h:290

Here is the call graph for this function:

Here is the caller graph for this function: