Doubly-linked list example


#1

Hi all,

The idea of this code is to create a linked list to buffer datas. For example, you can use this to buffer GPS infos and then send it thought GPRS. :open_mouth:

There is no way to put files into the forum, so I am copying the code here, see below instructions on how to use it. :smiley:

1 - Create a project using Open AT Project Wizard (this code works for any Open At version)
2 - Go to the project directory and create a directory named “inc”
3 - Inside this new “inc” directory, create a new file and named as “lla.h”
4 - Copy the code below to this new file
5 - Go to the “src” directory
6 - Replace the “appli.c” code for the one below and create a new file named “lla.c”, copy the code below into it.
7 - At the project directory, double click at the .scs file
8 - Click Ok to redo the project
9 - Now open Visual C++ or Eclipse and debug the code, it is the best way to understand how it works, go step by step into the adl_main function watching how the “buffer_1” variable changes !!!
10 - Have fun !!!

Source code for “lla.h”

#ifndef _LLA_
#define _LLA_

/*
Doubly-linked list 

Description:

  The idea of this code is to create a linked list to buffer datas. For example, you can use this to
  buffer GPS infos and then send it thought GPRS.

  The big difference from this code is the fact that it did not use dynamic memory allocation.
  Dynamic memory allocation can (depeending on the OS) corrupt the RAM and frezze the module,
  using knowm sizes of memory we can guarantee that the RAM area will be allocate to the list 
  and will never corrupt.

         cell 1      cell 2
		  ____		  ____
   -1 <--|last|	 |---|last|
		 |____|  |   |____|
		 |    |	 | 	 |    |
		 |data|<-||->|data| 
		 |____|	  |	 |____|
         |next|---|	 |next| --> -1 ( there is no next cell, so the value must be -1)
		 |____|		 |____|


Limitations:

  You can create many lists you want but all of them will have the same size and position number,
  as defined.
  You can just add datas at the end of the list.


Comments, bug reports and sugestions: gustavo.nunes@picomponentes.com.br

*/

#define LLA_VERSION 1.0

#define POSITIONS  10  //number of positions, or number of cells
#define POS_LENGTH 100 //number of bytes for each position

/*---------------------------------------------------------*/
/*
Structs
*/

struct lla_cell
{
	char data[POS_LENGTH];
	int  next;
	int  last;
};

struct lla_list
{
	struct lla_cell cell[POSITIONS];
	signed int free_pos; //the next free position of the list to be used
	signed int first_pos; //first position of the list
	signed int last_pos; //last position of the list
};

/*---------------------------------------------------------*/
/*
Functions
*/

/*list_init

Description: this function initialize the list, it is necessary
			 to run this function before use the list

Return: no returns

Parameters:

 -the list you want to initialize--|
								   |					   */
void list_init ( struct lla_list *list );

/*---------------------------------------------------------*/

/*list_add

Description: use this function to add new data to the list,
			 it will create a cell at the end of the list.

Return:  0 - success
		-1 - the list if full (the max number of cells is
							  defined as POSITIONS )
Parameters:

 -pointer to the data to be added----------|
 -pointer to the list------------|         |
								 |		   |			   */
int list_add ( struct lla_list *list, char *data );

/*---------------------------------------------------------*/

/*list_read

Description: use this function to read any position of the 
			 list, if pos is NULL, the function will return
			 the first position of the list

Return: - a pointer to the data
		- NULL if the position does not exist or if the list is
		  empty

Parameters:

  -position to be read-------------------------|
  -pointer to the list---------------|		   |
									 |		   |		   */
char * list_read ( struct lla_list *list, int pos );

/*---------------------------------------------------------*/

/*list_delete

Description: use this function to delete any cell of the list,
			 if pos is NULL, it will delete he first cell of
			 the list

Return:  0 - success
		-1 - the list is empty or the position does not exist

Parameters:

  -position to be read-------------------------|
  -pointer to the list---------------|		   |
									 |		   |		   */
int list_delete ( struct lla_list *list, int pos );

/*---------------------------------------------------------*/

#endif

Source code for “appli.c”

