[Spread-cvs] commit: r350 - trunk/stdutil/src
jschultz at spread.org
jschultz at spread.org
Wed Apr 19 13:55:21 EDT 2006
Author: jschultz
Date: 2006-04-19 13:55:21 -0400 (Wed, 19 Apr 2006)
New Revision: 350
Modified:
trunk/stdutil/src/stdskl.c
Log:
Change skiplist to use 25% promotion probability rather than 50%.
Modified: trunk/stdutil/src/stdskl.c
===================================================================
--- trunk/stdutil/src/stdskl.c 2006-03-17 22:34:03 UTC (rev 349)
+++ trunk/stdutil/src/stdskl.c 2006-04-19 17:55:21 UTC (rev 350)
@@ -1,1182 +1,1181 @@
-/* Copyright (c) 2000-2005, The Johns Hopkins University
- * All rights reserved.
- *
- * The contents of this file are subject to a license (the ``License'')
- * that is the exact equivalent of the BSD license as of July 23, 1999.
- * You may not use this file except in compliance with the License. The
- * specific language governing the rights and limitations of the License
- * can be found in the file ``STDUTIL_LICENSE'' found in this
- * distribution.
- *
- * Software distributed under the License is distributed on an AS IS
- * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.
- *
- * The Original Software is:
- * The Stdutil Library
- *
- * Contributors:
- * Creator - John Lane Schultz (jschultz at cnds.jhu.edu)
- * The Center for Networking and Distributed Systems
- * (CNDS - http://www.cnds.jhu.edu)
- */
-
-#include <stdlib.h>
-#include <string.h>
-
-#include <stdutil/stdutil.h>
-#include <stdutil/stderror.h>
-#include <stdutil/stdtime.h>
-#include <stdutil/stdskl.h>
-
-/* TODO: consider shrinking end_node's arrays when the top level
- becomes empty (down to some minimum height like 4 or 5); this is
- easy to detect: if the node being removed has the same height as
- the end_node and his top level prev and next are the end node then
- the level is about to become empty; alternatively after removal you
- can just check the top levels for self reference; also might not
- want to make end_node taller than the tallest node on insert --
- don't know how big an effect on find this will have as find as it
- will simply run down end_node's nexts array while next equals
- end_node not doing any real work
-*/
-
-#define STDSKL_MAX_HEIGHT 31
-
-#define STDSKL_IS_LEGAL(l) ((l)->end_node != NULL && (l)->ksize != 0 && (l)->bits_left >= 0 && (l)->bits_left < 32)
-#define STDSKL_IT_IS_LEGAL(l, i) ((i)->ksize == (l)->ksize && (i)->vsize == (l)->vsize)
-#define STDIT_SKL_IS_LEGAL(i) (((i)->type_id == STDSKL_IT_ID || (i)->type_id == STDSKL_IT_KEY_ID) && \
- (i)->impl.skl.node != NULL && (i)->impl.skl.ksize != 0)
-
-#define STDSKL_NKEY(node) ((node)->key)
-#define STDSKL_NVAL(node) ((node)->val)
-
-/************************************************************************************************
- * stdskl_low_key_cmp: Compares 2 keys, uses memcmp if no comparison fcn defined.
- ***********************************************************************************************/
-
-STDINLINE static int stdskl_low_key_cmp(const stdskl *l, const void *k1, const void *k2)
-{
- return (l->cmp_fcn == NULL ? memcmp(k1, k2, l->ksize) : l->cmp_fcn(k1, k2));
-}
-
-/************************************************************************************************
- * stdskl_low_create_node: Create a node to be inserted into 'l.'
- ***********************************************************************************************/
-
-STDINLINE static stdskl_node *stdskl_low_create_node(stdskl *l, stdint8 height, const void *key, const void *val)
-{
- stdskl_node * node;
- stdsize mem_tot;
- stdsize prevs_off;
- stdsize nexts_off;
- stdsize key_off;
- stdsize val_off;
-
- if (height == -1) { /* height generation requested */
- stdbool keep_going = STDTRUE;
-
- for (; keep_going && height < STDSKL_MAX_HEIGHT; ++height) { /* count how many random "on" bits we get in a row */
-
- if (l->bits_left == 0) { /* out of random bits */
- l->rand_bits = stdrand32(l->seed); /* generate 32 new ones */
- l->bits_left = 32;
- }
-
- keep_going = ((l->rand_bits & 0x1) == 0x1); /* break loop on a "off" bit */
-
- --l->bits_left; /* remove used bit */
- l->rand_bits >>= 1;
- }
- }
-
- /* calculate memory needed for node and pointer arrays and the offsets for the pointers in the node */
-
- mem_tot = sizeof(stdskl_node); /* memory for node structure */
- prevs_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */
-
- mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for prevs array */
- nexts_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */
-
- mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for nexts array */
- mem_tot = STDARCH_PADDED_SIZE(mem_tot); /* pad memory for key */
- key_off = mem_tot;
-
- /* TODO: might only pad the key size if vsize != 0 */
-
- mem_tot += STDARCH_PADDED_SIZE(l->ksize); /* memory for key and padding for value */
- val_off = mem_tot;
-
- mem_tot += l->vsize; /* memory for value */
-
- /* allocate the node and extra memory */
-
- if ((node = (stdskl_node*) malloc(mem_tot)) == NULL) {
- goto stdskl_low_create_node_end;
- }
-
- /* init node: set height, point pointers to appropriate offsets in allocated memory block */
-
- node->height = height;
- node->prevs = (stdskl_node**) ((char*) node + prevs_off);
- node->nexts = (stdskl_node**) ((char*) node + nexts_off);
- node->key = (char*) node + key_off;
- node->val = (char*) node + val_off;
-
- /* copy key + value if given */
-
- if (key != NULL) {
- memcpy((void*) STDSKL_NKEY(node), key, l->ksize);
- memcpy(STDSKL_NVAL(node), val, l->vsize);
- }
-
- stdskl_low_create_node_end:
- return node;
-}
-
-/************************************************************************************************
- * stdskl_low_find_right: Search 'l' for 'key' from left to right.
- *
- * If (find_any) immediately return on any match. Otherwise if 'key'
- * exists in 'l' return the "leftmost" (least) match if multiple
- * matches exist. On no match, returns the "leftmost" (least) entry
- * in 'l' with a greater key, or end if no such entry exists.
- ***********************************************************************************************/
-
-STDINLINE static stdbool stdskl_low_find_right(const stdskl *l, const void *key,
- stdbool find_any, stdskl_node **pos)
-{
- const stdskl_node * next = NULL;
- const stdskl_node * curr = l->end_node;
- stdint8 lvl = l->end_node->height;
- int cmp = -1; /* get rid of compiler warning */
-
- /* run down to bottom level list */
-
- while (lvl > 0) {
- next = curr->nexts[lvl];
-
- /* run right at this level while key is greater than next's key */
-
- while (next != l->end_node &&
- (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) {
- curr = next;
- next = next->nexts[lvl];
- }
-
- /* if we found a match and any match will do */
-
- if (find_any && next != l->end_node && cmp == 0) {
- *pos = (stdskl_node*) next;
- return STDTRUE;
- }
-
- /* run down curr's levels while they equal next */
-
- for (--lvl; lvl > 0 && curr->nexts[lvl] == next; --lvl);
- }
-
- /* lvl is zero: run right on bottom level list trying to match key */
-
- curr = curr->nexts[0];
-
- if (curr != next) {
-
- while (curr != l->end_node &&
- (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) > 0) {
- curr = curr->nexts[0];
- }
- } /* else we already compared key to curr above */
-
- *pos = (stdskl_node*) curr;
-
- return (curr != l->end_node && cmp == 0);
-}
-
-/************************************************************************************************
- * stdskl_low_find_left: Search 'l' for 'key' from right to left.
- *
- * If (find_any) immediately return on any match. Otherwise if 'key'
- * exists in 'l' return the "rightmost" (greatest) match if multiple
- * matches exist. On no match, returns the "rightmost" (greatest)
- * entry in 'l' with a lesser key, or end if no such entry exists.
- ***********************************************************************************************/
-
-STDINLINE static stdbool stdskl_low_find_left(const stdskl *l, const void *key,
- stdbool find_any, stdskl_node **pos)
-{
- const stdskl_node * prev = NULL;
- const stdskl_node * curr = l->end_node;
- stdint8 lvl = l->end_node->height;
- int cmp = -1; /* get rid of compiler warning */
-
- /* run down to bottom level list */
-
- while (lvl > 0) {
- prev = curr->prevs[lvl];
-
- /* run left at this level while key is less than prev's key */
-
- while (prev != l->end_node &&
- (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev))) < 0) {
- curr = prev;
- prev = prev->prevs[lvl];
- }
-
- /* if we found a match and any match will do */
-
- if (find_any && prev != l->end_node && cmp == 0) {
- *pos = (stdskl_node*) prev;
- return STDTRUE;
- }
-
- /* run down curr's prevs levels while they equal prev */
-
- for (--lvl; lvl > 0 && curr->prevs[lvl] == prev; --lvl);
- }
-
- /* run left on bottom level list trying to match key */
-
- curr = curr->prevs[0];
-
- if (curr != prev) {
-
- while (curr != l->end_node &&
- (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) < 0) {
- curr = curr->prevs[0];
- }
- } /* else we already compared key to curr above */
-
- *pos = (stdskl_node*) curr;
-
- return (curr != l->end_node && cmp == 0);
-}
-
-/************************************************************************************************
- * stdskl_low_link_right: Link 'node' into entries greater than or
- * equal to 'ins_pos' in 'l.'
- ***********************************************************************************************/
-
-STDINLINE static void stdskl_low_link_right(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node)
-{
- stdskl_node * next = ins_pos;
- stdint8 height = node->height;
- stdint8 lvl = 0;
-
- node->nexts[0] = next;
- next->prevs[0] = node;
-
- while (lvl != height) {
-
- /* if we've maxed out next's height, then find a later, taller node on this lvl */
-
- while (lvl == next->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */
- next = next->nexts[lvl]; /* so we can't erroneously wrap around past sentinel end node here */
- }
-
- ++lvl;
- node->nexts[lvl] = next;
- next->prevs[lvl] = node;
- }
-}
-
-/************************************************************************************************
- * stdskl_low_link_left: Link in 'node' to entries less than 'ins_pos'
- * in 'l.'
- ***********************************************************************************************/
-
-STDINLINE static void stdskl_low_link_left(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node)
-{
- stdskl_node * prev = ins_pos->prevs[0]; /* NOTE: this is why we must link_left b4 link_right in insert! */
- stdint8 height = node->height;
- stdint8 lvl = 0;
-
- node->prevs[0] = prev;
- prev->nexts[0] = node;
-
- while (lvl != height) {
-
- /* if we've maxed out prev's height, then find an earlier, taller node on this lvl */
-
- while (lvl == prev->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */
- prev = prev->prevs[lvl]; /* so we can't erroneously wrap around past sentinel end node here */
- }
-
- ++lvl;
- node->prevs[lvl] = prev;
- prev->nexts[lvl] = node;
- }
-}
-
-/************************************************************************************************
- * stdskl_low_insert: Insert multiple keys and values into a list
- * using an iterator sequence with various options.
- ***********************************************************************************************/
-
-STDINLINE static stdcode stdskl_low_insert(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdsize num_ins,
- stdbool hint, stdbool overwrite, stdbool advance)
-{
- stdcode ret = STDESUCCESS;
- stdskl_node * node;
- stdskl_node * prev;
- stdskl_node * next = (it != NULL ? it->impl.skl.node : l->end_node);
- stdskl_node * first_ins = NULL;
- stdit src_it = *b;
- stdbool keyed = (stdit_key_size(b) != 0);
- stdint8 lvl;
- const void * key;
- const void * val;
- int cmp;
-
- /* loop over input sequence defined either by [b, b+num_ins) or [b, e) */
-
- while (num_ins-- != 0 && (e == NULL || !stdit_eq(&src_it, e))) {
-
- /* get pointers to the key and value we are about to insert */
-
- val = stdit_val(&src_it);
- key = (keyed ? stdit_key(&src_it) : val);
- cmp = -1;
-
- /* get insertion position for this key: next */
-
- if (hint) { /* 'next' is a potential insertion point -> verify! */
- prev = next->prevs[0];
-
- if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) ||
- (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) {
-
- prev = next;
- next = next->nexts[0]; /* next was inappropriate; try ++next */
- cmp = -1;
-
- if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) ||
- (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) {
- hint = STDFALSE; /* both next and ++next were inappropriate: do a full search */
- }
- }
- }
-
- if (!hint) {
- cmp = !stdskl_low_find_right(l, key, STDTRUE, &next);
- }
-
- hint = STDTRUE; /* use next as a hint for following iteration (optimize for nearly contiguous, sorted inserts) */
-
- /* create + insert new node; or overwrite pre-existing match if so instructed and appropriate */
-
- if (!overwrite || next == l->end_node || cmp != 0) { /* create new node to insert */
-
- if ((node = stdskl_low_create_node(l, -1, key, val)) == NULL) { /* create a node with a random height */
- ret = STDENOMEM;
- goto stdskl_low_insert_end;
- }
-
- /* ensure that l->end_node is at least as tall as the new node */
-
- if (node->height > l->end_node->height) {
- stdskl_node * new_end;
-
- /* ratchet up new end_node's height to be at least 1 level higher (usually 2) than before */
-
- lvl = node->height; /* 0 <= node->height <= STDSKL_MAX_HEIGHT */
-
- if (lvl < STDSKL_MAX_HEIGHT) {
- ++lvl;
- }
-
- if ((new_end = stdskl_low_create_node(l, lvl, NULL, NULL)) == NULL) {
- ret = STDENOMEM;
- goto stdskl_low_insert_fail;
- }
-
- /* set new_end's nexts and prevs and update nodes ref'ing end_node to now point to new_end */
- /* loop while we haven't updated all levels of the lists AND end_node is NOT self-referring */
-
- lvl = 0;
- do {
-
- if (l->end_node->prevs[lvl] == l->end_node) { /* break on end_node referring to itself -> */
- break; /* all prevs, nexts of this and higher lvls are self-referring */
- }
-
- new_end->prevs[lvl] = l->end_node->prevs[lvl];
- l->end_node->prevs[lvl]->nexts[lvl] = new_end;
-
- new_end->nexts[lvl] = l->end_node->nexts[lvl];
- l->end_node->nexts[lvl]->prevs[lvl] = new_end;
-
- } while (lvl++ != l->end_node->height);
-
- /* set additional lvls in new_end to be self-referencing. NOTE: new_end is at least 1 lvl taller than end_node */
-
- do {
- new_end->prevs[lvl] = new_end;
- new_end->nexts[lvl] = new_end;
-
- } while (lvl++ != new_end->height);
-
- /* correct next if it referenced the end_node */
-
- if (next == l->end_node) {
- next = new_end;
- }
-
- free(l->end_node);
- l->end_node = new_end;
- }
-
- /* link 'node' into list before next */
-
- stdskl_low_link_left(l, next, node); /* NOTE: we must link_left before we link_right due to loss of information */
- stdskl_low_link_right(l, next, node);
-
- ++l->size;
-
- } else { /* overwrite existing match */
- node = next;
- memcpy((void*) STDSKL_NKEY(node), key, l->ksize); /* overwrite */
- memcpy(STDSKL_NVAL(node), val, l->vsize);
- }
-
- /* remember first insertion/overwrite */
-
- if (first_ins == NULL) {
- first_ins = node;
- }
-
- /* advance 'src_it' if so instructed */
-
- if (advance) {
- stdit_next(&src_it);
- }
- }
-
- goto stdskl_low_insert_end;
-
- /* error handling and return */
-
- stdskl_low_insert_fail:
- free(node);
-
- stdskl_low_insert_end:
- if (it != NULL) {
- it->type_id = STDSKL_IT_ID;
- it->impl.skl.node = (first_ins != NULL ? first_ins : l->end_node); /* point to end if no insert/overwrite occurred */
- it->impl.skl.ksize = l->ksize;
- it->impl.skl.vsize = l->vsize;
- }
-
- return ret;
-}
-
-/************************************************************************************************
- * stdskl_low_erase: Erase multiple key-value pairs from a list using
- * either an iterator sequence to delete or a number of elements to
- * erase.
- ***********************************************************************************************/
-
-STDINLINE static void stdskl_low_erase(stdskl *l, stdit *b, stdit *e, stdsize num_erase)
-{
- stdskl_node * ers;
- stdskl_node * prev = b->impl.skl.node->prevs[0];
- stdskl_node * next = b->impl.skl.node;
- stdskl_node * end_node = (e != NULL ? e->impl.skl.node : NULL);
- stdint8 max_lvl = 0;
- stdsize erased;
- stdint8 lvl;
-
- /* go through [b, b+num_erase) or [b, e) free'ing nodes -- record
- max height of free'd nodes and how many nodes we erased
- */
-
- for (erased = 0; erased != num_erase && next != end_node; ++erased) {
- STDBOUNDS_CHECK(next != l->end_node);
-
- if (next->height > max_lvl) {
- max_lvl = next->height;
- }
-
- ers = next;
- next = next->nexts[0];
- free(ers);
- }
-
- /* update list size */
-
- l->size -= num_erase;
-
- /* stitch together the left and right portions of the list */
-
- ers = next; /* remember where erasure stopped */
- prev->nexts[0] = next; /* perform base re-linkage */
- next->prevs[0] = prev;
-
- for (lvl = 0; lvl != max_lvl; ) { /* run left and run right up to max_lvl height nodes re-linking */
-
- while (lvl == prev->height) {
- prev = prev->prevs[lvl];
- }
-
- while (lvl == next->height) {
- next = next->nexts[lvl];
- }
-
- ++lvl;
- prev->nexts[lvl] = next;
- next->prevs[lvl] = prev;
- }
-
- /* advance 'b' and 'e' */
-
- b->impl.skl.node = ers;
-
- if (e != NULL) {
- e->impl.skl.node = ers;
- }
-}
-
-/************************************************************************************************
- * stdskl_construct: Construct an initially empty list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_construct(stdskl *l, stdsize ksize, stdsize vsize, stdcmp_fcn kcmp)
-{
- stdcode ret = STDESUCCESS;
- stdint8 lvl;
- stdtime t;
-
- if (ksize == 0) {
- ret = STDEINVAL;
- goto stdskl_construct_fail;
- }
-
- l->size = 0;
- l->ksize = ksize;
- l->vsize = vsize;
- l->cmp_fcn = kcmp;
-
- /* initialize randomization using current system time w/ subsecond precision */
-
- stdtime_now(&t);
- stdrand32_dseed(l->seed, stdhcode_sfh(&t, sizeof(t)));
- l->bits_left = 0;
-
- /* allocate and init end_node -- NOTE: rest of list must be initialized b4 calling this fcn */
-
- if ((l->end_node = stdskl_low_create_node(l, 4, NULL, NULL)) == NULL) {
- ret = STDENOMEM;
- goto stdskl_construct_fail;
- }
-
- /* make end_node reference itself */
-
- lvl = l->end_node->height;
-
- do {
- l->end_node->nexts[lvl] = l->end_node;
- l->end_node->prevs[lvl] = l->end_node;
-
- } while (lvl-- != 0);
-
- goto stdskl_construct_end;
-
- /* error handling and return */
-
- stdskl_construct_fail:
- l->end_node = NULL;
- l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */
-
- stdskl_construct_end:
- return ret;
-}
-
-/************************************************************************************************
- * stdskl_copy_construct: Construct a copy of a list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_copy_construct(stdskl *dst, const stdskl *src)
-{
- stdcode ret;
- stdit it;
-
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(src));
-
- if ((ret = stdskl_construct(dst, src->ksize, src->vsize, src->cmp_fcn)) != STDESUCCESS) {
- goto stdskl_copy_construct_fail;
- }
-
- if ((ret = stdskl_insert_seq_n(dst, NULL, stdskl_begin(src, &it), src->size, STDFALSE)) != STDESUCCESS) {
- goto stdskl_copy_construct_fail2;
- }
-
- goto stdskl_copy_construct_end;
-
- /* error handling and return */
-
- stdskl_copy_construct_fail2:
- stdskl_destruct(dst);
-
- stdskl_copy_construct_fail:
- dst->end_node = NULL;
- dst->ksize = 0; /* make STDSKL_IS_LEGAL(dst) false */
-
- stdskl_copy_construct_end:
- return ret;
-}
-
-/************************************************************************************************
- * stdskl_destruct: Reclaim a list's resources and invalidate it.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_destruct(stdskl *l)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- stdskl_clear(l);
- free(l->end_node);
-
- l->end_node = NULL;
- l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */
-}
-
-/************************************************************************************************
- * stdskl_set_eq: Set a list to contain the same contents as another.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_set_eq(stdskl *dst, const stdskl *src)
-{
- stdcode ret = STDESUCCESS;
- stdskl cpy;
-
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(dst) && STDSKL_IS_LEGAL(src) &&
- dst->ksize == src->ksize && dst->vsize == src->vsize &&
- dst->cmp_fcn == src->cmp_fcn);
-
- /* TODO: an improvement would be to resize the number of nodes in
- the table as needed: just slice off or splice on an appropriate
- sequence of nodes to the begin or end of the list and overwrite
- all nodes: this would cut down on "unnecessary" memory
- allocs/frees
- */
-
- if (dst == src) {
- goto stdskl_set_eq_end;
- }
-
- if ((ret = stdskl_copy_construct(&cpy, src)) != STDESUCCESS) {
- goto stdskl_set_eq_end;
- }
-
- stdskl_swap(dst, &cpy);
- stdskl_destruct(&cpy);
-
- stdskl_set_eq_end:
- return ret;
-}
-
-/************************************************************************************************
- * stdskl_swap: Set a l1 to reference l2's sequence and vice versa.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_swap(stdskl *l1, stdskl *l2)
-{
- stdskl cpy;
-
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l1) && STDSKL_IS_LEGAL(l2));
-
- STDSWAP(*l1, *l2, cpy);
-}
-
-/************************************************************************************************
- * stdskl_begin: Get an iterator to the beginning of a list.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_begin(const stdskl *l, stdit *it)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- it->type_id = STDSKL_IT_ID;
- it->impl.skl.node = l->end_node->nexts[0];
- it->impl.skl.ksize = l->ksize;
- it->impl.skl.vsize = l->vsize;
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_last: Get an iterator to the last element of a list.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_last(const stdskl *l, stdit *it)
-{
- STDBOUNDS_CHECK(l->size != 0);
-
- return stdit_prev(stdskl_end(l, it));
-}
-
-/************************************************************************************************
- * stdskl_end: Get an iterator to the sentinel end of a list.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_end(const stdskl *l, stdit *it)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- it->type_id = STDSKL_IT_ID;
- it->impl.skl.node = l->end_node;
- it->impl.skl.ksize = l->ksize;
- it->impl.skl.vsize = l->vsize;
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_get: Get an iterator to an element of a list.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_get(const stdskl *l, stdit *it, stdsize elem_num)
-{
- STDBOUNDS_CHECK(elem_num <= l->size);
-
- if (elem_num < (l->size >> 1)) {
- stdskl_it_advance(stdskl_begin(l, it), elem_num);
-
- } else {
- stdskl_it_retreat(stdskl_end(l, it), l->size - elem_num);
- }
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_is_begin: Return whether or not an iterator refers to the beginning of a list.
- ***********************************************************************************************/
-
-STDINLINE stdbool stdskl_is_begin(const stdskl *l, const stdit *it)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl));
-
- return it->impl.skl.node == l->end_node->nexts[0];
-}
-
-/************************************************************************************************
- * stdskl_is_end: Return whether or not an iterator refers to the end of a list.
- ***********************************************************************************************/
-
-STDINLINE stdbool stdskl_is_end(const stdskl *l, const stdit *it)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl));
-
- return it->impl.skl.node == l->end_node;
-}
-
-/************************************************************************************************
- * stdskl_size: Return the number of key-value pairs a list contains.
- ***********************************************************************************************/
-
-STDINLINE stdsize stdskl_size(const stdskl *l)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- return l->size;
-}
-
-/************************************************************************************************
- * stdskl_empty: Return whether or not a list's size is zero.
- ***********************************************************************************************/
-
-STDINLINE stdbool stdskl_empty(const stdskl *l)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- return l->size == 0;
-}
-
-/************************************************************************************************
- * stdskl_clear: Set a lists size to zero.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_clear(stdskl *l)
-{
- stdskl_node * curr;
- stdskl_node * prev;
- stdint8 lvl;
-
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- /* run through list destroying all nodes */
-
- for (curr = l->end_node->nexts[0]; curr != l->end_node; ) {
- prev = curr;
- curr = curr->nexts[0];
- free(prev);
- }
-
- /* fix list entries: end_node needs to self reference at all levels and size */
-
- curr = l->end_node;
- lvl = l->end_node->height;
-
- do {
- curr->prevs[lvl] = curr;
- curr->nexts[lvl] = curr;
-
- } while (lvl-- != 0);
-
- l->size = 0;
-}
-
-/************************************************************************************************
- * stdskl_find: Find a key-value pair in a list.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_find(const stdskl *l, stdit *it, const void *key)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- if (!stdskl_low_find_right(l, key, STDTRUE, &it->impl.skl.node)) {
- it->impl.skl.node = l->end_node;
- }
-
- it->type_id = STDSKL_IT_ID;
- it->impl.skl.ksize = l->ksize;
- it->impl.skl.vsize = l->vsize;
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_lowerb: Find the least element for which kcmp(key, elem) >= 0.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_lowerb(const stdskl *l, stdit *it, const void *key)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- stdskl_low_find_right(l, key, STDFALSE, &it->impl.skl.node);
-
- it->type_id = STDSKL_IT_ID;
- it->impl.skl.ksize = l->ksize;
- it->impl.skl.vsize = l->vsize;
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_upperb: Find the least element for which kcmp(key, elem) > 0.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_upperb(const stdskl *l, stdit *it, const void *key)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- stdskl_low_find_left(l, key, STDFALSE, &it->impl.skl.node);
- it->impl.skl.node = it->impl.skl.node->nexts[0]; /* found either the last entry for key or the prev entry if none: so get next */
-
- it->type_id = STDSKL_IT_ID;
- it->impl.skl.ksize = l->ksize;
- it->impl.skl.vsize = l->vsize;
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_contains: Return whether or not a list contains a certain key.
- ***********************************************************************************************/
-
-STDINLINE stdbool stdskl_contains(const stdskl *l, const void *key)
-{
- stdskl_node * n;
-
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- return stdskl_low_find_right(l, key, STDTRUE, &n);
-}
-
-/************************************************************************************************
- * stdskl_put: If 'key' already exists in the list, overwrite such an
- * entry with 'key' and 'value;' otherwise insert 'key' and 'value'
- * into the list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_put(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint)
-{
- return stdskl_put_n(l, it, key, val, 1, hint);
-}
-
-/************************************************************************************************
- * stdskl_put_n: For each (key, val) in [(keys, vals), (keys+num_put, vals+num_put))
- * perform stdskl_put(l, it, key, val).
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_put_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_put, stdbool hint)
-{
- stdit b;
-
- return stdskl_put_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_put, hint);
-}
-
-/************************************************************************************************
- * stdskl_put_seq: For each (key, val) in [b, e) perform
- * stdskl_put(l, it, key, val).
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_put_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) &&
- (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
- (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
- (stdit_val_size(b) == l->vsize || l->vsize == 0));
-
- return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDTRUE, STDTRUE);
-}
-
-/************************************************************************************************
- * stdskl_put_seq_n: For each (key, val) in [b, b+num_put) perform
- * stdskl_put(l, it, key, val).
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_put_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_put, stdbool hint)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) &&
- (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
- (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
- (stdit_val_size(b) == l->vsize || l->vsize == 0));
-
- return stdskl_low_insert(l, it, b, NULL, num_put, hint, STDTRUE, STDTRUE);
-}
-
-/************************************************************************************************
- * stdskl_insert: Insert a key and value into a list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_insert(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint)
-{
- return stdskl_insert_n(l, it, key, val, 1, hint);
-}
-
-/************************************************************************************************
- * stdskl_insert_n: Insert multiple keys and values into a list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_insert_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_insert, stdbool hint)
-{
- stdit b;
-
- return stdskl_insert_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_insert, hint);
-}
-
-/************************************************************************************************
- * stdskl_insert_seq: Insert a sequence of key-value pairs into a list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_insert_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) &&
- (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
- (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
- (stdit_val_size(b) == l->vsize || l->vsize == 0));
-
- return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDFALSE, STDTRUE);
-}
-
-/************************************************************************************************
- * stdskl_insert_seq_n: Insert a sequence of key-value pairs into a list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_insert_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_insert, stdbool hint)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) &&
- (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
- (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
- (stdit_val_size(b) == l->vsize || l->vsize == 0));
-
- return stdskl_low_insert(l, it, b, NULL, num_insert, hint, STDFALSE, STDTRUE);
-}
-
-/************************************************************************************************
- * stdskl_insert_rep: Repeatedly insert a key-value pair into a list.
- ***********************************************************************************************/
-
-STDINLINE stdcode stdskl_insert_rep(stdskl *l, stdit *it, const void *key, const void *val, stdsize num_times, stdbool hint)
-{
- stdit b;
-
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) &&
- (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))));
-
- return stdskl_low_insert(l, it, stdit_pptr(&b, key, val, l->ksize, l->vsize), NULL, num_times, hint, STDFALSE, STDFALSE);
-}
-
-/************************************************************************************************
- * stdskl_erase: Erase a key-value pair from a list.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_erase(stdskl *l, stdit *it)
-{
- stdskl_erase_n(l, it, 1);
-}
-
-/************************************************************************************************
- * stdskl_erase_n: Erase multiple key-value pairs from a list.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_erase_n(stdskl *l, stdit *it, stdsize num_erase)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl));
-
- stdskl_low_erase(l, it, NULL, num_erase);
-}
-
-/************************************************************************************************
- * stdskl_erase_seq: Erase a sequence from a list.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_erase_seq(stdskl *l, stdit *b, stdit *e)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(b) && STDSKL_IT_IS_LEGAL(l, &b->impl.skl) && (stdit_eq(b, e) || STDTRUE));
-
- stdskl_low_erase(l, b, e, (stdsize) -1);
-}
-
-/************************************************************************************************
- * stdskl_erase_key: Erase all entries of a key from a list.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_erase_key(stdskl *l, const void *key)
-{
- stdit it;
-
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- stdskl_lowerb(l, &it, key);
-
- while (it.impl.skl.node != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(it.impl.skl.node)) == 0) {
- stdskl_erase(l, &it); /* advances 'it' */
- }
-}
-
-/************************************************************************************************
- * stdskl_dseed: Set a skiplist's random number generator with a deterministic value.
- ***********************************************************************************************/
-
-STDINLINE void stdskl_dseed(stdskl *l, const void *seed, stdsize sizeof_seed)
-{
- STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
-
- stdrand32_dseed(l->seed, stdhcode_sfh(seed, sizeof_seed));
- l->bits_left = 0;
-}
-
-/************************************************************************************************
- * stdskl_it_key: Get a key from an iterator.
- ***********************************************************************************************/
-
-STDINLINE const void *stdskl_it_key(const stdit *it)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- return STDSKL_NKEY(it->impl.skl.node);
-}
-
-/************************************************************************************************
- * stdskl_it_key_size: Get the size in bytes of the keys to which 'it' refers.
- ***********************************************************************************************/
-
-STDINLINE stdsize stdskl_it_key_size(const stdit *it)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- return it->impl.skl.ksize;
-}
-
-/************************************************************************************************
- * stdskl_it_val: Get a value from an iterator.
- ***********************************************************************************************/
-
-STDINLINE void *stdskl_it_val(const stdit *it)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- return (void*) (it->type_id == STDSKL_IT_ID ? STDSKL_NVAL(it->impl.skl.node) : STDSKL_NKEY(it->impl.skl.node));
-}
-
-/************************************************************************************************
- * stdskl_it_val_size: Get the size in bytes of the values to which 'it' refers.
- ***********************************************************************************************/
-
-STDINLINE stdsize stdskl_it_val_size(const stdit *it)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- return (it->type_id == STDSKL_IT_ID ? it->impl.skl.vsize : it->impl.skl.ksize);
-}
-
-/************************************************************************************************
- * stdskl_it_eq: Compare two iterators for equality (refer to the same element).
- ***********************************************************************************************/
-
-STDINLINE stdbool stdskl_it_eq(const stdit *it1, const stdit *it2)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it1) && STDIT_SKL_IS_LEGAL(it2) &&
- it1->impl.skl.ksize == it2->impl.skl.ksize &&
- it1->impl.skl.vsize == it2->impl.skl.vsize);
-
- return it1->impl.skl.node == it2->impl.skl.node;
-}
-
-/************************************************************************************************
- * stdskl_it_next: Advance 'it' towards end by one position.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_it_next(stdit *it)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- it->impl.skl.node = it->impl.skl.node->nexts[0];
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_it_advance: Advance 'it' towards end by 'num_advance' positions.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_it_advance(stdit *it, stdsize num_advance)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- while (num_advance-- != 0) {
- it->impl.skl.node = it->impl.skl.node->nexts[0];
- }
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_it_prev: Advance 'it' towards begin by one position.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_it_prev(stdit *it)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- it->impl.skl.node = it->impl.skl.node->prevs[0];
-
- return it;
-}
-
-/************************************************************************************************
- * stdskl_it_retreat: Advance 'it' towards end by 'num_retreat' positions.
- ***********************************************************************************************/
-
-STDINLINE stdit *stdskl_it_retreat(stdit *it, stdsize num_retreat)
-{
- STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
-
- while (num_retreat-- != 0) {
- it->impl.skl.node = it->impl.skl.node->prevs[0];
- }
-
- return it;
-}
+/* Copyright (c) 2000-2005, The Johns Hopkins University
+ * All rights reserved.
+ *
+ * The contents of this file are subject to a license (the ``License'')
+ * that is the exact equivalent of the BSD license as of July 23, 1999.
+ * You may not use this file except in compliance with the License. The
+ * specific language governing the rights and limitations of the License
+ * can be found in the file ``STDUTIL_LICENSE'' found in this
+ * distribution.
+ *
+ * Software distributed under the License is distributed on an AS IS
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.
+ *
+ * The Original Software is:
+ * The Stdutil Library
+ *
+ * Contributors:
+ * Creator - John Lane Schultz (jschultz at cnds.jhu.edu)
+ * The Center for Networking and Distributed Systems
+ * (CNDS - http://www.cnds.jhu.edu)
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <stdutil/stdutil.h>
+#include <stdutil/stderror.h>
+#include <stdutil/stdtime.h>
+#include <stdutil/stdskl.h>
+
+/* TODO: consider shrinking end_node's arrays when the top level
+ becomes empty (down to some minimum height like 4 or 5); this is
+ easy to detect: if the node being removed has the same height as
+ the end_node and his top level prev and next are the end node then
+ the level is about to become empty; alternatively after removal you
+ can just check the top levels for self reference; also might not
+ want to make end_node taller than the tallest node on insert --
+ don't know how big an effect on find this will have as find as it
+ will simply run down end_node's nexts array while next equals
+ end_node not doing any real work
+*/
+
+#define STDSKL_MAX_HEIGHT 31
+
+#define STDSKL_IS_LEGAL(l) ((l)->end_node != NULL && (l)->ksize != 0 && (l)->bits_left >= 0 && (l)->bits_left < 32)
+#define STDSKL_IT_IS_LEGAL(l, i) ((i)->ksize == (l)->ksize && (i)->vsize == (l)->vsize)
+#define STDIT_SKL_IS_LEGAL(i) (((i)->type_id == STDSKL_IT_ID || (i)->type_id == STDSKL_IT_KEY_ID) && \
+ (i)->impl.skl.node != NULL && (i)->impl.skl.ksize != 0)
+
+#define STDSKL_NKEY(node) ((node)->key)
+#define STDSKL_NVAL(node) ((node)->val)
+
+/************************************************************************************************
+ * stdskl_low_key_cmp: Compares 2 keys, uses memcmp if no comparison fcn defined.
+ ***********************************************************************************************/
+
+STDINLINE static int stdskl_low_key_cmp(const stdskl *l, const void *k1, const void *k2)
+{
+ return (l->cmp_fcn == NULL ? memcmp(k1, k2, l->ksize) : l->cmp_fcn(k1, k2));
+}
+
+/************************************************************************************************
+ * stdskl_low_create_node: Create a node to be inserted into 'l.'
+ ***********************************************************************************************/
+
+STDINLINE static stdskl_node *stdskl_low_create_node(stdskl *l, stdint8 height, const void *key, const void *val)
+{
+ stdskl_node * node;
+ stdsize mem_tot;
+ stdsize prevs_off;
+ stdsize nexts_off;
+ stdsize key_off;
+ stdsize val_off;
+
+ if (height == -1) { /* height generation requested */
+ stdbool keep_going = STDTRUE;
+
+ for (; keep_going && height < STDSKL_MAX_HEIGHT; ++height) { /* count how many random "on" bits we get in a row */
+
+ if (l->bits_left <= 0) { /* out of random bits */
+ l->rand_bits = stdrand32(l->seed); /* generate 32 new ones */
+ l->bits_left = 32;
+ }
+
+ keep_going = ((l->rand_bits & 0x3) == 0x3); /* keep going on a 3 out of 0-3 chance */
+ l->bits_left -= 2; /* remove used bit */
+ l->rand_bits >>= 2;
+ }
+ }
+
+ /* calculate memory needed for node and pointer arrays and the offsets for the pointers in the node */
+
+ mem_tot = sizeof(stdskl_node); /* memory for node structure */
+ prevs_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */
+
+ mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for prevs array */
+ nexts_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */
+
+ mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for nexts array */
+ mem_tot = STDARCH_PADDED_SIZE(mem_tot); /* pad memory for key */
+ key_off = mem_tot;
+
+ /* TODO: might only pad the key size if vsize != 0 */
+
+ mem_tot += STDARCH_PADDED_SIZE(l->ksize); /* memory for key and padding for value */
+ val_off = mem_tot;
+
+ mem_tot += l->vsize; /* memory for value */
+
+ /* allocate the node and extra memory */
+
+ if ((node = (stdskl_node*) malloc(mem_tot)) == NULL) {
+ goto stdskl_low_create_node_end;
+ }
+
+ /* init node: set height, point pointers to appropriate offsets in allocated memory block */
+
+ node->height = height;
+ node->prevs = (stdskl_node**) ((char*) node + prevs_off);
+ node->nexts = (stdskl_node**) ((char*) node + nexts_off);
+ node->key = (char*) node + key_off;
+ node->val = (char*) node + val_off;
+
+ /* copy key + value if given */
+
+ if (key != NULL) {
+ memcpy((void*) STDSKL_NKEY(node), key, l->ksize);
+ memcpy(STDSKL_NVAL(node), val, l->vsize);
+ }
+
+ stdskl_low_create_node_end:
+ return node;
+}
+
+/************************************************************************************************
+ * stdskl_low_find_right: Search 'l' for 'key' from left to right.
+ *
+ * If (find_any) immediately return on any match. Otherwise if 'key'
+ * exists in 'l' return the "leftmost" (least) match if multiple
+ * matches exist. On no match, returns the "leftmost" (least) entry
+ * in 'l' with a greater key, or end if no such entry exists.
+ ***********************************************************************************************/
+
+STDINLINE static stdbool stdskl_low_find_right(const stdskl *l, const void *key,
+ stdbool find_any, stdskl_node **pos)
+{
+ const stdskl_node * next = NULL;
+ const stdskl_node * curr = l->end_node;
+ stdint8 lvl = l->end_node->height;
+ int cmp = -1; /* get rid of compiler warning */
+
+ /* run down to bottom level list */
+
+ while (lvl > 0) {
+ next = curr->nexts[lvl];
+
+ /* run right at this level while key is greater than next's key */
+
+ while (next != l->end_node &&
+ (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) {
+ curr = next;
+ next = next->nexts[lvl];
+ }
+
+ /* if we found a match and any match will do */
+
+ if (find_any && next != l->end_node && cmp == 0) {
+ *pos = (stdskl_node*) next;
+ return STDTRUE;
+ }
+
+ /* run down curr's levels while they equal next */
+
+ for (--lvl; lvl > 0 && curr->nexts[lvl] == next; --lvl);
+ }
+
+ /* lvl is zero: run right on bottom level list trying to match key */
+
+ curr = curr->nexts[0];
+
+ if (curr != next) {
+
+ while (curr != l->end_node &&
+ (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) > 0) {
+ curr = curr->nexts[0];
+ }
+ } /* else we already compared key to curr above */
+
+ *pos = (stdskl_node*) curr;
+
+ return (curr != l->end_node && cmp == 0);
+}
+
+/************************************************************************************************
+ * stdskl_low_find_left: Search 'l' for 'key' from right to left.
+ *
+ * If (find_any) immediately return on any match. Otherwise if 'key'
+ * exists in 'l' return the "rightmost" (greatest) match if multiple
+ * matches exist. On no match, returns the "rightmost" (greatest)
+ * entry in 'l' with a lesser key, or end if no such entry exists.
+ ***********************************************************************************************/
+
+STDINLINE static stdbool stdskl_low_find_left(const stdskl *l, const void *key,
+ stdbool find_any, stdskl_node **pos)
+{
+ const stdskl_node * prev = NULL;
+ const stdskl_node * curr = l->end_node;
+ stdint8 lvl = l->end_node->height;
+ int cmp = -1; /* get rid of compiler warning */
+
+ /* run down to bottom level list */
+
+ while (lvl > 0) {
+ prev = curr->prevs[lvl];
+
+ /* run left at this level while key is less than prev's key */
+
+ while (prev != l->end_node &&
+ (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev))) < 0) {
+ curr = prev;
+ prev = prev->prevs[lvl];
+ }
+
+ /* if we found a match and any match will do */
+
+ if (find_any && prev != l->end_node && cmp == 0) {
+ *pos = (stdskl_node*) prev;
+ return STDTRUE;
+ }
+
+ /* run down curr's prevs levels while they equal prev */
+
+ for (--lvl; lvl > 0 && curr->prevs[lvl] == prev; --lvl);
+ }
+
+ /* run left on bottom level list trying to match key */
+
+ curr = curr->prevs[0];
+
+ if (curr != prev) {
+
+ while (curr != l->end_node &&
+ (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) < 0) {
+ curr = curr->prevs[0];
+ }
+ } /* else we already compared key to curr above */
+
+ *pos = (stdskl_node*) curr;
+
+ return (curr != l->end_node && cmp == 0);
+}
+
+/************************************************************************************************
+ * stdskl_low_link_right: Link 'node' into entries greater than or
+ * equal to 'ins_pos' in 'l.'
+ ***********************************************************************************************/
+
+STDINLINE static void stdskl_low_link_right(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node)
+{
+ stdskl_node * next = ins_pos;
+ stdint8 height = node->height;
+ stdint8 lvl = 0;
+
+ node->nexts[0] = next;
+ next->prevs[0] = node;
+
+ while (lvl != height) {
+
+ /* if we've maxed out next's height, then find a later, taller node on this lvl */
+
+ while (lvl == next->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */
+ next = next->nexts[lvl]; /* so we can't erroneously wrap around past sentinel end node here */
+ }
+
+ ++lvl;
+ node->nexts[lvl] = next;
+ next->prevs[lvl] = node;
+ }
+}
+
+/************************************************************************************************
+ * stdskl_low_link_left: Link in 'node' to entries less than 'ins_pos'
+ * in 'l.'
+ ***********************************************************************************************/
+
+STDINLINE static void stdskl_low_link_left(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node)
+{
+ stdskl_node * prev = ins_pos->prevs[0]; /* NOTE: this is why we must link_left b4 link_right in insert! */
+ stdint8 height = node->height;
+ stdint8 lvl = 0;
+
+ node->prevs[0] = prev;
+ prev->nexts[0] = node;
+
+ while (lvl != height) {
+
+ /* if we've maxed out prev's height, then find an earlier, taller node on this lvl */
+
+ while (lvl == prev->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */
+ prev = prev->prevs[lvl]; /* so we can't erroneously wrap around past sentinel end node here */
+ }
+
+ ++lvl;
+ node->prevs[lvl] = prev;
+ prev->nexts[lvl] = node;
+ }
+}
+
+/************************************************************************************************
+ * stdskl_low_insert: Insert multiple keys and values into a list
+ * using an iterator sequence with various options.
+ ***********************************************************************************************/
+
+STDINLINE static stdcode stdskl_low_insert(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdsize num_ins,
+ stdbool hint, stdbool overwrite, stdbool advance)
+{
+ stdcode ret = STDESUCCESS;
+ stdskl_node * node;
+ stdskl_node * prev;
+ stdskl_node * next = (it != NULL ? it->impl.skl.node : l->end_node);
+ stdskl_node * first_ins = NULL;
+ stdit src_it = *b;
+ stdbool keyed = (stdit_key_size(b) != 0);
+ stdint8 lvl;
+ const void * key;
+ const void * val;
+ int cmp;
+
+ /* loop over input sequence defined either by [b, b+num_ins) or [b, e) */
+
+ while (num_ins-- != 0 && (e == NULL || !stdit_eq(&src_it, e))) {
+
+ /* get pointers to the key and value we are about to insert */
+
+ val = stdit_val(&src_it);
+ key = (keyed ? stdit_key(&src_it) : val);
+ cmp = -1;
+
+ /* get insertion position for this key: next */
+
+ if (hint) { /* 'next' is a potential insertion point -> verify! */
+ prev = next->prevs[0];
+
+ if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) ||
+ (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) {
+
+ prev = next;
+ next = next->nexts[0]; /* next was inappropriate; try ++next */
+ cmp = -1;
+
+ if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) ||
+ (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) {
+ hint = STDFALSE; /* both next and ++next were inappropriate: do a full search */
+ }
+ }
+ }
+
+ if (!hint) {
+ cmp = !stdskl_low_find_right(l, key, STDTRUE, &next);
+ }
+
+ hint = STDTRUE; /* use next as a hint for following iteration (optimize for nearly contiguous, sorted inserts) */
+
+ /* create + insert new node; or overwrite pre-existing match if so instructed and appropriate */
+
+ if (!overwrite || next == l->end_node || cmp != 0) { /* create new node to insert */
+
+ if ((node = stdskl_low_create_node(l, -1, key, val)) == NULL) { /* create a node with a random height */
+ ret = STDENOMEM;
+ goto stdskl_low_insert_end;
+ }
+
+ /* ensure that l->end_node is at least as tall as the new node */
+
+ if (node->height > l->end_node->height) {
+ stdskl_node * new_end;
+
+ /* ratchet up new end_node's height to be at least 1 level higher (usually 2) than before */
+
+ lvl = node->height; /* 0 <= node->height <= STDSKL_MAX_HEIGHT */
+
+ if (lvl < STDSKL_MAX_HEIGHT) {
+ ++lvl;
+ }
+
+ if ((new_end = stdskl_low_create_node(l, lvl, NULL, NULL)) == NULL) {
+ ret = STDENOMEM;
+ goto stdskl_low_insert_fail;
+ }
+
+ /* set new_end's nexts and prevs and update nodes ref'ing end_node to now point to new_end */
+ /* loop while we haven't updated all levels of the lists AND end_node is NOT self-referring */
+
+ lvl = 0;
+ do {
+
+ if (l->end_node->prevs[lvl] == l->end_node) { /* break on end_node referring to itself -> */
+ break; /* all prevs, nexts of this and higher lvls are self-referring */
+ }
+
+ new_end->prevs[lvl] = l->end_node->prevs[lvl];
+ l->end_node->prevs[lvl]->nexts[lvl] = new_end;
+
+ new_end->nexts[lvl] = l->end_node->nexts[lvl];
+ l->end_node->nexts[lvl]->prevs[lvl] = new_end;
+
+ } while (lvl++ != l->end_node->height);
+
+ /* set additional lvls in new_end to be self-referencing. NOTE: new_end is at least 1 lvl taller than end_node */
+
+ do {
+ new_end->prevs[lvl] = new_end;
+ new_end->nexts[lvl] = new_end;
+
+ } while (lvl++ != new_end->height);
+
+ /* correct next if it referenced the end_node */
+
+ if (next == l->end_node) {
+ next = new_end;
+ }
+
+ free(l->end_node);
+ l->end_node = new_end;
+ }
+
+ /* link 'node' into list before next */
+
+ stdskl_low_link_left(l, next, node); /* NOTE: we must link_left before we link_right due to loss of information */
+ stdskl_low_link_right(l, next, node);
+
+ ++l->size;
+
+ } else { /* overwrite existing match */
+ node = next;
+ memcpy((void*) STDSKL_NKEY(node), key, l->ksize); /* overwrite */
+ memcpy(STDSKL_NVAL(node), val, l->vsize);
+ }
+
+ /* remember first insertion/overwrite */
+
+ if (first_ins == NULL) {
+ first_ins = node;
+ }
+
+ /* advance 'src_it' if so instructed */
+
+ if (advance) {
+ stdit_next(&src_it);
+ }
+ }
+
+ goto stdskl_low_insert_end;
+
+ /* error handling and return */
+
+ stdskl_low_insert_fail:
+ free(node);
+
+ stdskl_low_insert_end:
+ if (it != NULL) {
+ it->type_id = STDSKL_IT_ID;
+ it->impl.skl.node = (first_ins != NULL ? first_ins : l->end_node); /* point to end if no insert/overwrite occurred */
+ it->impl.skl.ksize = l->ksize;
+ it->impl.skl.vsize = l->vsize;
+ }
+
+ return ret;
+}
+
+/************************************************************************************************
+ * stdskl_low_erase: Erase multiple key-value pairs from a list using
+ * either an iterator sequence to delete or a number of elements to
+ * erase.
+ ***********************************************************************************************/
+
+STDINLINE static void stdskl_low_erase(stdskl *l, stdit *b, stdit *e, stdsize num_erase)
+{
+ stdskl_node * ers;
+ stdskl_node * prev = b->impl.skl.node->prevs[0];
+ stdskl_node * next = b->impl.skl.node;
+ stdskl_node * end_node = (e != NULL ? e->impl.skl.node : NULL);
+ stdint8 max_lvl = 0;
+ stdsize erased;
+ stdint8 lvl;
+
+ /* go through [b, b+num_erase) or [b, e) free'ing nodes -- record
+ max height of free'd nodes and how many nodes we erased
+ */
+
+ for (erased = 0; erased != num_erase && next != end_node; ++erased) {
+ STDBOUNDS_CHECK(next != l->end_node);
+
+ if (next->height > max_lvl) {
+ max_lvl = next->height;
+ }
+
+ ers = next;
+ next = next->nexts[0];
+ free(ers);
+ }
+
+ /* update list size */
+
+ l->size -= num_erase;
+
+ /* stitch together the left and right portions of the list */
+
+ ers = next; /* remember where erasure stopped */
+ prev->nexts[0] = next; /* perform base re-linkage */
+ next->prevs[0] = prev;
+
+ for (lvl = 0; lvl != max_lvl; ) { /* run left and run right up to max_lvl height nodes re-linking */
+
+ while (lvl == prev->height) {
+ prev = prev->prevs[lvl];
+ }
+
+ while (lvl == next->height) {
+ next = next->nexts[lvl];
+ }
+
+ ++lvl;
+ prev->nexts[lvl] = next;
+ next->prevs[lvl] = prev;
+ }
+
+ /* advance 'b' and 'e' */
+
+ b->impl.skl.node = ers;
+
+ if (e != NULL) {
+ e->impl.skl.node = ers;
+ }
+}
+
+/************************************************************************************************
+ * stdskl_construct: Construct an initially empty list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_construct(stdskl *l, stdsize ksize, stdsize vsize, stdcmp_fcn kcmp)
+{
+ stdcode ret = STDESUCCESS;
+ stdint8 lvl;
+ stdtime t;
+
+ if (ksize == 0) {
+ ret = STDEINVAL;
+ goto stdskl_construct_fail;
+ }
+
+ l->size = 0;
+ l->ksize = ksize;
+ l->vsize = vsize;
+ l->cmp_fcn = kcmp;
+
+ /* initialize randomization using current system time w/ subsecond precision */
+
+ stdtime_now(&t);
+ stdrand32_dseed(l->seed, stdhcode_sfh(&t, sizeof(t)));
+ l->bits_left = 0;
+
+ /* allocate and init end_node -- NOTE: rest of list must be initialized b4 calling this fcn */
+
+ if ((l->end_node = stdskl_low_create_node(l, 4, NULL, NULL)) == NULL) {
+ ret = STDENOMEM;
+ goto stdskl_construct_fail;
+ }
+
+ /* make end_node reference itself */
+
+ lvl = l->end_node->height;
+
+ do {
+ l->end_node->nexts[lvl] = l->end_node;
+ l->end_node->prevs[lvl] = l->end_node;
+
+ } while (lvl-- != 0);
+
+ goto stdskl_construct_end;
+
+ /* error handling and return */
+
+ stdskl_construct_fail:
+ l->end_node = NULL;
+ l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */
+
+ stdskl_construct_end:
+ return ret;
+}
+
+/************************************************************************************************
+ * stdskl_copy_construct: Construct a copy of a list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_copy_construct(stdskl *dst, const stdskl *src)
+{
+ stdcode ret;
+ stdit it;
+
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(src));
+
+ if ((ret = stdskl_construct(dst, src->ksize, src->vsize, src->cmp_fcn)) != STDESUCCESS) {
+ goto stdskl_copy_construct_fail;
+ }
+
+ if ((ret = stdskl_insert_seq_n(dst, NULL, stdskl_begin(src, &it), src->size, STDFALSE)) != STDESUCCESS) {
+ goto stdskl_copy_construct_fail2;
+ }
+
+ goto stdskl_copy_construct_end;
+
+ /* error handling and return */
+
+ stdskl_copy_construct_fail2:
+ stdskl_destruct(dst);
+
+ stdskl_copy_construct_fail:
+ dst->end_node = NULL;
+ dst->ksize = 0; /* make STDSKL_IS_LEGAL(dst) false */
+
+ stdskl_copy_construct_end:
+ return ret;
+}
+
+/************************************************************************************************
+ * stdskl_destruct: Reclaim a list's resources and invalidate it.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_destruct(stdskl *l)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ stdskl_clear(l);
+ free(l->end_node);
+
+ l->end_node = NULL;
+ l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */
+}
+
+/************************************************************************************************
+ * stdskl_set_eq: Set a list to contain the same contents as another.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_set_eq(stdskl *dst, const stdskl *src)
+{
+ stdcode ret = STDESUCCESS;
+ stdskl cpy;
+
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(dst) && STDSKL_IS_LEGAL(src) &&
+ dst->ksize == src->ksize && dst->vsize == src->vsize &&
+ dst->cmp_fcn == src->cmp_fcn);
+
+ /* TODO: an improvement would be to resize the number of nodes in
+ the table as needed: just slice off or splice on an appropriate
+ sequence of nodes to the begin or end of the list and overwrite
+ all nodes: this would cut down on "unnecessary" memory
+ allocs/frees
+ */
+
+ if (dst == src) {
+ goto stdskl_set_eq_end;
+ }
+
+ if ((ret = stdskl_copy_construct(&cpy, src)) != STDESUCCESS) {
+ goto stdskl_set_eq_end;
+ }
+
+ stdskl_swap(dst, &cpy);
+ stdskl_destruct(&cpy);
+
+ stdskl_set_eq_end:
+ return ret;
+}
+
+/************************************************************************************************
+ * stdskl_swap: Set a l1 to reference l2's sequence and vice versa.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_swap(stdskl *l1, stdskl *l2)
+{
+ stdskl cpy;
+
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l1) && STDSKL_IS_LEGAL(l2));
+
+ STDSWAP(*l1, *l2, cpy);
+}
+
+/************************************************************************************************
+ * stdskl_begin: Get an iterator to the beginning of a list.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_begin(const stdskl *l, stdit *it)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ it->type_id = STDSKL_IT_ID;
+ it->impl.skl.node = l->end_node->nexts[0];
+ it->impl.skl.ksize = l->ksize;
+ it->impl.skl.vsize = l->vsize;
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_last: Get an iterator to the last element of a list.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_last(const stdskl *l, stdit *it)
+{
+ STDBOUNDS_CHECK(l->size != 0);
+
+ return stdit_prev(stdskl_end(l, it));
+}
+
+/************************************************************************************************
+ * stdskl_end: Get an iterator to the sentinel end of a list.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_end(const stdskl *l, stdit *it)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ it->type_id = STDSKL_IT_ID;
+ it->impl.skl.node = l->end_node;
+ it->impl.skl.ksize = l->ksize;
+ it->impl.skl.vsize = l->vsize;
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_get: Get an iterator to an element of a list.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_get(const stdskl *l, stdit *it, stdsize elem_num)
+{
+ STDBOUNDS_CHECK(elem_num <= l->size);
+
+ if (elem_num < (l->size >> 1)) {
+ stdskl_it_advance(stdskl_begin(l, it), elem_num);
+
+ } else {
+ stdskl_it_retreat(stdskl_end(l, it), l->size - elem_num);
+ }
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_is_begin: Return whether or not an iterator refers to the beginning of a list.
+ ***********************************************************************************************/
+
+STDINLINE stdbool stdskl_is_begin(const stdskl *l, const stdit *it)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl));
+
+ return it->impl.skl.node == l->end_node->nexts[0];
+}
+
+/************************************************************************************************
+ * stdskl_is_end: Return whether or not an iterator refers to the end of a list.
+ ***********************************************************************************************/
+
+STDINLINE stdbool stdskl_is_end(const stdskl *l, const stdit *it)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl));
+
+ return it->impl.skl.node == l->end_node;
+}
+
+/************************************************************************************************
+ * stdskl_size: Return the number of key-value pairs a list contains.
+ ***********************************************************************************************/
+
+STDINLINE stdsize stdskl_size(const stdskl *l)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ return l->size;
+}
+
+/************************************************************************************************
+ * stdskl_empty: Return whether or not a list's size is zero.
+ ***********************************************************************************************/
+
+STDINLINE stdbool stdskl_empty(const stdskl *l)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ return l->size == 0;
+}
+
+/************************************************************************************************
+ * stdskl_clear: Set a lists size to zero.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_clear(stdskl *l)
+{
+ stdskl_node * curr;
+ stdskl_node * prev;
+ stdint8 lvl;
+
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ /* run through list destroying all nodes */
+
+ for (curr = l->end_node->nexts[0]; curr != l->end_node; ) {
+ prev = curr;
+ curr = curr->nexts[0];
+ free(prev);
+ }
+
+ /* fix list entries: end_node needs to self reference at all levels and size */
+
+ curr = l->end_node;
+ lvl = l->end_node->height;
+
+ do {
+ curr->prevs[lvl] = curr;
+ curr->nexts[lvl] = curr;
+
+ } while (lvl-- != 0);
+
+ l->size = 0;
+}
+
+/************************************************************************************************
+ * stdskl_find: Find a key-value pair in a list.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_find(const stdskl *l, stdit *it, const void *key)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ if (!stdskl_low_find_right(l, key, STDTRUE, &it->impl.skl.node)) {
+ it->impl.skl.node = l->end_node;
+ }
+
+ it->type_id = STDSKL_IT_ID;
+ it->impl.skl.ksize = l->ksize;
+ it->impl.skl.vsize = l->vsize;
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_lowerb: Find the least element for which kcmp(key, elem) >= 0.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_lowerb(const stdskl *l, stdit *it, const void *key)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ stdskl_low_find_right(l, key, STDFALSE, &it->impl.skl.node);
+
+ it->type_id = STDSKL_IT_ID;
+ it->impl.skl.ksize = l->ksize;
+ it->impl.skl.vsize = l->vsize;
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_upperb: Find the least element for which kcmp(key, elem) > 0.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_upperb(const stdskl *l, stdit *it, const void *key)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ stdskl_low_find_left(l, key, STDFALSE, &it->impl.skl.node);
+ it->impl.skl.node = it->impl.skl.node->nexts[0]; /* found either the last entry for key or the prev entry if none: so get next */
+
+ it->type_id = STDSKL_IT_ID;
+ it->impl.skl.ksize = l->ksize;
+ it->impl.skl.vsize = l->vsize;
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_contains: Return whether or not a list contains a certain key.
+ ***********************************************************************************************/
+
+STDINLINE stdbool stdskl_contains(const stdskl *l, const void *key)
+{
+ stdskl_node * n;
+
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ return stdskl_low_find_right(l, key, STDTRUE, &n);
+}
+
+/************************************************************************************************
+ * stdskl_put: If 'key' already exists in the list, overwrite such an
+ * entry with 'key' and 'value;' otherwise insert 'key' and 'value'
+ * into the list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_put(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint)
+{
+ return stdskl_put_n(l, it, key, val, 1, hint);
+}
+
+/************************************************************************************************
+ * stdskl_put_n: For each (key, val) in [(keys, vals), (keys+num_put, vals+num_put))
+ * perform stdskl_put(l, it, key, val).
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_put_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_put, stdbool hint)
+{
+ stdit b;
+
+ return stdskl_put_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_put, hint);
+}
+
+/************************************************************************************************
+ * stdskl_put_seq: For each (key, val) in [b, e) perform
+ * stdskl_put(l, it, key, val).
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_put_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) &&
+ (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
+ (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
+ (stdit_val_size(b) == l->vsize || l->vsize == 0));
+
+ return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDTRUE, STDTRUE);
+}
+
+/************************************************************************************************
+ * stdskl_put_seq_n: For each (key, val) in [b, b+num_put) perform
+ * stdskl_put(l, it, key, val).
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_put_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_put, stdbool hint)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) &&
+ (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
+ (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
+ (stdit_val_size(b) == l->vsize || l->vsize == 0));
+
+ return stdskl_low_insert(l, it, b, NULL, num_put, hint, STDTRUE, STDTRUE);
+}
+
+/************************************************************************************************
+ * stdskl_insert: Insert a key and value into a list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_insert(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint)
+{
+ return stdskl_insert_n(l, it, key, val, 1, hint);
+}
+
+/************************************************************************************************
+ * stdskl_insert_n: Insert multiple keys and values into a list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_insert_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_insert, stdbool hint)
+{
+ stdit b;
+
+ return stdskl_insert_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_insert, hint);
+}
+
+/************************************************************************************************
+ * stdskl_insert_seq: Insert a sequence of key-value pairs into a list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_insert_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) &&
+ (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
+ (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
+ (stdit_val_size(b) == l->vsize || l->vsize == 0));
+
+ return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDFALSE, STDTRUE);
+}
+
+/************************************************************************************************
+ * stdskl_insert_seq_n: Insert a sequence of key-value pairs into a list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_insert_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_insert, stdbool hint)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) &&
+ (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) &&
+ (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) &&
+ (stdit_val_size(b) == l->vsize || l->vsize == 0));
+
+ return stdskl_low_insert(l, it, b, NULL, num_insert, hint, STDFALSE, STDTRUE);
+}
+
+/************************************************************************************************
+ * stdskl_insert_rep: Repeatedly insert a key-value pair into a list.
+ ***********************************************************************************************/
+
+STDINLINE stdcode stdskl_insert_rep(stdskl *l, stdit *it, const void *key, const void *val, stdsize num_times, stdbool hint)
+{
+ stdit b;
+
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) &&
+ (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))));
+
+ return stdskl_low_insert(l, it, stdit_pptr(&b, key, val, l->ksize, l->vsize), NULL, num_times, hint, STDFALSE, STDFALSE);
+}
+
+/************************************************************************************************
+ * stdskl_erase: Erase a key-value pair from a list.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_erase(stdskl *l, stdit *it)
+{
+ stdskl_erase_n(l, it, 1);
+}
+
+/************************************************************************************************
+ * stdskl_erase_n: Erase multiple key-value pairs from a list.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_erase_n(stdskl *l, stdit *it, stdsize num_erase)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl));
+
+ stdskl_low_erase(l, it, NULL, num_erase);
+}
+
+/************************************************************************************************
+ * stdskl_erase_seq: Erase a sequence from a list.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_erase_seq(stdskl *l, stdit *b, stdit *e)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(b) && STDSKL_IT_IS_LEGAL(l, &b->impl.skl) && (stdit_eq(b, e) || STDTRUE));
+
+ stdskl_low_erase(l, b, e, (stdsize) -1);
+}
+
+/************************************************************************************************
+ * stdskl_erase_key: Erase all entries of a key from a list.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_erase_key(stdskl *l, const void *key)
+{
+ stdit it;
+
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ stdskl_lowerb(l, &it, key);
+
+ while (it.impl.skl.node != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(it.impl.skl.node)) == 0) {
+ stdskl_erase(l, &it); /* advances 'it' */
+ }
+}
+
+/************************************************************************************************
+ * stdskl_dseed: Set a skiplist's random number generator with a deterministic value.
+ ***********************************************************************************************/
+
+STDINLINE void stdskl_dseed(stdskl *l, const void *seed, stdsize sizeof_seed)
+{
+ STDSAFETY_CHECK(STDSKL_IS_LEGAL(l));
+
+ stdrand32_dseed(l->seed, stdhcode_sfh(seed, sizeof_seed));
+ l->bits_left = 0;
+}
+
+/************************************************************************************************
+ * stdskl_it_key: Get a key from an iterator.
+ ***********************************************************************************************/
+
+STDINLINE const void *stdskl_it_key(const stdit *it)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ return STDSKL_NKEY(it->impl.skl.node);
+}
+
+/************************************************************************************************
+ * stdskl_it_key_size: Get the size in bytes of the keys to which 'it' refers.
+ ***********************************************************************************************/
+
+STDINLINE stdsize stdskl_it_key_size(const stdit *it)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ return it->impl.skl.ksize;
+}
+
+/************************************************************************************************
+ * stdskl_it_val: Get a value from an iterator.
+ ***********************************************************************************************/
+
+STDINLINE void *stdskl_it_val(const stdit *it)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ return (void*) (it->type_id == STDSKL_IT_ID ? STDSKL_NVAL(it->impl.skl.node) : STDSKL_NKEY(it->impl.skl.node));
+}
+
+/************************************************************************************************
+ * stdskl_it_val_size: Get the size in bytes of the values to which 'it' refers.
+ ***********************************************************************************************/
+
+STDINLINE stdsize stdskl_it_val_size(const stdit *it)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ return (it->type_id == STDSKL_IT_ID ? it->impl.skl.vsize : it->impl.skl.ksize);
+}
+
+/************************************************************************************************
+ * stdskl_it_eq: Compare two iterators for equality (refer to the same element).
+ ***********************************************************************************************/
+
+STDINLINE stdbool stdskl_it_eq(const stdit *it1, const stdit *it2)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it1) && STDIT_SKL_IS_LEGAL(it2) &&
+ it1->impl.skl.ksize == it2->impl.skl.ksize &&
+ it1->impl.skl.vsize == it2->impl.skl.vsize);
+
+ return it1->impl.skl.node == it2->impl.skl.node;
+}
+
+/************************************************************************************************
+ * stdskl_it_next: Advance 'it' towards end by one position.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_it_next(stdit *it)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ it->impl.skl.node = it->impl.skl.node->nexts[0];
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_it_advance: Advance 'it' towards end by 'num_advance' positions.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_it_advance(stdit *it, stdsize num_advance)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ while (num_advance-- != 0) {
+ it->impl.skl.node = it->impl.skl.node->nexts[0];
+ }
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_it_prev: Advance 'it' towards begin by one position.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_it_prev(stdit *it)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ it->impl.skl.node = it->impl.skl.node->prevs[0];
+
+ return it;
+}
+
+/************************************************************************************************
+ * stdskl_it_retreat: Advance 'it' towards end by 'num_retreat' positions.
+ ***********************************************************************************************/
+
+STDINLINE stdit *stdskl_it_retreat(stdit *it, stdsize num_retreat)
+{
+ STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it));
+
+ while (num_retreat-- != 0) {
+ it->impl.skl.node = it->impl.skl.node->prevs[0];
+ }
+
+ return it;
+}
More information about the Spread-cvs
mailing list