Added ecbuf - An efficient expanding circular buffer

2 files changed, 150 insertions, 0 deletions

diff --git a/README b/README
index d0cdd8e..9c488b4 100644
--- a/README
+++ b/README
@@ -2,6 +2,7 @@ This git repository holds a collection of small and independent C libraries.
 
   dbusev  - Register a DBusConnection with libev
   dbusuv  - Register a DBusConnection with libuv
+  ecbuf   - An efficient expanding circular buffer
   ylog    - A small, flexible and efficient logging system for C
   yopt    - A small, simple and portable getopt_long() replacement
   yuri    - A minimal URI validation and parsing library
diff --git a/ecbuf.h b/ecbuf.h
new file mode 100644
index 0000000..c493894
--- /dev/null
+++ b/ecbuf.h
@@ -0,0 +1,149 @@
+/* Copyright (c) 2012 Yoran Heling
+
+  Permission is hereby granted, free of charge, to any person obtaining
+  a copy of this software and associated documentation files (the
+  "Software"), to deal in the Software without restriction, including
+  without limitation the rights to use, copy, modify, merge, publish,
+  distribute, sublicense, and/or sell copies of the Software, and to
+  permit persons to whom the Software is furnished to do so, subject to
+  the following conditions:
+
+  The above copyright notice and this permission notice shall be included
+  in all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+  CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+  TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+/* This is an efficient circular buffer implementation that automatically
+ * expands the buffer when it's full. As such, it behaves like any other FIFO
+ * queue.
+ *
+ * Usage:
+ *
+ *    ecbuf_t(int) queue;
+ *    ecbuf_init(queue);
+ *
+ *    // Writing
+ *    ecbuf_push(queue, 3);
+ *    ecbuf_push(queue, 5);
+ *    ecbuf_push(queue, 7);
+ *    ecbuf_push(queue, 11);
+ *
+ *    // = 11
+ *    printf("Most recently queued = %d\n", ecbuf_pry(queue));
+ *    // = 3
+ *    printf("Least recently queued = %d\n", ecbuf_peek(queue));
+ *    // = 4
+ *    printf("Queue length = %d\n", ecbuf_len(queue));
+ *
+ *    // Reading
+ *    while(!ecbuf_empty(queue)) {
+ *        printf("Item: %d\n", ecbuf_pop(queue));
+ *    }
+ *
+ *    ecbuf_destroy(queue);
+ *
+ *
+ * The concept is explained at
+ * http://blog.labix.org/2010/12/23/efficient-algorithm-for-expanding-circular-buffers
+ *
+ * This implementation is slightly different, in that it provides a macro to
+ * read back the most recently written value without adding more overhead in
+ * terms of the number of variables to keep track of. This implementation does
+ * leave at least one slot empty, so in terms of memory usage, it doesn't
+ * really matter (depending on the pointer size of your machine and the size of
+ * your elements).
+ */
+
+#ifndef ECBUF_H
+#define ECBUF_H
+
+#include <stdlib.h>
+
+
+/* The variables are:
+ *  i: Index we're going to write to in the next push()
+ * li: Last index we've written to in the last push()
+ *  o: Index we're going to read from in the next pop()
+ *  b: Index of the last written item before the buffer has been expanded.
+ * cm: Maximum index of the circular buffer. (i.e. size of circular buffer -1)
+ * bm: Maximum index of the complete buffer. (i.e. size of complete buffer -1)
+ */
+#define ecbuf_t(type) struct {\
+		int i, li, o, b, cm, bm;\
+		type *a;\
+	}
+
+/* Internal type for use with ecbuf__pop() */
+typedef ecbuf_t(void) ecbuf__t;
+
+
+#define ecbuf_init(v) do {\
+		(v).bm = (v).cm = 31;\
+		(v).o = (v).i = 0;\
+		(v).b = -1;\
+		(v).a = malloc(((v).bm+1)*sizeof(*(v).a));\
+	} while(0)
+
+#define ecbuf_destroy(v) free((v).a)
+
+/* Number of items queued. The first macro is our initial implementation and
+ * covers each case separately, the latter one is an optimization with only a
+ * single branch. Both *should* be correct, but I'm keeping the old one for
+ * reference. */
+#define ecbuf__len_ref(v) ((v).cm == (v).bm\
+		? ((v).i >= (v).o ? (v).i - (v).o : (v).cm - (v).o + (v).i + 1)\
+		: ((v).b >= (v).o ? (v).b - (v).o + (v).i - (v).cm : (v).b - (v).o + (v).i + 1))
+
+#define ecbuf_len(v) (((v).i - (v).o + (v).b + 1 + ((v).b >= (v).o ? -1 - (v).cm : (v).bm + 1)) & (v).bm)
+
+
+/* A faster version of ecbuf_len(v) == 0 */
+#define ecbuf_empty(v) ((v).i == (v).o)
+
+/* Peek into the queue, requires !ecbuf_empty(v) */
+#define ecbuf_peek(v) ((v).a[(v).o])
+
+/* Similar to peek, but reads back the most *recently* queued item.
+ * (I'm bad at naming, I know) */
+#define ecbuf_pry(v) ((v).a[(v).li])
+
+#define ecbuf_push(v, x) do {\
+		(v).a[(v).i] = (x);\
+		(v).li = (v).i;\
+		if((v).i == (v).o-1 || ((v).i == (v).cm && (v).o == 0) || ((v).i == (v).bm && (v).bm != (v).cm)) {\
+			if((v).i == (v).o-1)\
+				(v).b = (v).i;\
+			(v).i = (v).bm+1;\
+			(v).bm = ((v).bm+1)*2-1;\
+			(v).a = realloc((v).a, ((v).bm+1)*sizeof(*(v).a));\
+			if((v).li == (v).cm && (v).o == 0)\
+				(v).cm = (v).bm;\
+		} else\
+			(v).i = (v).i == (v).bm ? 0 : (v).i+1;\
+	} while(0)
+
+
+static inline int ecbuf__pop(ecbuf__t *v) {
+	int l = v->o;
+	if(v->o == v->cm)
+		v->o = 0;
+	else if(v->o == v->b) {
+		v->o = v->cm + 1;
+		v->b = -1;
+		v->cm = v->bm;
+	} else
+		v->o++;
+	return l;
+}
+#define ecbuf_pop(v) ((v).a[ecbuf__pop((ecbuf__t *)&(v))])
+
+#endif
+
+/* vim: set noet sw=4 ts=4: */