Listas enlazadas en Arduino (primera versión)
Miércoles, 30 de Noviembre de 2011
Sin comentarios
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
5struct 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 http://totaki.com/poesiabinaria * @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); // } // } |
Últimos comentarios