ctables/skiplists/jsw_slib.c

// $Id$

/*
  Classic skip list library

    > Created (Julienne Walker): April 11, 2004
    > Updated (Julienne Walker): August 19, 2005

    based on code released to the publicdata domain by Julienne Walker
*/
#include "jsw_rand.h"
#include "jsw_slib.h"
#ifdef WITH_SHARED_TABLES
#include "shared.h"
#endif

#ifdef __cplusplus
#include <climits>
#include <cstdlib>

using std::size_t;
#else
#include <limits.h>
#include <stdlib.h>
#endif

#define DUMPER 1

typedef struct jsw_node {
  ctable_BaseRow         *row;      /* Data row with combined key */
  size_t                  height;   /* Column height of this node */
  struct jsw_node        *next[];   /* Dynamic array of next links */
} jsw_node_t;

// dynamic shared elements
typedef struct jsw_pub {
  jsw_node_t  *head; /* Full height header node */
  size_t       curh; /* Tallest available column */
  size_t       size; /* Number of row at level 0 */
} jsw_pub_t;

// statically defined and private elements
struct jsw_skip {
  int          id; /* 0 for owner, pid for shared reader */
  jsw_pub_t   *publicdata; /* shared data */
  jsw_node_t  *curl; /* Current link for traversal */
  size_t       maxh; /* Tallest possible column */
  cmp_f        cmp;  /* User defined row compare function */
#ifdef WITH_SHARED_TABLES
  shm_t       *share; /* Shared memory this table belongs to */
#else
  void        *share;
#endif
  jsw_node_t **fix;  /* Update array */
};

/*
  Weighted random level with probability 1/2.
  (For better distribution, modify with 1/3)

  Implements a tuned bit stream algorithm.
*/
INLINE
static size_t rlevel ( size_t max )
{
  static size_t bits = 0;
  static size_t reset = 0;
  size_t h, found = 0;

  for ( h = 0; !found; h++ ) {
    if ( reset == 0 ) {
      bits = jsw_rand();
// printf("bits %lx\n", bits);

      // reset = sizeof ( size_t ) * CHAR_BIT - 1;
      reset = 31;

// printf("bits %lx, reset %d\n", (long)bits, (int)reset);
    }

    /*
      For 1/3 change to:

      found = bits % 3;
      bits = bits / 3;
    */
    found = bits & 1;
    bits = bits >> 1;
    --reset;
// printf("found %d bits %lx reset %d h %d\n", (int)found, (long)bits, (int)reset, (int)h);
  }
// printf("rlh %d\n", (int) h);

  if ( h >= max )
// printf("big h %d\n", (int) h);
    h = max - 1;

  return h;
}

//
// new_node - construct an empty new node, does not make a copy of the row
//
INLINE
static jsw_node_t *new_node ( ctable_BaseRow *row, size_t height, void *share )
{
  jsw_node_t *node;
  size_t i;

#ifdef WITH_SHARED_TABLES
  if(share) {
    node  = (jsw_node_t *)shmalloc ((shm_t*)share, sizeof (jsw_node_t) + height * sizeof (jsw_node_t *) );
    if(!node) {
      //if(DUMPER) shmdump(share);
      Tcl_Panic("Can't allocate shared memory for skiplist");
    }
  } else
#endif
    node  = (jsw_node_t *)ckalloc ( sizeof (jsw_node_t) + height * sizeof (jsw_node_t *) );

  node->row = row;

  node->height = height;

  for ( i = 0; i < height; i++ )
    node->next[i] = NULL;

  return node;
}

//
// free_node - free a skip list node but not the row associated with it
//
INLINE
static void free_node ( jsw_node_t *node, void *share )
{
#ifdef WITH_SHARED_TABLES
  if(share)
    shmfree((shm_t *)share, (char *)node);
  else
#endif
    ckfree ( (char *)node );
}

//
// locate - find an existing row, or the position before where it would be
//
INLINE
static jsw_node_t *locate ( jsw_skip_t *skip, ctable_BaseRow *row )
{
  jsw_node_t *p = skip->publicdata->head;
  cmp_f       cmp = skip->cmp;
  size_t i;
  jsw_node_t *next;

  for ( i = skip->publicdata->curh; i < (size_t)-1; i-- ) {
    while ( (next = p->next[i]) != NULL ) {
      if ( cmp ( row, next->row ) <= 0 ) {
        break;
      }

      p = next;
    }

    skip->fix[i] = p;
  }

  return p;
}

