util/skiplist.h

/* 
 *
 * Thread-safe Skiplist Using Integer Identifiers
 * Copyright 1998-2000 Scott Shambarger (scott@shambarger.net)
 *
 * This software is open source. Permission to use, copy, modify, and
 * distribute this software for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies.  No
 * warranty of any kind is expressed or implied.  Use at your own risk.
 *
 * 1/14/2001 blong
 *   Made it use neo errs... probably need to check locking functions
 *   for error returns...
 *
 */

#ifndef __SKIPLIST_H_
#define __SKIPLIST_H_

#include "util/neo_err.h"

__BEGIN_DECLS

/* 
 * Larger values of <root> means fewer levels and faster lookups,
 * but more variability in those lookup times (range limited from 2 to 4).
 *
 * <maxLevel> should be calculated from expected list size using (^ = power):
 *
 *     <root> ^ <maxLevel> == expected # of items 
 *
 * I've capped <maxLevel> at 20, which would be good for a minimum of
 * 1 million items on lists with <root> == 2.
 *
 *
 * Example
 *    skipNewList(&(my_wdb->ondisk), 0, 4, 2, 0, NULL, NULL);
 */
#define SKIP_MAXLEVEL 20

/* SKIP LIST TYPEDEFS */
typedef struct skipList_struct *skipList;
typedef void (*skipFreeValue)(void *value, void *ctx);

NEOERR *skipNewList(skipList *skip, int threaded, int root, int maxLevel,
                     int flushLimit, skipFreeValue freeValue, void *ctx);
/*
 * Function:    skipNewList - create a skip list.
 * Description: Returns a new skip list.  If <threaded> is true, list is
 *              multi-thread safe.  <root> and <maxLevel> determine 
 *              performance and expected size (see discussion above).
 *              <flushLimit> is for threaded lists and determines the
 *              maximum number of deleted items to keep cached during
 *              concurrent searches.  Once the limit is reached, new 
 *              concurrent reads are blocked until all deleted items are 
 *              flushed.
 * Input:       threaded - true if list should be thread-safe.
 *              root - performance parameter (see above).
 *              maxLevel - performance parameter (see above).
 *              flushLimit - max deleted items to keep cached before
 *                forcing a flush.
 *              freeValue - callback made whenever a value is flushed.
 *              ctx - context to pass to <freeValue>.
 * Output:      None.
 * Return:      New skip list, NULL on error.
 * MT-Level:    Safe.
 */

void skipFreeList(skipList list);
/*
 * Function:    skipFreeList - free a skip list.
 * Description: Release all resources used by <list> including all key/value
 *              pairs.
 * Input:       list - list to free.
 * Output:      None.
 * Return:      None.
 * MT-Level:    Safe for unique <list>.
 */

void *skipNext(skipList list, UINT32 *pkey, void **plock);
/*
 * Function:    skipNext - find next item.
 * Description: Searches in list <list> for item with key next larger
 *              that the one in <pkey>, and returns its value if 
 *              found, or NULL if not.  If <plock> is non-NULL, then
 *              the lock returned in <plock> will be associated with
 *              the returned value.  Until this lock is passed to
 *              skipRelease(), the value will not be freed with the
 *              freeValue callback (see skipNewList()).
 * Input:       list - list to search in.
 *              pkey - pointer to previous key (0 to start).
 *              plock - place for value lock (or NULL).
 * Output:      pkey - set to new key.
 *              plock - set to value lock.
 * Return:      Value associated with new <pkey>, or NULL last item.
 * MT-Level:    Safe if <list> thread-safe.
 */

void *skipSearch(skipList list, UINT32 key, void **plock);
/*
 * Function:    skipSearch - search a skip list.
 * Description: Searches for <key> in <list>, and returns value if 
 *              found, or NULL if not.  If <plock> is non-NULL, then
 *              the lock returned in <plock> will be associated with
 *              the returned value.  Until this lock is passed to
 *              skipRelease(), the value will not be freed with the
 *              freeValue callback (see skipNewList()).
 * Input:       list - list to search in.
 *              key - key to look for.
 *              plock - place for value lock (or NULL).
 * Output:      plock - set to value lock.
 * Return:      Value associated with <key>, or NULL if <key> not found.
 * MT-Level:    Safe if <list> thread-safe.
 */

void skipRelease(skipList list, void *lock);
/*
 * Function:    skipRelease - release lock on value.
 * Description: Releases the lock on the value associated with <lock>.  Once
 *              the lock is released, the freeValue callback can be called
 *              and the item freed (see skipNewList()).
 * Input:       list - list containing value to release.
 *              lock - lock to release.
 * Output:      None.
 * Return:      None.
 * MT-Level:    Safe if <list> thread-safe.
 */

NEOERR *skipInsert(skipList list, UINT32 key, void *value, int allowUpdate);
/*
 * Function:    skipInsert - insert an item.
 * Description: Inserts the <key>/<value> pair into the <list>.
 *              Key values 0 and -1 are reserved (and illegal).
 *              If key is already in list, and <allowUpdate> is true, 
 *              value is updated, otherwise SKIPERR_EXISTS is returned.
 * Input:       list - list to add pair to.
 *              key - key identifying <value>.
 *              value - value to store (may NOT be NULL)
 * Output:      None.
 * Return:      NERR_ASSERT on invalid key or value
 *              NERR_DUPLICATE if allowUpdate is 0 and key exists
 *              NERR_NOMEM
 * MT-Level:    Safe if <list> thread-safe.
 */

void skipDelete(skipList list, UINT32 key);
/*
 * Function:    skipDelete - delete an item.
 * Description: Delete the item associated with <key> from <list>.
 * Input:       list - list to delete item from.
 *              key - key identifying value to delete.
 * Output:      None.
 * Return:      None.
 * MT-Level:    Safe if <list> thread-safe.
 */

__END_DECLS

#endif                                                   /* __SKIPLIST_H_ */