/* Pepito v1.59  -- file: skipl.c --
   Copyright (c) 2000-01 Carlos del Cacho

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.

   Contact the author: guggenjaimito@yahoo.com
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "skipl.h"

#ifndef Min
#define Min(a,b) ((a) > (b) ? (b) : (a))
#endif

//----------------------------------------------------------------
void SL_FreeEntry(sl_entry *pe)
{
    if (pe->key)
    {
        free(pe->key);

        if (pe->data)
           free(pe->data);
    }

    if (pe->next)
       free(pe->next);

    free(pe);
}
//----------------------------------------------------------------
int SL_AllocEntry(skip_list *sl, sl_entry **pe, void *key, void *data, int data_size, int level)
{
    sl_entry *p = malloc(sizeof(sl_entry));

    if (!p)
       return -1;

    if (key)
    {
        p->key = malloc(sl->key_size);

        if (!p->key)
        {
            free(p);
            return -1;
        }

        memcpy(p->key,key,sl->key_size);

        p->data = malloc(data_size);

        if (!p->key)
        {
            free(p->data);
            free(p);
            return -1;
        }

        memcpy(p->data, data, data_size);
        p->data_size = data_size;

    }
    else
    {
        p->key = NULL;
        p->data = NULL;
    }

    if (level == -1)
    {

        do {
              level++;
        }
        while (level <= sl->max_level && rand() & 1);

        level &= (MAX_LEVELS-1);
    }

    if (!(p->next = malloc((level+1) * sizeof(sl_entry *))))
    {
       SL_FreeEntry(p);
       return -1;
    }

    *pe = p;
    return level;
}


//-----------------------------------------------------------------
int SL_Insert(skip_list *sl, void *key, void *data, int data_size, void (*pfun)(void *, int, void *, int))
{
    int i, cmp = 1, level;
    sl_entry *pe;
    sl_entry *last[MAX_LEVELS];

    pe = sl->levels;

    for (i = sl->max_level; i >= 0; i--)
    {
       while (pe->next[i] && (cmp = memcmp(key, pe->next[i]->key, sl->key_size)) == 1)
          pe = pe->next[i];

       last[i] = pe;
    }

    if (!cmp)
    {
        if (pfun)
        {
           pe = pe->next[0];
           pfun(data, data_size, pe->data, pe->data_size);
        }
        return 0;
    }

    if ((level = SL_AllocEntry(sl, &pe, key, data, data_size, -1)) != -1)
    {
        for(i=0; i <= Min(level,sl->max_level); i++)
        {
            pe->next[i] = last[i]->next[i];
            last[i]->next[i] = pe;
        }

        if (level > sl->max_level)
        {
            sl->levels->next[level] = pe;
            pe->next[level] = NULL;
            sl->max_level = level;
        }

        sl->nentries++;
    }
    return 0;
}
//-----------------------------------------------------------------
int SL_Delete(skip_list *sl, void *key)
{
    int i, cmp = 1;
    sl_entry *pe;
    sl_entry *last[MAX_LEVELS];

    pe = sl->levels;

    for (i = sl->max_level; i >= 0; i--)
    {
        while (pe->next[i] && (cmp = memcmp(key, pe->next[i]->key, sl->key_size)) == 1)
            pe = pe->next[i];

        last[i] = pe;

        if (!cmp)
        {
           pe = pe->next[i];
           if (i == sl->max_level && sl->levels->next[i] == pe &&
               pe->next[i] == NULL)
           {
               sl->max_level--;
           }

           do {
                 last[i]->next[i] = pe->next[i];
           } while (i--);


           SL_FreeEntry(pe);
           sl->nentries--;
        }
    }
    return 0;
}

//-----------------------------------------------------------------
sl_entry *SL_ExtractFirst(skip_list *sl)
{
    int i, cmp = 1;
    sl_entry *pe;

    pe = sl->levels->next[0];

    if (pe)
    {
        sl->levels->next[0] = pe->next[0];

        for (i=1; i <= sl->max_level && sl->levels->next[i] == pe; i++)
            sl->levels->next[i] = pe->next[i];

        if (!sl->levels->next[sl->max_level] && sl->max_level)
            sl->max_level--;

        sl->nentries--;
    }

    return pe;
}
//-----------------------------------------------------------------
int SL_Find(skip_list *sl, void *key, void **data)
{
    int i, cmp;
    sl_entry *pe;

    pe = sl->levels;

    for (i = sl->max_level; i >= 0; i--)
    {
        while (pe->next[i] && (cmp = memcmp(key, pe->next[i]->key, sl->key_size)) == 1)
            pe = pe->next[i];

        if (!cmp)
        {
            pe = pe->next[i];
            *data = pe->data;
            return pe->data_size;
        }
    }
    return 0;
}
//-----------------------------------------------------------------
int SL_Init(skip_list *sl, int key_size)
{
    srand(time(NULL));
    sl->key_size = key_size;
    sl->max_level = 0;
    sl->nentries = 0;

    SL_AllocEntry(sl, &sl->levels, NULL, NULL, 0, MAX_LEVELS-1);
    sl->levels->next[0] = NULL;
    return 0;
}
//-----------------------------------------------------------------
int SL_CheckConsistency(skip_list *sl)
{
   int i, error = 0;
   sl_entry *pe;

   for(i=0; i <= sl->max_level; i++)
   {
      pe = sl->levels->next[i];
      while (pe->next[i])
      {
         if (memcmp(pe->key, pe->next[i]->key, sl->key_size) != -1)
         {
            printf("error en lista a nivel %d\n",i);
            error = 1;
         }
         
         pe = pe->next[i];
      }
   }
   return error;
}
//-----------------------------------------------------------------
int SL_Print(skip_list *sl)
{
   int i, error = 0;
   sl_entry *pe;

   for(i=0; i <= sl->max_level; i++)
   {
      pe = sl->levels->next[i];
      printf("L%d:", i);
      while (pe)
      {
         printf(" %d", *((int *)pe->key));
         pe = pe->next[i];
      }
      printf("\n");
   }
   return error;
}
//----------------------------------------------------------------------
void SL_DestroyList(skip_list *sl)
{
   sl_entry *pe, *pkill;

   pe = sl->levels->next[0];
   while (pe)
   {
      pkill = pe;
      pe = pe->next[0];
      SL_FreeEntry(pkill);
   }
}
