src/Util/FifoBuffer.hpp

   1 /*
   2  * Copyright (C) 2003-2010 Max Kellermann <max@duempel.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * - Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * - Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the
  14  * distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  20  * FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  27  * OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #ifndef XCSOAR_FIFO_BUFFER_HPP
  31 #define XCSOAR_FIFO_BUFFER_HPP
  32
  33 #include <utility>
  34 #include <algorithm>
  35
  36 #include <assert.h>
  37 #include <stddef.h>
  38
  39 /**
  40  * A first-in-first-out buffer: you can append data at the end, and
  41  * read data from the beginning.  This class automatically shifts the
  42  * buffer as needed.  It is not thread safe.
  43  */
  44 template<class T, size_t size>
  45 class FifoBuffer {
  46 public:
  47   typedef size_t size_type;
  48
  49 public:
  50   struct Range {
  51     T *data;
  52
  53     size_type length;
  54
  55     Range() = default;
  56
  57     constexpr
  58     Range(T *_data, size_type _length):data(_data), length(_length) {}
  59
  60     constexpr
  61     bool IsEmpty() const {
  62       return length == 0;
  63     }
  64   };
  65
  66 protected:
  67   size_type head, tail;
  68   T data[size];
  69
  70 public:
  71   constexpr
  72   FifoBuffer():head(0), tail(0) {}
  73
  74 protected:
  75   void Shift() {
  76     if (head == 0)
  77       return;
  78
  79     assert(head <= size);
  80     assert(tail <= size);
  81     assert(tail >= head);
  82
  83     std::move(data + head, data + tail, data);
  84
  85     tail -= head;
  86     head = 0;
  87   }
  88
  89 public:
  90   void Clear() {
  91     head = tail = 0;
  92   }
  93
  94   bool IsEmpty() const {
  95     return head == tail;
  96   }
  97
  98   bool IsFull() const {
  99     return head == 0 && tail == size;
 100   }
 101
 102   /**
 103    * Prepares writing.  Returns a buffer range which may be written.
 104    * When you are finished, call append().
 105    */
 106   Range Write() {
 107     Shift();
 108     return Range(data + tail, size - tail);
 109   }
 110
 111   /**
 112    * Expands the tail of the buffer, after data has been written to
 113    * the buffer returned by write().
 114    */
 115   void Append(size_type n) {
 116     assert(tail <= size);
 117     assert(n <= size);
 118     assert(tail + n <= size);
 119
 120     tail += n;
 121   }
 122
 123   /**
 124    * Return a buffer range which may be read.  The buffer pointer is
 125    * writable, to allow modifications while parsing.
 126    */
 127   Range Read() {
 128     return Range(data + head, tail - head);
 129   }
 130
 131   /**
 132    * Marks a chunk as consumed.
 133    */
 134   void Consume(size_type n) {
 135     assert(tail <= size);
 136     assert(head <= tail);
 137     assert(n <= tail);
 138     assert(head + n <= tail);
 139
 140     head += n;
 141   }
 142 };
 143
 144 #endif