dce2_list.c

snort2.8.4版本

/****************************************************************************
 * Copyright (C) 2008-2008 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.
 *
 **************************************************************************** 
 * Provides list, queue and stack data structures and methods for use
 * with the preprocessor.
 * 
 * 8/17/2008 - Initial implementation ... Todd Wease <[e-mail]>
 *
 ****************************************************************************/

#include "dce2_list.h"
#include "dce2_memory.h"
#include "dce2_debug.h"
#include "dce2_utils.h"
#include "sf_types.h"

/********************************************************************
 * Private function prototyes
 ********************************************************************/
static void DCE2_ListInsertTail(DCE2_List *, DCE2_ListNode *);
static void DCE2_ListInsertHead(DCE2_List *, DCE2_ListNode *);
static void DCE2_ListInsertBefore(DCE2_List *, DCE2_ListNode *, DCE2_ListNode *);

/********************************************************************
 * Function: DCE2_ListNew()
 *
 * Creates and returns a new list object.
 *
 * Arguments:
 *  DCE2_ListType
 *      The type of list this should be - sorted, splayed, etc.
 *  DCE2_ListKeyCompare
 *      The comparison function to call when comparing two keys
 *      for inserting, finding, etc.
 *  DCE2_ListDataFree
 *      An optional function to call to free data in the list.
 *      If NULL is passed in, the user will have to manually free
 *      the data.
 *  DCE2_ListKeyFree
 *      An optional function to call to free keys used in the list.
 *      If NULL is passed in, the user will have to manually free
 *      the keys.
 *  int
 *      Flags that affect processing of the list.
 *      See DCE2_ListFlags for possible combinations.
 *  DCE2_MemType
 *      The memory type that dynamically allocated data should be
 *      associated with.
 *
 * Returns:
 *  DCE2_List *
 *      Pointer to a valid list object.
 *      NULL if an error occurs.
 *
 ********************************************************************/
DCE2_List * DCE2_ListNew(DCE2_ListType type, DCE2_ListKeyCompare kc,
                         DCE2_ListDataFree df, DCE2_ListKeyFree kf,
                         int flags, DCE2_MemType mtype)
{
    DCE2_List *list;

    /* Must have a key compare function */
    if (kc == NULL)
        return NULL;

    list = (DCE2_List *)DCE2_Alloc(sizeof(DCE2_List), mtype);
    if (list == NULL)
        return NULL;

    list->type = type;
    list->compare = kc;
    list->data_free = df;
    list->key_free = kf;
    list->flags = flags;
    list->mtype = mtype;

    return list;
}

/********************************************************************
 * Function: DCE2_ListFind()
 *
 * Trys to find a node in the list using key passed in.  If list
 * is splayed, found node is moved to front of list.  The data
 * associated with the node is returned.
 *
 * Arguments:
 *  DCE2_List *
 *      A pointer to the list object.
 *  void *
 *      Pointer to a key.
 *
 * Returns:
 *  void *
 *      If the key is found, the data associated with the node 
 *          is returned.
 *      NULL is returned if the item cannot be found given the key.
 *
 ********************************************************************/
void * DCE2_ListFind(DCE2_List *list, void *key)
{
    DCE2_ListNode *n;

    if (list == NULL)
        return NULL;

    for (n = list->head; n != NULL; n = n->next)
    {
        int comp = list->compare(key, n->key);
        if (comp == 0)
        {
            /* Found it, break out */
            break;
        }
        else if ((comp < 0) && (list->type == DCE2_LIST_TYPE__SORTED))
        {
            /* Don't look any more if the list is sorted */
            return NULL;
        }
    }

    if (n != NULL)
    {
        /* If list is splayed, move found node to front of list */
        if ((list->type == DCE2_LIST_TYPE__SPLAYED) &&
            (n != list->head))
        {
            n->prev->next = n->next;

            if (n->next != NULL)
                n->next->prev = n->prev;
            else  /* it's the tail */
                list->tail = n->prev;

            n->prev = NULL;
            n->next = list->head;
            list->head->prev = n;
            list->head = n;
        }

        return n->data;
    }

    return NULL;
}

/********************************************************************
 * Function: DCE2_ListFindKey()
 *
 * Trys to find a node in the list using key passed in.  If list
 * is splayed, found node is moved to front of list.  Returns
 * whether or not the key is associated with a node in the list.
 *
 * Arguments:
 *  DCE2_List *
 *      A pointer to the list object.
 *  void *
 *      Pointer to a key.
 *
 * Returns:
 *  DCE2_Ret
 *      DCE2_RET__SUCCESS if the key is found.
 *      DCE2_RET__ERROR if the key is not found.
 *
 ********************************************************************/
DCE2_Ret DCE2_ListFindKey(DCE2_List *list, void *key)
{
    DCE2_ListNode *n;

    if (list == NULL)
        return DCE2_RET__ERROR;

    for (n = list->head; n != NULL; n = n->next)
    {
        int comp = list->compare(key, n->key);
        if (comp == 0)
        {
            /* Found it, break out */
            break;
        }
        else if ((comp < 0) && (list->type == DCE2_LIST_TYPE__SORTED))
        {
            /* Don't look any more if the list is sorted */
            return DCE2_RET__ERROR;
        }
    }

    if (n != NULL)
    {
        /* If list is splayed, move found node to front of list */
        if ((list->type == DCE2_LIST_TYPE__SPLAYED) &&
            (n != list->head))
        {
            n->prev->next = n->next;

            if (n->next != NULL)
                n->next->prev = n->prev;
            else  /* it's the tail */
                list->tail = n->prev;

            n->prev = NULL;
            n->next = list->head;
            list->head->prev = n;
            list->head = n;
        }

        return DCE2_RET__SUCCESS;
    }

    return DCE2_RET__ERROR;
}

/********************************************************************
 * Function: DCE2_ListInsert()
 *
 * Adds a new node to the list with the key and data supplied.
 * If no duplicates are allowed in the key is searched for first
 * to see if a node is already present in the list.  If sorted,
 * the node is inserted into the list based on the key compare
 * function associated with the list object.
 *
 * Arguments:
 *  DCE2_List *
 *      A pointer to the list object.
 *  void *
 *      Pointer to a key to associate with data.
 *  void *
 *      Pointer to the data to insert into the list.
 *
 * Returns:
 *  DCE2_Ret
 *      DCE2_RET__DUPLICATE if an entry with the key is already
 *          in the list and no duplicates are allowed.
 *      DCE2_RET__SUCCESS if a new node with key and data is
 *          successfully inserted into the list.
 *      DCE2_RET__ERROR if memory cannot be allocated for the 
 *          new node or a NULL list object was passed in.
 *
 ********************************************************************/
DCE2_Ret DCE2_ListInsert(DCE2_List *list, void *key, void *data)
{
    DCE2_ListNode *n;
    DCE2_ListNode *last = NULL;
    int dup_check = 0;

    if (list == NULL)
        return DCE2_RET__ERROR;

    if (list->flags & DCE2_LIST_FLAG__NO_DUPS)
    {
        for (last = list->head; last != NULL; last = last->next)
        {
            int comp = list->compare(key, last->key);
            if (comp == 0)
            {
                /* It's already in the list */
                return DCE2_RET__DUPLICATE;
            }
            else if ((comp < 0) && (list->type == DCE2_LIST_TYPE__SORTED))
            {
                /* Break out here so as to insert after this node since
                 * the list is sorted */
                break;
            }
        }

        dup_check = 1;
    }

    n = (DCE2_ListNode *)DCE2_Alloc(sizeof(DCE2_ListNode), list->mtype);
    if (n == NULL)
        return DCE2_RET__ERROR;

    n->key = key;
    n->data = data;

    if ((list->type != DCE2_LIST_TYPE__SORTED) ||
        (list->head == NULL))
    {
        if (list->flags & DCE2_LIST_FLAG__INS_TAIL)
            DCE2_ListInsertTail(list, n);
        else
            DCE2_ListInsertHead(list, n);
    }
    else if (dup_check)  /* and the list is sorted */
    {
        if (last == NULL)
            DCE2_ListInsertTail(list, n);
        else
            DCE2_ListInsertBefore(list, n, last);
    }
    else
    {
        DCE2_ListNode *tmp;

        for (tmp = list->head; tmp != NULL; tmp = tmp->next)
        {
            if (list->compare(key, tmp->key) <= 0)
                break;
        }

        if (tmp == NULL)
            DCE2_ListInsertTail(list, n);
        else if (tmp == list->head)
            DCE2_ListInsertHead(list, n);
        else
            DCE2_ListInsertBefore(list, n, tmp);
    }

    return DCE2_RET__SUCCESS;
}

/********************************************************************
 * Function: DCE2_ListRemove()
 *
 * Removes the node in the list with the specified key.  If 
 * data free and key free functions were given with the creation
 * of the list object, they are called with the data and key
 * respectively.
 *
 * Arguments:
 *  DCE2_List *
 *      A pointer to the list object.
 *  void *
 *      Pointer to a key.
 *
 * Returns:
 *  DCE2_Ret
 *      DCE2_RET__ERROR if a node in the list with the specified
 *          key cannot be found or the list object passed in is NULL.
 *      DCE2_RET__SUCCESS if the node is successfully removed from
 *          the list.
 *
 ********************************************************************/
DCE2_Ret DCE2_ListRemove(DCE2_List *list, void *key)
{
    DCE2_ListNode *n;

    if (list == NULL)
        return DCE2_RET__ERROR;

    for (n = list->head; n != NULL; n = n->next)
    {
        int comp = list->compare(key, n->key);
        if (comp == 0)
        {
            /* Found it */
            break;
        }
        else if ((comp < 0) && (list->type == DCE2_LIST_TYPE__SORTED))
        {
            /* Won't find it after this since the list is sorted */
            return DCE2_RET__ERROR;
        }
    }
    
    if (n == NULL)
        return DCE2_RET__ERROR;

    if (n == list->head)
        list->head = n->next;
    if (n == list->tail)
        list->tail = n->prev;
    if (n->prev != NULL)
        n->prev->next = n->next;
    if (n->next != NULL)
        n->next->prev = n->prev;
    
    if (list->key_free != NULL)
        list->key_free(n->key);

    if (list->data_free != NULL)
        list->data_free(n->data);

    DCE2_Free((void *)n, sizeof(DCE2_ListNode), list->mtype);

    list->num_nodes--;

    return DCE2_RET__SUCCESS;
}

/********************************************************************
 * Function: DCE2_ListFirst()
 *
 * Returns a pointer to the data of the first node in the list.
 * Sets a current pointer to the first node in the list for
 * iterating over the list.
 *
 * Arguments:
 *  DCE2_List *
 *      A pointer to the list object.
 *
 * Returns:
 *  void *
 *      The data in the first node in the list.
 *      NULL if the list object passed in is NULL, or there are
 *          no items in the list.
 *
 ********************************************************************/
void * DCE2_ListFirst(DCE2_List *list)
{
    if (list == NULL)
        return NULL;

    list->current = list->head;
    list->next = NULL;

    if (list->current != NULL)
        return list->current->data;

    return NULL;
}

/********************************************************************
 * Function: DCE2_ListNext()
 *
 * Increments the current pointer in the list to the next node in
 * the list and returns the data associated with it.  This in
 * combination with DCE2_ListFirst is useful in a for loop to 
 * iterate over the items in a list.
 *
 * Arguments:
 *  DCE2_List *
 *      A pointer to the list object.
 *
 * Returns:
 *  void *
 *      The data in the next node in the list.
 *      NULL if the list object passed in is NULL, or we are at
 *          the end of the list and there are no next nodes.
 *
 ********************************************************************/
void * DCE2_ListNext(DCE2_List *list)
{
    if (list == NULL)
        return NULL;

    if (list->next != NULL)
    {
        list->current = list->next;
        list->next = NULL;
        return list->current->data;
    }
    else if (list->current != NULL)
    {
        list->current = list->current->next;
        if (list->current != NULL)
            return list->current->data;
    }

    return NULL;
}

/********************************************************************
 * Function: DCE2_ListLast()
 *
 * Returns a pointer to the data of the last node in the list.
 * Sets a current pointer to the last node in the list for
 * iterating over the list backwards.
 *
 * Arguments:
 *  DCE2_List *
 *      A pointer to the list object.
 *
 * Returns:
 *  void *
 *      The data in the last node in the list.
 *      NULL if the list object passed in is NULL, or there are
 *          no items in the list.
 *
 ********************************************************************/
void * DCE2_ListLast(DCE2_List *list)
{
    if (list == NULL)
        return NULL;