/* 

Example of Skip List source code for C:

Skip Lists are a probabilistic alternative to balanced trees, as
described in the June 1990 issue of CACM and were invented by 
William Pugh in 1987. 

This file contains source code to implement a dictionary using 
skip lists and a test driver to test the routines.

A couple of comments about this implementation:
  The routine randomLevel has been hard-coded to generate random
  levels using p=0.25. It can be easily changed.
  
  The insertion routine has been implemented so as to use the
  dirty hack described in the CACM paper: if a random level is
  generated that is more than the current maximum level, the
  current maximum level plus one is used instead.

  Levels start at zero and go up to MaxLevel (which is equal to
	(MaxNumberOfLevels-1).

The compile flag allowDuplicates determines whether or not duplicates
are allowed. If defined, duplicates are allowed and act in a FIFO manner.
If not defined, an insertion of a value already in the file updates the
previously existing binding.

BitsInRandom is defined to be the number of bits returned by a call to
random(). For most all machines with 32-bit integers, this is 31 bits
as currently set. 

*/

#include <stdio.h>
#include "list.h"
#include "db_list.h"

db_node NIL;

int randomsLeft;
int randomBits;

/* db_init - defines NIL and initializes the random bit source */ 
db_init() { 
  char *ckalloc();
  
  NIL = db_newNodeOfLevel(0);
  NIL->key = 0x7fffffff;
  NIL->value = NULL;
  NIL->forward[0] = NIL;
  randomBits = random();
  randomsLeft = BitsInRandom/2;
}

/* db_newList - create a new list */
db_list db_newList() {
  db_list l;
  int i;
  char *ckalloc();

  l = (db_list)ckalloc(sizeof(struct db_listStructure));
  l->level = 0;
  l->header = db_newNodeOfLevel(MaxNumberOfLevels);
  l->header->key = -1;
  l->header->value = NULL;
  l->header->back = NULL;
  for(i=0;i<MaxNumberOfLevels;i++) l->header->forward[i] = NIL;
  return(l);
  }

/* idb_newList - create a new list */
idb_list idb_newList() {
  idb_list l;
  int i;
  char *ckalloc();

  l = (idb_list)ckalloc(sizeof(struct idb_listStructure));
  l->level = 0;
  l->header = db_newNodeOfLevel(IMaxNumberOfLevels);
  l->header->key = -1;
  l->header->value = NULL;
  l->header->back = NULL;
  for(i=0;i<IMaxNumberOfLevels;i++) l->header->forward[i] = NIL;
  return(l);
  }

/* db_reset_pos - reset cur_p */
void db_reset_pos(db_list l)
{
	register int k;
	register db_node p;

	p = l->header;
	for (k = 0; k <= l->level; ++k)   l->update[k] = p;
}

/* db_sreset_pos - reset l->update[0] */
db_sreset_pos(db_list l)
{
	l->update[0] = l->header;
}

/* idb_reset_pos - reset cur_p */
idb_reset_pos(idb_list l)
{
	l->update = l->header;
}

/* db_freeList - free the space of the list */
void db_freeList(db_list l) 
  {
  register db_node p,q;
  p = l->header;
  do {
    q = p->forward[0];
    decre(p->value);
    free(p);
    p = q; }
    while (p!=NIL);
  free(l);
  }

/* idb_freeList - free the space of the list */
idb_freeList(idb_list l) 
  {
  register db_node p,q;
  p = l->header;
    while (p != NIL) {
    q = p->forward[0];
    free(p);
    p = q; }
  free(l);
  }

/* db_randomLevel - return a random level */
int db_randomLevel(int maxl)
  {register int level = 0;
   register int b;
   do {
    b = randomBits&3;
    if (!b) level++;
    randomBits>>=2;
    if (--randomsLeft == 0) {
        randomBits = random();
        randomsLeft = BitsInRandom/2;
        }
    } while (!b);
    return(level>maxl ? maxl : level);
    }

/* db_insert - insert a new node to the list */
void db_insert(idb_list l, keyType key, valueType value) 
  {
  register int k;
  register db_node p,q;
  db_node update[IMaxNumberOfLevels];
  char *ckalloc();

  if (!l) return;
  p = l->header;
  k = l->level;
  do {
	while (q = p->forward[k], q->key < key) p = q;
	update[k] = p;
	} while(--k>=0);


    k = db_randomLevel(IMaxLevel);
    if (k>l->level) {
	k = ++l->level;
	update[k] = l->header;
	}
    q = db_newNodeOfLevel(k);
    q->key = key;
    q->value = value;
    do {
	p = update[k];
	q->forward[k] = p->forward[k];
	p->forward[k] = q;
	} while(--k>=0);
    q->back = update[0];
    (q->forward[0])->back = q;
    return;
    }

/* db_delete - delete a node from the list by key */
void db_delete(idb_list l, keyType key) 
  {
  register int k,m;
  register db_node p,q;
  db_node update[IMaxNumberOfLevels];

  if (!l) return;
  p = l->header;
  k = m = l->level;
  do {
	while (q = p->forward[k], q->key < key) p = q;
	update[k] = p;
	} while(--k>=0);

  for(k=0; k<=m && (p=update[k])->forward[k] == q; k++) 
    p->forward[k] = q->forward[k];
  (q->forward[0])->back = p;
  free(q);
  while( l->header->forward[m] == NIL && m > 0 )
       m--;
  l->level = m;
  }

/* db_rsearch - search a node in the list by key */
/*	     find p s.t. p->key < key <= (p->forward[0])->key */
valueType db_rsearch(db_list l, keyType key)
  {
  register int k;
  register db_node p,q;
  p = l->header;
  k = l->level;
  do {
	while (q = p->forward[k], q->key < key) p = q;
	l->update[k] = p;
	} while(--k>=0);
  return(p->value);
  }

/* db_rsearch_next - search from cur_p */
/*	     find p s.t. p->key < key <= (p->forward[0])->key */
valueType db_rsearch_next(db_list l, keyType key)
  {
  register int k;
  register db_node p,q;
  k = l->level;
  p = l->update[k];
  do {
	while (q = p->forward[k] ,  q->key < key) p = q;
	l->update[k] = p;
	} while(--k>=0);
  return(p->value);
  }

/* db_lsearch - search a node in the list by key */
/*	     find p s.t. p->key <= key < (p->forward[0])->key */
valueType db_lsearch(db_list l, keyType key)
  {
  register int k;
  register db_node p,q;
  p = l->header;
  k = l->level;
  do {
	while (q = p->forward[k], q->key <= key) p = q;
	l->update[k] = p;
	} while(--k>=0);
  return(p->value);
  }

/* db_lsearch_next - search from cur_p */
/*	     find p s.t. p->key <= key < (p->forward[0])->key */
valueType db_lsearch_next(db_list l, keyType key)
  {
  register int k;
  register db_node p,q;
  k = l->level;
  p = l->update[k];
  do {
	while (q = p->forward[k] ,  q->key <= key) p = q;
	l->update[k] = p;
	} while(--k>=0);
  return(p->value);
  }

/* db_cur_key - return the key of the node pointed by the pointer cur_p */
keyType db_cur_key(db_list l)
{
	return((l->update[0])->key);
}

/* db_update_node - update the value of the node pointed by cur_p */
void db_update_node(db_list l, valueType value)
{
	(l->update[0])->value = value;
}

/* db_next_key - return the key of the node next to the node pointed by cur_p */
keyType db_next_key(db_list l)
{
	db_node p;

	p = (l->update[0])->forward[0];
	if (p != NIL) return(p->key);
	else return(-1);
}

/* db_next_val - return the value of the node next to the node pointed by cur_p */
valueType db_next_val(db_list l)
{
	db_node p;

	p = (l->update[0])->forward[0];
	if (p != NIL) return(p->value);
	else return(NULL);
}

/* db_prev_key - return the key of the node before the node pointed by cur_p */
keyType db_prev_key(db_list l)
{
	db_node p;

	p = (l->update[0])->back;
	if (p) return(p->key);
	else return(-1);
}

/* db_prev_val - return the value of the node before the node pointed by cur_p */
valueType db_prev_val(db_list l)
{
	db_node p;

	p = (l->update[0])->back;
	if (p) return(p->value);
	else return(NULL);
}

/* db_key_next - move l->cur_p right */
db_key_next(db_list l)
{
	db_node p, q;
	int k;

	p = l->update[0];
	q = p->forward[0];
	if (q == NIL) return (-1);
	else {
		for (k = 0; k <= l->level && (((l->update[k])->forward[k])
			== q); k++)   l->update[k] = q;
		return(q->key);
	}
}

/* idb_key_next - move l->cur_p right */
idb_key_next(idb_list l)
{
	db_node p, q;
	int k;

	p = l->update;
	q = p->forward[0];
	if (q == NIL) return (-1);
	else {
		l->update = q;
		return(q->key);
	}
}

/* db_next - move l->cur_p right */
valueType db_next(db_list l)
{
	db_node p, q;
	int k;

	p = l->update[0];
	q = p->forward[0];
	if (q == NIL) return (NULL);
	else {
		for (k = 0; k <= l->level && (((l->update[k])->forward[k])
			== q); k++)   l->update[k] = q;
		return(q->value);
	}
}

/* db_snext - search sequencially */
valueType db_snext(db_list l)
{
	db_node p, q;
	int k;

	p = l->update[0];
	q = p->forward[0];
	l->update[0]=q;
	return(q->value);
}

/*db_delete_next - delete the node next to the node pointed by cur_p */
void db_delete_next(db_list l)
{
	register int k,m;
	register db_node p,q;

	m = l->level;
	q = (l->update[0])->forward[0];
	if (q == NIL) return;
	for (k=0; k<=m && (p=l->update[k])->forward[k] == q; k++)
		p->forward[k] = q->forward[k];
	(q->forward[0])->back = l->update[0];
	free(q);
	while (l->header->forward[m] == NIL && m > 0)  m--;
	l->level = m;
}

/* db_insert_next - insert a new node next to the node pointed by cur_p */
void db_insert_next(db_list l, keyType key, valueType value)
{
	register int k;
	register db_node p,q;
  	char *ckalloc();

	k = db_randomLevel(MaxLevel);
	if (k>l->level) {
		k = ++l->level;
		l->update[k] = l->header;
	}
	q = db_newNodeOfLevel(k);
	q->key = key;
	q->value = value;
	do {
		p = l->update[k];
		q->forward[k] = p->forward[k];
		p->forward[k] = q;
		l->update[k] = q;
	} while (--k >= 0);
	q->back = p;
	(q->forward[0])->back = q;
}

db_print(db_list l)
{
	db_node p;
	valueType v;

	for (p = (l->header)->forward[0]; p != NIL; p = p->forward[0]) {
		v=p->value;
		if (v && p->key==34658) {
			printf("key= %d, %6d %6d %6d %6d %6d %6d\n",p->key,v->i,v->j,v->k,v->ref,pos_diag(v),v->score);
			fflush(stdout);
		}
	}
	printf("This row OK\n");
	printf("*******************\n");
	fflush(stdout);
}