//
// jsw_private - return a private version of a skiplist in shared memory
//
jsw_skip_t *jsw_private ( jsw_skip_t *skip, size_t max, cmp_f cmp, void *share, int id )
{
  jsw_skip_t *new_skip = skip;

  if(id == 0) {
    // If this is a new skiplist, initialize skiplist structure
    skip->id = id;
    skip->fix = NULL;
    skip->curl = NULL;
  } else if(skip->id != id) {
    // If this isn't my skiplist, allocate new skiplist structure
    new_skip = (jsw_skip_t *)ckalloc(sizeof *skip);

    new_skip->curl = skip->curl;
    new_skip->id = id;
    new_skip->fix = NULL;
    new_skip->publicdata = skip->publicdata;

    skip = new_skip;
  }

  // initialise dynamic private data if necessary
  if (!skip->fix) {
    skip->fix = (jsw_node_t **)ckalloc ( max * sizeof *skip->fix );
  }

  // Fill in static private data
  skip->maxh = max;
#ifdef WITH_SHARED_TABLES
  skip->share = (shm_t*) share;
#else
  skip->share = share;
#endif
  skip->cmp = cmp;
  return skip;
}

//
// free private copy of skiplist only
//
void jsw_free_private_copy(jsw_skip_t *skip)
{
    if(skip->fix)
	ckfree((char *)skip->fix);
    ckfree((char *)skip);
}

//
// clone skiplist if needed
//
jsw_skip_t *jsw_private_copy(jsw_skip_t *skip, int id, cmp_f cmp)
{
    if(skip->id != id)
	return jsw_private(skip, skip->maxh, cmp?cmp:skip->cmp, skip->share, id);
    return NULL;
}

//
// jsw_sinit - initialize a skip list
//
void jsw_sinit ( jsw_skip_t *skip, size_t max, cmp_f cmp, void *share)
{
#ifdef WITH_SHARED_TABLES
  if(share) {
    skip->publicdata = (jsw_pub_t *)shmalloc ( (shm_t *)share, sizeof *skip->publicdata );
    if(!skip) {
      //if(DUMPER) shmdump(share);
      Tcl_Panic("Can't allocate shared memory for skiplist");
    }
  } else
#endif
    skip->publicdata = (jsw_pub_t *)ckalloc ( sizeof *skip->publicdata );

  skip->publicdata->head = new_node ( NULL, ++max, share );

  skip->publicdata->curh = 0;
  skip->publicdata->size = 0;

  // We're creating this skiplist, our "id" is zero
  // (now fills in skip->maxh, skip->curl)
  jsw_private(skip, max, cmp, share, 0);

  jsw_seed ( jsw_time_seed() );
}

//
// jsw_snew - allocate and initialize a new skip list
//
jsw_skip_t *jsw_snew ( size_t max, cmp_f cmp, void *share)
{
  jsw_skip_t *skip;

#ifdef WITH_SHARED_TABLES
  if(share) {
    skip = (jsw_skip_t *)shmalloc ( (shm_t *)share, sizeof *skip );
    if(!skip) {
      //if(DUMPER) shmdump(share);
      Tcl_Panic("Can't allocate shared memory for skiplist");
    }
  } else
#endif
    skip = (jsw_skip_t *)ckalloc ( sizeof *skip );

  jsw_sinit (skip, max, cmp, share);

  return skip;
}

//
// jsw_sdelete_skiplist - delete the entire skip list
//
// you have to delete your own row data
//
void jsw_sdelete_skiplist ( jsw_skip_t *skip, int final )
{
  jsw_node_t *it = skip->publicdata->head->next[0];
  jsw_node_t *save;

  while ( it != NULL ) {
    save = it->next[0];
#ifdef WITH_SHARED_TABLES
    if(!final || !skip->share)
#endif
      free_node ( it, skip->share );
    it = save;
  }

  free_node ( skip->publicdata->head, skip->share );

  ckfree ( (char *)skip->fix );

#ifdef WITH_SHARED_TABLES
  if(skip->share) {
    if(!final)
      shmfree(skip->share, (char *)skip);
  } else
#endif
    ckfree ( (char *)skip );
}

//
// jsw_sfind - given a skip list and a row, return the corresponding
//             skip list node pointer or NULL if none is found.
//
INLINE
void *jsw_sfind ( jsw_skip_t *skip, ctable_BaseRow *row )
{
  jsw_node_t *p = locate ( skip, row )->next[0];

  skip->curl = p;

  if ( p != NULL && skip->cmp ( row, p->row ) == 0 )
    return p;

  return NULL;
}

//
// jsw_sfind_equal_or_greater - given a skip list and a row, return the
//     corresponding skip list node pointer that matches the specified
//     row or exceeds it.
//
INLINE
void *jsw_sfind_equal_or_greater ( jsw_skip_t *skip, ctable_BaseRow *row )
{
  jsw_node_t *p = locate ( skip, row )->next[0];
  cmp_f       cmp = skip->cmp;

//printf("find_equal_or_greater row %8lx, p %8lx ", (long unsigned int)row, (long unsigned int)p);

  while (p !=NULL && cmp (p->row, row) < 0) {
//printf("p->%8lx ", (long unsigned int)p);
      p = p->next[0];
  }

//printf(" *%d* ", cmp (p->row, row));
//printf("skip->curl %8lx\n", (long unsigned int)p);
  skip->curl = p;

  return p;
}

//
// jsw_findlast - find a row with the lexically highest key in the table
//
INLINE
void *jsw_findlast ( jsw_skip_t *skip)
{
  jsw_node_t *p = skip->publicdata->head;
  size_t i;
  jsw_node_t *next;

  for ( i = skip->publicdata->curh; i < (size_t)-1; i-- ) {
    while ( (next = p->next[i]) != NULL ) {
      p = next;
    }
  }

  skip->curl = p;
  return p;
}

//
// jsw_sinsert - insert row into the skip list if it's not already there
//
// forces there to be no duplicate row by failing if a matching row is found
//
INLINE
int jsw_sinsert ( jsw_skip_t *skip, ctable_BaseRow *row )
{
  // void *p = locate ( skip, row )->row;
  jsw_node_t *p = locate ( skip, row )->next[0];
  cmp_f       cmp = skip->cmp;

  // if we got something and it compares the same, it's already there
  if ( p != NULL && cmp ( row, p->row ) == 0 ) {
    return 0;
  } else {
    // it's new
    size_t h = rlevel ( skip->maxh );
    jsw_node_t *it;

    it = new_node ( row, h, skip->share );

    /* Raise height if necessary */
    if ( h > skip->publicdata->curh ) {
// printf("raising the height from %d to %d, size %d\n", (int)skip->publicdata->curh, (int)h, (int)skip->publicdata->size);
      h = ++skip->publicdata->curh;
      skip->fix[h] = skip->publicdata->head;
    }

    /* Build skip links */
    while ( --h < (size_t)-1 ) {
      it->next[h] = skip->fix[h]->next[h];
      skip->fix[h]->next[h] = it;
    }
  }

  skip->publicdata->size++;
  return 1;
}

//
// jsw_sinsert_linked - insert row into the skip list if it's not already
// there.  if it is already there, link this row into the skip list.
//
INLINE
int jsw_sinsert_linked ( jsw_skip_t *skip, ctable_BaseRow *row , int nodeIdx, int unique)
{
  // void *p = locate ( skip, row )->row;
  jsw_node_t *p = locate ( skip, row )->next[0];

  if ( p != NULL && skip->cmp ( row, p->row ) == 0 ) {
    // we found a matching skip list entry

    // if dups aren't allowed, don't do anything and return 0
    if (unique) {
        return 0;
    }

    // dups are allowed, insert this guy
    ctable_ListInsertHead (&p->row, row, nodeIdx);
  } else {
    // no matching skip list entry

    // insert the new node
    size_t h = rlevel ( skip->maxh );
    jsw_node_t *it;

// printf("h %d\n", (int)h);

    it = new_node ( row, h, skip->share );

    // Throw away the row we just inserted with new_node! Yes, we mean to do this.
    ctable_ListInit (&it->row, __FILE__, __LINE__);

    ctable_ListInsertHead (&it->row, row, nodeIdx);

    /* Raise height if necessary */
    if ( h > skip->publicdata->curh ) {
// printf("raising the height from %d to %d, size %d\n", (int)skip->publicdata->curh, (int)h, (int)skip->publicdata->size);
      h = ++skip->publicdata->curh;
      skip->fix[h] = skip->publicdata->head;
    }

    /* Build skip links */
    while ( --h < (size_t)-1 ) {
      it->next[h] = skip->fix[h]->next[h];
      skip->fix[h]->next[h] = it;
    }
  }

  skip->publicdata->size++;
  return 1;
}

