summaryrefslogtreecommitdiffstats
path: root/libnetdata/circular_buffer
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/circular_buffer')
-rw-r--r--libnetdata/circular_buffer/Makefile.am8
-rw-r--r--libnetdata/circular_buffer/README.md12
-rw-r--r--libnetdata/circular_buffer/circular_buffer.c85
-rw-r--r--libnetdata/circular_buffer/circular_buffer.h16
4 files changed, 121 insertions, 0 deletions
diff --git a/libnetdata/circular_buffer/Makefile.am b/libnetdata/circular_buffer/Makefile.am
new file mode 100644
index 0000000..161784b
--- /dev/null
+++ b/libnetdata/circular_buffer/Makefile.am
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+AUTOMAKE_OPTIONS = subdir-objects
+MAINTAINERCLEANFILES = $(srcdir)/Makefile.in
+
+dist_noinst_DATA = \
+ README.md \
+ $(NULL)
diff --git a/libnetdata/circular_buffer/README.md b/libnetdata/circular_buffer/README.md
new file mode 100644
index 0000000..d36c05f
--- /dev/null
+++ b/libnetdata/circular_buffer/README.md
@@ -0,0 +1,12 @@
+<!--
+title: "circular_buffer"
+custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/circular_buffer/README.md
+-->
+
+# Circular Buffer
+
+`struct circular_buffer` is an adaptive circular buffer. It will start at an initial size
+and grow up to a maximum size as it fills. Two indices within the structure track the current
+`read` and `write` position for data.
+
+[![analytics](https://www.google-analytics.com/collect?v=1&aip=1&t=pageview&_s=1&ds=github&dr=https%3A%2F%2Fgithub.com%2Fnetdata%2Fnetdata&dl=https%3A%2F%2Fmy-netdata.io%2Fgithub%2Flibnetdata%2Fcircular_buffer%2README&_u=MAC~&cid=5792dfd7-8dc4-476b-af31-da2fdb9f93d2&tid=UA-64295674-3)]()
diff --git a/libnetdata/circular_buffer/circular_buffer.c b/libnetdata/circular_buffer/circular_buffer.c
new file mode 100644
index 0000000..998008d
--- /dev/null
+++ b/libnetdata/circular_buffer/circular_buffer.c
@@ -0,0 +1,85 @@
+#include "../libnetdata.h"
+
+struct circular_buffer *cbuffer_new(size_t initial, size_t max) {
+ struct circular_buffer *result = mallocz(sizeof(*result));
+ result->size = initial;
+ result->data = mallocz(initial);
+ result->write = 0;
+ result->read = 0;
+ result->max_size = max;
+ return result;
+}
+
+void cbuffer_free(struct circular_buffer *buf) {
+ freez(buf->data);
+ freez(buf);
+}
+
+static int cbuffer_realloc_unsafe(struct circular_buffer *buf) {
+ // Check that we can grow
+ if (buf->size >= buf->max_size)
+ return 1;
+ size_t new_size = buf->size * 2;
+ if (new_size > buf->max_size)
+ new_size = buf->max_size;
+
+ // We know that: size < new_size <= max_size
+ // For simplicity align the current data at the bottom of the new buffer
+ char *new_data = mallocz(new_size);
+ if (buf->read == buf->write)
+ buf->write = 0; // buffer is empty
+ else if (buf->read < buf->write) {
+ memcpy(new_data, buf->data + buf->read, buf->write - buf->read);
+ buf->write -= buf->read;
+ } else {
+ size_t top_part = buf->size - buf->read;
+ memcpy(new_data, buf->data + buf->read, top_part);
+ memcpy(new_data + top_part, buf->data, buf->write);
+ buf->write = top_part + buf->write;
+ }
+ buf->read = 0;
+
+ // Switch buffers
+ freez(buf->data);
+ buf->data = new_data;
+ buf->size = new_size;
+ return 0;
+}
+
+int cbuffer_add_unsafe(struct circular_buffer *buf, const char *d, size_t d_len) {
+ size_t len = (buf->write >= buf->read) ? (buf->write - buf->read) : (buf->size - buf->read + buf->write);
+ while (d_len + len >= buf->size) {
+ if (cbuffer_realloc_unsafe(buf)) {
+ return 1;
+ }
+ }
+ // Guarantee: write + d_len cannot hit read
+ if (buf->write + d_len < buf->size) {
+ memcpy(buf->data + buf->write, d, d_len);
+ buf->write += d_len;
+ }
+ else {
+ size_t top_part = buf->size - buf->write;
+ memcpy(buf->data + buf->write, d, top_part);
+ memcpy(buf->data, d + top_part, d_len - top_part);
+ buf->write = d_len - top_part;
+ }
+ return 0;
+}
+
+// Assume caller does not remove too many bytes (i.e. read will jump over write)
+void cbuffer_remove_unsafe(struct circular_buffer *buf, size_t num) {
+ buf->read += num;
+ // Assume num < size (i.e. caller cannot remove more bytes than are in the buffer)
+ if (buf->read >= buf->size)
+ buf->read -= buf->size;
+}
+
+size_t cbuffer_next_unsafe(struct circular_buffer *buf, char **start) {
+ if (start != NULL)
+ *start = buf->data + buf->read;
+ if (buf->read <= buf->write) {
+ return buf->write - buf->read; // Includes empty case
+ }
+ return buf->size - buf->read;
+}
diff --git a/libnetdata/circular_buffer/circular_buffer.h b/libnetdata/circular_buffer/circular_buffer.h
new file mode 100644
index 0000000..ba37e0e
--- /dev/null
+++ b/libnetdata/circular_buffer/circular_buffer.h
@@ -0,0 +1,16 @@
+#ifndef CIRCULAR_BUFFER_H
+#define CIRCULAR_BUFFER_H 1
+
+#include <string.h>
+
+struct circular_buffer {
+ size_t size, write, read, max_size;
+ char *data;
+};
+
+extern struct circular_buffer *cbuffer_new(size_t initial, size_t max);
+extern void cbuffer_free(struct circular_buffer *buf);
+extern int cbuffer_add_unsafe(struct circular_buffer *buf, const char *d, size_t d_len);
+extern void cbuffer_remove_unsafe(struct circular_buffer *buf, size_t num);
+extern size_t cbuffer_next_unsafe(struct circular_buffer *buf, char **start);
+#endif