From e5174304054e26cd8f3cd1f9980871c20c07fc46 Mon Sep 17 00:00:00 2001 From: bernie Date: Wed, 13 Aug 2008 09:26:37 +0000 Subject: [PATCH] Move data structures to new directory struct/ git-svn-id: https://src.develer.com/svnoss/bertos/trunk@1626 38d2e660-2303-0410-9eaa-f027e97ec537 --- README.bertos | 3 +- bertos/mware/fifobuf.h | 362 +--------------------------------------- bertos/mware/formatwr.c | 2 +- bertos/mware/heap.h | 93 +---------- bertos/mware/list.h | 333 +----------------------------------- bertos/mware/pool.h | 76 +-------- bertos/struct/fifobuf.h | 361 +++++++++++++++++++++++++++++++++++++++ bertos/struct/heap.c | 236 ++++++++++++++++++++++++++ bertos/struct/heap.h | 89 ++++++++++ bertos/struct/list.h | 330 ++++++++++++++++++++++++++++++++++++ bertos/struct/pool.h | 74 ++++++++ 11 files changed, 1097 insertions(+), 862 deletions(-) create mode 100644 bertos/struct/fifobuf.h create mode 100644 bertos/struct/heap.c create mode 100644 bertos/struct/heap.h create mode 100644 bertos/struct/list.h create mode 100644 bertos/struct/pool.h diff --git a/README.bertos b/README.bertos index 2ef126a1..7c7cfb12 100644 --- a/README.bertos +++ b/README.bertos @@ -66,7 +66,8 @@ The modules are sorted in subdirectories by their category: - bertos/hw/ : hardware-specific declarations; - bertos/icons/ : conversion tool from image TXT format to LCD bitmap; - bertos/kern/ : multitasking kernel; - - bertos/mware/ : algorithms, containers and other standalone code; + - bertos/mware/ : algorithms, other standalone code; + - bertos/struct/ : containers and other data structures; - bertos/os/ : OS-abstraction layers for hosted environments; - doc/ : documentation; diff --git a/bertos/mware/fifobuf.h b/bertos/mware/fifobuf.h index 1e855582..73f6c14e 100644 --- a/bertos/mware/fifobuf.h +++ b/bertos/mware/fifobuf.h @@ -1,361 +1 @@ -/** - * \file - * - * - * \version $Id$ - * - * \author Bernie Innocenti - * - * \brief General pourpose FIFO buffer implemented with a ring buffer - * - * \li \c begin points to the first buffer element; - * \li \c end points to the last buffer element (unlike the STL convention); - * \li \c head points to the element to be extracted next; - * \li \c tail points to the location following the last insertion; - * \li when any of the pointers advances beyond \c end, it is reset - * back to \c begin. - * - * \code - * - * +-----------------------------------+ - * | empty | valid data | empty | - * +-----------------------------------+ - * ^ ^ ^ ^ - * begin head tail end - * - * \endcode - * - * The buffer is EMPTY when \c head and \c tail point to the same location: - * \code head == tail \endcode - * - * The buffer is FULL when \c tail points to the location immediately - * after \c head: - * \code tail == head - 1 \endcode - * - * The buffer is also FULL when \c tail points to the last buffer - * location and head points to the first one: - * \code head == begin && tail == end \endcode - */ - -#ifndef MWARE_FIFO_H -#define MWARE_FIFO_H - -#include -#include -#include - -typedef struct FIFOBuffer -{ - unsigned char * volatile head; - unsigned char * volatile tail; - unsigned char *begin; - unsigned char *end; -} FIFOBuffer; - - -#define ASSERT_VALID_FIFO(fifo) \ - ATOMIC( \ - ASSERT((fifo)->head >= (fifo)->begin); \ - ASSERT((fifo)->head <= (fifo)->end); \ - ASSERT((fifo)->tail >= (fifo)->begin); \ - ASSERT((fifo)->tail <= (fifo)->end); \ - ) - - -/** - * Check whether the fifo is empty - * - * \note Calling fifo_isempty() is safe while a concurrent - * execution context is calling fifo_push() or fifo_pop() - * only if the CPU can atomically update a pointer - * (which the AVR and other 8-bit processors can't do). - * - * \sa fifo_isempty_locked - */ -INLINE bool fifo_isempty(const FIFOBuffer *fb) -{ - //ASSERT_VALID_FIFO(fb); - return fb->head == fb->tail; -} - - -/** - * Check whether the fifo is full - * - * \note Calling fifo_isfull() is safe while a concurrent - * execution context is calling fifo_pop() and the - * CPU can update a pointer atomically. - * It is NOT safe when the other context calls - * fifo_push(). - * This limitation is not usually problematic in a - * consumer/producer scenario because the - * fifo_isfull() and fifo_push() are usually called - * in the producer context. - */ -INLINE bool fifo_isfull(const FIFOBuffer *fb) -{ - //ASSERT_VALID_FIFO(fb); - return - ((fb->head == fb->begin) && (fb->tail == fb->end)) - || (fb->tail == fb->head - 1); -} - - -/** - * Push a character on the fifo buffer. - * - * \note Calling \c fifo_push() on a full buffer is undefined. - * The caller must make sure the buffer has at least - * one free slot before calling this function. - * - * \note It is safe to call fifo_pop() and fifo_push() from - * concurrent contexts, unless the CPU can't update - * a pointer atomically (which the AVR and other 8-bit - * processors can't do). - * - * \sa fifo_push_locked - */ -INLINE void fifo_push(FIFOBuffer *fb, unsigned char c) -{ -#ifdef __MWERKS__ -#pragma interrupt called -#endif - //ASSERT_VALID_FIFO(fb); - - /* Write at tail position */ - *(fb->tail) = c; - - if (UNLIKELY(fb->tail == fb->end)) - /* wrap tail around */ - fb->tail = fb->begin; - else - /* Move tail forward */ - fb->tail++; -} - - -/** - * Pop a character from the fifo buffer. - * - * \note Calling \c fifo_pop() on an empty buffer is undefined. - * The caller must make sure the buffer contains at least - * one character before calling this function. - * - * \note It is safe to call fifo_pop() and fifo_push() from - * concurrent contexts. - */ -INLINE unsigned char fifo_pop(FIFOBuffer *fb) -{ -#ifdef __MWERKS__ -#pragma interrupt called -#endif - //ASSERT_VALID_FIFO(fb); - - if (UNLIKELY(fb->head == fb->end)) - { - /* wrap head around */ - fb->head = fb->begin; - return *(fb->end); - } - else - /* move head forward */ - return *(fb->head++); -} - - -/** - * Make the fifo empty, discarding all its current contents. - */ -INLINE void fifo_flush(FIFOBuffer *fb) -{ - //ASSERT_VALID_FIFO(fb); - fb->head = fb->tail; -} - - -#if CPU_REG_BITS >= CPU_BITS_PER_PTR - - /* - * 16/32bit CPUs that can update a pointer with a single write - * operation, no need to disable interrupts. - */ - #define fifo_isempty_locked(fb) fifo_isempty((fb)) - #define fifo_push_locked(fb, c) fifo_push((fb), (c)) - #define fifo_pop_locked(fb) fifo_pop((fb)) - #define fifo_flush_locked(fb) fifo_flush((fb)) - -#else /* CPU_REG_BITS < CPU_BITS_PER_PTR */ - - /** - * Similar to fifo_isempty(), but with stronger guarantees for - * concurrent access between user and interrupt code. - * - * \note This is actually only needed for 8-bit processors. - * - * \sa fifo_isempty() - */ - INLINE bool fifo_isempty_locked(const FIFOBuffer *fb) - { - bool result; - ATOMIC(result = fifo_isempty(fb)); - return result; - } - - - /** - * Similar to fifo_push(), but with stronger guarantees for - * concurrent access between user and interrupt code. - * - * \note This is actually only needed for 8-bit processors. - * - * \sa fifo_push() - */ - INLINE void fifo_push_locked(FIFOBuffer *fb, unsigned char c) - { - ATOMIC(fifo_push(fb, c)); - } - - /* Probably not really needed, but hard to prove. */ - INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb) - { - unsigned char c; - ATOMIC(c = fifo_pop(fb)); - return c; - } - - /** - * Similar to fifo_flush(), but with stronger guarantees for - * concurrent access between user and interrupt code. - * - * \note This is actually only needed for 8-bit processors. - * - * \sa fifo_flush() - */ - INLINE void fifo_flush_locked(FIFOBuffer *fb) - { - ATOMIC(fifo_flush(fb)); - } - -#endif /* CPU_REG_BITS < BITS_PER_PTR */ - - -/** - * Thread safe version of fifo_isfull() - */ -INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb) -{ - bool result; - ATOMIC(result = fifo_isfull(_fb)); - return result; -} - - -/** - * FIFO Initialization. - */ -INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size) -{ - /* FIFO buffers have a known bug with 1-byte buffers. */ - ASSERT(size > 1); - - fb->head = fb->tail = fb->begin = buf; - fb->end = buf + size - 1; -} - -/** - * \return Lenght of the FIFOBuffer \a fb. - */ -INLINE size_t fifo_len(FIFOBuffer *fb) -{ - return fb->end - fb->begin; -} - - -#if 0 - -/* - * UNTESTED: if uncommented, to be moved in fifobuf.c - */ -void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len) -{ - size_t freelen; - - /* Se c'e' spazio da tail alla fine del buffer */ - if (fb->tail >= fb->head) - { - freelen = fb->end - fb->tail + 1; - - /* C'e' abbastanza spazio per scrivere tutto il blocco? */ - if (freelen < len) - { - /* Scrivi quello che entra fino alla fine del buffer */ - memcpy(fb->tail, block, freelen); - block += freelen; - len -= freelen; - fb->tail = fb->begin; - } - else - { - /* Scrivi tutto il blocco */ - memcpy(fb->tail, block, len); - fb->tail += len; - return; - } - } - - for(;;) - { - while (!(freelen = fb->head - fb->tail - 1)) - Delay(FIFO_POLLDELAY); - - /* C'e' abbastanza spazio per scrivere tutto il blocco? */ - if (freelen < len) - { - /* Scrivi quello che entra fino alla fine del buffer */ - memcpy(fb->tail, block, freelen); - block += freelen; - len -= freelen; - fb->tail += freelen; - } - else - { - /* Scrivi tutto il blocco */ - memcpy(fb->tail, block, len); - fb->tail += len; - return; - } - } -} -#endif - -#endif /* MWARE_FIFO_H */ - +#include diff --git a/bertos/mware/formatwr.c b/bertos/mware/formatwr.c index 6d725f97..0c0e39c7 100644 --- a/bertos/mware/formatwr.c +++ b/bertos/mware/formatwr.c @@ -844,7 +844,7 @@ FLOATING_CONVERSION: { case 'l': case 'z': - /* for the 'z' modifier, we make this assmumption */ + /* for the 'z' modifier, we make this assumption */ STATIC_ASSERT(sizeof(size_t) == sizeof(long)); l_modifier = true; format++; diff --git a/bertos/mware/heap.h b/bertos/mware/heap.h index 0524dbcf..0a987b13 100644 --- a/bertos/mware/heap.h +++ b/bertos/mware/heap.h @@ -1,92 +1 @@ -/** - * \file - * - * - * \brief Heap subsystem (public interface). - * - * \todo Heap memory could be defined as an array of MemChunk, and used - * in this form also within the implementation. This would probably remove - * memory alignment problems, and also some aliasing issues. - * - * \version $Id$ - * - * \author Bernie Innocenti - * - */ - -#ifndef MWARE_HEAP_H -#define MWARE_HEAP_H - -#include "cfg/cfg_heap.h" -#include - -struct _MemChunk; - -/// A heap -struct Heap -{ - struct _MemChunk *FreeList; ///< Head of the free list -}; - - -/// Initialize \a heap within the buffer pointed by \a memory which is of \a size bytes -void heap_init(struct Heap* heap, void* memory, size_t size); - -/// Allocate a chunk of memory of \a size bytes from the heap -void *heap_allocmem(struct Heap* heap, size_t size); - -/// Free a chunk of memory of \a size bytes from the heap -void heap_freemem(struct Heap* heap, void *mem, size_t size); - - -#define HNEW(heap, type) \ - (type*)heap_allocmem(heap, sizeof(type)) - -#define HNEWVEC(heap, type, nelem) \ - (type*)heap_allocmem(heap, sizeof(type) * (nelem)) - -#define HDELETE(heap, type, mem) \ - heap_freemem(heap, mem, sizeof(type)) - -#define HDELETEVEC(heap, type, nelem, mem) \ - heap_freemem(heap, mem, sizeof(type) * (nelem)) - - -#if CONFIG_HEAP_MALLOC - -void *heap_malloc(struct Heap* heap, size_t size); -void *heap_calloc(struct Heap* heap, size_t size); -void heap_free(struct Heap* heap, void * mem); - -#endif - -#endif /* MWARE_HEAP_H */ +#include diff --git a/bertos/mware/list.h b/bertos/mware/list.h index bd93ba2e..32ca7091 100644 --- a/bertos/mware/list.h +++ b/bertos/mware/list.h @@ -1,332 +1 @@ -/** - * \file - * - * - * \version $Id$ - * - * \author Bernie Innocenti - * - * \brief General pourpose double-linked lists - */ - -#ifndef MWARE_LIST_H -#define MWARE_LIST_H - -#include /* INLINE */ -#include /* ASSERT_VALID_PTR() */ - -/** - * This structure represents a node for bidirectional lists. - * - * Data is usually appended to nodes by making them the first - * field of another struture, as a poor-man's form of inheritance. - */ -typedef struct _Node -{ - struct _Node *succ; - struct _Node *pred; -} Node; - -/** - * Head of a doubly-linked list of \c Node structs. - * - * Lists must be initialized with LIST_INIT() prior to use. - * - * Nodes can be added and removed from either end of the list - * with O(1) performance. Iterating over these lists can be - * tricky: use the FOREACH_NODE() macro instead. - */ -typedef struct _List -{ - Node head; - Node tail; -} List; - -/** - * Extended node for priority queues. - */ -typedef struct _PriNode -{ - Node link; - int pri; -} PriNode; - - -/** - * Template for a naked node in a list of \a T structures. - * - * To be used as data member in other structures: - * - * \code - * struct Foo - * { - * DECLARE_NODE_ANON(struct Foo) - * int a; - * float b; - * } - * - * DECLARE_LIST_TYPE(Foo); - * - * void foo(void) - * { - * static LIST_TYPE(Foo) foo_list; - * static Foo foo1, foo2; - * Foo *fp; - * - * LIST_INIT(&foo_list); - * ADDHEAD(&foo_list, &foo1); - * INSERT_BEFORE(&foo_list, &foo2); - * FOREACH_NODE(fp, &foo_list) - * fp->a = 10; - * } - * - * \endcode - */ -#define DECLARE_NODE_ANON(T) \ - T *succ; T *pred; - -/** Declare a typesafe node for structures of type \a T. */ -#define DECLARE_NODE_TYPE(T) \ - typedef struct T##Node { T *succ; T *pred; } T##Node - -/** Template for a list of \a T structures. */ -#define DECLARE_LIST_TYPE(T) \ - DECLARE_NODE_TYPE(T); \ - typedef struct T##List { \ - T##Node head; \ - T##Node tail; \ - } T##List - -#define NODE_TYPE(T) T##Node -#define LIST_TYPE(T) T##List - -/** - * Get a pointer to the first node in a list. - * - * If \a l is empty, result points to l->tail. - */ -#define LIST_HEAD(l) ((l)->head.succ) - -/** - * Get a pointer to the last node in a list. - * - * If \a l is empty, result points to l->head. - */ -#define LIST_TAIL(l) ((l)->tail.pred) - -// TODO: move in compiler.h -#if COMPILER_TYPEOF - #define TYPEOF_OR_VOIDPTR(type) typeof(type) -#else - #define TYPEOF_OR_VOIDPTR(type) void * -#endif - -/** - * Iterate over all nodes in a list. - * - * This macro generates a "for" statement using the following parameters: - * \param n Node pointer to be used in each iteration. - * \param l Pointer to list. - */ -#define FOREACH_NODE(n, l) \ - for( \ - (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l); \ - ((Node *)(n))->succ; \ - (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \ - ) - -/** - * Iterate backwards over all nodes in a list. - * - * This macro generates a "for" statement using the following parameters: - * \param n Node pointer to be used in each iteration. - * \param l Pointer to list. - */ -#define REVERSE_FOREACH_NODE(n, l) \ - for( \ - (n) = (TYPEOF_OR_VOIDPTR(n))LIST_TAIL(l); \ - ((Node *)(n))->pred; \ - (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \ - ) - -/** Initialize a list. */ -#define LIST_INIT(l) \ - do { \ - (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \ - (l)->head.pred = NULL; \ - (l)->tail.succ = NULL; \ - (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \ - } while (0) - -#ifdef _DEBUG - /** Make sure that a list is valid (it was initialized and is not corrupted). */ - #define LIST_ASSERT_VALID(l) \ - do { \ - Node *n, *pred; \ - ASSERT((l)->head.succ != NULL); \ - ASSERT((l)->head.pred == NULL); \ - ASSERT((l)->tail.succ == NULL); \ - ASSERT((l)->tail.pred != NULL); \ - pred = &(l)->head; \ - FOREACH_NODE(n, l) \ - { \ - ASSERT(n->pred == pred); \ - pred = n; \ - } \ - ASSERT(n == &(l)->tail); \ - } while (0) - - #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL) -#else - #define LIST_ASSERT_VALID(l) do {} while (0) - #define INVALIDATE_NODE(n) do {} while (0) -#endif - -/** Add node to list head. */ -#define ADDHEAD(l,n) \ - do { \ - ASSERT_VALID_PTR(l); \ - ASSERT_VALID_PTR(n); \ - (n)->succ = (l)->head.succ; \ - (n)->pred = (l)->head.succ->pred; \ - (n)->succ->pred = (n); \ - (n)->pred->succ = (n); \ - } while (0) - -/** Add node to list tail. */ -#define ADDTAIL(l,n) \ - do { \ - ASSERT_VALID_PTR(l); \ - ASSERT_VALID_PTR(n); \ - (n)->succ = &(l)->tail; \ - (n)->pred = (l)->tail.pred; \ - (n)->pred->succ = (n); \ - (l)->tail.pred = (n); \ - } while (0) - -/** - * Insert node \a n before node \a ln. - * - * \note You can't pass in a list header as \a ln, but - * it is safe to pass list-\>head of an empty list. - */ -#define INSERT_BEFORE(n,ln) \ - do { \ - ASSERT_VALID_PTR(n); \ - ASSERT_VALID_PTR(ln); \ - (n)->succ = (ln); \ - (n)->pred = (ln)->pred; \ - (ln)->pred->succ = (n); \ - (ln)->pred = (n); \ - } while (0) - -/** - * Remove \a n from whatever list it is in. - * - * \note Removing a node that has not previously been - * inserted into a list invokes undefined behavior. - */ -#define REMOVE(n) \ - do { \ - ASSERT_VALID_PTR(n); \ - (n)->pred->succ = (n)->succ; \ - (n)->succ->pred = (n)->pred; \ - INVALIDATE_NODE(n); \ - } while (0) - -/** Tell whether a list is empty. */ -#define LIST_EMPTY(l) ( (void *)((l)->head.succ) == (void *)(&(l)->tail) ) - -/** - * Insert a priority node in a priority queue. - * - * The new node is inserted immediately before the - * first node with lower priority or appended to - * the tail if no such node exists. - */ -#define LIST_ENQUEUE(list, node) \ - do { \ - PriNode *ln; \ - ASSERT_VALID_PTR(list); \ - ASSERT_VALID_PTR(node); \ - FOREACH_NODE(ln, (list)) \ - if (ln->pri < (node)->pri) \ - break; \ - INSERT_BEFORE(&(node)->link, &ln->link); \ - } while (0) - - -/** - * Unlink a node from the head of the list \a l. - * - * \return Pointer to node, or NULL if the list was empty. - */ -INLINE Node *list_remHead(List *l) -{ - Node *n; - - ASSERT_VALID_PTR(l); - - if (LIST_EMPTY(l)) - return (Node *)0; - - n = l->head.succ; /* Get first node. */ - l->head.succ = n->succ; /* Link list head to second node. */ - n->succ->pred = &l->head; /* Link second node to list head. */ - - INVALIDATE_NODE(n); - return n; -} - -/** - * Unlink a node from the tail of the list \a l. - * - * \return Pointer to node, or NULL if the list was empty. - */ -INLINE Node *list_remTail(List *l) -{ - Node *n; - - ASSERT_VALID_PTR(l); - - if (LIST_EMPTY(l)) - return NULL; - - n = l->tail.pred; /* Get last node. */ - l->tail.pred = n->pred; /* Link list tail to second last node. */ - n->pred->succ = &l->tail; /* Link second last node to list tail. */ - - INVALIDATE_NODE(n); - return n; -} - -#endif /* MWARE_LIST_H */ +#include diff --git a/bertos/mware/pool.h b/bertos/mware/pool.h index 6100abba..98d627a8 100644 --- a/bertos/mware/pool.h +++ b/bertos/mware/pool.h @@ -1,75 +1 @@ -/** - * \file - * - * - * \brief Pool macros. - * - * \version $Id$ - * \author Giovanni Bajo - */ - -#ifndef MWARE_POOL_H -#define MWARE_POOL_H - -#include -#include - -#define EXTERN_POOL(name) \ - extern List name - -#define DECLARE_POOL_WITH_STORAGE(name, type, num, storage) \ - static type name##_items[num]; \ - storage name; \ - INLINE void name##_init(void (*init_func)(type*)) \ - { \ - int i; \ - LIST_INIT(&name); \ - for (i=0;i diff --git a/bertos/struct/fifobuf.h b/bertos/struct/fifobuf.h new file mode 100644 index 00000000..1d7b555a --- /dev/null +++ b/bertos/struct/fifobuf.h @@ -0,0 +1,361 @@ +/** + * \file + * + * + * \version $Id: fifobuf.h 1532 2008-08-04 07:21:26Z bernie $ + * + * \author Bernie Innocenti + * + * \brief General pourpose FIFO buffer implemented with a ring buffer + * + * \li \c begin points to the first buffer element; + * \li \c end points to the last buffer element (unlike the STL convention); + * \li \c head points to the element to be extracted next; + * \li \c tail points to the location following the last insertion; + * \li when any of the pointers advances beyond \c end, it is reset + * back to \c begin. + * + * \code + * + * +-----------------------------------+ + * | empty | valid data | empty | + * +-----------------------------------+ + * ^ ^ ^ ^ + * begin head tail end + * + * \endcode + * + * The buffer is EMPTY when \c head and \c tail point to the same location: + * \code head == tail \endcode + * + * The buffer is FULL when \c tail points to the location immediately + * after \c head: + * \code tail == head - 1 \endcode + * + * The buffer is also FULL when \c tail points to the last buffer + * location and head points to the first one: + * \code head == begin && tail == end \endcode + */ + +#ifndef MWARE_FIFO_H +#define MWARE_FIFO_H + +#include +#include +#include + +typedef struct FIFOBuffer +{ + unsigned char * volatile head; + unsigned char * volatile tail; + unsigned char *begin; + unsigned char *end; +} FIFOBuffer; + + +#define ASSERT_VALID_FIFO(fifo) \ + ATOMIC( \ + ASSERT((fifo)->head >= (fifo)->begin); \ + ASSERT((fifo)->head <= (fifo)->end); \ + ASSERT((fifo)->tail >= (fifo)->begin); \ + ASSERT((fifo)->tail <= (fifo)->end); \ + ) + + +/** + * Check whether the fifo is empty + * + * \note Calling fifo_isempty() is safe while a concurrent + * execution context is calling fifo_push() or fifo_pop() + * only if the CPU can atomically update a pointer + * (which the AVR and other 8-bit processors can't do). + * + * \sa fifo_isempty_locked + */ +INLINE bool fifo_isempty(const FIFOBuffer *fb) +{ + //ASSERT_VALID_FIFO(fb); + return fb->head == fb->tail; +} + + +/** + * Check whether the fifo is full + * + * \note Calling fifo_isfull() is safe while a concurrent + * execution context is calling fifo_pop() and the + * CPU can update a pointer atomically. + * It is NOT safe when the other context calls + * fifo_push(). + * This limitation is not usually problematic in a + * consumer/producer scenario because the + * fifo_isfull() and fifo_push() are usually called + * in the producer context. + */ +INLINE bool fifo_isfull(const FIFOBuffer *fb) +{ + //ASSERT_VALID_FIFO(fb); + return + ((fb->head == fb->begin) && (fb->tail == fb->end)) + || (fb->tail == fb->head - 1); +} + + +/** + * Push a character on the fifo buffer. + * + * \note Calling \c fifo_push() on a full buffer is undefined. + * The caller must make sure the buffer has at least + * one free slot before calling this function. + * + * \note It is safe to call fifo_pop() and fifo_push() from + * concurrent contexts, unless the CPU can't update + * a pointer atomically (which the AVR and other 8-bit + * processors can't do). + * + * \sa fifo_push_locked + */ +INLINE void fifo_push(FIFOBuffer *fb, unsigned char c) +{ +#ifdef __MWERKS__ +#pragma interrupt called +#endif + //ASSERT_VALID_FIFO(fb); + + /* Write at tail position */ + *(fb->tail) = c; + + if (UNLIKELY(fb->tail == fb->end)) + /* wrap tail around */ + fb->tail = fb->begin; + else + /* Move tail forward */ + fb->tail++; +} + + +/** + * Pop a character from the fifo buffer. + * + * \note Calling \c fifo_pop() on an empty buffer is undefined. + * The caller must make sure the buffer contains at least + * one character before calling this function. + * + * \note It is safe to call fifo_pop() and fifo_push() from + * concurrent contexts. + */ +INLINE unsigned char fifo_pop(FIFOBuffer *fb) +{ +#ifdef __MWERKS__ +#pragma interrupt called +#endif + //ASSERT_VALID_FIFO(fb); + + if (UNLIKELY(fb->head == fb->end)) + { + /* wrap head around */ + fb->head = fb->begin; + return *(fb->end); + } + else + /* move head forward */ + return *(fb->head++); +} + + +/** + * Make the fifo empty, discarding all its current contents. + */ +INLINE void fifo_flush(FIFOBuffer *fb) +{ + //ASSERT_VALID_FIFO(fb); + fb->head = fb->tail; +} + + +#if CPU_REG_BITS >= CPU_BITS_PER_PTR + + /* + * 16/32bit CPUs that can update a pointer with a single write + * operation, no need to disable interrupts. + */ + #define fifo_isempty_locked(fb) fifo_isempty((fb)) + #define fifo_push_locked(fb, c) fifo_push((fb), (c)) + #define fifo_pop_locked(fb) fifo_pop((fb)) + #define fifo_flush_locked(fb) fifo_flush((fb)) + +#else /* CPU_REG_BITS < CPU_BITS_PER_PTR */ + + /** + * Similar to fifo_isempty(), but with stronger guarantees for + * concurrent access between user and interrupt code. + * + * \note This is actually only needed for 8-bit processors. + * + * \sa fifo_isempty() + */ + INLINE bool fifo_isempty_locked(const FIFOBuffer *fb) + { + bool result; + ATOMIC(result = fifo_isempty(fb)); + return result; + } + + + /** + * Similar to fifo_push(), but with stronger guarantees for + * concurrent access between user and interrupt code. + * + * \note This is actually only needed for 8-bit processors. + * + * \sa fifo_push() + */ + INLINE void fifo_push_locked(FIFOBuffer *fb, unsigned char c) + { + ATOMIC(fifo_push(fb, c)); + } + + /* Probably not really needed, but hard to prove. */ + INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb) + { + unsigned char c; + ATOMIC(c = fifo_pop(fb)); + return c; + } + + /** + * Similar to fifo_flush(), but with stronger guarantees for + * concurrent access between user and interrupt code. + * + * \note This is actually only needed for 8-bit processors. + * + * \sa fifo_flush() + */ + INLINE void fifo_flush_locked(FIFOBuffer *fb) + { + ATOMIC(fifo_flush(fb)); + } + +#endif /* CPU_REG_BITS < BITS_PER_PTR */ + + +/** + * Thread safe version of fifo_isfull() + */ +INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb) +{ + bool result; + ATOMIC(result = fifo_isfull(_fb)); + return result; +} + + +/** + * FIFO Initialization. + */ +INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size) +{ + /* FIFO buffers have a known bug with 1-byte buffers. */ + ASSERT(size > 1); + + fb->head = fb->tail = fb->begin = buf; + fb->end = buf + size - 1; +} + +/** + * \return Lenght of the FIFOBuffer \a fb. + */ +INLINE size_t fifo_len(FIFOBuffer *fb) +{ + return fb->end - fb->begin; +} + + +#if 0 + +/* + * UNTESTED: if uncommented, to be moved in fifobuf.c + */ +void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len) +{ + size_t freelen; + + /* Se c'e' spazio da tail alla fine del buffer */ + if (fb->tail >= fb->head) + { + freelen = fb->end - fb->tail + 1; + + /* C'e' abbastanza spazio per scrivere tutto il blocco? */ + if (freelen < len) + { + /* Scrivi quello che entra fino alla fine del buffer */ + memcpy(fb->tail, block, freelen); + block += freelen; + len -= freelen; + fb->tail = fb->begin; + } + else + { + /* Scrivi tutto il blocco */ + memcpy(fb->tail, block, len); + fb->tail += len; + return; + } + } + + for(;;) + { + while (!(freelen = fb->head - fb->tail - 1)) + Delay(FIFO_POLLDELAY); + + /* C'e' abbastanza spazio per scrivere tutto il blocco? */ + if (freelen < len) + { + /* Scrivi quello che entra fino alla fine del buffer */ + memcpy(fb->tail, block, freelen); + block += freelen; + len -= freelen; + fb->tail += freelen; + } + else + { + /* Scrivi tutto il blocco */ + memcpy(fb->tail, block, len); + fb->tail += len; + return; + } + } +} +#endif + +#endif /* MWARE_FIFO_H */ + diff --git a/bertos/struct/heap.c b/bertos/struct/heap.c new file mode 100644 index 00000000..b4380a4d --- /dev/null +++ b/bertos/struct/heap.c @@ -0,0 +1,236 @@ +/** + * \file + * + * + * \brief Heap subsystem (public interface). + * + * \version $Id: heap.c 1532 2008-08-04 07:21:26Z bernie $ + * \author Bernie Innocenti + */ + +#include "heap.h" + +#include // IS_POW2() +#include // ASSERT() + +#include // memset() + +/* NOTE: struct size must be a 2's power! */ +typedef struct _MemChunk +{ + struct _MemChunk *next; + size_t size; +} MemChunk; + +STATIC_ASSERT(IS_POW2(sizeof(MemChunk))); + +#define FREE_FILL_CODE 0xDEAD +#define ALLOC_FILL_CODE 0xBEEF + +void heap_init(struct Heap* h, void* memory, size_t size) +{ +#ifdef _DEBUG + memset(memory, FREE_FILL_CODE, size); +#endif + + /* Initialize heap with a single big chunk */ + h->FreeList = (MemChunk *)memory; + h->FreeList->next = NULL; + h->FreeList->size = size; +} + + +void *heap_allocmem(struct Heap* h, size_t size) +{ + MemChunk *chunk, *prev; + + /* Round size up to the allocation granularity */ + size = ROUND2(size, sizeof(MemChunk)); + + /* Handle allocations of 0 bytes */ + if (!size) + size = sizeof(MemChunk); + + /* Walk on the free list looking for any chunk big enough to + * fit the requested block size. + */ + for (prev = (MemChunk *)&h->FreeList, chunk = h->FreeList; + chunk; + prev = chunk, chunk = chunk->next) + { + if (chunk->size >= size) + { + if (chunk->size == size) + { + /* Just remove this chunk from the free list */ + prev->next = chunk->next; + #ifdef _DEBUG + memset(chunk, ALLOC_FILL_CODE, size); + #endif + return (void *)chunk; + } + else + { + /* Allocate from the END of an existing chunk */ + chunk->size -= size; + #ifdef _DEBUG + memset((uint8_t *)chunk + chunk->size, ALLOC_FILL_CODE, size); + #endif + return (void *)((uint8_t *)chunk + chunk->size); + } + } + } + + return NULL; /* fail */ +} + + +void heap_freemem(struct Heap* h, void *mem, size_t size) +{ + MemChunk *prev; + ASSERT(mem); + +#ifdef _DEBUG + memset(mem, FREE_FILL_CODE, size); +#endif + + /* Round size up to the allocation granularity */ + size = ROUND2(size, sizeof(MemChunk)); + + /* Handle allocations of 0 bytes */ + if (!size) + size = sizeof(MemChunk); + + /* Special case: first chunk in the free list */ + ASSERT((uint8_t*)mem != (uint8_t*)h->FreeList); + if (((uint8_t *)mem) < ((uint8_t *)h->FreeList)) + { + /* Insert memory block before the current free list head */ + prev = (MemChunk *)mem; + prev->next = h->FreeList; + prev->size = size; + h->FreeList = prev; + } + else /* Normal case: not the first chunk in the free list */ + { + /* + * Walk on the free list. Stop at the insertion point (when mem + * is between prev and prev->next) + */ + prev = h->FreeList; + while (prev->next < (MemChunk *)mem && prev->next) + prev = prev->next; + + /* Make sure mem is not *within* prev */ + ASSERT((uint8_t*)mem >= (uint8_t*)prev + prev->size); + + /* Should it be merged with previous block? */ + if (((uint8_t *)prev) + prev->size == ((uint8_t *)mem)) + { + /* Yes */ + prev->size += size; + } + else /* not merged with previous chunk */ + { + MemChunk *curr = (MemChunk*)mem; + + /* insert it after the previous node + * and move the 'prev' pointer forward + * for the following operations + */ + curr->next = prev->next; + curr->size = size; + prev->next = curr; + + /* Adjust for the following test */ + prev = curr; + } + } + + /* Also merge with next chunk? */ + if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next)) + { + prev->size += prev->next->size; + prev->next = prev->next->next; + + /* There should be only one merge opportunity, becuase we always merge on free */ + ASSERT((uint8_t*)prev + prev->size != (uint8_t*)prev->next); + } +} + +#if CONFIG_HEAP_MALLOC + +void *heap_malloc(struct Heap* h, size_t size) +{ + size_t *mem; + + size += sizeof(size_t); + if ((mem = (size_t*)heap_allocmem(h, size))) + *mem++ = size; + + return mem; +} + +void *heap_calloc(struct Heap* h, size_t size) +{ + void *mem; + + if ((mem = heap_malloc(h, size))) + memset(mem, 0, size); + + return mem; +} + +/** + * Free a block of memory, determining its size automatically. + * + * \param h Heap from which the block was allocated. + * \param mem Pointer to a block of memory previously allocated with + * either heap_malloc() or heap_calloc(). + * + * \note If \a mem is a NULL pointer, no operation is performed. + * + * \note Freeing the same memory block twice has undefined behavior. + * + * \note This function works like the ANSI C free(). + */ +void heap_free(struct Heap *h, void *mem) +{ + size_t *_mem = (size_t *)mem; + + if (_mem) + { + --_mem; + heap_freemem(h, _mem, *_mem); + } +} + +#endif /* CONFIG_HEAP_MALLOC */ diff --git a/bertos/struct/heap.h b/bertos/struct/heap.h new file mode 100644 index 00000000..6819d679 --- /dev/null +++ b/bertos/struct/heap.h @@ -0,0 +1,89 @@ +/** + * \file + * + * + * \brief Heap subsystem (public interface). + * + * \todo Heap memory could be defined as an array of MemChunk, and used + * in this form also within the implementation. This would probably remove + * memory alignment problems, and also some aliasing issues. + * + * \version $Id: heap.h 1532 2008-08-04 07:21:26Z bernie $ + * \author Bernie Innocenti + */ + +#ifndef MWARE_HEAP_H +#define MWARE_HEAP_H + +#include "cfg/cfg_heap.h" +#include + +struct _MemChunk; + +/// A heap +struct Heap +{ + struct _MemChunk *FreeList; ///< Head of the free list +}; + + +/// Initialize \a heap within the buffer pointed by \a memory which is of \a size bytes +void heap_init(struct Heap* heap, void* memory, size_t size); + +/// Allocate a chunk of memory of \a size bytes from the heap +void *heap_allocmem(struct Heap* heap, size_t size); + +/// Free a chunk of memory of \a size bytes from the heap +void heap_freemem(struct Heap* heap, void *mem, size_t size); + + +#define HNEW(heap, type) \ + (type*)heap_allocmem(heap, sizeof(type)) + +#define HNEWVEC(heap, type, nelem) \ + (type*)heap_allocmem(heap, sizeof(type) * (nelem)) + +#define HDELETE(heap, type, mem) \ + heap_freemem(heap, mem, sizeof(type)) + +#define HDELETEVEC(heap, type, nelem, mem) \ + heap_freemem(heap, mem, sizeof(type) * (nelem)) + + +#if CONFIG_HEAP_MALLOC + +void *heap_malloc(struct Heap* heap, size_t size); +void *heap_calloc(struct Heap* heap, size_t size); +void heap_free(struct Heap* heap, void * mem); + +#endif + +#endif /* MWARE_HEAP_H */ diff --git a/bertos/struct/list.h b/bertos/struct/list.h new file mode 100644 index 00000000..87808edf --- /dev/null +++ b/bertos/struct/list.h @@ -0,0 +1,330 @@ +/** + * \file + * + * + * \brief General pourpose double-linked lists + * + * \version $Id: list.h 1594 2008-08-10 12:20:10Z bernie $ + * \author Bernie Innocenti + */ + +#ifndef MWARE_LIST_H +#define MWARE_LIST_H + +#include /* INLINE */ +#include /* ASSERT_VALID_PTR() */ + +/** + * This structure represents a node for bidirectional lists. + * + * Data is usually appended to nodes by making them the first + * field of another struture, as a poor-man's form of inheritance. + */ +typedef struct _Node +{ + struct _Node *succ; + struct _Node *pred; +} Node; + +/** + * Head of a doubly-linked list of \c Node structs. + * + * Lists must be initialized with LIST_INIT() prior to use. + * + * Nodes can be added and removed from either end of the list + * with O(1) performance. Iterating over these lists can be + * tricky: use the FOREACH_NODE() macro instead. + */ +typedef struct _List +{ + Node head; + Node tail; +} List; + +/** + * Extended node for priority queues. + */ +typedef struct _PriNode +{ + Node link; + int pri; +} PriNode; + + +/** + * Template for a naked node in a list of \a T structures. + * + * To be used as data member in other structures: + * + * \code + * struct Foo + * { + * DECLARE_NODE_ANON(struct Foo) + * int a; + * float b; + * } + * + * DECLARE_LIST_TYPE(Foo); + * + * void foo(void) + * { + * static LIST_TYPE(Foo) foo_list; + * static Foo foo1, foo2; + * Foo *fp; + * + * LIST_INIT(&foo_list); + * ADDHEAD(&foo_list, &foo1); + * INSERT_BEFORE(&foo_list, &foo2); + * FOREACH_NODE(fp, &foo_list) + * fp->a = 10; + * } + * + * \endcode + */ +#define DECLARE_NODE_ANON(T) \ + T *succ; T *pred; + +/** Declare a typesafe node for structures of type \a T. */ +#define DECLARE_NODE_TYPE(T) \ + typedef struct T##Node { T *succ; T *pred; } T##Node + +/** Template for a list of \a T structures. */ +#define DECLARE_LIST_TYPE(T) \ + DECLARE_NODE_TYPE(T); \ + typedef struct T##List { \ + T##Node head; \ + T##Node tail; \ + } T##List + +#define NODE_TYPE(T) T##Node +#define LIST_TYPE(T) T##List + +/** + * Get a pointer to the first node in a list. + * + * If \a l is empty, result points to l->tail. + */ +#define LIST_HEAD(l) ((l)->head.succ) + +/** + * Get a pointer to the last node in a list. + * + * If \a l is empty, result points to l->head. + */ +#define LIST_TAIL(l) ((l)->tail.pred) + +// TODO: move in compiler.h +#if COMPILER_TYPEOF + #define TYPEOF_OR_VOIDPTR(type) typeof(type) +#else + #define TYPEOF_OR_VOIDPTR(type) void * +#endif + +/** + * Iterate over all nodes in a list. + * + * This macro generates a "for" statement using the following parameters: + * \param n Node pointer to be used in each iteration. + * \param l Pointer to list. + */ +#define FOREACH_NODE(n, l) \ + for( \ + (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l); \ + ((Node *)(n))->succ; \ + (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \ + ) + +/** + * Iterate backwards over all nodes in a list. + * + * This macro generates a "for" statement using the following parameters: + * \param n Node pointer to be used in each iteration. + * \param l Pointer to list. + */ +#define REVERSE_FOREACH_NODE(n, l) \ + for( \ + (n) = (TYPEOF_OR_VOIDPTR(n))LIST_TAIL(l); \ + ((Node *)(n))->pred; \ + (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \ + ) + +/** Initialize a list. */ +#define LIST_INIT(l) \ + do { \ + (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \ + (l)->head.pred = NULL; \ + (l)->tail.succ = NULL; \ + (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \ + } while (0) + +#ifdef _DEBUG + /** Make sure that a list is valid (it was initialized and is not corrupted). */ + #define LIST_ASSERT_VALID(l) \ + do { \ + Node *n, *pred; \ + ASSERT((l)->head.succ != NULL); \ + ASSERT((l)->head.pred == NULL); \ + ASSERT((l)->tail.succ == NULL); \ + ASSERT((l)->tail.pred != NULL); \ + pred = &(l)->head; \ + FOREACH_NODE(n, l) \ + { \ + ASSERT(n->pred == pred); \ + pred = n; \ + } \ + ASSERT(n == &(l)->tail); \ + } while (0) + + #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL) +#else + #define LIST_ASSERT_VALID(l) do {} while (0) + #define INVALIDATE_NODE(n) do {} while (0) +#endif + +/** Add node to list head. */ +#define ADDHEAD(l,n) \ + do { \ + ASSERT_VALID_PTR(l); \ + ASSERT_VALID_PTR(n); \ + (n)->succ = (l)->head.succ; \ + (n)->pred = (l)->head.succ->pred; \ + (n)->succ->pred = (n); \ + (n)->pred->succ = (n); \ + } while (0) + +/** Add node to list tail. */ +#define ADDTAIL(l,n) \ + do { \ + ASSERT_VALID_PTR(l); \ + ASSERT_VALID_PTR(n); \ + (n)->succ = &(l)->tail; \ + (n)->pred = (l)->tail.pred; \ + (n)->pred->succ = (n); \ + (l)->tail.pred = (n); \ + } while (0) + +/** + * Insert node \a n before node \a ln. + * + * \note You can't pass in a list header as \a ln, but + * it is safe to pass list-\>head of an empty list. + */ +#define INSERT_BEFORE(n,ln) \ + do { \ + ASSERT_VALID_PTR(n); \ + ASSERT_VALID_PTR(ln); \ + (n)->succ = (ln); \ + (n)->pred = (ln)->pred; \ + (ln)->pred->succ = (n); \ + (ln)->pred = (n); \ + } while (0) + +/** + * Remove \a n from whatever list it is in. + * + * \note Removing a node that has not previously been + * inserted into a list invokes undefined behavior. + */ +#define REMOVE(n) \ + do { \ + ASSERT_VALID_PTR(n); \ + (n)->pred->succ = (n)->succ; \ + (n)->succ->pred = (n)->pred; \ + INVALIDATE_NODE(n); \ + } while (0) + +/** Tell whether a list is empty. */ +#define LIST_EMPTY(l) ( (void *)((l)->head.succ) == (void *)(&(l)->tail) ) + +/** + * Insert a priority node in a priority queue. + * + * The new node is inserted immediately before the + * first node with lower priority or appended to + * the tail if no such node exists. + */ +#define LIST_ENQUEUE(list, node) \ + do { \ + PriNode *ln; \ + ASSERT_VALID_PTR(list); \ + ASSERT_VALID_PTR(node); \ + FOREACH_NODE(ln, (list)) \ + if (ln->pri < (node)->pri) \ + break; \ + INSERT_BEFORE(&(node)->link, &ln->link); \ + } while (0) + + +/** + * Unlink a node from the head of the list \a l. + * + * \return Pointer to node, or NULL if the list was empty. + */ +INLINE Node *list_remHead(List *l) +{ + Node *n; + + ASSERT_VALID_PTR(l); + + if (LIST_EMPTY(l)) + return (Node *)0; + + n = l->head.succ; /* Get first node. */ + l->head.succ = n->succ; /* Link list head to second node. */ + n->succ->pred = &l->head; /* Link second node to list head. */ + + INVALIDATE_NODE(n); + return n; +} + +/** + * Unlink a node from the tail of the list \a l. + * + * \return Pointer to node, or NULL if the list was empty. + */ +INLINE Node *list_remTail(List *l) +{ + Node *n; + + ASSERT_VALID_PTR(l); + + if (LIST_EMPTY(l)) + return NULL; + + n = l->tail.pred; /* Get last node. */ + l->tail.pred = n->pred; /* Link list tail to second last node. */ + n->pred->succ = &l->tail; /* Link second last node to list tail. */ + + INVALIDATE_NODE(n); + return n; +} + +#endif /* MWARE_LIST_H */ diff --git a/bertos/struct/pool.h b/bertos/struct/pool.h new file mode 100644 index 00000000..01c18d38 --- /dev/null +++ b/bertos/struct/pool.h @@ -0,0 +1,74 @@ +/** + * \file + * + * + * \brief Pool macros. + * + * \version $Id: pool.h 1294 2008-05-20 13:43:57Z asterix $ + * \author Giovanni Bajo + */ + +#ifndef MWARE_POOL_H +#define MWARE_POOL_H + +#include +#include + +#define EXTERN_POOL(name) \ + extern List name + +#define DECLARE_POOL_WITH_STORAGE(name, type, num, storage) \ + static type name##_items[num]; \ + storage name; \ + INLINE void name##_init(void (*init_func)(type*)) \ + { \ + int i; \ + LIST_INIT(&name); \ + for (i=0;i