/**************************************************************************** * * Copyright (C) 2003-2007 Sourcefire, Inc. * * 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.  You may not use, modify or * distribute this program under any other version of the GNU General * Public License. * * 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ****************************************************************************/ /**   sflsq.c    **   Simple list, stack, queue, and dictionary implementations *   ( most of these implementations are list based - not performance monsters,*     and they all use alloc via s_alloc/s_free )*   Stack based Ineteger and Pointer Stacks, these are for performance.(inline would be better)**   11/05/2005 - man - Added sflist_firstx() and sflist_nextx() with user*   provided SF_NODE inputs for tracking the list position.  This allows*   multiple readers to traverse a list. The built in 'cur' field does not *   wrok for multiple readers.***/#include <stdio.h>#include <stdlib.h>#include <string.h>#include "sflsq.h"/**  private alloc*/ static void * s_alloc (int n) {  void *p=0;  if( n > 0 )p = (void*) calloc( 1,n );  return p;}/**  private free*/ static void s_free (void *p) {  if( p ) free( p );}/**   INIT - called by the NEW functions*/ void sflist_init ( SF_LIST * s) {  s->count=0;   s->head = s->tail = s->cur = 0;}/**    NEW*/SF_LIST * sflist_new(void) {   SF_LIST * s;   s = (SF_LIST*)s_alloc( sizeof(SF_LIST) );   if( s )sflist_init( s );   return s;}SF_STACK * sfstack_new(void) {   return (SF_STACK*)sflist_new();}SF_QUEUE * sfqueue_new(void) {   return (SF_QUEUE*)sflist_new();}/**  Add-before Item */ int sflist_add_before ( SF_LIST* s, SF_LNODE * lnode, NODE_DATA ndata ){  SF_LNODE * q;  if( !lnode )      return 0;  /* Add to head of list */  if( s->head == lnode )  {      return sflist_add_head ( s, ndata );  }  else  {      q = (SF_LNODE *) s_alloc ( sizeof (SF_LNODE) );      if( !q )      {          return -1;      }      q->ndata = (NODE_DATA)ndata;      q->next = lnode;      q->prev = lnode->prev;      lnode->prev->next = q;      lnode->prev       = q;  }  s->count++;  return 0;}/**     ADD to List/Stack/Queue/Dictionary*//**  Add-Head Item */ int sflist_add_head ( SF_LIST* s, NODE_DATA ndata ){  SF_LNODE * q;  if (!s->head)    {      q = s->tail = s->head = (SF_LNODE *) s_alloc (sizeof (SF_LNODE));      if(!q)return -1;      q->ndata = (NODE_DATA)ndata;      q->next = 0;      q->prev = 0;    }  else    {      q = (SF_LNODE *) s_alloc (sizeof (SF_LNODE));      if(!q)return -1;      q->ndata = ndata;      q->next = s->head;      q->prev = 0;      s->head->prev = q;      s->head = q;    }  s->count++;  return 0;}/**  Add-Tail Item */ int sflist_add_tail ( SF_LIST* s, NODE_DATA ndata ){  SF_LNODE * q;  if (!s->head)    {      q = s->tail = s->head = (SF_LNODE *) s_alloc (sizeof (SF_LNODE));      if(!q)return -1;      q->ndata = (NODE_DATA)ndata;      q->next = 0;      q->prev = 0;    }  else    {      q = (SF_LNODE *) s_alloc (sizeof (SF_LNODE));      if(!q)return -1;      q->ndata = ndata;      q->next = 0;      q->prev = s->tail;      s->tail->next = q;      s->tail = q;    }  s->count++;  return 0;}int sfqueue_add(SF_QUEUE * s, NODE_DATA ndata ) {  return sflist_add_tail ( s, ndata );}int sfstack_add( SF_STACK* s, NODE_DATA ndata ) {  return sflist_add_tail ( s, ndata );}/* *   List walk - First/Next - return the node data or NULL*/NODE_DATA sflist_first( SF_LIST * s ){    if(!s)         return 0;    s->cur = s->head;    if( s->cur )         return s->cur->ndata;    return 0;}NODE_DATA sflist_next( SF_LIST * s ){    if(!s)        return 0;    if( s->cur )    {        s->cur = s->cur->next;        if( s->cur )             return s->cur->ndata;    }    return 0;}NODE_DATA sflist_firstpos( SF_LIST * s, SF_LNODE ** v ){    if(!s)        return 0;        *v = s->head;        if( *v )        return (*v)->ndata;    return 0;}NODE_DATA sflist_nextpos( SF_LIST * s,  SF_LNODE ** v ){    if(!s)        return 0;        if(v)    {       if(*v)       {          *v = (*v)->next;          if( *v )               return (*v)->ndata;       }    }    return 0;}/* *   List walk - First/Next - return the node data or NULL*/SF_LNODE * sflist_first_node( SF_LIST * s ){    if(!s)        return 0;    s->cur = s->head;    if( s->cur )         return s->cur;    return 0;}SF_LNODE * sflist_next_node( SF_LIST * s ){    if(!s)        return 0;    if( s->cur )    {        s->cur = s->cur->next;        if( s->cur )             return s->cur;    }    return 0;}/**  Remove Head Item from list*/ NODE_DATA sflist_remove_head (SF_LIST * s) {  NODE_DATA ndata = 0;  SF_QNODE * q;  if ( s && s->head  )    {      q = s->head;      ndata = q->ndata;      s->head = s->head->next;      s->count--;      if( !s->head  )	  {	    s->tail = 0;	    s->count = 0;	  }      s_free( q );    }  return (NODE_DATA)ndata;}/**  Remove tail Item from list*/NODE_DATA sflist_remove_tail (SF_LIST * s){  NODE_DATA ndata = 0;  SF_QNODE * q;  if (s && s->tail)    {      q = s->tail;      ndata = q->ndata;      s->count--;      s->tail = q->prev;      if (!s->tail)      {	s->tail = 0;        s->head = 0;	s->count = 0;      }      else      {        if( q->prev ) q->prev->next = 0;      }      s_free (q);    }  return (NODE_DATA)ndata;}void sflist_remove_node (SF_LIST * s, SF_LNODE * n, void(*nfree)(void*) ) { // NODE_DATA ndata = 0;  SF_LNODE * cur;        if( n == s->head )  {        s->head = s->head->next;        s->count--;        if (!s->head)	    {	      s->tail = 0;	      s->count = 0;	    }        if( nfree ) nfree( n->ndata );        s_free( n );        return ;  }  else if( n == s->tail )  {        s->tail = s->tail->prev;        s->count--;        if (!s->tail )	    {	      s->head = 0;	      s->count = 0;	    }        if( nfree ) nfree( n->ndata );        s_free( n );        return ;  }  for(cur = s->head;      cur!= NULL;      cur = cur->next )  {    if( n == cur )    {       /* unlink a middle node */       n->next->prev = n->prev;       n->prev->next = n->next;	   s->count--;       if( nfree ) nfree( n->ndata );       s_free(n);       return ;     }  }}/**  Remove Head Item from queue*/ NODE_DATA sfqueue_remove (SF_QUEUE * s) {  return (NODE_DATA)sflist_remove_head( s );}/**  Remove Tail Item from stack*/ NODE_DATA sfstack_remove (SF_QUEUE * s) {  return (NODE_DATA)sflist_remove_tail( s );}/**  COUNT*/ int sfqueue_count (SF_QUEUE * s) {  if(!s)return 0;  return s->count;}int sflist_count ( SF_LIST* s) {  if(!s)return 0;  return s->count;}int sfstack_count ( SF_STACK * s) {  if(!s)return 0;  return s->count;}/**   Free List + Free it's data nodes using 'nfree' */void sflist_free_all( SF_LIST * s, void (*nfree)(void*) ) {  void * p;    if(!s)      return;    while( s->count > 0 )  {     p = sflist_remove_head (s);    	 if( p && nfree )          nfree( p );  }  s_free(s);}void sfqueue_free_all(SF_QUEUE * s,void (*nfree)(void*) ) {  sflist_free_all( s, nfree ); }void sfstack_free_all(SF_STACK * s,void (*nfree)(void*) ) {  sflist_free_all( s, nfree ); }/**  FREE List/Queue/Stack/Dictionary**  This does not free a nodes data*/ void sflist_free (SF_LIST * s){  while( sflist_count(s) )  {    sflist_remove_head(s);  }  s_free(s);}void sfqueue_free (SF_QUEUE * s) {  sflist_free ( s ); }void sfstack_free (SF_STACK * s){  sflist_free ( s ); }/**   Integer stack functions - for performance scenarios*/int sfistack_init( SF_ISTACK * s, unsigned * a,  int n  ){   s->imalloc=0;   if( a ) s->stack = a;   else   {      s->stack = (unsigned*) calloc( n, sizeof(unsigned) );      s->imalloc=1;   }   if( !s->stack ) return -1;   s->nstack= n;   s->n =0;   return 0;}int sfistack_push( SF_ISTACK *s, unsigned value){   if( s->n < s->nstack )   {       s->stack[s->n++] = value;       return 0;   }   return -1;}int sfistack_pop( SF_ISTACK *s, unsigned * value){   if( s->n > 0 )   {       s->n--;       *value = s->stack[s->n];       return 0;   }   return -1;}/**  Pointer Stack Functions - for performance scenarios*/int sfpstack_init( SF_PSTACK * s, void ** a,  int n  ){   s->imalloc=0;   if( a ) s->stack = a;   else   {      s->stack = (void**) calloc( n , sizeof(void*) );      s->imalloc=1;   }   if( !s->stack ) return -1;   s->nstack= n;   s->n =0;   return 0;}int sfpstack_push( SF_PSTACK *s, void * value){   if( s->n < s->nstack )   {       s->stack[s->n++] = value;       return 0;   }   return -1;}int sfpstack_pop( SF_PSTACK *s, void ** value){   if( s->n > 0 )   {       s->n--;       *value = s->stack[s->n];       return 0;   }   return -1;}