Logo Search packages:      
Sourcecode: nagios3 version File versions  Download package

skiplist.c

/************************************************************************
 *
 * SKIPLIST.C - Skiplist functions for use in Nagios event/object lists
 *
 * Copyright (c) 2008 Ethan Galstad
 * Last Modified: 02-28-2008
 *
 * Notes:
 * 
 * These function implement a slightly modified skiplist from that
 * described by William Pugh (ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf).
 * The structures and function were modified to allow the list to act
 * like a priority queue for the Nagios event list/queue(s).  Multiple nodes with
 * the same key value are allowed on the list to accomodate multiple events
 * occurring at the same (second) point in time.  Implemented peek() and pop()
 * functions to allow for quick event queue processing, and a method to delete
 * a specific list item, based on its pointer, rather than its data value.  Again,
 * this is useful for the Nagios event queue.
 *
 * License:
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * 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; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 ************************************************************************/

#include "../include/config.h"
#include "../include/common.h"

#include "../include/skiplist.h"



skiplist *skiplist_new(int max_levels, float level_probability, int allow_duplicates, int append_duplicates, int (*compare_function)(void *,void *)){
      skiplist *newlist=NULL;

      /* alloc memory for new list structure */
      if((newlist=(skiplist *)malloc(sizeof(skiplist)))){

            /* initialize levels, etc. */
            newlist->current_level=0;
            newlist->max_levels=max_levels;
            newlist->level_probability=level_probability;
            newlist->allow_duplicates=allow_duplicates;
            newlist->append_duplicates=append_duplicates;
            newlist->items=0;
            newlist->compare_function=compare_function;

            /* initialize head node */
            newlist->head=skiplist_new_node(newlist,max_levels);
            }

      return newlist;
      }


int skiplist_insert(skiplist *list, void *data){
      skiplistnode **update=NULL;
      skiplistnode *thisnode=NULL;
      skiplistnode *nextnode=NULL;
      skiplistnode *newnode=NULL;
      int level=0;
      int x=0;

      if(list==NULL || data==NULL){
            return SKIPLIST_ERROR_ARGS;
            }

      /* initialize update vector */
      if((update=(skiplistnode **)malloc(sizeof(skiplistnode *) * list->max_levels))==NULL){
            return SKIPLIST_ERROR_MEMORY;
            }
      for(x=0;x<list->max_levels;x++)
            update[x]=NULL;

      /* check to make sure we don't have duplicates */
      /* NOTE: this could made be more efficient */
      if(list->allow_duplicates==FALSE){
            if(skiplist_find_first(list,data,NULL))
                  return SKIPLIST_ERROR_DUPLICATE;
            }

      /* find proper position for insert, remember pointers  with an update vector */
      thisnode=list->head;
      for(level=list->current_level;level>=0;level--){

            while((nextnode=thisnode->forward[level])){
                  if(list->append_duplicates==TRUE){
                        if(list->compare_function(nextnode->data,data)>0)
                              break;
                        }
                  else{
                        if(list->compare_function(nextnode->data,data)>=0)
                              break;
                        }
                  thisnode=nextnode;
                  }

            update[level]=thisnode;
            }

      /* get a random level the new node should be inserted at */
      level=skiplist_random_level(list);
      /*printf("INSERTION LEVEL: %d\n",level);*/

      /* we're adding a new level... */
      if(level > list->current_level){
            /*printf("NEW LEVEL!\n");*/
            list->current_level++;
            level=list->current_level;
            update[level]=list->head;
            }

      /* create a new node */
      if((newnode=skiplist_new_node(list,level))==NULL){
            /*printf("NODE ERROR\n");*/
            free(update);
            return SKIPLIST_ERROR_MEMORY;
            }
      newnode->data=data;

      /* update pointers to insert node at proper location */
      do{
            thisnode=update[level];
            newnode->forward[level]=thisnode->forward[level];
            thisnode->forward[level]=newnode;

            }while(--level>=0);

      /* update counters */
      list->items++;

      /* free memory */
      free(update);

      return SKIPLIST_OK;
      }



skiplistnode *skiplist_new_node(skiplist *list, int node_levels){
      skiplistnode *newnode=NULL;
      register int x=0;

      if(list==NULL)
            return NULL;

      if(node_levels<0 || node_levels>list->max_levels)
            return NULL;

      /* allocate memory for node + variable number of level pointers */
      if((newnode=(skiplistnode *)malloc(sizeof(skiplistnode) + (node_levels * sizeof(skiplistnode *))))){

            /* initialize forward pointers */
            for(x=0;x<node_levels;x++)
                  newnode->forward[x]=NULL;

            /* initialize data pointer */
            newnode->data=NULL;
            }

      return newnode;
      }


