First version

git-svn-id: svn://svn.rockbox.org/rockbox/trunk@187 a1c6a512-1295-4272-9138-f99709370657

2 files changed, 664 insertions, 0 deletions

diff --git a/firmware/common/lists.c b/firmware/common/lists.c
new file mode 100644
index 0000000000..46380e744f
--- /dev/null
+++ b/firmware/common/lists.c
@@ -0,0 +1,305 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * Copyright (C) 2002 by Linus Nielsen Feltzing
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+/*
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+  Description:
+  
+  This file contains functions implementing a double linked list. 
+  The functions uses the types LIST and LISTNODE.
+  There is a trick with the three nodes in LIST. By placing the 
+  tail_pred field in middle, makes it possible to avoid special code
+  to handle nodes in the beginning or end of the list.
+  
+  The 'head' and 'tail' field in LIST are never NULL, even if the
+  list is empty.
+  
+  The 'succ' and 'pred' field in a LIST_NODE that is in the list,
+  are never NULL. The 'pred' field for the first LIST_NODE points
+  to the 'head' field in LIST. The 'succ' node for the last LIST_NODE
+  points the the tail_pred field in LIST.
+  
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+*/
+#include "lists.h"
+
+/****************************************************************************
+** FUNCTION:    list_init
+**
+** DESCRIPTION: Initiate a LIST structure. 
+**              If max_num_nodes is set to NO_SIZE_CHECK there 
+**              will be no check of the length of the list.
+**
+** RETURN:      Nothing
+******************************************************************************/
+void list_init(LIST *list,         /* The list to initiate */
+	       int max_num_nodes)  /* Maximum number of nodes */
+{
+   list->first = (LIST_NODE *)&list->last_prev;
+   list->last_prev = NULL;
+   list->last = (LIST_NODE *)&list->first;
+   list->num_nodes = 0;
+   list->max_num_nodes = max_num_nodes;
+}
+
+/****************************************************************************
+** FUNCTION:    list_insert_before
+**
+** DESCRIPTION: Insert a LIST_NODE in a list before another node in a LIST.
+**
+** RETURN:      Nothing
+******************************************************************************/
+void list_insert_before(LIST_NODE *ref,    /* The reference node */
+			     LIST_NODE *ln)     /* The node to insert */
+{
+   ln->next = ref;               /* ref is after us */
+   ln->prev = ref->prev;         /* ref's prev is before us */
+   ref->prev = ln;               /* we are before ref */
+   ln->prev->next = ln;          /* we are after ref's prev */
+}
+
+/****************************************************************************
+** FUNCTION:    list_insert_after
+**
+** DESCRIPTION: Insert a LIST_NODE in a list after another node in a LIST.
+**
+** RETURN:      Nothing
+*****************************************************************************/
+void list_insert_after(LIST_NODE *ref,     /* The reference node */
+			    LIST_NODE *ln)      /* The node to insert */
+{
+   ln->prev = ref;               /* ref is before us */
+   ln->next = ref->next;         /* ref's next is after us */
+   ref->next = ln;               /* we are after ref */
+   ln->next->prev = ln;          /* we are before ref's next */
+}
+
+/****************************************************************************
+** FUNCTION:    list_extract_node
+**
+** DESCRIPTION: Extract a LIST_NODE from a list.
+**
+** RETURN:      The same LIST_NODE pointer that was passed as a parameter.
+*****************************************************************************/
+LIST_NODE *list_extract_node(LIST_NODE *ln)     /* The node to extract */
+{
+  ln->prev->next = ln->next;      /* Our prev's next points to our next */
+  ln->next->prev = ln->prev;      /* Our next's prev points to our prev */
+  return ln;
+}
+
+/******************************************************************************
+** FUNCTION:    list_add_first
+**
+** DESCRIPTION: Add a LIST_NODE at the beginning of a LIST.
+**
+** RETURN:      1 if OK
+**              0 if list was full
+******************************************************************************/
+int list_add_first(LIST *list,             /* The list to add to */
+                 LIST_NODE *ln)         /* The node to add */
+{
+   if (NO_SIZE_CHECK != list->max_num_nodes)
+   {
+      if(list->num_nodes >= list->max_num_nodes)  /* List full? */
+      {
+	 return 0;
+      }
+   }
+   list_insert_after((LIST_NODE *)list, ln);
+   list->num_nodes++;            /* Increment node counter */
+   return 1;
+}
+
+/******************************************************************************
+** FUNCTION:    list_extract_first
+**
+** DESCRIPTION: Extract a LIST_NODE from the beginning of a LIST.
+**
+** RETURN:      The extracted LIST_NODE or NULL if the list is empty
+******************************************************************************/
+LIST_NODE *list_extract_first(LIST *list)       /* The list to extract from */
+{
+   LIST_NODE *ln;
+  
+   if(list_empty(list))             /* Return NULL if the list is empty */
+   {
+      return NULL;
+   }
+  
+   ln = list_extract_node((LIST_NODE *)list->first);  /* Get first node */
+  
+   list->num_nodes--;                    /* Decrement node counter */
+  
+   return ln;
+}
+
+/******************************************************************************
+** FUNCTION:    list_add_last
+**
+** DESCRIPTION: Add a LIST_NODE at the end of a LIST.
+**
+** RETURN:      NULL if OK
+**              0 if list was full
+******************************************************************************/
+int list_add_last(LIST *list,              /* The list to add to */
+                LIST_NODE *ln)          /* The node to add */
+{
+   if (NO_SIZE_CHECK != list->max_num_nodes)
+   {
+      if(list->num_nodes >= list->max_num_nodes)  /* List full? */
+      {
+	 return 0;      
+      }
+   }
+   list_insert_before((LIST_NODE *)&list->last_prev, ln);
+   list->num_nodes++;                    /* Increment node counter */
+   return 1;
+}
+
+/******************************************************************************
+** FUNCTION:    list_extract_last
+**
+** DESCRIPTION: Extract a LIST_NODE from the end of a LIST.
+**
+** RETURN:      The extracted LIST_NODE or NULL if the list is empty
+******************************************************************************/
+LIST_NODE *list_extract_last(LIST *list)        /* The list to extract from */
+{
+   LIST_NODE *ln;
+  
+   if(list_empty(list))             /* Return NULL if the list is empty */
+   {
+      return NULL;
+   }
+  
+   ln = list_extract_node((LIST_NODE *)list->last);
+  
+   list->num_nodes--;    /* Decrement node counter */
+  
+   return ln;           /* Is NULL if the list is empty */
+}
+
+/******************************************************************************
+** FUNCTION:    list_last_in_list
+**
+** DESCRIPTION: Check if a LIST_NODE is last in the list
+**
+** RETURN:      1 if last in list
+******************************************************************************/
+int list_last_in_list(LIST_NODE *ln)    /* The node to check */
+{
+   return ln->next->next == NULL;
+}
+
+/*****************************************************************************
+** FUNCTION:    list_first_in_list
+**
+** DESCRIPTION: Check if a LIST_NODE is first in the list
+**
+** RETURN:      1 if first in list
+******************************************************************************/
+int list_first_in_list(LIST_NODE *ln)   /* The node to check */
+{
+   return ln->prev->prev == NULL;
+}
+
+/******************************************************************************
+** FUNCTION:    list_empty
+**
+** DESCRIPTION: Check if a LIST is empty
+**
+** RETURN:      1 if list is empty
+******************************************************************************/
+int list_empty(LIST *list)         /* The list to check */
+{
+   return list->first == (LIST_NODE *)&list->last_prev;
+}
+
+/******************************************************************************
+** FUNCTION:    list_get_first
+**
+** DESCRIPTION: Return a LIST_NODE from the beginning of a LIST.
+**
+** RETURN:      The first LIST_NODE or NULL if the list is empty
+******************************************************************************/
+LIST_NODE *list_get_first(LIST *lh)   /* The list to read from */
+{
+   LIST_NODE *ln;
+  
+   if(list_empty(lh))       /* Return NULL if the list is empty */
+   {
+      return NULL;
+   }
+  
+   return lh->first;     /* Get first node */
+}
+
+/******************************************************************************
+** FUNCTION:    list_get_last
+**
+** DESCRIPTION: Return a LIST_NODE from the end of a LIST.
+**
+** RETURN:      The last LIST_NODE or NULL if the list is empty
+******************************************************************************/
+LIST_NODE *list_get_last(LIST *lh)    /* The list to read from */
+{
+   LIST_NODE *ln;
+  
+   if(list_empty(lh))               /* Return NULL if the list is empty */
+   {
+      return NULL;
+   }
+  
+   return lh->last;
+}
+
+/******************************************************************************
+** FUNCTION:    list_get_next
+**
+** DESCRIPTION: Return the LIST_NODE following the specified one.
+**
+** RETURN:      Next LIST_NODE or NULL if the list ends here
+*******************************************************************************/
+LIST_NODE *list_get_next(LIST_NODE *ln) /* The list node to get next from */
+{
+   if(list_last_in_list(ln))       /* Return NULL if this is the end of list */
+   {
+      return NULL;
+   }
+  
+   return ln->next;
+}
+
+/******************************************************************************
+** FUNCTION:    list_get_prev
+**
+** DESCRIPTION: Return the LIST_NODE preceding the specified one.
+**
+** RETURN:      Previous LIST_NODE or NULL if the list ends here
+*******************************************************************************/
+LIST_NODE *list_get_prev(LIST_NODE *ln) /* The list node to get previous from */
+{
+   if(list_first_in_list(ln))            /* Return NULL if this is the start of list */
+   {
+      return NULL;
+   }
+  
+   return ln->prev;
+}
diff --git a/firmware/common/lists.h b/firmware/common/lists.h
new file mode 100644
index 0000000000..d9713b6a15
--- /dev/null
+++ b/firmware/common/lists.h
@@ -0,0 +1,359 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * Copyright (C) 2002 by Linus Nielsen Feltzing
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+#ifndef LISTS_INCLUDED
+#define LISTS_INCLUDED
+/*
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++  
+*               DESCRIPTION                                         *
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++  
+           
+  Functions for handling of a double linked list (code in lists.c):
+  
+  list_init                     - Initiate a LIST structure
+  list_insert_before            - Insert a node in a list before another node
+  list_insert_after             - Insert a node in a list after another node
+  list_extract                  - Extract a node from a list
+  list_extract_first            - Extract a node from the beginning of a list
+  list_extract_last             - Extract a node from the end of a list
+  list_add_first                - Add a node at the beginning of a list
+  list_add_last                 - Add a node at the end of a list
+  list_last_in_list             - Check if a node is last in the list
+  list_first_in_list            - Check if a node is first in the list
+  list_empty                    - Check if a list is empty
+  list_get_first                - Returns the first node in the list
+  list_get_last                 - Returns the last node in the list
+  list_get_next                 - Returns the next node
+  list_get_prev                 - Returns the previous node
+   
+ General about the list functions:
+ 
+ This package contains two structs and a set of functions implementing a
+ double linked list. When using a list with these, add nodes with
+ list_add_first or list_add_last and extract nodes with list_extract_first or list_extract_last.
+ 
+ A FIFO queue can be implemented using list_add_last to insert
+ nodes at the end and list_extract_first to extract nodes at the beginning
+ of the list.
+
+ When using the list-functions you need one instance of the type LIST
+ (contains the start pointer etc), You also need to call InitList once.
+ When calling InitList you decide if the list shall have a max size,
+ and if so how big it will be.
+ 
+ NOTE! when using list_insert_before, list_insert_after and
+ list_extract the num_nodes field in the LIST struct will not be updated.
+ 
+ To use the list-functions you define a struct with LIST_NODE as one member.
+ When a LIST_NODE is extracted from the list the address of the LIST_NODE 
+ is returned. If the LIST_NODE field is not the first field in your struct,
+ you must subtract the returned address with the size of the field that is 
+ before LIST_NODE in your struct to get the start address of your struct.
+    
+ For example: Consider you want to use the list-functions to implement a FIFO
+ queue for the test_list_sig signal, using the OSE operating system.
+ 
+ You may declare your signal struct something like:
+ 
+    typedef struct
+    {
+       SIGSELECT sig_no;
+       LIST_NODE list_node;
+       .
+       .
+    } TEST_LIST_STRUCT;
+    
+ In your code you may have:
+ 
+    LIST test_list;
+    TEST_LIST_STRUCT *list_sig;
+    LIST_NODE *ln;
+        
+    list_init_list(&test_list, MAX_NODES_IN_LIST);
+    
+    for(;;)
+    {
+        sig = receive(all);
+        switch(sig->sig_no)
+        {
+           case TEST_ADD:
+              if (list_add_first(&test_list, &sig->list_node))
+              {
+                  * The list was full *
+                  * Handle the returned sig *
+              }
+              
+           case TEST_REM:
+                if (ln = list_extract_last(&test_list))
+                {
+                  list_sig = (TEST_LIST_STRUCT *)((char)ln - sizeof(SIGSELECT));
+                  * Continue ... *
+                }
+                else
+                {
+                   * handle empty list *
+                   
+*/
+
+/*--------------------------------------------------------------------
+   List handling definitions
+----------------------------------------------------------------------*/
+
+/* Used as input parameter to list_init_list */
+#define NO_SIZE_CHECK 0
+
+#ifndef NULL
+#define NULL ((void *)0)
+#endif
+
+
+/***********************************************************************
+** Type definitions
+**
+** The LIST_NODE, and LIST types are used by the LIST class in common drv
+************************************************************************/
+
+
+typedef struct list_node
+{
+                                /*** NOTE! The next and prev fields 
+                                     are never NULL within a LIST.
+                                     Use list_first_in_list and 
+                                     list_last_in_list to check if a node 
+                                     is first or last in the list     ***/
+  struct list_node *next;            /* Successor node                  */
+  struct list_node *prev;            /* Predessor node                  */
+} LIST_NODE;
+
+typedef struct
+{
+  /* The three list node fields are 
+     used for internal represenation 
+     of the list.                               */
+  LIST_NODE *first;             /* First node in list                   */
+  LIST_NODE *last_prev;         /* Always NULL                          */
+  LIST_NODE *last;              /* Last node in list                    */
+  int num_nodes;                /* Number of nodes in list              */
+  int max_num_nodes;            /* Max number of nodes in list          */
+} LIST;
+
+
+/******************************************************************************
+**
+** FUNCTION:    list_init_list
+**
+** DESCRIPTION: Initiate a LIST structure.
+**
+** INPUT:       The LIST to be initiated
+**      
+**              Max nr of elements in the list, or NO_SIZE_CHECK if 
+**              list may be of any size
+*******************************************************************************
+*/
+void list_init_list(LIST *list,               /* The list to initiate */
+		    int max_num_nodes);       /* Maximum number of nodes */
+
+/******************************************************************************
+**
+** FUNCTION:    list_insert_before
+**
+** DESCRIPTION: Insert a LIST_NODE before another LIST_NODE in a LIST.
+**
+** INPUT:       The reference LIST_NODE
+**
+**              The LIST_NODE to be inserted
+**
+** OBSERVE:     When using list_insert_before, list_insert_after
+**              and list_extract the nume_nodes field in the LIST struct
+**              will not be updated.
+******************************************************************************
+*/
+void list_insert_before(LIST_NODE *ref,    /* The reference node */
+			LIST_NODE *ln);    /* The node to insert */
+
+/*****************************************************************************
+**
+** FUNCTION:    list_insert_after
+**
+** DESCRIPTION: Insert a LIST_NODE after another LIST_NODE in a LIST.
+**
+** INPUT:       The reference LIST_NODE
+**
+**              The LIST_NODE to be inserted
+**
+** OBSERVE:     When using list_insert_before, list_insert_after
+**              and list_extract the num_nodes field in the LIST struct
+**              will not be updated.
+*******************************************************************************
+*/
+void list_insert_after(LIST_NODE *ref,     /* The reference node */
+                     LIST_NODE *ln);       /* The node to insert */
+
+/******************************************************************************
+**
+** FUNCTION:    list_extract
+**
+** DESCRIPTION: Extract a LIST_NODE from a LIST.
+**
+** INPUT:       The LIST_NODE to be removed.
+**
+** RETURN:      The same LIST_NODE pointer that was passed as a parameter
+**
+** OBSERVE:     When using list_insert_before, list_insert_after
+**              and list_extract the num_nodes field in the LIST struct
+**              will not be updated.
+*******************************************************************************
+*/
+LIST_NODE *list_extract(LIST_NODE *ln);    /* The node to extract */
+
+/******************************************************************************
+**
+** FUNCTION:    list_add_first
+**
+** DESCRIPTION: Add a LIST_NODE at the beginning of a LIST.
+**
+** INPUT:       The LIST
+**
+**              The LIST_NODE 
+**
+** RETURN:      TRUE if OK
+**              FALSE if list is full
+*******************************************************************************
+*/
+int list_add_first(LIST *list,       /* The list to add to */
+		   LIST_NODE *ln);   /* The node to add */
+
+/******************************************************************************
+**
+** FUNCTION:    list_extract_first
+**
+** DESCRIPTION: Extract a LIST_NODE from the beginning of a LIST.
+**
+** INPUT:       The LIST from where a node is to be removed.
+**
+** RETURN:      The extracted LIST_NODE or NULL if the list is empty
+*******************************************************************************
+*/
+LIST_NODE *list_extract_first(LIST *list);      /* The list to extract from */
+
+/******************************************************************************
+**
+** FUNCTION:    list_add_last
+**
+** DESCRIPTION: Add a LIST_NODE at the end of a LIST.
+**
+** INPUT:       The LIST
+**
+**              The LIST_NODE 
+**
+** RETURN:      TRUE if OK
+**              FALSE if list is full
+*******************************************************************************
+*/
+int list_add_last(LIST *list,        /* The list to add to */
+		  LIST_NODE *ln);    /* The node to add  */
+/******************************************************************************
+**
+** FUNCTION:    list_extract_last
+**
+** DESCRIPTION: Extract a LIST_NODE from the end of a LIST.
+**
+** INPUT:       The LIST from where a node is to be removed.
+**
+** RETURN:      The extracted LIST_NODE or NULL if the list is empty
+*******************************************************************************
+*/
+LIST_NODE *list_extract_last(LIST *list);   /* The list to extract from */
+
+/******************************************************************************
+**
+** FUNCTION:    list_last_in_list
+**
+** DESCRIPTION: Check if a LIST_NODE is at the end of the list
+**
+** INPUT:       The LIST_NODE to check
+**
+** RETURN:      TRUE if LIST_NODE is last in the list, else FALSE.
+*******************************************************************************
+*/
+int list_last_in_list(LIST_NODE *ln);       /* The node to check */
+
+/******************************************************************************
+**
+** FUNCTION:    list_first_in_list
+**
+** DESCRIPTION: Check if a LIST_NODE is first in the list
+**
+** INPUT:       The LIST_NODE to check
+**
+** RETURN:      TRUE if LIST_NODE is first in the list, else FALSE.
+*******************************************************************************
+*/
+int list_first_in_list(LIST_NODE *ln);  /* The node to check */
+
+/******************************************************************************
+**
+** FUNCTION:    list_list_empty
+**
+** DESCRIPTION: Check if a LIST is empty
+**
+** INPUT:       The LIST to check
+**
+** RETURN:      TRUE if LIST is empty, else FALSE.
+**
+*******************************************************************************
+*/ 
+int list_empty(LIST *list);     /* The list to check */
+
+/******************************************************************************
+** FUNCTION:    list_get_first
+**
+** DESCRIPTION: Return a LIST_NODE from the beginning of a LIST.
+**
+** RETURN:      The first LIST_NODE or NULL if the list is empty
+******************************************************************************/
+LIST_NODE *list_get_first(LIST *lh);  /* The list to read from */
+
+/******************************************************************************
+** FUNCTION:    list_get_last
+**
+** DESCRIPTION: Return a LIST_NODE from the end of a LIST.
+**
+** RETURN:      The last LIST_NODE or NULL if the list is empty
+******************************************************************************/
+LIST_NODE *list_get_last(LIST *lh);   /* The list to read from */
+
+/******************************************************************************
+** FUNCTION:    list_get_next
+**
+** DESCRIPTION: Return the LIST_NODE following the specified one.
+**
+** RETURN:      Next LIST_NODE or NULL if the list ends here
+*******************************************************************************/
+LIST_NODE *list_get_next(LIST_NODE *ln); /* The list node to get next from */
+
+/******************************************************************************
+** FUNCTION:    list_get_prev
+**
+** DESCRIPTION: Return the LIST_NODE preceding the specified one.
+**
+** RETURN:      Previous LIST_NODE or NULL if the list ends here
+*******************************************************************************/
+LIST_NODE *list_get_prev(LIST_NODE *ln); /* The list node to get previous from */
+
+#endif /* LISTS_INCLUDED */