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

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

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

Modified Files:
	BinaryTrees.c DoubleLinkedLists.c LinkedLists.c LinkedLists.h 
Log Message:
Starting low-level docs with doxygen

Index: BinaryTrees.c
===================================================================
RCS file: /cvsroot/anet/ANet/ANet_Daemon/Common/Lists/BinaryTrees.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** BinaryTrees.c	2001/11/05 23:27:03	1.1
--- BinaryTrees.c	2001/12/12 20:05:09	1.2
***************
*** 1,7 ****
--- 1,18 ----
  /* Binary trees. */
  
+ /*!
+   \addtogroup lists
+   \{
+ */
+ 
+ /*!
+   \file
+   \brief Binary trees.
+ */
+ 
  #include <stdlib.h>
  #include "LinkedLists.h"
  
+ //! Inserts a node in a binary tree.
  void InsertInTree(BinaryNodePtr theNode, BinaryNodePtr *root,
  		  SInt8 (*CompareFunction)(NodePtr a, NodePtr b))
***************
*** 26,36 ****
  }
  
  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;
--- 37,48 ----
  }
  
+ //! Transforms a sorted double linked list into a binary tree.
+ /*!
+   \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.
+ */
  BinaryNodePtr SortedDoubleToBinaryWithSize(DoubleNodePtr linkedList, UInt32 size)
  {
    UInt32 halfSize = (size >> 1), counter, sizeA, sizeB;
    DoubleNodePtr middleNode;
***************
*** 60,63 ****
--- 72,76 ----
  }
  
+ //! Transforms a (sorted) binary tree to a sorted double linked list.
  DoubleNodePtr BinaryToDouble(BinaryNodePtr root, UInt8 fillPrev)
  {
***************
*** 73,81 ****
  }
  
  IndirectNodePtr* LeftNodeRight(BinaryNodePtr node, IndirectNodePtr *theList)
  {
-   /*
-     Used only for the BinaryToDouble function.
-   */
    IndirectNodePtr newNode = malloc(sizeof(IndirectNode));
    if (node->left)
--- 86,95 ----
  }
  
+ //! Used only for the <CODE>BinaryToDouble</CODE> function.
+ /*!
+   \see BinaryToDouble()
+ */
  IndirectNodePtr* LeftNodeRight(BinaryNodePtr node, IndirectNodePtr *theList)
  {
    IndirectNodePtr newNode = malloc(sizeof(IndirectNode));
    if (node->left)
***************
*** 90,93 ****
--- 104,111 ----
  }
  
+ //! Balances a binary tree.
+ /*!
+   \note Can be quite slow. You've been warned.
+ */
  void BalanceTree(BinaryNodePtr *root)
  {
***************
*** 96,97 ****
--- 114,117 ----
    /* It's that small! Wow! */
  }
+ 
+ /*! \} */

Index: DoubleLinkedLists.c
===================================================================
RCS file: /cvsroot/anet/ANet/ANet_Daemon/Common/Lists/DoubleLinkedLists.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** DoubleLinkedLists.c	2001/11/05 23:27:03	1.1
--- DoubleLinkedLists.c	2001/12/12 20:05:09	1.2
***************
*** 1,12 ****
  /* 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)
--- 1,24 ----
  /* Double linked lists. */
  
+ /*!
+   \addtogroup lists
+   \{
+ */
+ 
+ /*!
+   \file
+   \brief Double linked lists.
+ */
+ 
  #include <stdlib.h>
  #include "LinkedLists.h"
  
+ 
+ //! Same as InvertList, but for double linked lists, and much faster.
+ /*!
+   \see InvertList()
+ */
  void InvertDoubleList(DoubleNodePtr *doubleLinkedListPtr)
  {
    DoubleNodePtr curNode = *doubleLinkedListPtr, copyPtr;
    while (1)
***************
*** 22,30 ****
  }
  
  UInt32 FindFirst(DoubleNodePtr linkedList, DoubleNodePtr* first)
  {
-   /*
-     Same as FindLast, but backwards with a double linked list.
-   */
    DoubleNodePtr curNode;
    UInt32 nbrNodes = 0;
--- 34,43 ----
  }
  
+ //! Same as FindLast, but backwards with a double linked list.
+ /*
+   \see FindLast()
+ */
  UInt32 FindFirst(DoubleNodePtr linkedList, DoubleNodePtr* first)
  {
    DoubleNodePtr curNode;
    UInt32 nbrNodes = 0;
***************
*** 36,45 ****
  }
  
  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)
--- 49,59 ----
  }
  
+ //! Fills the <CODE>"prev"</CODE> values.
+ /*
+   Fills the 'prev' values based on the single linked list given
+   by the 'next' values.
+ */
  void FillPrev(DoubleNodePtr linkedList)
  {
    DoubleNodePtr prev = NULL, curNode = linkedList;
    while (curNode)
***************
*** 50,51 ****
--- 64,67 ----
    }
  }
+ 
+ /*! \} */

Index: LinkedLists.c
===================================================================
RCS file: /cvsroot/anet/ANet/ANet_Daemon/Common/Lists/LinkedLists.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** LinkedLists.c	2001/11/05 23:27:03	1.1
--- LinkedLists.c	2001/12/12 20:05:09	1.2
***************
*** 1,16 ****
  /* 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;
--- 1,28 ----
  /* Single and indirect linked lists.*/
  
+ /*!
+   \addtogroup lists
+   \{
+ */
+ 
+ /*!
+   \file
+   \brief Single and indirect linked lists.
+ */
+ 
  #include <stdlib.h>
  #include <math.h>
  #include "LinkedLists.h"
  
+ //! Destroys all elements in a linked list.
+ /*!
+   Destroys all elements in a linked list pointed by <CODE>"linkedList"</CODE>.
+   The destructor function must destroy the node and return 0 only
+   if no error occured.
+   Returns the number of nodes successfully destroyed.
+ */
  UInt32 DestroyLinkedList(NodePtr linkedList, UInt8 (*DestructorFunction)(NodePtr theNode))
  {
!   
    NodePtr curNode, copyPtr;
    UInt32 nbrDestroyed = 0;
***************
*** 28,31 ****
--- 40,44 ----
  }
  
+ //! Destroys an indirect node.
  UInt8 DestroyIndirectNode(NodePtr theNode)
  {
***************
*** 34,45 ****
  }
  
  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;
--- 47,61 ----
  }
  
+ //! Finds the last node in a linked list.
+ /*!
+   Sets <CODE>"*last"</CODE> to point at the last node of the linked lisk pointed by
+   <CODE>"linkedList"</CODE>, unless <CODE>"last"</CODE> is <CODE>NULL</CODE>.
+   Returns the numbers of nodes in the list.
+   You can also use the macro function <CODE>"NbrNodes(NodePtr linkedList);"</CODE>.
+   \see NbrNodes()
+ */
  UInt32 FindLast(NodePtr linkedList, NodePtr* last)
  {
!   
    NodePtr curNode;
    UInt32 nbrNodes = 0;
***************
*** 51,60 ****
  }
  
  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) )
--- 67,77 ----
  }
  
+ //! Finds the Nth node of a linked list.
+ /*!
+   Returns a pointer to the Nth node of the linked list, the first node
+   being node 0 (the 0th node), as with arrays.
+ */
  NodePtr GetNthNode(NodePtr linkedList, UInt32 n)
  {
    NodePtr curNode = linkedList;
    while ( (n--) && (curNode) )
***************
*** 63,73 ****
  }
  
  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;
--- 80,91 ----
  }
  
+ //! Splits a linked list in two.
+ /*!
+   Splits the linked list pointed by <CODE>"linkedList"</CODE> into 2 linked lists
+   after node <CODE>"n"</CODE>, the first node being node 0, as with arrays.
+   Returns a pointer to the beginning of the second linked list.
+ */
  NodePtr SplitAtNth(NodePtr linkedList, UInt32 n)
  {
    UInt32 curPos = 0;
    NodePtr curNode, copyPtr;
***************
*** 82,94 ****
  }
  
  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;
--- 100,114 ----
  }
  
+ //! Finds nodes in a linked list based on a "matching" function.
+ /*!
+   Using the key function <CODE>"IsWhatIWant"</CODE>, 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 <CODE>"DestroyLinkedList((Node*)(returnedIndirectList), DestroyIndirectNode);"</CODE>
+   to destroy the indirect linked list returned by this function.
+   \see DestroyLinkedList()
+ */
  IndirectNodePtr FindAndList(NodePtr linkedList, UInt8 (*IsWhatIWant)(NodePtr theNode))
  {
    NodePtr curNode;
    IndirectNodePtr foundList = NULL, lastInFoundList = NULL;
***************
*** 117,126 ****
  }
  
  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;
--- 137,148 ----
  }
  
+ //! Finds and removes nodes based on a "matching" function.
+ /*!
+   Does the same thing as <CODE>"FindAndList"</CODE>, but also removes all found nodes
+   and places them in a new single linked list, which is the returned value.
+   \see FindAndList()
+ */
  NodePtr FindAndMoveOut(NodePtr *linkedListPtr, UInt8 (*IsWhatIWant)(NodePtr theNode))
  {
    NodePtr *curNodePtrPtr, newList;
    IndirectNodePtr foundList = FindAndList(*linkedListPtr, IsWhatIWant), curIndirect;
***************
*** 150,162 ****
  }
  
  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;
--- 172,185 ----
  }
  
+ //! Applies an indirect linked list on a linked list.
+ /*!
+   Applies the ordering of an 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.
+ */
  void ApplyIndirectOnSimple(IndirectNodePtr indirectList)
  {
    IndirectNodePtr curIndirect;
    for (curIndirect = indirectList; curIndirect->nodeHeader.next;
***************
*** 171,181 ****
  }
  
  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;
--- 194,206 ----
  }
  
+ //! Inverses a linked list.
+ /*!
+   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.
+   \see InvertDoubleList
+ */
  void InvertList(NodePtr *linkedListPtr)
  {
    NodePtr newList, lastNode;
    UInt32 nbrNodes = NbrNodes(*linkedListPtr), curNth;
***************
*** 194,205 ****
  }
  
  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;
--- 219,231 ----
  }
  
+ //! Sorts a linked list.
+ /*!
+   Given a pointer to the beginning of a linked list and a compare function,
+   this function sorts the list using the "split-merge" algorythm.
+   <CODE>CompareFunction(NodePtr a, NodePtr b)</CODE> should return a value < 1 if and only if
+   a is smaller than b.
+ */
  void SplitAndMergeSort(NodePtr *linkedList, SInt8 (*CompareFunction)(NodePtr a, NodePtr b))
  {
    Node empty;
    NodePtr listA, listB, curNode = &empty, newList = &empty;
***************
*** 210,214 ****
    listB = SplitAtNth(listA, nbrNodesFullList/2);
  	
! 	/* ...(sorting)... */
    if (floor((double)(nbrNodesFullList)/2) > 1) /* Size of listA */
      SplitAndMergeSort(&listA, CompareFunction);
--- 236,240 ----
    listB = SplitAtNth(listA, nbrNodesFullList/2);
  	
!   /* ...(sorting)... */
    if (floor((double)(nbrNodesFullList)/2) > 1) /* Size of listA */
      SplitAndMergeSort(&listA, CompareFunction);
***************
*** 216,220 ****
      SplitAndMergeSort(&listB, CompareFunction);
  	
! 	/* ... and Merge */
    while (listA && listB)
    {
--- 242,246 ----
      SplitAndMergeSort(&listB, CompareFunction);
  	
!   /* ... and Merge */
    while (listA && listB)
    {
***************
*** 249,250 ****
--- 275,278 ----
    *linkedList = newList;
  }
+ 
+ /*! \} */

Index: LinkedLists.h
===================================================================
RCS file: /cvsroot/anet/ANet/ANet_Daemon/Common/Lists/LinkedLists.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** LinkedLists.h	2001/11/05 23:27:03	1.1
--- LinkedLists.h	2001/12/12 20:05:09	1.2
***************
*** 2,15 ****
  #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;
--- 2,34 ----
  #define __BENAD_LINKED_LISTS__
  
! /*!
!   \addtogroup lists Linked Lists
!   \ingroup utils
!   \brief Linked list utilities.
!   
!   Those are Link List utility functions.
!   They help the maintenance and use of single linked lists, double linked lists and of binary trees.
!   They are very low-level, thus making use of it will require use of typecasting. The trick is to make a new structure that starts with the <I>exact</I> same contents as the <CODE>Node</CODE> structure. Here's an example:
!   \code
!   struct MyNode {
!     Node n;
!     int val;
!   };\endcode
!   \{
! */
  
! /*!
!   \file
!   \brief Linked lists header.
!   
!   This file assumes that:
!   <UL><LI><CODE>char</CODE> =  8 bits,</LI>
!   <LI><CODE>short</CODE> = 16 bits and</LI>
!   <LI><CODE>long</CODE> = 32 bits.</LI></UL>
!   If this is false, just change the typedefs correctly.
  */
  
+ #ifndef __MACTYPES__
+ 
  typedef unsigned	char	UInt8;
  typedef signed		char	SInt8;
***************
*** 21,24 ****
--- 40,47 ----
  #endif /* #ifndef __MACTYPES__ */
  
+ //! A node in a single linked list.
+ /*!
+   The only thing that is assumed with the use of this function is that any structure that you want to use for a linked list node (whatever is the actual contents) starts with a pointer to the next node.
+ */
  typedef struct Node
  {
***************
*** 26,29 ****
--- 49,56 ----
  } Node, *NodePtr;
  
+ //! A node in a linked list that additionally points to a node in another list.
+ /*!
+   This is made to make an ordered list of some nodes in another, differently ordered list.
+ */
  typedef struct IndirectNode
  {
***************
*** 32,35 ****
--- 59,66 ----
  } IndirectNode, *IndirectNodePtr;
  
+ //! A node in a double linked list.
+ /*!
+   This node points to both directions in a linked list. Because it starts with the <CODE>next</CODE> pointer, it can be safely typecasted as a <CODE>Node</CODE>.
+ */
  typedef struct DoubleNode
  {
***************
*** 38,41 ****
--- 69,76 ----
  } DoubleNode, *DoubleNodePtr;
  
+ //! A node in a binary tree.
+ /*!
+   This node points to the left and right child in a binary tree.
+ */
  typedef struct BinaryNode
  {
***************
*** 46,49 ****
--- 81,88 ----
  UInt32 DestroyLinkedList(NodePtr linkedList, UInt8 (*DestructorFunction)(NodePtr theNode));
  UInt32 FindLast(NodePtr linkedList, NodePtr* last);
+ //! Returns the number of nodes in a list.
+ /*!
+   This is actually a macro, so be careful.
+ */
  #define NbrNodes(linkedList) FindLast(linkedList, NULL)
  NodePtr GetNthNode(NodePtr linkedList, UInt32 n);
***************
*** 62,65 ****
--- 101,109 ----
  		  SInt8 (*CompareFunction)(NodePtr a, NodePtr b));
  BinaryNodePtr SortedDoubleToBinaryWithSize(DoubleNodePtr linkedList, UInt32 size);
+ //! Transforms a double linked list into a binary tree.
+ /*!
+   This is a shortcut to the function <CODE>SortedDoubleToBinaryWithSize</CODE>.
+   \see SortedDoubleToBinaryWithSize()
+ */
  #define SortedDoubleToBinary(l) SortedDoubleToBinaryWithSize(l, NbrNodes((NodePtr)(l)));
  DoubleNodePtr BinaryToDouble(BinaryNodePtr root, UInt8 fillPrev);
***************
*** 70,71 ****
--- 114,117 ----
  
  #endif /* #ifndef __BENAD_LINKED_LISTS__ */
+ 
+ /*! \} */