From 7a6db77f598f0f4723b3f6048e372daa92ec2430 Mon Sep 17 00:00:00 2001 From: Nicolas Schodet Date: Sat, 15 Dec 2012 16:06:59 +0100 Subject: digital/ucoolib/ucoolib/utils: add fifo low level container --- digital/ucoolib/ucoolib/common.hh | 11 +++ digital/ucoolib/ucoolib/utils/fifo.hh | 76 +++++++++++++++++ digital/ucoolib/ucoolib/utils/fifo.tcc | 108 ++++++++++++++++++++++++ digital/ucoolib/ucoolib/utils/test/Makefile | 6 +- digital/ucoolib/ucoolib/utils/test/test_fifo.cc | 82 ++++++++++++++++++ 5 files changed, 281 insertions(+), 2 deletions(-) create mode 100644 digital/ucoolib/ucoolib/utils/fifo.hh create mode 100644 digital/ucoolib/ucoolib/utils/fifo.tcc create mode 100644 digital/ucoolib/ucoolib/utils/test/test_fifo.cc (limited to 'digital/ucoolib') diff --git a/digital/ucoolib/ucoolib/common.hh b/digital/ucoolib/ucoolib/common.hh index 1f6d75ae..83763899 100644 --- a/digital/ucoolib/ucoolib/common.hh +++ b/digital/ucoolib/ucoolib/common.hh @@ -27,6 +27,9 @@ namespace ucoo { +/// Integer which is read and written atomically. +typedef int int_atomic_t; + /// Compiler barrier. Prevents the compiler from moving the memory accesses /// from one side of it to the other side. extern inline void @@ -35,6 +38,14 @@ barrier () __asm__ __volatile__("": : : "memory"); } +/// Ensure a single access is done, avoid compiler optimisations. +template +extern inline volatile T & +access_once (T &x) +{ + return *static_cast (&x); +} + /// Stop, abruptly. void halt () __attribute__ ((noreturn)); diff --git a/digital/ucoolib/ucoolib/utils/fifo.hh b/digital/ucoolib/ucoolib/utils/fifo.hh new file mode 100644 index 00000000..0b8aa282 --- /dev/null +++ b/digital/ucoolib/ucoolib/utils/fifo.hh @@ -0,0 +1,76 @@ +#ifndef ucoolib_utils_fifo_hh +#define ucoolib_utils_fifo_hh +// ucoolib - Microcontroller object oriented library. {{{ +// +// Copyright (C) 2012 Nicolas Schodet +// +// APBTeam: +// Web: http://apbteam.org/ +// Email: team AT apbteam DOT org +// +// 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 2 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, write to the Free Software +// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +// +// }}} +#include "ucoolib/common.hh" + +namespace ucoo { + +/// First In First Out container. It is implemented as a circular buffer, +/// providing thread safety if the reader and the writer are in separated +/// threads. +/// +/// This is a rather low level container used to implement ucoolib features. +/// Be careful that there is only room for size - 1 elements in the FIFO. +template +class Fifo +{ + public: + /// Constructor, initialise an empty FIFO. + Fifo (); + /// Test whether the FIFO is empty. + bool empty () const { return head_ == tail_; } + /// Test whether the FIFO is full. + bool full () const { return head_ == next (tail_); } + /// Remove an element, do not do that if FIFO is empty! + T pop (); + /// Add an element, do not do that if FIFO is full! + void push (const T &e); + /// Pop up to COUNT elements and store them in BUF. Return the number of + /// read elements. + int read (T *buf, int count); + /// Push up to COUNT elements from BUF. Return the number of written + /// elements. + int write (const T *buf, int count); + private: + /// Return next index, use unsigned operation for optimisation. + int next (int index) const + { + return (static_cast (index) + 1) % size; + } + private: + /// Index of the next element to pop, always incremented. + int_atomic_t head_; + /// Index of the next free space where to put a pushed element, also + /// always incremented. + int_atomic_t tail_; + /// Memory to store elements. + T buffer_[size]; +}; + +} // namespace ucoo + +#include "fifo.tcc" + +#endif // ucoolib_utils_fifo_hh diff --git a/digital/ucoolib/ucoolib/utils/fifo.tcc b/digital/ucoolib/ucoolib/utils/fifo.tcc new file mode 100644 index 00000000..c9227ecf --- /dev/null +++ b/digital/ucoolib/ucoolib/utils/fifo.tcc @@ -0,0 +1,108 @@ +#ifndef ucoolib_utils_fifo_tcc +#define ucoolib_utils_fifo_tcc +// ucoolib - Microcontroller object oriented library. {{{ +// +// Copyright (C) 2012 Nicolas Schodet +// +// APBTeam: +// Web: http://apbteam.org/ +// Email: team AT apbteam DOT org +// +// 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 2 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, write to the Free Software +// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +// +// }}} +#include + +namespace ucoo { + +template +inline +Fifo::Fifo () + : head_ (0), tail_ (0) +{ +} + +template +inline T +Fifo::pop () +{ + // Reader, can only update head. + int head = head_; + assert (head != tail_); + T v = buffer_[head]; + head = next (head); + barrier (); + head_ = head; + return v; +} + +template +inline void +Fifo::push (const T &e) +{ + // Writer, can only update tail. + int tail = tail_; + buffer_[tail] = e; + tail = next (tail); + assert (head_ != tail); + barrier (); + tail_ = tail; +} + +template +inline int +Fifo::read (T *buf, int count) +{ + // Reader, can only update head. + int r = 0; + int head = head_; + int tail = access_once (tail_); + while (r < count && head != tail) + { + buf[r] = buffer_[head]; + head = next (head); + r++; + } + // Ensure data is copied, then update head. + barrier (); + head_ = head; + return r; +} + +template +inline int +Fifo::write (const T *buf, int count) +{ + // Writer, can only update tail. + int r = 0; + int head = access_once (head_); + int tail = tail_; + int tailp1 = next (tail); + while (r < count && tailp1 != head) + { + buffer_[tail] = buf[r]; + tail = tailp1; + r++; + tailp1 = next (tail); + } + // Ensure data is copied, then update tail. + barrier (); + tail_ = tail; + return r; +} + +} // namespace ucoo + +#endif // ucoolib_utils_fifo_tcc diff --git a/digital/ucoolib/ucoolib/utils/test/Makefile b/digital/ucoolib/ucoolib/utils/test/Makefile index 2c45dc44..874bc325 100644 --- a/digital/ucoolib/ucoolib/utils/test/Makefile +++ b/digital/ucoolib/ucoolib/utils/test/Makefile @@ -1,9 +1,11 @@ BASE = ../../.. -TARGETS = stm32f4 +TARGETS = host stm32f4 +PROGS = test_fifo stm32f4_PROGS = test_delay +test_fifo_SOURCES = test_fifo.cc test_delay_SOURCES = test_delay.cc -MODULES = utils +MODULES = utils base/test hal/usb include $(BASE)/build/top.mk diff --git a/digital/ucoolib/ucoolib/utils/test/test_fifo.cc b/digital/ucoolib/ucoolib/utils/test/test_fifo.cc new file mode 100644 index 00000000..3f89276e --- /dev/null +++ b/digital/ucoolib/ucoolib/utils/test/test_fifo.cc @@ -0,0 +1,82 @@ +// ucoolib - Microcontroller object oriented library. {{{ +// +// Copyright (C) 2012 Nicolas Schodet +// +// APBTeam: +// Web: http://apbteam.org/ +// Email: team AT apbteam DOT org +// +// 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 2 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, write to the Free Software +// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +// +// }}} +#include "ucoolib/utils/fifo.hh" +#include "ucoolib/arch/arch.hh" +#include "ucoolib/base/test/test.hh" + +int +main (int argc, const char **argv) +{ + ucoo::arch_init (argc, argv); + ucoo::Test test ("fifo"); + { + test.begin ("push pop"); + ucoo::Fifo fifo; + fifo.push (1); + fifo.push (2); + fifo.push (3); + if (fifo.pop () != 1 || fifo.pop () != 2 || fifo.pop () != 3) + test.fail (); + else + test.pass (); + } + { + test.begin ("full empty"); + ucoo::Fifo fifo; + do + { + test_fail_break_unless (test, fifo.empty () && !fifo.full ()); + fifo.push (1); + test_fail_break_unless (test, !fifo.empty () && !fifo.full ()); + fifo.push (2); + test_fail_break_unless (test, !fifo.empty () && !fifo.full ()); + fifo.push (3); + test_fail_break_unless (test, !fifo.empty () && fifo.full ()); + test.pass (); + } while (0); + } + { + test.begin ("write read"); + ucoo::Fifo fifo; + static const int b[] = { 1, 2, 3, 4, 5 }; + int c[8]; + int r; + do + { + r = fifo.write (b, 5); + test_fail_break_unless (test, r == 5); + r = fifo.read (c, 2); + test_fail_break_unless (test, r == 2 && c[0] == 1 && c[1] == 2); + r = fifo.write (b, 5); + test_fail_break_unless (test, r == 4); + r = fifo.read (c, 8); + test_fail_break_unless (test, r == 7); + test_fail_break_unless (test, c[0] == 3 && c[1] == 4 && c[2] == 5); + test_fail_break_unless (test, c[3] == 1 && c[4] == 2 && c[5] == 3 + && c[6] == 4); + test.pass (); + } while (0); + } + return test.report () ? 0 : 1; +} -- cgit v1.2.3