---

List.c

Go to the documentation of this file.

/*
 *    gui - [gega user interface] the flexible solution for user interface problems
 *    Copyright (C) 2002  Gergely Gati
 *
 *    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; version 2 of the 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
 *
 *    Gergely Gati
 *      email:           g.gati@freemail.hu
 *      AIM screenname:  GatiGergely
 *      ICQ number:      93131690
 *
 */
/*
 *  Author        : Ferenc Zavacki
 *
 *  Creation date : 2001/03/02
 *
 *  Description   :
 *
 */

/***********************************************************************
*                               Includes                               *
***********************************************************************/

#include <stdlib.h>

#include "debug.h"
#include "List.h"
#include "Memory.h"

/***********************************************************************
*                              Structures                              *
***********************************************************************/

struct Node_s
{
  Node_t *Prev;
  Node_t *Next;
  void *Data;
};

struct List_s
{
  Node_t *Head;
  Node_t *Tail;
  int Count;
};

/***********************************************************************
*                           Public functions                           *
***********************************************************************/

/*
 *  This function creates an empty list and returns a pointer to it.
 *  Returns NULL on error.
 */

List_t *list_CreateList(void)
{
  List_t *List;

  debug_Begin();

  List = mem_calloc(1, sizeof(List_t));

  debug_End();

  return (List);
}

/*
 *  This function deletes the specified list. The nodes in the list are
 *  not deleted.
 */

void list_DeleteList(List_t *List)
{
  debug_Begin();

  if (List != NULL)
  {
    mem_free(List);
  }

  debug_End();
}

/*
 *  This function creates a node and sets its data pointer to NULL.
 *  Returns NULL on error.
 */

Node_t *list_CreateNode(void)
{
  Node_t *Node;

  debug_Begin();

  Node = mem_calloc(1, sizeof(Node_t));

  debug_End();

  return (Node);
}

/*
 *  This function deletes the specified node. The attached data is not
 *  deleted.
 */

void list_DeleteNode(Node_t *Node)
{
  debug_Begin();

  if (Node != NULL)
  {
    mem_free(Node);
  }

  debug_End();
}

/*
 *  This function inserts the specified node into the specified list
 *  before all other nodes of the list.
 */

void list_InsertNodeHead(List_t *List, Node_t *Node)
{
  debug_Begin();

  if ((List != NULL) && (Node != NULL))
  {
    Node->Prev = NULL;

    if ((Node->Next = List->Head) != NULL)
    {
      List->Head->Prev = Node;
    }
    else
    {
      List->Tail = Node;
    }

    List->Head = Node;

    List->Count++;
  }

  debug_End();
}

/*
 *  This function inserts the specified node into the specified list
 *  after all other nodes of the list.
 */

void list_InsertNodeTail(List_t *List, Node_t *Node)
{
  debug_Begin();

  if ((List != NULL) && (Node != NULL))
  {
    Node->Next = NULL;

    if ((Node->Prev = List->Tail) != NULL)
    {
      List->Tail->Next = Node;
    }
    else
    {
      List->Head = Node;
    }

    List->Tail = Node;

    List->Count++;
  }

  debug_End();
}

/*
 *  This function inserts the specified node into the specified list
 *  after the other specified node of the list.
 */

void list_InsertNodeNext(List_t *List, Node_t *PrevNode, Node_t *Node)
{
  debug_Begin();

  if ((List != NULL) && (PrevNode != NULL) && (Node != NULL))
  {
    Node->Prev = PrevNode;

    if ((Node->Next = PrevNode->Next) != NULL)
    {
      PrevNode->Next->Prev = Node;
    }
    else
    {
      List->Tail = Node;
    }

    PrevNode->Next = Node;

    List->Count++;
  }

  debug_End();
}

/*
 *  This function inserts the specified node into the specified list
 *  before the other specified node of the list.
 */

void list_InsertNodePrev(List_t *List, Node_t *NextNode, Node_t *Node)
{
  debug_Begin();

  if ((List != NULL) && (NextNode != NULL) && (Node != NULL))
  {
    Node->Next = NextNode;

    if ((Node->Prev = NextNode->Prev) != NULL)
    {
      NextNode->Prev->Next = Node;
    }
    else
    {
      List->Head = Node;
    }

    NextNode->Prev = Node;

    List->Count++;
  }

  debug_End();
}

/*
 *  This function removes the specified node from the specified list and
 *  returns a pointer to the same node.
 */

Node_t *list_RemoveNode(List_t *List, Node_t *Node)
{
  debug_Begin();

  if ((List != NULL) && (Node != NULL))
  {
    if (Node == List->Head)
    {
      List->Head = Node->Next;
    }
    else
    {
      Node->Prev->Next = Node->Next;
    }

    if (Node == List->Tail)
    {
      List->Tail = Node->Prev;
    }
    else
    {
      Node->Next->Prev = Node->Prev;
    }

    List->Count--;
  }

  debug_End();

  return (Node);
}

/*
 *  This function removes the first node from the specified list and
 *  returns a pointer to the node. Returns NULL if the list is empty.
 */