int skiplist_random_level(skiplist *list){
      int level=0;
      float r=0.0;

      if(list==NULL)
            return -1;

      for(level=0;level<list->max_levels;level++){
            r=((float)rand()/(float)RAND_MAX);
            if(r>list->level_probability)
                  break;
            }

      return (level >= list->max_levels)?list->max_levels-1:level;
      }


int skiplist_empty(skiplist *list){
      skiplistnode *this=NULL;
      skiplistnode *next=NULL;
      int level=0;

      if(list==NULL)
            return ERROR;

      /* free all list nodes (but not header) */
      for(this=list->head->forward[0];this!=NULL;this=next){
            next=this->forward[0];
            free(this);
            }

      /* reset level pointers */
      for(level=list->current_level;level>=0;level--)
            list->head->forward[level]=NULL;

      /* reset list level */
      list->current_level=0;

      /* reset items */
      list->items=0;

      return OK;
      }



int skiplist_free(skiplist **list){
      skiplistnode *this=NULL;
      skiplistnode *next=NULL;

      if(list==NULL)
            return ERROR;
      if(*list==NULL)
            return OK;

      /* free header and all list nodes */
      for(this=(*list)->head;this!=NULL;this=next){
            next=this->forward[0];
            free(this);
            }

      /* free list structure */
      free(*list);
      *list=NULL;

      return OK;
      }



/* get first item in list */
void *skiplist_peek(skiplist *list){

      if(list==NULL)
            return NULL;

      /* return first item */
      return list->head->forward[0]->data;
      }



/* get/remove first item in list */
void *skiplist_pop(skiplist *list){
      skiplistnode *thisnode=NULL;
      void *data=NULL;
      int level=0;

      if(list==NULL)
            return NULL;

      /* get first item */
      thisnode=list->head->forward[0];
      if(thisnode==NULL)
            return NULL;

      /* get data for first item */
      data=thisnode->data;

      /* remove first item from queue - update forward links from head to first node */
      for(level=0;level<=list->current_level;level++){
            if(list->head->forward[level]==thisnode)
                  list->head->forward[level]=thisnode->forward[level];
            }

      /* free deleted node */
      free(thisnode);

      /* adjust items */
      list->items--;

      return data;
      }



/* get first item in list */
void *skiplist_get_first(skiplist *list, void **node_ptr){
      skiplistnode *thisnode=NULL;

      if(list==NULL)
            return NULL;

      /* get first node */
      thisnode=list->head->forward[0];

      /* return pointer to node */
      if(node_ptr)
            *node_ptr=(void *)thisnode;

      if(thisnode)
            return thisnode->data;
      else
            return NULL;
      }



/* get next item in list */
void *skiplist_get_next(void **node_ptr){
      skiplistnode *thisnode=NULL;
      skiplistnode *nextnode=NULL;

      if(node_ptr==NULL || *node_ptr==NULL)
            return NULL;

      thisnode=(skiplistnode *)(*node_ptr);
      nextnode=thisnode->forward[0];

      *node_ptr=(void *)nextnode;

      if(nextnode)
            return nextnode->data;
      else
            return NULL;
      }



/* first first item in list */
void *skiplist_find_first(skiplist *list, void *data, void **node_ptr){
      skiplistnode *thisnode=NULL;
      skiplistnode *nextnode=NULL;
      int level=0;

      if(list==NULL || data==NULL)
            return NULL;

      thisnode=list->head;
      for(level=list->current_level;level>=0;level--){
            while((nextnode=thisnode->forward[level])){
                  if(list->compare_function(nextnode->data,data)>=0)
                        break;
                  thisnode=nextnode;
                  }
            }

      /* we found it! */
      if(nextnode && list->compare_function(nextnode->data,data)==0){
            if(node_ptr)
                  *node_ptr=(void *)nextnode;
            return nextnode->data;
            }
      else{
            if(node_ptr)
                  *node_ptr=NULL;
            }

      return NULL;
      }



/* find next match */
void *skiplist_find_next(skiplist *list, void *data, void **node_ptr){
      skiplistnode *thisnode=NULL;
      skiplistnode *nextnode=NULL;

      if(list==NULL || data==NULL || node_ptr==NULL)
            return NULL;
      if(*node_ptr==NULL)
            return NULL;

      thisnode=(skiplistnode *)(*node_ptr);
      nextnode=thisnode->forward[0];

      if(nextnode){
            if(list->compare_function(nextnode->data,data)==0){
                  *node_ptr=(void *)nextnode;
                  return nextnode->data;
                  }
            }

      *node_ptr=NULL;
      return NULL;
      }



