Thread: Skip lists

  1. #1
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362

    Skip lists

    Okay, I looked all over the place for ideas on how to make a skip list and everything just went overboard with nasty code I couldn't understand or just explanations of what a skip list is, which I know already. So I cheated a little. I started with a regular list and added the skip links in a separate function. Here's what I have, can someone tell me if I'm on the right track as well as how to destroy the entire list? I can't seem to get that to work right. I also didn't do any error checking and such, so I already know about those potential oopsies.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_LEV 3
    
    typedef struct node
    {
      int data;
      struct node *next[MAX_LEV];
    } *NODE;
    
    NODE new_node(int data)
    {
      int i;
      NODE np;
    
      np = malloc(sizeof *np);
      np->data = data;
      for (i = 0; i < MAX_LEV; i++)
      {
        np->next[i] = 0;
      }
    
      return np;
    }
    
    NODE set_skip(NODE list)
    {
      int i, j, k;
      NODE np, nn;
    
      for (j = 1, k = 2; j < MAX_LEV; j++, k += 3)
      {
        for (i = 0, nn = np = list; np != 0; np = np->next[0], i++)
        {
          if (i % k == 0)
          {
            nn->next[j] = np;
            nn = np;
          }
        }
      }
    
      return list;
    }
    
    void del_skip(NODE list)
    {
      int i;
      NODE np, nn;
    
      for (i = MAX_LEV - 1; i >= 0; i--)
      {
        for (np = list->next[i]; np != 0; np = nn)
        {
          nn = np->next[i];
          free(np);
        }
      }
    }
    
    void print_skip(NODE list)
    {
      int i;
      NODE np;
      static char *lev[] = {
        "->",
        "----->",
        "----------------->",
      };
    
      for (i = MAX_LEV - 1; i >= 0; i--)
      {
        for (np = list; np != 0; np = np->next[i])
        {
          printf("%02d%s", np->data, np->next[i] == 0 ? "\n" : lev[i]);
        }
      }
    }
    
    int main(void)
    {
      int i;
      NODE head = 0, np;
    
      for (i = 11; i > 0; i--)
      {
        np = new_node(i);
        np->next[0] = head;
        head = np;
      }
    
      head = set_skip(head);
      print_skip(head);
    
      return 0;
    }
    This is the list destroyer I have so far, it bombs out with a bad pointer access on the second iteration of the outer loop
    Code:
    void del_skip(NODE list)
    {
      int i;
      NODE np, nn;
    
      for (i = MAX_LEV - 1; i >= 0; i--)
      {
        for (np = list->next[i]; np != 0; np = nn)
        {
          nn = np->next[i];
          free(np);
        }
      }
    
      free(list);
    }
    *Cela*

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I've never coded one of these
    http://www.cs.umd.edu/~pugh/

    From the picture it would look like you would delete
    one of these things like this

    Code:
    void del_skip(NODE list)
    {
      int i;
      NODE np, nn;
    
      for (np = list->next[0]; np != 0; np = nn)
      {
          nn = np->next[0];
          free(np);
        }
      }
    
      free(list);
    }
    From the picture it looks like you would have 3 seperate
    list but they share nodes. So it should be only necessary
    to delete the level 0 nodes.

  3. #3
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    That's for that link, it was just what I needed. Here's what I came up with
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    
    #define MAX_LEV 4
    
    #define LEAK_CHECK 1
    #ifdef LEAK_CHECK
      int cnt;
      #define LeakMalloc(x) (cnt++, malloc(x))
      #define LeakFree(x) (cnt--, free(x))
      #define LeakPrint() (printf("Leaks found: %d\n", cnt))
    #else
      #define LeakMalloc(x) (malloc(x))
      #define LeakFree(x) (free(x))
      #define LeakPrint()
    #endif
    
    typedef struct node_s {
      int key;
      struct node_s **forward;
    } *NODE;
    
    typedef struct list_s {
      int level;
      struct node_s *header;
    } *LIST;
    
    static NODE NIL; /* End of list marker */
    
    static NODE make_node(int lvl, int key)
    {
      NODE np = LeakMalloc(sizeof *np);
    
      if (np == 0)
      {
        fprintf(stderr, "%d: Bad allocation in make_node()", __LINE__);
        exit(1);
      }
    
      np->forward = LeakMalloc(sizeof *np->forward * lvl);
    
      if (np->forward == 0)
      {
        fprintf(stderr, "%d: Bad allocation in make_node()", __LINE__);
        exit(1);
      }
    
      np->key = key;
    
      return np;
    }
    
    static int randomLevel(void)
    {
      int lvl = 0;
    
      while (rand() < RAND_MAX/2 && lvl < MAX_LEV)
      {
        lvl++;
      }
    
      return lvl;
    }
    
    void skip_init(void)
    {
      NIL = make_node(0, INT_MAX);
    }
    
    void skip_end(void)
    {
      LeakFree(NIL->forward);
      LeakFree(NIL);
    }
    
    LIST skip_new_list(void)
    {
      int i;
      LIST list;
    
      list = LeakMalloc(sizeof *list);
    
      if (list == 0)
      {
        fprintf(stderr, "%d: Bad allocation in skip_new_list()", __LINE__);
        exit(1);
      }
    
      list->level = 0;
      list->header = make_node(MAX_LEV, -1);
    
      for (i = 0; i < MAX_LEV; i++)
      {
        list->header->forward[i] = NIL;
      }
    
      return list;
    }
    
    void skip_free_list(LIST list)
    {
      NODE np, nn;
      
      for (np = list->header; np != NIL; np = nn)
      {
        nn = np->forward[0];
        LeakFree(np->forward);
        LeakFree(np);
      }
      
      LeakFree(list);
    }
    
    void skip_insert(LIST list, int searchkey)
    {
      int i, lvl;
      NODE update[MAX_LEV + 1];
      NODE x = list->header;
      
      /* Find the insertion point */
      for (i = list->level; i >= 0; i--)
      {
        while (x->forward[i] != NIL && x->forward[i]->key < searchkey)
        {
          x = x->forward[i];
        }
    
        update[i] = x;
      }
    
      x = x->forward[0];
    
      /* If it's a duplicate, replace */
      if (x->key == searchkey)
      {
        x->key = searchkey;
      }
      /* Not found */
      else
      {
        lvl = randomLevel();
        
        /* Update the current max level if i is bigger */
        if (lvl > list->level)
        {
          for (i = list->level + 1; i <= lvl; i++)
          {
            update[i] = list->header;
          }
    
          list->level = lvl;
        }
        
        x = make_node(lvl, searchkey);
        
        /* Link it */
        for (i = 0; i <= lvl; i++)
        {
          x->forward[i] = update[i]->forward[i];
          update[i]->forward[i] = x;
        }
      }
    }
    
    int main(void)
    {
      int i;
      LIST list;
      NODE np;
    
      skip_init();
      list = skip_new_list();
    
      for (i = 0; i < 10; i++)
      {
        skip_insert(list, i);
      }
    
      for (i = 0; i < MAX_LEV; i++)
      {
        for (np = list->header; np != NIL; np = np->forward[i])
        {
          printf("%d%s", np->key, np->forward[i] == NIL ? "\n" : "->");
        }
      }
    
      skip_free_list(list);
      skip_end();
    
      LeakPrint();
    
      return 0;
    }
    *Cela*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help creating lists of pointers
    By The_Kingpin in forum C Programming
    Replies: 2
    Last Post: 12-11-2004, 08:10 PM
  2. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 02:49 AM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  4. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  5. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM