Publi

Listas enlazadas en Arduino (primera versión)

Es parte de un proyecto personal que quiero compartir. Se trata de una clase para utilizar listas enlazadas desde Arduino, aunque la memoria RAM de estos bichillos no sea gran cosa (1K para la versión Diecimila), puede dar para mucho, y es que hay ocasiones en las que podemos necesitar esta flexibilidad a la hora de almacenar y acceder a la información (aunque no pueda ser mucha).

La clase ha sido desarrollada utilizando templates, por lo que podréis particularizar esta clase para cualquier tipo de dato que estéis manejando. Declarando la lista de la siguiente forma:

1
LList <tipo> lista;

Antes de dar el código, hagamos algunas operaciones, vamos a ver lo que podemos hacer con 1K (vale con 600 bytes libres):

  • Con un tipo int, cada nodo ocupará 4 bytes: 600 / 4 = 150 nodos (alguno menos en realidad). Pero estos nodos pueden indicar posiciones en un mapa, un pequeño informe de lo que ha transcurrido, lecturas, estado de periféricos, etc
  • Con un tipo:
    1
    2
    3
    4
    5
    struct Map
    {
      int key;
      int value;
    }

    : podemos almacenar 600/6 = 100 elementos con clave y valor, por ejemplo, una matriz o vector disperso que nos pueden ayudar para un cálculo matemático

  • Lo malo son las cadenas, no podemos escribir un libro, pero si hacemos un tipo que almacene unas 28 letras, cuyo nodo ocupará 30 bytes, podremos almacenar 600/30=20 mensajes distintos, aunque recomiendo que esos mensajes sean generados por el programa, ya que si los mensajes son predefinidos, podemos almacenarlos en la memoria flash, que tendremos más sitio.

Ahí va el código para los copy-paste aunque el archivo lo podéis bajar de aquí (9.5Kb). Por cierto, al final del archivo hay un código de ejemplo para probar que todo funcione bien.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
/**
*************************************************************
* @file ArduinoList.pde
* Another implementation of linked lists to use in Arduino.
*    Copyright (C) 2011 Gaspar Fernández
*
*    This program is free software: you can redistribute it and/or modify
*    it under the terms of the GNU General Public License as published by
*    the Free Software Foundation, either version 3 of the License, or
*    (at your option) any later version.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*
*    You should have received a copy of the GNU General Public License
*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*
* @brief Linked list implementation for Arduino
*
* Features:
*   - Can access to head and tail directly
*   - Can pop back and front from this class
*   - Can access any item from the item number
*   - Can set a callback function when an error occurs
*
* @author Gaspar Fernández <blakeyed@totaki.com>
* @web https://poesiabinaria.net
* @version 0.1
* @date 27 nov 2011
* Change history
*
* To-do:
*   - Better control over non-critical errors, maybe another callback
*   - Pre-defined error methods: by serial, by output leds...
*************************************************************/


#define LLIST_ERROR_NOMEMORY     1 // Not enough memory to insert element
#define LLIST_ERROR_NOTAIL       2 // Can't get last items
#define LLIST_ERROR_NOFRONT      3 // Can't get head items
#define LLIST_ERROR_NOITEMS      4 // List empty, can't read items
#define LLIST_ERROR_NEITEMS      5 // Not enough items (pos>=sz)

template <typename Type>
class LList
{
public:
  typedef void (*ErrorCallback)(int);

  // We can add more error types
  enum ListErrorType
    {
      NO_ERROR_REPORTING,   // No error reporting
      CALLBACK          // Errors will trigger a callback
    };

  // Destruction. Clear data
  ~LList();

  // Initialization
  LList();

  // Inserts new item in the last position
  void push_back(const Type item);
  // Is the list empty?
  inline bool isEmpty() const;
  // Returns the size of the list
  inline int size();
  // Returns the last item
  inline Type back();
  // Returns the first item
  inline Type front();
  // Return the last item and delete it
  Type pop_back();
  // Return the first item and delete it
  Type pop_front();

  // Get the item at position pos
  Type getElement(unsigned pos);
  // Insert a new item at position pos
  void insert(int pos, Type item);
  // set error callback function
  void setErrorCallback(ErrorCallback cback);
  // no error reporting
  void setNoErrorReporting();
  // clears the list
  void clear();
private:
  // Reports an error
  void report_error(int err);
 
  // Deletes a list when there is only one element
  void delete_list();

  typedef struct node
  {
    Type item;
    node *next;
  } node;

  node *head;           // Pointer to the head
  node *tail;           // Pointer to the tail
  int sz;           // List size
  ListErrorType errorType; 
  ErrorCallback ecback;     // Callback when reporting an error
};

template <typename Type>
LList<Type>::LList()
{
  head=NULL;
  tail=NULL;
  sz=0;
  errorType=NO_ERROR_REPORTING;
}

template <typename Type>
LList<Type>::~LList()
{
  clear();          // Clears the list before destroying
}

template <typename Type>
void LList<Type>::push_back(const Type item)
{
  node *aux=tail;
 
  // Reserve memory for a new node
  tail=(node*)malloc(sizeof(node));
  if (tail==NULL)
    {
      report_error(LLIST_ERROR_NOMEMORY);
      return;
    }

  // Stores the item information
  tail->item=item;
  tail->next=NULL;

  // Link to the list
  if (isEmpty())
    head=tail;
  else
    aux->next=tail;

  sz++;

}

template <typename Type>
bool LList<Type>::isEmpty() const
{
  return (sz==0);       // (sz==0) = EMPTY
}

template <typename Type>
int LList<Type>::size()
{
  return sz;
}

template <typename Type>
inline Type LList<Type>::back()
{
  if (isEmpty())        // List empty = No last item
    {
      Type t;
      report_error(LLIST_ERROR_NOTAIL);
      return t;
    }

  return tail->item;
}

template <typename Type>
inline Type LList<Type>::front()
{
  if (isEmpty())        // List empty = No first item
    {
      Type t;
      report_error(LLIST_ERROR_NOFRONT);
      return t;
    }

  return head->item;
}

template <typename Type>
Type LList<Type>::pop_back()
{
  node *aux=head;
  Type t;

  if (isEmpty())        // List empty = No last item
    {
      report_error(LLIST_ERROR_NOTAIL);
      return t;
    }
 
  if (head==tail)       // If there is only 1 item
    {
      t=head->item;
      delete_list();
      return t;
    }
  else
    {               // More than one item
      while (aux->next!=tail)   // Searches for the item previous to the last
    aux=aux->next;
     
      t=tail->item;     // I will return the tail item
      free(tail);      
      tail=aux;         // Define the new tail
      tail->next=NULL;
      sz--;         // 1 item less

      return t;
    }
}

template <typename Type>
Type LList<Type>::pop_front()
{
  Type t;
  node *aux=head;
 
  if (isEmpty())        // List empty = No head
    {
      report_error(LLIST_ERROR_NOFRONT);
      return t;
    }

  t=aux->item;          // I will return the head
  head=head->next;      // The new head is the item after the head
  free(aux);
  if (head==NULL)       // If I had deleted the last item, replace the tail
    tail=NULL;          // too.
  sz--;

  return t;
}

template <typename Type>
void LList<Type>::delete_list()
{
  free(head);           // I will call this method when deleting
  head=NULL;            // a list with only one element, so all
  tail=NULL;            // the variables are set.
  sz=0;
}

template <typename Type>
void LList<Type>::insert(int pos, Type item)
{
  node *newitem;
  node *aux=head;
  int i;

  // Allocate memory for the new item
  newitem=(node*)malloc(sizeof(node));
  if (newitem==NULL)
    {
      report_error(LLIST_ERROR_NOMEMORY);
      return;
    }
  // Stores the item information
  newitem->item=item;
  newitem->next=NULL;

  // Link the item to the list
  if (isEmpty())
    {               // If the list is empty there will be only
      head=newitem;     // one item, so it will be the head and the
      tail=newitem;     // tail.
    }
  else if (pos==0)      // If the item is going to be inserted at the beginning
    {
      newitem->next=head;   // we will move the head
      head=newitem;
    }
  else if (pos>=sz)     // If the position is greater than the last item's position
    {               // it will be inserted after this item, at the tail.
      tail->next=newitem;      
      tail=newitem;
    }
  else
    {               // If not, we will have to find the position of the
      i=0;          // previous item to link its next pointer to the new
      while (i<pos-1)       // element.
    {
      aux=aux->next;
      ++i;
    }
      newitem->next=aux->next;  // And then link the next pointer of our new element
      aux->next=newitem;    // to where the next pointer of the previour element
    }               // was pointing.
  sz++;
}

template <typename Type>
Type LList<Type>::getElement(unsigned pos)
{
  int i=0;
  Type t;
  node *aux=head;

  if (isEmpty())        // If the list is empty = No data
    {
      report_error(LLIST_ERROR_NOITEMS);
      return t;
    }

  if (pos>=sz)          // If the item asked for is greater than the
    {               // last item's position. There is no valid element
      report_error(LLIST_ERROR_NEITEMS);
      return t;
    }
 
  if (pos==sz-1)        // If the item we asked for is the last, we can
    return tail->item;      // return it inmediately


  while (i<pos)         // If not, we must look for it
    {
      aux=aux->next;
      i++;
    }
  return aux->item;
}

template <typename Type>
void LList<Type>::setErrorCallback(ErrorCallback cback)
{
  ecback=cback;         // This method sets the error callback to invoke
  errorType=CALLBACK;       // when an error occurs.
}

template <typename Type>
void LList<Type>::report_error(int err)
{
  if (errorType==CALLBACK)  // If the error reporting is through a callback,
    {               // call it.
      ecback(err);
    }
}

template <typename Type>
void LList<Type>::clear()
{
  node *aux;

  while (head!=NULL)        // Delete all elements
    {
      aux=head;
      head=head->next;
      free(aux);
    }
 
  tail=NULL;            // Restore variable stats
  sz=0;
}  

template <typename Type>
void LList<Type>::setNoErrorReporting()
{
  errorType=NO_ERROR_REPORTING;
}

// Test program
// LList<int> l;

// void blink(int err)
// {
//   while (1)
//     {
//       digitalWrite(11,HIGH);
//       delay(1000);
//       digitalWrite(11, LOW);
//       delay(1000);  
//     }
// }

// void setup()
// {
//   pinMode(11, OUTPUT);
//   Serial.begin(9600);
//   l.setErrorCallback(blink);
//   l.push_back(45);
//   l.push_back(42);
//   l.push_back(47);
//   l.push_back(89);
//   l.insert(0, 33);
//   l.insert(1, 53);
//   l.insert(9, 73);
//   // 33
//   // 53
//   // 45
//   // 42
//   // 47
//   // 89
//   // 73
// }

// void loop()
// {
//   char r;
//   if (Serial.available()>0)
//     {
//       while (Serial.available()>0)
//  {
//    r=Serial.read();
//    delayMicroseconds(10000);
//  }

//       for (unsigned i=0; i<l.size(); i++)
//  {
//    Serial.println(l.getElement(i), DEC);
//  }
//       Serial.print("Elements: ");
//       Serial.println(l.size(), DEC);
//       Serial.print("Last: ");
//       Serial.println(l.pop_front(), DEC);
//     }
// }

También podría interesarte...

There are 6 comments left Ir a comentario

  1. Pingback: Bitacoras.com /

  2. Pingback: BlogESfera.com /

  3. Nico /
    Usando Google Chrome Google Chrome 25.0.1364.160 en Ubuntu Linux Ubuntu Linux

    Hola, una consulta amigo, si quisiera traer los datos de un Objeto.
    Ejemplo, tengo una lista declarada asi:
    LList listavalores;

    Donde ValorEntero es una clase que tiene 2 atributos, un tipo int y un tipo Char.
    Trato de traer el contenido de esta forma pero me arroja errores

    Serial.println(listavalores.getElement(i));

    Saludos.

  4. Nico /
    Usando Google Chrome Google Chrome 25.0.1364.160 en Ubuntu Linux Ubuntu Linux

    @Nico
    No e dicho nada, ya logre traer los valores!

    1. admin / Post Author
      Usando Mozilla Firefox Mozilla Firefox 21.0 en Ubuntu Linux Ubuntu Linux

      Perfecto Nico, muchas gracias por tus comentarios

  5. Nico /
    Usando Google Chrome Google Chrome 28.0.1500.52 en Ubuntu Linux Ubuntu Linux

    @admin
    Muchas Gracias por la libreria, me ha sido de mucha utilidad!

Leave a Reply