[Anet-checkins] CVS: ANet/ANet_Daemon/Common/Lists BinaryTrees.c,NONE,1.1 DoubleLinkedLists.c,NONE,1.1 LinkedLists.c,NONE,1.1 LinkedLists.h,NONE,1.1 README.txt,NONE,1.1 sample.c,NONE,1.1

[Benoit N. <be...@us...>]

Update of /cvsroot/anet/ANet/ANet_Daemon/Common/Lists
In directory usw-pr-cvs1:/tmp/cvs-serv7895/Common/Lists

Added Files:
	BinaryTrees.c DoubleLinkedLists.c LinkedLists.c LinkedLists.h 
	README.txt sample.c 
Log Message:
Added linked lists, Makefile, and did some cleanup

--- NEW FILE: BinaryTrees.c ---
/* Binary trees. */

#include <stdlib.h>
#include "LinkedLists.h"

void InsertInTree(BinaryNodePtr theNode, BinaryNodePtr *root,
		  SInt8 (*CompareFunction)(NodePtr a, NodePtr b))
{
  BinaryNode **curPos = root;
  while (1) /* Who needs recursion? */
  {
    if (!*curPos)
    {
      *curPos = theNode;
      break;
    }
    else if (CompareFunction((NodePtr)(theNode), (NodePtr)(*curPos)) >= 0)
    {
      curPos = &((*curPos)->right);
    }
    else
    {
      curPos = &((*curPos)->left);
    }
  }
}

BinaryNodePtr SortedDoubleToBinaryWithSize(DoubleNodePtr linkedList, UInt32 size)
{
  /*
    Note: Ignores the "prev" pointers. So, if you want to pass the result
    of BinaryToDouble to this function, you don't need to call FillPrev
    first.
  */
  UInt32 halfSize = (size >> 1), counter, sizeA, sizeB;
  DoubleNodePtr middleNode;
	
  sizeA = halfSize;
  sizeB = halfSize;
  sizeB -= ((size & 1) ? (0) : (1));
	
  counter = halfSize;
  middleNode = linkedList;
  while (counter--)
    middleNode = middleNode->next;
	
  if (sizeB)
    middleNode->next = /* Or ->right */
    (DoubleNodePtr)(SortedDoubleToBinaryWithSize(middleNode->next, sizeB));
  else
    middleNode->next = (DoubleNodePtr)(0);
	
  if (sizeA)
    middleNode->prev = /* Or ->left */
    (DoubleNodePtr)(SortedDoubleToBinaryWithSize(linkedList, sizeA));
  else
    middleNode->prev = (DoubleNodePtr)(0);
	
  return (BinaryNodePtr)(middleNode);
}

DoubleNodePtr BinaryToDouble(BinaryNodePtr root, UInt8 fillPrev)
{
  IndirectNodePtr list;
  DoubleNodePtr doubleList;
  LeftNodeRight(root, &list);
  ApplyIndirectOnSimple(list);
  if (fillPrev)
    FillPrev((DoubleNodePtr)(list->nodePtr));
  doubleList = (DoubleNodePtr)(list->nodePtr);
  DestroyLinkedList((NodePtr)(list), DestroyIndirectNode);
  return doubleList;
}

IndirectNodePtr* LeftNodeRight(BinaryNodePtr node, IndirectNodePtr *theList)
{
  /*
    Used only for the BinaryToDouble function.
  */
  IndirectNodePtr newNode = malloc(sizeof(IndirectNode));
  if (node->left)
    theList = LeftNodeRight(node->left, theList);
  newNode->nodePtr = (NodePtr)(node);
  newNode->nodeHeader.next = (NodePtr)(0);
  *theList = newNode;
  theList = (IndirectNodePtr*)(&newNode->nodeHeader.next);
  if (node->right)
    theList = LeftNodeRight(node->right, theList);
  return theList;
}

void BalanceTree(BinaryNodePtr *root)
{
  DoubleNodePtr doubleList = BinaryToDouble(*root, 0);
  *root = SortedDoubleToBinary(doubleList);
  /* It's that small! Wow! */
}

--- NEW FILE: DoubleLinkedLists.c ---
/* Double linked lists. */

#include <stdlib.h>
#include "LinkedLists.h"

void InvertDoubleList(DoubleNodePtr *doubleLinkedListPtr)
{
  /*
    Same as InvertList, but for double linked lists, and much faster.
  */
  DoubleNodePtr curNode = *doubleLinkedListPtr, copyPtr;
  while (1)
  {
    copyPtr = curNode->next;
    curNode->next = curNode->prev;
    curNode->prev = copyPtr;
    if (!copyPtr)
      break;
    curNode = copyPtr;
  }
  *doubleLinkedListPtr = curNode;
}

UInt32 FindFirst(DoubleNodePtr linkedList, DoubleNodePtr* first)
{
  /*
    Same as FindLast, but backwards with a double linked list.
  */
  DoubleNodePtr curNode;
  UInt32 nbrNodes = 0;
  for (curNode = linkedList; curNode->prev; curNode = curNode->prev)
    nbrNodes++;
  if (first)
    *first = curNode;
  return (nbrNodes + 1);
}

void FillPrev(DoubleNodePtr linkedList)
{
  /*
    Fills the 'prev' values based on the single linked list given
    by the 'next' values.
  */
  DoubleNodePtr prev = NULL, curNode = linkedList;
  while (curNode)
  {
    curNode->prev = prev;
    prev = curNode;
    curNode = curNode->next;
  }
}

--- NEW FILE: LinkedLists.c ---
/* Single and indirect linked lists.*/

#include <stdlib.h>
#include <math.h>
#include "LinkedLists.h"

UInt32 DestroyLinkedList(NodePtr linkedList, UInt8 (*DestructorFunction)(NodePtr theNode))
{
  /*
    Destroys all elements in a linked list pointed by "linkedList".
    The destructor function must destroy the node and return 0 only
    if no error occured.
    Returns the number of nodes successfully destroyed.
  */
  NodePtr curNode, copyPtr;
  UInt32 nbrDestroyed = 0;
  if (!DestructorFunction)
    return 0;
  for (curNode = linkedList; curNode;)
  {
    copyPtr = curNode->next;
    if (DestructorFunction(curNode))
      return nbrDestroyed;
    nbrDestroyed++;
    curNode = copyPtr;
  }
  return nbrDestroyed;
}

UInt8 DestroyIndirectNode(NodePtr theNode)
{
  free((IndirectNodePtr)(theNode));
  return (!theNode);
}

UInt32 FindLast(NodePtr linkedList, NodePtr* last)
{
  /*
    Sets "*last" to point at the last node of the linked lisk pointed by
    "linkedList", unless "last" is NULL.
    Returns the numbers of nodes in the list.
    You can also use the macro function "NbrNodes(NodePtr linkedList);".
  */
  NodePtr curNode;
  UInt32 nbrNodes = 0;
  for (curNode = linkedList; curNode->next; curNode = curNode->next)
    nbrNodes++;
  if (last)
    *last = curNode;
  return (nbrNodes + 1);
}

NodePtr GetNthNode(NodePtr linkedList, UInt32 n)
{
  /*
    Returns a pointer to the Nth node of the linked list, the first node
    being node 0 (the 0th node?), as with arrays.
  */
  NodePtr curNode = linkedList;
  while ( (n--) && (curNode) )
    curNode = curNode->next;
  return curNode;
}

NodePtr SplitAtNth(NodePtr linkedList, UInt32 n)
{
  /*
    Splits the linked list pointed by "linkedList" into 2 linked lists
    after node "n", the first node being node 0, as with arrays.
    Returns a pointer to the beginning of the second linked list.
  */
  UInt32 curPos = 0;
  NodePtr curNode, copyPtr;
  for (curNode = linkedList; (++curPos) != n; curNode = curNode->next)
  {
    if (!curPos)
      return NULL;
  }
  copyPtr = curNode->next;
  curNode->next = NULL;
  return copyPtr;
}

IndirectNodePtr FindAndList(NodePtr linkedList, UInt8 (*IsWhatIWant)(NodePtr theNode))
{
  /*
    Using the key function "IsWhatIWant", makes a new indirect list (made of
    indirect nodes) that lists pointers to found nodes. They are listed in
    the order that they were found.
    Call "DestroyLinkedList((Node*)(returnedIndirectList), DestroyIndirectNode);"
    to destroy the indirect linked list returned by this function.
  */
  NodePtr curNode;
  IndirectNodePtr foundList = NULL, lastInFoundList = NULL;
  if (!IsWhatIWant)
    return NULL;
  for(curNode = linkedList; curNode; curNode = curNode->next)
  {
    if (IsWhatIWant(curNode))
    {
      IndirectNodePtr newNode = malloc(sizeof(IndirectNode));
      newNode->nodePtr = curNode;
      if (!foundList)
      {
	foundList = newNode;
	lastInFoundList = newNode;
      }
      else
      {
	lastInFoundList->nodeHeader.next = (Node*)(newNode);
	lastInFoundList = newNode;
      }
      lastInFoundList->nodeHeader.next = NULL;
    }
  }
  return foundList;
}

NodePtr FindAndMoveOut(NodePtr *linkedListPtr, UInt8 (*IsWhatIWant)(NodePtr theNode))
{
  /*
    Does the same thing as "FindAndList", but also removes all found nodes
    and places them in a new single linked list, which is the returned value.
  */
  NodePtr *curNodePtrPtr, newList;
  IndirectNodePtr foundList = FindAndList(*linkedListPtr, IsWhatIWant), curIndirect;
  if (!foundList)
    return NULL;
  curIndirect = foundList;
  for(curNodePtrPtr = linkedListPtr; *curNodePtrPtr;)
  {
    if (*curNodePtrPtr == curIndirect->nodePtr)
    {
      *curNodePtrPtr = (*curNodePtrPtr)->next;
      /* Searching for next one */
      curIndirect = (IndirectNodePtr)(curIndirect->nodeHeader.next);
      if (!curIndirect)
	break;
    }
    else
    {
      curNodePtrPtr = &((*curNodePtrPtr)->next);
    }
  }
  ApplyIndirectOnSimple(foundList);
  newList = foundList->nodePtr;
  /* Destroying temporary indirect linked list... */
  DestroyLinkedList((Node*)(foundList), DestroyIndirectNode);
  return newList;
}

void ApplyIndirectOnSimple(IndirectNodePtr indirectList)
{
  /*
    Applies the indirect linked list on the single list.
    This means that if an indirect node IndB, that points to node B, is after
    the indirect node IndA, that points to node A, in the indirect linked list,
    then this function will make node B be after node A in the single linked
    list.
	*/
  IndirectNodePtr curIndirect;
  for (curIndirect = indirectList; curIndirect->nodeHeader.next;
       curIndirect = (IndirectNodePtr)(curIndirect->nodeHeader.next))
  {
    curIndirect->nodePtr->next =
    ((IndirectNodePtr)(curIndirect->nodeHeader.next))->nodePtr;
  }
  /* Do the last one. Otherwise ((IndirectNodePtr)(curIndirect->nodeHeader.next))->nodePtr */
  /* is just junk from *NULL... */
  curIndirect->nodePtr->next = NULL;
}

void InvertList(NodePtr *linkedListPtr)
{
  /*
    Inverts the list pointed by *linkedListPtr. So, a->b->c becomes c->b->a.
    If you plan to do this often, use InvertDoubleList with a double linked list,
    as it's much faster.
  */
  NodePtr newList, lastNode;
  UInt32 nbrNodes = NbrNodes(*linkedListPtr), curNth;
  if (nbrNodes < 2)
    return;
  lastNode = newList = GetNthNode(*linkedListPtr, nbrNodes-1);
  for (curNth = (nbrNodes - 2); curNth; curNth--)
  {
    lastNode->next = GetNthNode(*linkedListPtr, curNth);
    lastNode = lastNode->next;
  }
  /* Add the last one. */
  lastNode->next = *linkedListPtr;
  (*linkedListPtr)->next = NULL;
  *linkedListPtr = newList;
}

void SplitAndMergeSort(NodePtr *linkedList, SInt8 (*CompareFunction)(NodePtr a, NodePtr b))
{
  /*
    Given a pointer to the beginning of a linked list and a compare function,
    this function sorts the list using the "split-merge" algorythm.
    CompareFunction(NodePtr a, NodePtr b) should return a value < 1 if and only if
    a is smaller than b.
  */
  Node empty;
  NodePtr listA, listB, curNode = &empty, newList = &empty;
  UInt32 nbrNodesFullList = NbrNodes(*linkedList);
	
  /* Split... */
  listA = *linkedList;
  listB = SplitAtNth(listA, nbrNodesFullList/2);
	
	/* ...(sorting)... */
  if (floor((double)(nbrNodesFullList)/2) > 1) /* Size of listA */
    SplitAndMergeSort(&listA, CompareFunction);
  if (ceil((double)(nbrNodesFullList)/2) > 1) /* Size of listB */
    SplitAndMergeSort(&listB, CompareFunction);
	
	/* ... and Merge */
  while (listA && listB)
  {
    if (CompareFunction(listA, listB) < 0)
    {
      /* listA is smaller than listB */
      curNode->next = listA;
      curNode = curNode->next;
      listA = listA->next;
    }
    else
    {
      /* listB is smaller or equal to listA */
      curNode->next = listB;
      curNode = curNode->next;
      listB = listB->next;
    }
  }
  while (listA)
  {
    curNode->next = listA;
    curNode = curNode->next;
    listA = listA->next;
  }
  while (listB)
  {
    curNode->next = listB;
    curNode = curNode->next;
    listB = listB->next;
  }
  newList = newList->next;
  *linkedList = newList;
}

--- NEW FILE: LinkedLists.h ---
#ifndef __BENAD_LINKED_LISTS__
#define __BENAD_LINKED_LISTS__

#ifndef __MACTYPES__

/*
  This is assuming that:
  char	=  8 bits,
  short	= 16 bits and
  long	= 32 bits.
	If this is false, just change those typedefs correctly.
*/

typedef unsigned	char	UInt8;
typedef signed		char	SInt8;
typedef unsigned	short	UInt16;
typedef signed		short	SInt16;
typedef unsigned	long	UInt32;
typedef signed		long	SInt32;

#endif /* #ifndef __MACTYPES__ */

typedef struct Node
{
  struct Node* next;
} Node, *NodePtr;

typedef struct IndirectNode
{
  Node nodeHeader;
  NodePtr nodePtr;
} IndirectNode, *IndirectNodePtr;

typedef struct DoubleNode
{
  struct DoubleNode* next;
  struct DoubleNode* prev;
} DoubleNode, *DoubleNodePtr;

typedef struct BinaryNode
{
  struct BinaryNode* right;
  struct BinaryNode* left;
} BinaryNode, *BinaryNodePtr;

UInt32 DestroyLinkedList(NodePtr linkedList, UInt8 (*DestructorFunction)(NodePtr theNode));
UInt32 FindLast(NodePtr linkedList, NodePtr* last);
#define NbrNodes(linkedList) FindLast(linkedList, NULL)
NodePtr GetNthNode(NodePtr linkedList, UInt32 n);
NodePtr SplitAtNth(NodePtr linkedList, UInt32 n);
IndirectNodePtr FindAndList(NodePtr linkedList, UInt8 (*IsWhatIWant)(NodePtr theNode));
NodePtr FindAndMoveOut(NodePtr *linkedListPtr, UInt8 (*IsWhatIWant)(NodePtr theNode));
void ApplyIndirectOnSimple(IndirectNodePtr indirectList);
void InvertList(NodePtr *linkedListPtr);
void SplitAndMergeSort(NodePtr *linkedList, SInt8 (*CompareFuntion)(NodePtr a, NodePtr b));

void InvertDoubleList(DoubleNodePtr *doubleLinkedListPtr);
UInt32 FindFirst(DoubleNodePtr linkedList, DoubleNodePtr* first);
void FillPrev(DoubleNodePtr linkedList);

void InsertInTree(BinaryNodePtr theNode, BinaryNodePtr *root,
		  SInt8 (*CompareFunction)(NodePtr a, NodePtr b));
BinaryNodePtr SortedDoubleToBinaryWithSize(DoubleNodePtr linkedList, UInt32 size);
#define SortedDoubleToBinary(l) SortedDoubleToBinaryWithSize(l, NbrNodes((NodePtr)(l)));
DoubleNodePtr BinaryToDouble(BinaryNodePtr root, UInt8 fillPrev);
IndirectNodePtr* LeftNodeRight(BinaryNodePtr node, IndirectNodePtr *theList);
void BalanceTree(BinaryNodePtr *root);

UInt8 DestroyIndirectNode(NodePtr theNode);

#endif /* #ifndef __BENAD_LINKED_LISTS__ */

--- NEW FILE: README.txt ---
Benad's Linked Lists is now distributed under GPL.

'Nuff said.
--- NEW FILE: sample.c ---
/*
	Benad's linked lists.
	Simple, fast linked lists.
	That's it.
	
	WARNING: Using a broken linked list with any of those functions may crash
	your computer, and/or do something crazy with it. I tested my functions
	enough to know that if that happens, it's not MY fault...
*/

#include <stdio.h>
#include <stdlib.h>
#include "LinkedLists.h"

UInt8 SimpleDestructor(NodePtr theNode);
UInt8 SimpleIsWhatIWant(NodePtr theNode);
SInt8 SimpleCompare(NodePtr a, NodePtr b);

int main(int argc, char **argv)
{
  DoubleNodePtr a, b, c, list;
  /*NodePtr found;*/
  /*BinaryNodePtr binaryTree, newVal;*/
  UInt32 nbr;
  a = malloc(sizeof(DoubleNode));
  b = malloc(sizeof(DoubleNode));
  c = malloc(sizeof(DoubleNode));
  a->next = b;
  a->prev = NULL;
  b->next = c;
  b->prev = NULL;
  c->next = NULL;
  c->prev = NULL;
  list = a;
  nbr = NbrNodes((NodePtr)(a));
  SplitAndMergeSort((NodePtr*)(&list), SimpleCompare);
  /*FillPrev(list);*/
  /*binaryTree = SortedDoubleToBinary(list);*/
  /*newVal = malloc(sizeof(BinaryNode));
    newVal->left = newVal->right = (BinaryNodePtr)(0);
    InsertInTree(newVal, &binaryTree, SimpleCompare);*/
  BalanceTree((BinaryNodePtr*)(&list)); /*List is like fully unbalanced tree*/
  /*if (SplitAtNth(a, 2) != c)
    return 1;*/
  /*if (GetNthNode(a, 2) != c)
    return 1;
    found = FindAndMoveOut(&a, SimpleIsWhatIWant);
    nbr = NbrNodes(found);
    if (DestroyLinkedList(found, SimpleDestructor) != nbr)
    /* ACK! Error! */
  /* return 1;*/
  /*InvertList(&list);*/
  /*SplitAndMergeSort(&(NodePtr)(list), SimpleCompare);*/
  /*InvertDoubleList(&list);*/
  return 0;
}

UInt8 SimpleDestructor(NodePtr theNode)
{
  free(theNode);
  return (!theNode);
}

UInt8 SimpleIsWhatIWant(NodePtr theNode)
{
  return (UInt8)(theNode);
}

SInt8 SimpleCompare(NodePtr a, NodePtr b)
{
  return (a-b);
}