include/aversive/list.h

   1 /*
   2  *  Copyright Droids Corporation, Microb Technology, Eirbot (2005)
   3  *
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 2 of the License, or
   7  *  (at your option) any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License
  15  *  along with this program; if not, write to the Free Software
  16  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  *
  18  *  Revision : $Id: list.h,v 1.1.2.4 2007-08-19 10:35:45 zer0 Exp $
  19  *
  20  */
  21
  22 /**
  23  * This header file provides LISTs implemented in tables. Don't use
  24  * list size > 127.
  25  *
  26  * WARNING ---------------------
  27  * This header file will probably be deprecated in a soon.
  28  * future. Consider using the 'cirbuf' module (circular buffer) instead.
  29  * Indeed, the full-macro implementation of this header file is not
  30  * the most efficient in terms of code size.... :)
  31  * WARNING ---------------------
  32  *
  33  *
  34  * Header
  35  * ------
  36  *
  37  * struct list_hdr {
  38  *   u08 size; < The size of the fifo
  39  *   u08 cur_size; < number of data in the fifo
  40  *   u08 beg_indice; < indice of the first elt
  41  *   u08 read_cursor; < read cursor
  42  * } __attribute__ ((packed));
  43  *
  44  *
  45  * ---------------------------------------------
  46  * I       I       I       I       I
  47  * I size  IcursizeI beg   I rcurs I    elements ...
  48  * I       I       I       I       I
  49  * ---------------------------------------------
  50  *
  51  * <------------------------------->
  52  *          list_hdr
  53  *
  54  *
  55  * Data
  56  * ----
  57  *
  58  * Data are stored in a circular buffer, beginning is specified by
  59  * beg_indice in header.
  60  *
  61  *
  62  * Type
  63  * ----
  64  *
  65  * For example, the type of a list of u08 with 10 elements is :
  66  *
  67  * struct list_u08_10 {
  68  *   struct list_hdr hdr;
  69  *   u08 elt[10];
  70  * }
  71  *
  72  * - With this example, an empty list is :
  73  *   size = 10
  74  *   cursize = 0
  75  *   beg = X
  76  *   curs = X
  77  *
  78  * - A full list :
  79  *   size = 10
  80  *   cursize = 10
  81  *   beg = X
  82  *   curs = X
  83  *
  84  *
  85  * Functions & Macros
  86  * ------------------
  87  *
  88  * ********** Define and init
  89  *
  90  * LIST_TYPE(typename, elttype, size) -> define type :
  91  *
  92  *     #define LIST_TYPE(typename, elttype, size)
  93  *      typedef struct typename {
  94  *         struct list_hdr hdr;
  95  *         elttype elt[size];
  96  *         } typename;
  97  *
  98  * LIST_INIT(list, beginning) -> flushes the list, and set size and beginning
  99  *
 100  *
 101  * ********** Control
 102  *
 103  * u08 LIST_FULL(list)
 104  * u08 LIST_EMPTY(list)
 105  *
 106  * u08 LIST_READ_GOTO(*elt, list, i) -> place the read cursor at position i (0 means
 107  *                   the beginning of the list) and set the elt if
 108  *                   pointer not NULL
 109  *
 110  * u08 LIST_READ_LEFT(*elt, list, i) -> move the read cursor left by i
 111  * u08 LIST_READ_RIGHT(*elt, list, i) -> move the read cursor right by i
 112  * u08 LIST_READ_START(*elt, list)
 113  * u08 LIST_READ_END(*elt, list)
 114  *
 115  * Examples :
 116  *
 117  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 118  *  6        3       2      3        X     X       A      B     C      X
 119  *
 120  *
 121  * we do LIST_READ_LEFT(NULL, x,x, 1) :
 122  *
 123  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 124  *  6        3       2      2        X     X       A      B     C      X
 125  *
 126  *
 127  * we do LIST_READ_LEFT(NULL, x,x, 1), but return 1 instead of 0 because we
 128  * overwrapped :
 129  *
 130  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 131  *  6        3       4      4        X     X       A      B     C      X
 132  *
 133  *
 134  * we do LIST_READ_GOTO(NULL, x,x, 0) :
 135  *
 136  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 137  *  6        3       4      2        X     X       A      B     C      X
 138  *
 139  *
 140  *
 141  * ********** accesses modifying the list
 142  *
 143  * u08 LIST_PUSH_START(elt, list)   -> add at the beginning (prepend)
 144  * u08 LIST_PUSH_END(elt, list)     -> add at the end (append)
 145  * u08 LIST_PULL_START(elt *, list) -> del at the beginning
 146  * u08 LIST_PULL_END(elt *, list)   -> del at the end
 147  *
 148  * u08 LIST_ARRAY_PUSH_START(*elt, list, n)   -> prepend n elts
 149  *                                                     from elt pointer
 150  * u08 LIST_ARRAY_PUSH_END(*elt, list, n)     -> append n elts
 151  * u08 LIST_ARRAY_PULL_START(elt *, list, n)  -> del n elts from buffer
 152  * u08 LIST_ARRAY_PULL_END(elt *, list, n)    -> del at the end
 153  *
 154  * Examples :
 155  *
 156  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 157  *  6        4       2      3        X     X      B      C      D      E
 158  *
 159  *
 160  * we do  LIST_PUSH_START(A, l, u08) :
 161  *
 162  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 163  *  6        5       1      3        X     A      B      C      D      E
 164  *
 165  *
 166  * we do  LIST_PUSH_END(F, l, u08) :
 167  *
 168  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 169  *  6        6       1      3       F      A      B      C      D      E
 170  *
 171  * we do  LIST_PUSH_END(X, l, u08) -> return -1
 172  *
 173  *
 174  *
 175  * ********** Accesses NOT modifying the list
 176  *
 177  * u08 LIST_FIRST(elt *, list)      -> Return the first elt
 178  * u08 LIST_LAST(elt *, list)       -> Return the last elt
 179  *
 180  * u08 LIST_READ(elt *, list)       -> Return the elt pointed by
 181  *                                           the read cursor
 182  *
 183  * u08 LIST_ARRAY_READ(elt *, list, n)  -> reads n elts from read cursor
 184  *
 185  * u08 LIST_READ_GET_PTR(list) -> return a pointer to the read
 186  * cursor. Warning, perhaps you need to do LIST_ALIGN_XXXX() before
 187  *
 188  * ********** loop functions
 189  *
 190  * #define LIST_FOREACH(list, elt)
 191  *    for( u08 ret = LIST_READ_START(elt, list) ;
 192  *              ret == 0 ;
 193  *              ret = LIST_READ_RIGHT(*elt, list, 1) )
 194  *
 195  *
 196  * ********** Alignement functions
 197  *
 198  * these functions can by quite long to execute. If possible, try to
 199  * avoid using them by choosing a good place for the beg_indice when
 200  * calling init of list. If you need it, prefer using
 201  * LIST_ALIGN_CONTINUOUS if possible.
 202  *
 203  * u08 LIST_ALIGN_LEFT(list)
 204  * u08 LIST_ALIGN_RIGHT(list)
 205  * u08 LIST_ALIGN_CONTINUOUS(list) -> just try to put data in a
 206  *                                 countinuous memory region in
 207  *                                 minimum operations.
 208  *
 209  * Example :
 210  *
 211  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 212  *  6        4       3      4       D      X      X      A      B      C
 213  *
 214  *
 215  * we do  LIST_ALIGN_LEFT(list) :
 216  *
 217  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 218  *  6        4       0      1       A      B      C      D      X      X
 219  *
 220  * we do  LIST_ALIGN_RIGHT(list) :
 221  *
 222  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 223  *  6        4       2      3       X      X      A      B      C      D
 224  *
 225  *
 226  * With these functions, you can easily imagine a network stack,
 227  * prepending headers to data, without copying the buffer multiple times.
 228  *
 229  * Example :
 230  *
 231  * LIST_INIT(mylist, 5)
 232  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 233  *  6        0       5      5       X      X      X      X      X      X
 234  *
 235  * LIST_ARRAY_PUSH_START("DATA", mylist, u08, strlen("DATA"))
 236  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 237  *  6        4       2      5       X      X      D      A      T      A
 238  *
 239  * LIST_PUSH_START('H', mylist, u08) (push header)
 240  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 241  *  6        5       1      5       X      H      D      A      T      A
 242  *
 243  * LIST_PUSH_START('H', mylist, u08) (push another header)
 244  * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
 245  *  6        6       0      5       H      H      D      A      T      A
 246  *
 247  */
 248
 249
 250 #ifndef _AVERSIVE_LIST_H_
 251 #define _AVERSIVE_LIST_H_
 252
 253 #ifndef LIST_DEBUG
 254 #define LIST_DEBUG 0
 255 #endif
 256
 257 #include <stdio.h>
 258
 259 #define WOVERWRAPPED -1
 260
 261 #ifdef HOST_VERSION
 262 #define CR "\n"
 263 #else
 264 #define CR "\r\n"
 265 #endif
 266
 267 #include <aversive.h>
 268
 269 /**
 270  * This structure is the header of a list type.
 271  */
 272 struct list_hdr {
 273   uint8_t size; /**< The size of the list (number of elements) */
 274   uint8_t cur_size; /**< number of data in the list */
 275   uint8_t beg_indice; /**< indice of the first elt */
 276   int8_t read_cursor; /**< read cursor */
 277 } __attribute__ ((packed));
 278
 279 /**
 280  * This is a generic kind of list, in which we suppose that elements
 281  * are char
 282 */
 283 struct generic_list {
 284         struct list_hdr hdr;
 285         char elt[0];
 286 } __attribute__ ((packed));
 287
 288
 289 /**
 290  * Define a new list type
 291  */
 292 #define LIST_TYPEDEF(typename, elttype, size) \
 293 typedef struct typename { \
 294         struct list_hdr hdr; \
 295         elttype elt[size]; \
 296 } typename;
 297
 298 #define LIST_INIT(list, beginning) \
 299 do { \
 300   list.hdr.size = sizeof(list.elt)/sizeof(list.elt[0]); \
 301   list.hdr.cur_size = 0; \
 302   list.hdr.beg_indice = beginning; \
 303   list.hdr.read_cursor = beginning; \
 304 } while(0)
 305
 306
 307 /**
 308  * Return 1 if the list is full
 309  */
 310 #define LIST_FULL(list) (list.hdr.size == list.hdr.cur_size)
 311
 312 /**
 313  * Return 1 if the list is empty
 314  */
 315 #define LIST_EMPTY(list) (list.hdr.cur_size == 0)
 316
 317 /**
 318  * return current size of the list (number of used elements)
 319  */
 320 #define LIST_CURSIZE(list) (list.hdr.cur_size)
 321
 322 /**
 323  * return size of the list (used + free elements)
 324  */
 325 #define LIST_SIZE(list) (list.hdr.size)
 326
 327 /**
 328  * return the number of free elts
 329  */
 330 #define LIST_FREESIZE(list) (list.hdr.size-list.hdr.cur_size)
 331
 332
 333
 334 #define LIST_READ_START(list, elt_p) ({ \
 335  uint8_t __ret=0; \
 336  list.hdr.read_cursor = 0 ; \
 337  *elt_p = list.elt[list.hdr.beg_indice] ;  \
 338  if(LIST_DEBUG) \
 339    printf("LIST_READ_START(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
 340  __ret; \
 341 })
 342
 343 #define LIST_READ_END(list, elt_p) ({ \
 344  uint8_t __ret=0; \
 345  list.hdr.read_cursor = list.hdr.cur_size-1; \
 346  *elt_p = list.elt[(list.hdr.beg_indice-1+list.hdr.cur_size) % list.hdr.size] ;  \
 347  if(LIST_DEBUG) \
 348    printf("LIST_READ_END(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
 349  __ret; \
 350 })
 351
 352
 353 #define LIST_READ_GOTO(list, elt_p, i) ({ \
 354  uint8_t __ret=0; \
 355  if( (i<0) || (i>=list.hdr.cur_size) ) \
 356          __ret = EINVAL; \
 357  else { \
 358         list.hdr.read_cursor = i; \
 359         *elt_p = list.elt[(list.hdr.beg_indice+i) % list.hdr.size] ;  \
 360  } \
 361  if(LIST_DEBUG) \
 362    printf("LIST_READ_GOTO(%s, %s, %d) -> ret %d"CR,#list, #elt_p, i, __ret); \
 363  __ret; \
 364 })
 365
 366 #define LIST_READ_MOVE(list, elt_p, i)  ({\
 367 uint8_t __ret=0;  \
 368  if (i<0) { \
 369         if( (-i) > list.hdr.read_cursor ) \
 370                  __ret = WOVERWRAPPED ; \
 371         list.hdr.read_cursor -= ((-i) % list.hdr.cur_size) ; \
 372         if (list.hdr.read_cursor < 0)  \
 373                 list.hdr.read_cursor += list.hdr.cur_size ;  \
 374  } \
 375  else {  \
 376          if( i >= list.hdr.cur_size - list.hdr.read_cursor )  \
 377                  __ret = WOVERWRAPPED ; \
 378          list.hdr.read_cursor += (i % list.hdr.cur_size) ; \
 379          if (list.hdr.read_cursor >= list.hdr.cur_size) \
 380                  list.hdr.read_cursor -= list.hdr.cur_size ; \
 381  } \
 382  if(LIST_DEBUG) \
 383    printf("LIST_READ_MOVE(%s, %s, %d) -> ret %d"CR,#list, #elt_p, i, __ret); \
 384  *elt_p = list.elt[(list.hdr.beg_indice+list.hdr.read_cursor) % list.hdr.size] ;  \
 385  __ret;  \
 386 })
 387
 388 #define LIST_READ(list, elt_p)  ({\
 389  *elt_p = list.elt[(list.hdr.beg_indice+list.hdr.read_cursor) % list.hdr.size] ;  \
 390  0;  \
 391 })
 392
 393 #define LIST_PUSH_START(list, e) ({ \
 394  uint8_t __ret=0; \
 395  if( LIST_FULL(list) ) \
 396          __ret=EINVAL; \
 397  else { \
 398          list.hdr.beg_indice = (list.hdr.beg_indice-1+list.hdr.size) % list.hdr.size; \
 399          list.elt [ list.hdr.beg_indice ] = e ; \
 400          list.hdr.cur_size ++ ; \
 401  } \
 402 if(LIST_DEBUG) \
 403  printf("LIST_PUSH_START(%s, %s) -> ret %d"CR,#list, #e, __ret); \
 404  __ret; \
 405 })
 406
 407 #define LIST_PUSH_END(list, e) ({ \
 408  uint8_t __ret=0; \
 409  if( LIST_FULL(list) ) \
 410          __ret=EINVAL; \
 411  else { \
 412          list.elt [ (list.hdr.beg_indice+list.hdr.cur_size) % list.hdr.size ] = e ; \
 413          list.hdr.cur_size ++ ; \
 414  } \
 415 if(LIST_DEBUG) \
 416  printf("LIST_PUSH_END(%s, %s) -> ret %d"CR,#list, #e, __ret); \
 417  __ret; \
 418 })
 419
 420 #define LIST_PULL_START(list, elt_p) ({ \
 421  uint8_t __ret=0; \
 422  if( LIST_EMPTY(list) ) \
 423          __ret=EINVAL; \
 424  else { \
 425          *elt_p = list.elt [ list.hdr.beg_indice ] ; \
 426          list.hdr.beg_indice = (list.hdr.beg_indice+1) % list.hdr.size; \
 427          list.hdr.cur_size -- ; \
 428  } \
 429 if(LIST_DEBUG) \
 430  printf("LIST_PULL_START(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
 431  __ret; \
 432 })
 433
 434 #define LIST_PULL_END(list, elt_p) ({ \
 435  uint8_t __ret=0; \
 436  if( LIST_EMPTY(list) ) \
 437          __ret=EINVAL; \
 438  else { \
 439          *elt_p = list.elt [ (list.hdr.beg_indice-1+list.hdr.cur_size) % list.hdr.size ] ; \
 440          list.hdr.cur_size -- ; \
 441  } \
 442 if(LIST_DEBUG) \
 443  printf("LIST_PULL_END(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
 444  __ret; \
 445 })
 446
 447 /* start by the last elt */
 448 #define LIST_ARRAY_PUSH_START(list, array, nb) ({\
 449  uint8_t __ret=0; \
 450  int8_t __i; \
 451  for(__i=nb-1 ; (__i>=0) && (!__ret) ; __i--) { \
 452     __ret=LIST_PUSH_START(list, array[__i]); \
 453  } \
 454  if(LIST_DEBUG) \
 455    printf("LIST_ARRAY_PUSH_START(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
 456  __ret; \
 457 })
 458
 459 #define LIST_ARRAY_PUSH_END(list, array, nb) ({\
 460  uint8_t __ret=0, __i; \
 461  for(__i=0 ; (__i<nb) && (!__ret) ; __i++) { \
 462     __ret=LIST_PUSH_END(list, array[__i]); \
 463  } \
 464  if(LIST_DEBUG) \
 465    printf("LIST_ARRAY_PUSH_END(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
 466  __ret; \
 467 })
 468
 469 #define LIST_ARRAY_PULL_START(list, array, nb) ({\
 470  uint8_t __ret=0, __i; \
 471  for(__i=0 ; (__i<nb) && (!__ret) ; __i++) { \
 472     __ret=LIST_PULL_START(list, (array+__i)); \
 473  } \
 474  if(LIST_DEBUG) \
 475    printf("LIST_ARRAY_PULL_START(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
 476  __ret; \
 477 })
 478
 479 #define LIST_ARRAY_PULL_END(list, array, nb) ({\
 480  uint8_t __ret=0; \
 481  int8_t __i; \
 482  for(__i=nb-1 ; (__i>=0) && (!__ret) ; __i--) { \
 483     __ret=LIST_PULL_END(list, (array+__i)); \
 484  } \
 485  if(LIST_DEBUG) \
 486    printf("LIST_ARRAY_PULL_END(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
 487  __ret; \
 488 })
 489
 490
 491 /* convert a list to an array, copy nb elts or less
 492  * if list is too small, return number of copied elts */
 493 #define LIST_TO_ARRAY(list, array, nb) ({\
 494  int8_t __i; \
 495  for(__i=0 ; __i<nb && __i<list.hdr.cur_size ; __i++) { \
 496     array[__i] = list.elt[(__i+list.hdr.beg_indice) % list.hdr.size]; \
 497  } \
 498  if(LIST_DEBUG) \
 499    printf("LIST_TO_ARRAY(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __i); \
 500  __i; \
 501 })
 502
 503
 504 #define LIST_ALIGN_LEFT(list) ({ \
 505 uint8_t __ret=0, __i; \
 506 if(list.hdr.beg_indice != 0) { \
 507         if(list.hdr.beg_indice+list.hdr.cur_size <= list.hdr.size) { \
 508                 for(__i=0 ; __i<list.hdr.cur_size ; __i++) { \
 509                         list.elt[__i] = list.elt[__i+list.hdr.beg_indice]; \
 510                 } \
 511         } \
 512         else { \
 513           uint8_t buffer_size=(list.hdr.size - list.hdr.beg_indice < (list.hdr.cur_size + list.hdr.beg_indice)%list.hdr.size) ? \
 514                            (list.hdr.size - list.hdr.beg_indice) * sizeof(list.elt[0]) : \
 515                               ((list.hdr.cur_size + list.hdr.beg_indice)%list.hdr.size) * sizeof(list.elt[0]); \
 516                      { \
 517                                 uint8_t buffer[buffer_size]; \
 518                                 memcpy(buffer, list.elt, buffer_size); \
 519                                 for(__i=0 ; __i<(list.hdr.cur_size - buffer_size/sizeof(list.elt[0])) ; __i++) { \
 520                                         list.elt[__i] = list.elt[__i+list.hdr.beg_indice]; \
 521                                 } \
 522                                 memcpy(&list.elt[list.hdr.cur_size - buffer_size/sizeof(list.elt[0])], buffer, buffer_size); \
 523                 } \
 524         } \
 525  list.hdr.beg_indice=0; \
 526 } \
 527  if(LIST_DEBUG) \
 528    printf("LIST_ALIGN_LEFT()"CR); \
 529  __ret; \
 530 })
 531
 532 #endif /* _AVERSIVE_LIST_H_ */