Node_t *list_RemoveNodeHead(List_t *List)
{
  Node_t *Node = NULL;

  debug_Begin();

  if (List != NULL)
  {
    if ((Node = List->Head) != NULL)
    {
      if ((List->Head = Node->Next) != NULL)
      {
        List->Head->Prev = NULL;
      }
      else
      {
        List->Tail = NULL;
      }

      List->Count--;
    }
  }

  debug_End();

  return (Node);
}

/*
 *  This function removes the last node from the specified list and
 *  returns a pointer to the node. Returns NULL if the list is empty.
 */

Node_t *list_RemoveNodeTail(List_t *List)
{
  Node_t *Node = NULL;

  debug_Begin();

  if (List != NULL)
  {
    if ((Node = List->Tail) != NULL)
    {
      if ((List->Tail = Node->Prev) != NULL)
      {
        List->Tail->Next = NULL;
      }
      else
      {
        List->Head = NULL;
      }

      List->Count--;
    }
  }

  debug_End();

  return (Node);
}

/*
 *  This function returns the first node of the specified list. Returns
 *  NULL if the list is empty.
 */

Node_t *list_GetNodeHead(List_t *List)
{
  Node_t *Node = NULL;

  debug_Begin();

  if (List != NULL)
  {
    Node = List->Head;
  }

  debug_End();

  return (Node);
}

/*
 *  This function returns the last node of the specified list. Returns
 *  NULL if the list is empty.
 */

Node_t *list_GetNodeTail(List_t *List)
{
  Node_t *Node = NULL;

  debug_Begin();

  if (List != NULL)
  {
    Node = List->Tail;
  }

  debug_End();

  return (Node);
}

/*
 *  This function returns a pointer to the next node of the specified
 *  node which can be NULL if the specified node is the last node of the
 *  specified list.
 */

Node_t *list_GetNodeNext(List_t *List, Node_t *Node)
{
  Node_t *NextNode = NULL;

  debug_Begin();

  if ((List != NULL) && (Node != NULL))
  {
    NextNode = Node->Next;
  }

  debug_End();

  return (NextNode);
}

/*
 *  This function returns a pointer to the previous node of the
 *  specified node which can be NULL if the specified node is the first
 *  node of the specified list.
 */

Node_t *list_GetNodePrev(List_t *List, Node_t *Node)
{
  Node_t *PrevNode = NULL;

  debug_Begin();

  if ((List != NULL) && (Node != NULL))
  {
    PrevNode = Node->Prev;
  }

  debug_End();

  return (PrevNode);
}

/*
 *  This function returns a pointer to the node at the specified
 *  position which can be NULL if the specified node does not exist.
 */

Node_t *list_GetNodeAt(List_t *List, int Index)
{
  Node_t *Node = NULL;
  int i;

  debug_Begin();

  if ((Index >= 0) && (Index < List->Count))
  {
    for (i = 0, Node = list_GetNodeHead(List); (i < Index) && (Node != NULL); i++, Node = list_GetNodeNext(List, Node));
  }

  debug_End();

  return (Node);
}

/*
 *  This function returns the ordinal number of the specified node in
 *  the specified list.
 */

int list_GetNodeIndex(List_t *List, Node_t *Node)
{
  int Index = 0;

  debug_Begin();

  if ((List != NULL) && (Node != NULL))
  {
    while ((Node = list_GetNodePrev(List, Node)) != NULL)
    {
      Index++;
    }
  }

  debug_End();

  return (Index);
}

/*
 *  This function returns the current number of nodes in the specified
 *  list.
 */

int list_GetNodeCount(List_t *List)
{
  int Count = 0;

  debug_Begin();

  if (List != NULL)
  {
    Count = List->Count;
  }

  debug_End();

  return (Count);
}

/*
 *  This function returns the data pointer associated with the specified
 *  node.
 */

void *list_GetNodeData(Node_t *Node)
{
  void *Data = NULL;

  debug_Begin();

  if (Node != NULL)
  {
    Data = Node->Data;
  }

  debug_End();

  return (Data);
}

/*
 *  This function sets the data pointer associated with the specified
 *  node.
 */

void list_SetNodeData(Node_t *Node, void *Data)
{
  debug_Begin();

  if (Node != NULL)
  {
    Node->Data = Data;
  }

  debug_End();
}

/*
 *  This function sorts the nodes in the specified list based on the
 *  return value of the specified compare function. The return values
 *  must be the same as returned by strcmp().
 */

void list_SortNodes(List_t *List, int (*Compare)(void *Data1, void *Data2))
{
  debug_Begin();

  if ((List != NULL) && (Compare != NULL))
  {
    Node_t *Node1, *Node2;
    void *Data1, *Data2;
    int i, j;

    for (i = list_GetNodeCount(List) - 1; i > 0; i--)
    {
      int Swapped = 0;

      for (Node1 = list_GetNodeHead(List), j = 0; j < i; j++, Node1 = list_GetNodeNext(List, Node1))
      {
        Node2 = list_GetNodeNext(List, Node1);

        Data1 = list_GetNodeData(Node1);
        Data2 = list_GetNodeData(Node2);

        if (Compare(Data1, Data2) > 0)
        {
          list_SetNodeData(Node1, Data2);
          list_SetNodeData(Node2, Data1);

          Swapped = 1;
        }
      }

      if (!Swapped) break;
    }
  }

  debug_End();
}

---