//
// jsw_serase - locate an row in the skip list.  if it exists, delete it.
//
// return 1 if it deleted and 0 if no row matched
//
// you have to release the node externally to this
//
int jsw_serase ( jsw_skip_t *skip, ctable_BaseRow *row )
{
  jsw_node_t *p = locate ( skip, row )->next[0];

  if ( p == NULL || skip->cmp ( row, p->row ) != 0 )
    return 0;
  else {
    size_t i;

    // fix skip list pointers that point directly to me by traversing
    // the fix list of stuff from the locate
    for ( i = 0; i < skip->publicdata->curh; i++ ) {
      if ( skip->fix[i]->next[i] != p )
        break;

      skip->fix[i]->next[i] = p->next[i];
    }

    // free the node
    free_node ( p, skip->share );
    skip->publicdata->size--;

    /* Lower height if necessary */
    while ( skip->publicdata->curh > 0 ) {
      if ( skip->publicdata->head->next[skip->publicdata->curh - 1] != NULL )
        break;

      --skip->publicdata->curh;
    }
  }

  /* Erasure invalidates traversal markers */
  jsw_sreset ( skip );

  return 1;
}

void
jsw_dump_node (const char *s, jsw_skip_t *skip, jsw_node_t *p, int indexNumber) {
    int             height;
    int             i;
    ctable_BaseRow *walkRow;
    cmp_f           cmp = skip->cmp;

    height = p->height;
    printf("%8lx '%s' height %d\n    list ", (long unsigned int)p, s, height);

    if (indexNumber < 0) {
        printf ("(head)");
    } else {
	CTABLE_LIST_FOREACH (p->row, walkRow, indexNumber) {
	    printf("%8lx ", (long unsigned int)walkRow);
	    if ( cmp ( p->row, walkRow ) != 0 ) {
	        Tcl_Panic ("index hosed - value in dup list doesn't match others, p->row == 0x%08lx, walkRow == 0x%08lx", (long)p->row, (long)walkRow);
	    }
	}
    }
    printf("\n");

    for ( i = 0; i < height; i++ ) {
        printf ("%8lx ", (long unsigned int)p->next[i]);
    }
    printf("\n");
}

void
jsw_dump (const char *s, jsw_skip_t *skip, int indexNumber) {
    jsw_node_t *p = skip->curl;

    jsw_dump_node (s, skip, p, indexNumber);
}

void
jsw_dump_head (jsw_skip_t *skip) {
    jsw_node_t *p = skip->publicdata->head;

    jsw_dump_node ("HEAD", skip, p, -1);
}

//
// jsw_ssize - return the size of the skip table
//
size_t jsw_ssize ( jsw_skip_t *skip )
{
  return skip->publicdata->size;
}

//
// jsw_reset - invalidate traversal markers by resetting the current link
//             for traversal to the first element in the list
//
void jsw_sreset ( jsw_skip_t *skip )
{
  skip->curl = skip->publicdata->head->next[0];
}

//
// jsw_sreset_head - like jsw_sreset except points to head instead of
// what head points to so jsw_snext can be called in a while loop to traverse
//
void jsw_sreset_head ( jsw_skip_t *skip )
{
  skip->curl = skip->publicdata->head;
}

//
// jsw_srow - get row pointed to by the the current link or NULL if none
//
INLINE
ctable_BaseRow *jsw_srow ( jsw_skip_t *skip )
{
  return skip->curl == NULL ? NULL : skip->curl->row;
}

//
// jsw_snext - move the current link to the next row, returning 1 if there
//             is a next row and a 0 if there isn't
//
INLINE int
jsw_snext ( jsw_skip_t *skip )
{
  jsw_node_t *curl = skip->curl;
  jsw_node_t *next = curl->next[0];
  return ( skip->curl = next ) != NULL;
}

// vim: set ts=8 sw=4 sts=4 noet :