/* delete (all) matching item(s) from list */
int skiplist_delete(skiplist *list, void *data){

      return skiplist_delete_all(list,data);
      }



/* delete first matching item from list */
int skiplist_delete_first(skiplist *list, void *data){
      skiplistnode **update=NULL;
      skiplistnode *thisnode=NULL;
      skiplistnode *nextnode=NULL;
      int level=0;
      int top_level=0;
      int deleted=FALSE;
      int x=0;

      if(list==NULL || data==NULL)
            return ERROR;

      /* initialize update vector */
      if((update=(skiplistnode **)malloc(sizeof(skiplistnode *) * list->max_levels))==NULL)
            return ERROR;
      for(x=0;x<list->max_levels;x++)
            update[x]=NULL;

      /* find location in list */
      thisnode=list->head;
      for(top_level=level=list->current_level;level>=0;level--){
            while((nextnode=thisnode->forward[level])){
                  if(list->compare_function(nextnode->data,data)>=0)
                        break;
                  thisnode=nextnode;
                  }
            update[level]=thisnode;
            }

      /* we found a match! */
      if(list->compare_function(nextnode->data,data)==0){

            /* adjust level pointers to bypass (soon to be) removed node */
            for(level=0;level<=top_level;level++){

                  thisnode=update[level];
                  if(thisnode->forward[level]!=nextnode)
                        break;

                  thisnode->forward[level]=nextnode->forward[level];
                  }

            /* free node memory */
            free(nextnode);

            /* adjust top/current level of list is necessary */
            while(list->head->forward[top_level]==NULL && top_level>0)
                  top_level--;
            list->current_level=top_level;

            /* adjust items */
            list->items--;

            deleted=TRUE;
            }

      /* free memory */
      free(update);

      return deleted;
      }



/* delete all matching items from list */
int skiplist_delete_all(skiplist *list, void *data){
      int deleted=0;
      int total_deleted=0;

      /* NOTE: there is a more efficient way to do this... */
      while((deleted=skiplist_delete_first(list,data))==1)
            total_deleted++;

      return total_deleted;
      }



/* delete specific node from list */
int skiplist_delete_node(skiplist *list, void *node_ptr){
      void *data=NULL;
      skiplistnode **update=NULL;
      skiplistnode *thenode=NULL;
      skiplistnode *thisnode=NULL;
      skiplistnode *nextnode=NULL;
      int level=0;
      int top_level=0;
      int deleted=FALSE;
      int x=0;

      if(list==NULL || node_ptr==NULL)
            return ERROR;

      /* we'll need the data from the node to first find the node */
      thenode=(skiplistnode *)node_ptr;
      data=thenode->data;

      /* initialize update vector */
      if((update=(skiplistnode **)malloc(sizeof(skiplistnode *) * list->max_levels))==NULL)
            return ERROR;
      for(x=0;x<list->max_levels;x++)
            update[x]=NULL;

      /* find location in list */
      thisnode=list->head;
      for(top_level=level=list->current_level;level>=0;level--){
            while((nextnode=thisnode->forward[level])){

                  /* next node would be too far */
                  if(list->compare_function(nextnode->data,data)>0)
                        break;
                  /* this is the exact node we want */
                  if(list->compare_function(nextnode->data,data)==0 && nextnode==thenode)
                        break;

                  thisnode=nextnode;
                  }
            update[level]=thisnode;
            }

      /* we found a match! (value + pointers match) */
      if(nextnode && list->compare_function(nextnode->data,data)==0 && nextnode==thenode){

            /* adjust level pointers to bypass (soon to be) removed node */
            for(level=0;level<=top_level;level++){

                  thisnode=update[level];
                  if(thisnode->forward[level]!=nextnode)
                        break;

                  thisnode->forward[level]=nextnode->forward[level];
                  }

            /* free node memory */
            free(nextnode);

            /* adjust top/current level of list is necessary */
            while(list->head->forward[top_level]==NULL && top_level>0)
                  top_level--;
            list->current_level=top_level;

            /* adjust items */
            list->items--;

            deleted=TRUE;
            }

      /* free memory */
      free(update);

      return deleted;
      }




Generated by  Doxygen 1.6.0   Back to index