2 * Copyright Droids Corporation, Microb Technology, Eirbot (2005)
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.
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.
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
18 * Revision : $Id: list.h,v 1.1.2.4 2007-08-19 10:35:45 zer0 Exp $
23 * This header file provides LISTs implemented in tables. Don't use
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 ---------------------
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));
45 * ---------------------------------------------
47 * I size IcursizeI beg I rcurs I elements ...
49 * ---------------------------------------------
51 * <------------------------------->
58 * Data are stored in a circular buffer, beginning is specified by
59 * beg_indice in header.
65 * For example, the type of a list of u08 with 10 elements is :
67 * struct list_u08_10 {
68 * struct list_hdr hdr;
72 * - With this example, an empty list is :
88 * ********** Define and init
90 * LIST_TYPE(typename, elttype, size) -> define type :
92 * #define LIST_TYPE(typename, elttype, size)
93 * typedef struct typename {
94 * struct list_hdr hdr;
98 * LIST_INIT(list, beginning) -> flushes the list, and set size and beginning
103 * u08 LIST_FULL(list)
104 * u08 LIST_EMPTY(list)
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
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)
117 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
118 * 6 3 2 3 X X A B C X
121 * we do LIST_READ_LEFT(NULL, x,x, 1) :
123 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
124 * 6 3 2 2 X X A B C X
127 * we do LIST_READ_LEFT(NULL, x,x, 1), but return 1 instead of 0 because we
130 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
131 * 6 3 4 4 X X A B C X
134 * we do LIST_READ_GOTO(NULL, x,x, 0) :
136 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
137 * 6 3 4 2 X X A B C X
141 * ********** accesses modifying the list
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
148 * u08 LIST_ARRAY_PUSH_START(*elt, list, n) -> prepend n elts
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
156 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
157 * 6 4 2 3 X X B C D E
160 * we do LIST_PUSH_START(A, l, u08) :
162 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
163 * 6 5 1 3 X A B C D E
166 * we do LIST_PUSH_END(F, l, u08) :
168 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
169 * 6 6 1 3 F A B C D E
171 * we do LIST_PUSH_END(X, l, u08) -> return -1
175 * ********** Accesses NOT modifying the list
177 * u08 LIST_FIRST(elt *, list) -> Return the first elt
178 * u08 LIST_LAST(elt *, list) -> Return the last elt
180 * u08 LIST_READ(elt *, list) -> Return the elt pointed by
183 * u08 LIST_ARRAY_READ(elt *, list, n) -> reads n elts from read cursor
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
188 * ********** loop functions
190 * #define LIST_FOREACH(list, elt)
191 * for( u08 ret = LIST_READ_START(elt, list) ;
193 * ret = LIST_READ_RIGHT(*elt, list, 1) )
196 * ********** Alignement functions
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.
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.
211 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
212 * 6 4 3 4 D X X A B C
215 * we do LIST_ALIGN_LEFT(list) :
217 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
218 * 6 4 0 1 A B C D X X
220 * we do LIST_ALIGN_RIGHT(list) :
222 * size | cursize | beg | cursor | elt0 | elt1 | elt2 | elt3 | elt4 | elt5 |
223 * 6 4 2 3 X X A B C D
226 * With these functions, you can easily imagine a network stack,
227 * prepending headers to data, without copying the buffer multiple times.
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
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
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
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
250 #ifndef _AVERSIVE_LIST_H_
251 #define _AVERSIVE_LIST_H_
259 #define WOVERWRAPPED -1
267 #include <aversive.h>
270 * This structure is the header of a list type.
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));
280 * This is a generic kind of list, in which we suppose that elements
283 struct generic_list {
286 } __attribute__ ((packed));
290 * Define a new list type
292 #define LIST_TYPEDEF(typename, elttype, size) \
293 typedef struct typename { \
294 struct list_hdr hdr; \
298 #define LIST_INIT(list, beginning) \
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; \
308 * Return 1 if the list is full
310 #define LIST_FULL(list) (list.hdr.size == list.hdr.cur_size)
313 * Return 1 if the list is empty
315 #define LIST_EMPTY(list) (list.hdr.cur_size == 0)
318 * return current size of the list (number of used elements)
320 #define LIST_CURSIZE(list) (list.hdr.cur_size)
323 * return size of the list (used + free elements)
325 #define LIST_SIZE(list) (list.hdr.size)
328 * return the number of free elts
330 #define LIST_FREESIZE(list) (list.hdr.size-list.hdr.cur_size)
334 #define LIST_READ_START(list, elt_p) ({ \
336 list.hdr.read_cursor = 0 ; \
337 *elt_p = list.elt[list.hdr.beg_indice] ; \
339 printf("LIST_READ_START(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
343 #define LIST_READ_END(list, elt_p) ({ \
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] ; \
348 printf("LIST_READ_END(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
353 #define LIST_READ_GOTO(list, elt_p, i) ({ \
355 if( (i<0) || (i>=list.hdr.cur_size) ) \
358 list.hdr.read_cursor = i; \
359 *elt_p = list.elt[(list.hdr.beg_indice+i) % list.hdr.size] ; \
362 printf("LIST_READ_GOTO(%s, %s, %d) -> ret %d"CR,#list, #elt_p, i, __ret); \
366 #define LIST_READ_MOVE(list, elt_p, i) ({\
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 ; \
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 ; \
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] ; \
388 #define LIST_READ(list, elt_p) ({\
389 *elt_p = list.elt[(list.hdr.beg_indice+list.hdr.read_cursor) % list.hdr.size] ; \
393 #define LIST_PUSH_START(list, e) ({ \
395 if( LIST_FULL(list) ) \
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 ++ ; \
403 printf("LIST_PUSH_START(%s, %s) -> ret %d"CR,#list, #e, __ret); \
407 #define LIST_PUSH_END(list, e) ({ \
409 if( LIST_FULL(list) ) \
412 list.elt [ (list.hdr.beg_indice+list.hdr.cur_size) % list.hdr.size ] = e ; \
413 list.hdr.cur_size ++ ; \
416 printf("LIST_PUSH_END(%s, %s) -> ret %d"CR,#list, #e, __ret); \
420 #define LIST_PULL_START(list, elt_p) ({ \
422 if( LIST_EMPTY(list) ) \
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 -- ; \
430 printf("LIST_PULL_START(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
434 #define LIST_PULL_END(list, elt_p) ({ \
436 if( LIST_EMPTY(list) ) \
439 *elt_p = list.elt [ (list.hdr.beg_indice-1+list.hdr.cur_size) % list.hdr.size ] ; \
440 list.hdr.cur_size -- ; \
443 printf("LIST_PULL_END(%s, %s) -> ret %d"CR,#list, #elt_p, __ret); \
447 /* start by the last elt */
448 #define LIST_ARRAY_PUSH_START(list, array, nb) ({\
451 for(__i=nb-1 ; (__i>=0) && (!__ret) ; __i--) { \
452 __ret=LIST_PUSH_START(list, array[__i]); \
455 printf("LIST_ARRAY_PUSH_START(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
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]); \
465 printf("LIST_ARRAY_PUSH_END(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
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)); \
475 printf("LIST_ARRAY_PULL_START(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
479 #define LIST_ARRAY_PULL_END(list, array, nb) ({\
482 for(__i=nb-1 ; (__i>=0) && (!__ret) ; __i--) { \
483 __ret=LIST_PULL_END(list, (array+__i)); \
486 printf("LIST_ARRAY_PULL_END(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __ret); \
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) ({\
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]; \
499 printf("LIST_TO_ARRAY(%s, %s, %d) -> ret %d"CR,#list, #array, nb, __i); \
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]; \
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]); \
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]; \
522 memcpy(&list.elt[list.hdr.cur_size - buffer_size/sizeof(list.elt[0])], buffer, buffer_size); \
525 list.hdr.beg_indice=0; \
528 printf("LIST_ALIGN_LEFT()"CR); \
532 #endif /* _AVERSIVE_LIST_H_ */