/********************************************************************************************/
/*  Appli.c   -  Copyright Wavecom S.A. (c) 2002										    */
/*																							*/
/*																							*/
/* DISCLAIMER OF WARRANTY																    */
/* ======================																    */
/* This Software is provided free of charge on an 'as is' basis. No warranty is given       */
/* by Wavecom S.A. in relation to the Software of the uses to which it may be put by you,   */
/* the user, or its merchantability, fitness or suitability for any particular purpose      */
/* or conditions; and/or that the use of the Software and all documentation relating        */
/* thereto by the Licensee will not infringe any third party copyright or other             */
/* intellectual property rights. Wavecom S.A. shall furthermore be under no obligation      */
/* to provide support of any nature for the Software and the Documentation.				    */
/*																						    */
/* LIMIT OF LIABILITY																	    */
/* ==================																		*/
/* In no event shall Wavecom S.A. be liable for any loss or damages whatsoever or howsoever	*/
/* caused arising directly or indirectly in connection with this licence, the Software,		*/
/* its use or otherwise except to the extent that such liability may not be lawfully		*/
/* excluded. Notwithstanding the generality of the foregoing, Wavecom S.A. expressly		*/
/* excludes liability for indirect, special, incidental or consequential loss or damage		*/
/* which may arise in respect of the Software or its use, or in respect of other equipment	*/
/* or property, or for loss of profit, business, revenue, goodwill or anticipated savings.	*/
/*																						    */
/********************************************************************************************/

/***************************************************************************/
/*  File       : Appli.c                                                   */
/*-------------------------------------------------------------------------*/
/*  Object     : Customer application                                      */
/*                                                                         */
/*  contents   : Customer main procedures                                  */
/*                                                                         */
/*  Change     :                                                           */
/***************************************************************************/
/*
    $LogWavecom: G:\projet\mmi\pvcsarch\archives\open-mmi\SAMPLES\adl\New_Project\src\appli.c-arc $
 * --------------------------------------------------------------------------
 *  Date     | Author | Revision       | Description
 * ----------+--------+----------------+-------------------------------------
 *  25.10.05 | DPO    | 1.1            | * New V4 interface                 
 * ----------+--------+----------------+-------------------------------------
 *  16.12.02 | dpo    | 1.0            | Initial revision.                  
 * ----------+--------+----------------+-------------------------------------
*/

#include "adl_global.h"
#include "lla.h"

/***************************************************************************/
/*  Mandatory variables                                                    */
/*-------------------------------------------------------------------------*/
/*  wm_apmCustomStackSize                                                  */
/*-------------------------------------------------------------------------*/
/***************************************************************************/
const u16 wm_apmCustomStackSize = 1024;


/***************************************************************************/
/*  Local variables                                                        */
/***************************************************************************/

struct lla_list buffer_1;
/***************************************************************************/
/*  Local functions                                                        */
/***************************************************************************/


/***************************************************************************/
/*  Function   : adl_main                                                  */
/*-------------------------------------------------------------------------*/
/*  Object     : Customer application initialisation                       */
/*                                                                         */
/*-------------------------------------------------------------------------*/
/*  Variable Name     |IN |OUT|GLB|  Utilisation                           */
/*--------------------+---+---+---+----------------------------------------*/
/*  InitType          |   |   |   |  Application start mode reason         */
/*--------------------+---+---+---+----------------------------------------*/
/***************************************************************************/
void adl_main ( adl_InitType_e InitType )
{
	char *data;

    TRACE (( 1, "Embedded Application : Main" ));
    
    // TO DO : Add your initialization code here

	list_init (&buffer_1); //list init

	//add cells to the list
	list_add ( &buffer_1, "lat:xx,lon:yy" ); 
	list_add ( &buffer_1, "test---" );
	list_add ( &buffer_1, "Van Halen" );

	//read the first cell
	data = list_read (&buffer_1, (int) NULL );

	list_delete( &buffer_1, 2 ); //delete cell at position 2

	list_delete( &buffer_1, (int) NULL ); //delete the first position
}

Source code for “lla.c”

#include "adl_global.h"
#include "lla.h"

/*---------------------------------------------------------*/
void list_init ( struct lla_list *list )
{
	int i;

	//list inicialization

	(*list).first_pos = -1; //the list is clear so there is no first position
	(*list).free_pos  =  0; //the first free position is 0
	(*list).last_pos  = -1; //the list is clear so there is not last position

	for( i=0; i<POSITIONS; i++ )
	{
		list->cell[i].last = i-1;
		list->cell[i].next = i+1;

		if( i == POSITIONS-1 )
		{
			list->cell[i].next = -1;
		}
	}

}

/*---------------------------------------------------------*/
int list_add ( struct lla_list *list, char *data )
{
	int act;

	if ( (*list).free_pos < 0 ) //if free_pos is negative, the list is full
	{
		return -1;
	}

	strcpy( (*list).cell[(*list).free_pos].data, data ); //copy the data to the list

	act = (*list).last_pos;
	(*list).last_pos = (*list).free_pos; //update the last position
	
	(*list).free_pos = (*list).cell[(*list).free_pos].next; //update the free position

	if ( act == -1 ) //check if list is empty
	{
		(*list).first_pos = (*list).last_pos; //if it is the first data, first pos is equal last pos

		(*list).cell[(*list).last_pos].next = -1;
		(*list).cell[(*list).first_pos].last = -1;

	}else{

		(*list).cell[act].next = (*list).last_pos;
		(*list).cell[(*list).last_pos].last = act;
		(*list).cell[(*list).last_pos].next = -1;

	}

	return 0;
}

/*---------------------------------------------------------*/
char * list_read ( struct lla_list *list, int pos )
{
	int act,i;

	act = (*list).first_pos; //update act as the first position of the list

	i=0;
	do
	{
		if( act < 0 ) //if act is negative, the list is empty or the pos does not exist
		{
			return NULL;
		}

		if( pos == (int) NULL ) //if pos is NULL, read the first position
		{
			break;
		}

		if( i != pos ) //if i is different from pos, update act
		{
			act = (*list).cell[act].next;
		}

		i++;

	}while( i < pos );

	return list->cell->data;
}

/*---------------------------------------------------------*/
int list_delete ( struct lla_list *list, int pos )
{
	int i;
	int act;
	int tmp;

	act = (*list).first_pos; //update act as the first position of the list

	i=0;
	do
	{
		if( act < 0 ) //if act is negative, the list is empty or the pos does not exist
		{
			return -1;
		}

		if( pos == (int) NULL ) //if pos is NULL, delete the first position
		{
			break;
		}

		if( i != pos ) //if i is different from pos, update act
		{
			act = (*list).cell[act].next;
		}

		i++;

	}while( i < pos );

	tmp = (*list).cell[act].last;

	if( tmp < 0 ) //check if it is the first position
	{
		(*list).first_pos = (*list).cell[act].next;

	}else{

		(*list).cell[tmp].next= (*list).cell[act].next;

	}

	tmp = (*list).cell[act].next;

	if( tmp < 0 ) //check if it is the last position
	{
		(*list).last_pos = (*list).cell[act].last;
	}else{
		(*list).cell[tmp].last = (*list).cell[act].last;
	}

	//update the list
	(*list).cell[act].next = (*list).free_pos;
	(*list).free_pos = act;

	return 0;
}

/*---------------------------------------------------------*/

#2

Hmm… but you seem to be copying data into the list using strcpy without checking that the string size does not exceed the cell size… :open_mouth:


#3

Awneil,

Maybe I can change for:

strncpy( (*list).cell[(*list).free_pos].data, data, POS_LENGTH);

or do you think it is better to return an error ???


#4

Hi,

your code looks like LISP :slight_smile:

Is there a reason why you use (*list).cell[(*list).free_pos] instead of list->cell[list->free_pos]? I guess it is a matter of style, but I think in C programs you usually use the -> notation, which I think is more readable…

Best Regards,
Jan


#5

It is not a question of either/or - you must do both!

You propose that your code is safer than dynamic allocation - so you need to ensure that it really is safe and that the user is advised of any errors!

I agree with Jan that list->cell[list->free_pos] would be the more usual ‘C’ idiom and, therefore, easier for ‘C’ programmers to read.


#6

To be really safe maybe he should copy with POS_LENGTH-1 and insert a null character at the end of the buffer himself

Best Regards,
Ralf


#7

Guys,

I will do the modifications and post here ASAP !!!

Tks for all!!

Gus


#8

Please also tidy up the comments.

I suspect that you have used TABs to lay-out your text?
You need to use just spaces - TABs are inherently non-portable! :frowning: