1 files changed, 305 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.c b/firmware/common/lists.c new file mode 100644 index 0000000000..46380e744f --- /dev/null +++ b/firmware/common/lists.c
@@ -0,0 +1,305 @@
	1	/***************************************************************************
	2	* __________ __ ___.
	3	* Open \______ \ ____ ____ \| \| _\_ \|__ _______ ___
	4	* Source \| _// _ \_/ ___\\| \|/ /\| __ \ / _ \ \/ /
	5	* Jukebox \| \| ( <_> ) \___\| < \| \_\ ( <_> > < <
	6	* Firmware \|____\|_ /\____/ \___ >__\|_ \\|___ /\____/__/\_ \
	7	* \/ \/ \/ \/ \/
	8	* $Id$
	9	*
	10	* Copyright (C) 2002 by Linus Nielsen Feltzing
	11	*
	12	* All files in this archive are subject to the GNU General Public License.
	13	* See the file COPYING in the source tree root for full license agreement.
	14	*
	15	* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
	16	* KIND, either express or implied.
	17	*
	18	****************************************************************************/
	19	/*
	20	++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	21
	22	Description:
	23
	24	This file contains functions implementing a double linked list.
	25	The functions uses the types LIST and LISTNODE.
	26	There is a trick with the three nodes in LIST. By placing the
	27	tail_pred field in middle, makes it possible to avoid special code
	28	to handle nodes in the beginning or end of the list.
	29
	30	The 'head' and 'tail' field in LIST are never NULL, even if the
	31	list is empty.
	32
	33	The 'succ' and 'pred' field in a LIST_NODE that is in the list,
	34	are never NULL. The 'pred' field for the first LIST_NODE points
	35	to the 'head' field in LIST. The 'succ' node for the last LIST_NODE
	36	points the the tail_pred field in LIST.
	37
	38	++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	39	*/
	40	#include "lists.h"
	41
	42	/****************************************************************************
	43	** FUNCTION: list_init
	44	**
	45	** DESCRIPTION: Initiate a LIST structure.
	46	** If max_num_nodes is set to NO_SIZE_CHECK there
	47	** will be no check of the length of the list.
	48	**
	49	** RETURN: Nothing
	50	******************************************************************************/
	51	void list_init(LIST list, / The list to initiate */
	52	int max_num_nodes) /* Maximum number of nodes */
	53	{
	54	list->first = (LIST_NODE *)&list->last_prev;
	55	list->last_prev = NULL;
	56	list->last = (LIST_NODE *)&list->first;
	57	list->num_nodes = 0;
	58	list->max_num_nodes = max_num_nodes;
	59	}
	60
	61	/****************************************************************************
	62	** FUNCTION: list_insert_before
	63	**
	64	** DESCRIPTION: Insert a LIST_NODE in a list before another node in a LIST.
	65	**
	66	** RETURN: Nothing
	67	******************************************************************************/
	68	void list_insert_before(LIST_NODE ref, / The reference node */
	69	LIST_NODE ln) / The node to insert */
	70	{
	71	ln->next = ref; /* ref is after us */
	72	ln->prev = ref->prev; /* ref's prev is before us */
	73	ref->prev = ln; /* we are before ref */
	74	ln->prev->next = ln; /* we are after ref's prev */
	75	}
	76
	77	/****************************************************************************
	78	** FUNCTION: list_insert_after
	79	**
	80	** DESCRIPTION: Insert a LIST_NODE in a list after another node in a LIST.
	81	**
	82	** RETURN: Nothing
	83	*****************************************************************************/
	84	void list_insert_after(LIST_NODE ref, / The reference node */
	85	LIST_NODE ln) / The node to insert */
	86	{
	87	ln->prev = ref; /* ref is before us */
	88	ln->next = ref->next; /* ref's next is after us */
	89	ref->next = ln; /* we are after ref */
	90	ln->next->prev = ln; /* we are before ref's next */
	91	}
	92
	93	/****************************************************************************
	94	** FUNCTION: list_extract_node
	95	**
	96	** DESCRIPTION: Extract a LIST_NODE from a list.
	97	**
	98	** RETURN: The same LIST_NODE pointer that was passed as a parameter.
	99	*****************************************************************************/
	100	LIST_NODE list_extract_node(LIST_NODE ln) /* The node to extract */
	101	{
	102	ln->prev->next = ln->next; /* Our prev's next points to our next */
	103	ln->next->prev = ln->prev; /* Our next's prev points to our prev */
	104	return ln;
	105	}
	106
	107	/******************************************************************************
	108	** FUNCTION: list_add_first
	109	**
	110	** DESCRIPTION: Add a LIST_NODE at the beginning of a LIST.
	111	**
	112	** RETURN: 1 if OK
	113	** 0 if list was full
	114	******************************************************************************/
	115	int list_add_first(LIST list, / The list to add to */
	116	LIST_NODE ln) / The node to add */
	117	{
	118	if (NO_SIZE_CHECK != list->max_num_nodes)
	119	{
	120	if(list->num_nodes >= list->max_num_nodes) /* List full? */
	121	{
	122	return 0;
	123	}
	124	}
	125	list_insert_after((LIST_NODE *)list, ln);
	126	list->num_nodes++; /* Increment node counter */
	127	return 1;
	128	}
	129
	130	/******************************************************************************
	131	** FUNCTION: list_extract_first
	132	**
	133	** DESCRIPTION: Extract a LIST_NODE from the beginning of a LIST.
	134	**
	135	** RETURN: The extracted LIST_NODE or NULL if the list is empty
	136	******************************************************************************/
	137	LIST_NODE list_extract_first(LIST list) /* The list to extract from */
	138	{
	139	LIST_NODE *ln;
	140
	141	if(list_empty(list)) /* Return NULL if the list is empty */
	142	{
	143	return NULL;
	144	}
	145
	146	ln = list_extract_node((LIST_NODE )list->first); / Get first node */
	147
	148	list->num_nodes--; /* Decrement node counter */
	149
	150	return ln;
	151	}
	152
	153	/******************************************************************************
	154	** FUNCTION: list_add_last
	155	**
	156	** DESCRIPTION: Add a LIST_NODE at the end of a LIST.
	157	**
	158	** RETURN: NULL if OK
	159	** 0 if list was full
	160	******************************************************************************/
	161	int list_add_last(LIST list, / The list to add to */
	162	LIST_NODE ln) / The node to add */
	163	{
	164	if (NO_SIZE_CHECK != list->max_num_nodes)
	165	{
	166	if(list->num_nodes >= list->max_num_nodes) /* List full? */
	167	{
	168	return 0;
	169	}
	170	}
	171	list_insert_before((LIST_NODE *)&list->last_prev, ln);
	172	list->num_nodes++; /* Increment node counter */
	173	return 1;
	174	}
	175
	176	/******************************************************************************
	177	** FUNCTION: list_extract_last
	178	**
	179	** DESCRIPTION: Extract a LIST_NODE from the end of a LIST.
	180	**
	181	** RETURN: The extracted LIST_NODE or NULL if the list is empty
	182	******************************************************************************/
	183	LIST_NODE list_extract_last(LIST list) /* The list to extract from */
	184	{
	185	LIST_NODE *ln;
	186
	187	if(list_empty(list)) /* Return NULL if the list is empty */
	188	{
	189	return NULL;
	190	}
	191
	192	ln = list_extract_node((LIST_NODE *)list->last);
	193
	194	list->num_nodes--; /* Decrement node counter */
	195
	196	return ln; /* Is NULL if the list is empty */
	197	}
	198
	199	/******************************************************************************
	200	** FUNCTION: list_last_in_list
	201	**
	202	** DESCRIPTION: Check if a LIST_NODE is last in the list
	203	**
	204	** RETURN: 1 if last in list
	205	******************************************************************************/
	206	int list_last_in_list(LIST_NODE ln) / The node to check */
	207	{
	208	return ln->next->next == NULL;
	209	}
	210
	211	/*****************************************************************************
	212	** FUNCTION: list_first_in_list
	213	**
	214	** DESCRIPTION: Check if a LIST_NODE is first in the list
	215	**
	216	** RETURN: 1 if first in list
	217	******************************************************************************/
	218	int list_first_in_list(LIST_NODE ln) / The node to check */
	219	{
	220	return ln->prev->prev == NULL;
	221	}
	222
	223	/******************************************************************************
	224	** FUNCTION: list_empty
	225	**
	226	** DESCRIPTION: Check if a LIST is empty
	227	**
	228	** RETURN: 1 if list is empty
	229	******************************************************************************/
	230	int list_empty(LIST list) / The list to check */
	231	{
	232	return list->first == (LIST_NODE *)&list->last_prev;
	233	}
	234
	235	/******************************************************************************
	236	** FUNCTION: list_get_first
	237	**
	238	** DESCRIPTION: Return a LIST_NODE from the beginning of a LIST.
	239	**
	240	** RETURN: The first LIST_NODE or NULL if the list is empty
	241	******************************************************************************/
	242	LIST_NODE list_get_first(LIST lh) /* The list to read from */
	243	{
	244	LIST_NODE *ln;
	245
	246	if(list_empty(lh)) /* Return NULL if the list is empty */
	247	{
	248	return NULL;
	249	}
	250
	251	return lh->first; /* Get first node */
	252	}
	253
	254	/******************************************************************************
	255	** FUNCTION: list_get_last
	256	**
	257	** DESCRIPTION: Return a LIST_NODE from the end of a LIST.
	258	**
	259	** RETURN: The last LIST_NODE or NULL if the list is empty
	260	******************************************************************************/
	261	LIST_NODE list_get_last(LIST lh) /* The list to read from */
	262	{
	263	LIST_NODE *ln;
	264
	265	if(list_empty(lh)) /* Return NULL if the list is empty */
	266	{
	267	return NULL;
	268	}
	269
	270	return lh->last;
	271	}
	272
	273	/******************************************************************************
	274	** FUNCTION: list_get_next
	275	**
	276	** DESCRIPTION: Return the LIST_NODE following the specified one.
	277	**
	278	** RETURN: Next LIST_NODE or NULL if the list ends here
	279	*******************************************************************************/
	280	LIST_NODE list_get_next(LIST_NODE ln) /* The list node to get next from */
	281	{
	282	if(list_last_in_list(ln)) /* Return NULL if this is the end of list */
	283	{
	284	return NULL;
	285	}
	286
	287	return ln->next;
	288	}
	289
	290	/******************************************************************************
	291	** FUNCTION: list_get_prev
	292	**
	293	** DESCRIPTION: Return the LIST_NODE preceding the specified one.
	294	**
	295	** RETURN: Previous LIST_NODE or NULL if the list ends here
	296	*******************************************************************************/
	297	LIST_NODE list_get_prev(LIST_NODE ln) /* The list node to get previous from */
	298	{
	299	if(list_first_in_list(ln)) /* Return NULL if this is the start of list */
	300	{
	301	return NULL;
	302	}
	303
	304	return ln->prev;
	305	}