summaryrefslogtreecommitdiff
path: root/ioreplay/src/datas
diff options
context:
space:
mode:
Diffstat (limited to 'ioreplay/src/datas')
-rw-r--r--ioreplay/src/datas/amap.c264
-rw-r--r--ioreplay/src/datas/amap.h49
-rw-r--r--ioreplay/src/datas/btree.c169
-rw-r--r--ioreplay/src/datas/btree.h52
-rw-r--r--ioreplay/src/datas/hmap.c364
-rw-r--r--ioreplay/src/datas/hmap.h56
-rw-r--r--ioreplay/src/datas/list.c279
-rw-r--r--ioreplay/src/datas/list.h56
-rw-r--r--ioreplay/src/datas/rbuffer.c147
-rw-r--r--ioreplay/src/datas/rbuffer.h102
-rw-r--r--ioreplay/src/datas/stack.c85
-rw-r--r--ioreplay/src/datas/stack.h43
12 files changed, 1666 insertions, 0 deletions
diff --git a/ioreplay/src/datas/amap.c b/ioreplay/src/datas/amap.c
new file mode 100644
index 0000000..806a3f8
--- /dev/null
+++ b/ioreplay/src/datas/amap.c
@@ -0,0 +1,264 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "amap.h"
+
+/**
+ * @brief Creates a new array map
+ *
+ * @param size The array map size
+ * @param mmapped true if the memory should be mmapped
+ * @return The new amap object
+ */
+static amap_s *_amap_new(long size, bool mmapped)
+{
+ amap_s *a = NULL;
+ void ***arrays = NULL;
+
+ // Calculate a multiple of 1024, but at least in size of 'size'.
+ if (size % 1024 != 0) {
+ size = 1024*(1+(long)(size/1024));
+ }
+
+ if (size < 1) {
+ Error("Size overflow");
+ }
+
+ int num_arrays = size / AMAP_MAX_ARRAY_LENGTH;
+
+ if (mmapped) {
+ a = Mmapshared(amap_s);
+ arrays = Cmapshared(num_arrays, void**);
+ } else {
+ a = Malloc(amap_s);
+ arrays = Calloc(num_arrays, void**);
+ }
+
+ for (int i = 0; i < num_arrays; ++i) {
+ if (mmapped) {
+ //Put("%d", AMAP_MAX_ARRAY_LENGTH);
+ arrays[i] = Cmapshared(AMAP_MAX_ARRAY_LENGTH, void*);
+ } else {
+ arrays[i] = Calloc(AMAP_MAX_ARRAY_LENGTH, void*);
+ }
+ for (int j = 0; j < AMAP_MAX_ARRAY_LENGTH; ++j) {
+ arrays[i][j] = NULL;
+ }
+ }
+
+ a->arrays = arrays;
+ a->num_arrays = num_arrays;
+ a->size = size;
+ a->data_destroy = NULL;
+ a->mmapped = mmapped;
+
+ return a;
+}
+
+/**
+ * @brief Creates a new array map
+ *
+ * @param size The array map size
+ * @return The new amap object
+ */
+amap_s* amap_new(const long size)
+{
+ return _amap_new(size, false);
+}
+
+/**
+ * @brief Creates a new mmapped array map
+ *
+ * @param size The array map size
+ * @return The new amap object
+ */
+amap_s* amap_new_mmapped(const long size)
+{
+ return _amap_new(size, true);
+}
+
+/**
+ * @brief Destroys a mmap object
+ *
+ * @a The new amap object
+ */
+void amap_destroy(amap_s* a)
+{
+ if (!a) {
+ return;
+ }
+
+ // Don't bother, the mmapped version of amap will stay alive until
+ // process terminations. And after process termination everything
+ // will be cleaned up automatically by Linux.
+ if (a->mmapped) {
+ return;
+ }
+
+ for (int i = 0; i < a->num_arrays; ++i) {
+ if (a->data_destroy) {
+ for (int j = 0; j < AMAP_MAX_ARRAY_LENGTH; ++j)
+ if (a->arrays[i][j]) {
+ a->data_destroy(a->arrays[i][j]);
+ }
+ }
+ free(a->arrays[i]);
+ }
+ free(a->arrays);
+ free(a);
+}
+
+/**
+ * @brief Resets a mmap object
+ *
+ * This resets all entries to NULL.
+ *
+ * @a The new amap object
+ */
+void amap_reset(amap_s* a)
+{
+ for (int i = 0; i < a->num_arrays; ++i) {
+ for (int j = 0; j < AMAP_MAX_ARRAY_LENGTH; ++j) {
+ if (a->data_destroy) {
+ if (a->arrays[i][j]) {
+ a->data_destroy(a->arrays[i][j]);
+ }
+ }
+ a->arrays[i][j] = NULL;
+ }
+ }
+}
+
+int amap_set(amap_s *a, const long position, void* value)
+{
+ if (position >= a->size)
+ return -1;
+ int which_array = position / AMAP_MAX_ARRAY_LENGTH;
+ int array_pos = position % AMAP_MAX_ARRAY_LENGTH;
+ a->arrays[which_array][array_pos] = value;
+ return 0;
+}
+
+void* amap_get(amap_s *a, const long position)
+{
+ if (position >= a->size)
+ return NULL;
+ int which_array = position / AMAP_MAX_ARRAY_LENGTH;
+ int array_pos = position % AMAP_MAX_ARRAY_LENGTH;
+ return a->arrays[which_array][array_pos];
+}
+
+void* amap_unset(amap_s *a, const long position)
+{
+ if (position >= a->size)
+ return NULL;
+ int which_array = position / AMAP_MAX_ARRAY_LENGTH;
+ int array_pos = position % AMAP_MAX_ARRAY_LENGTH;
+ void *value = a->arrays[which_array][array_pos];
+ a->arrays[which_array][array_pos] = NULL;
+ return value;
+}
+
+void amap_run_cb(amap_s *a, void (*cb)(void *data))
+{
+ for (int i = 0; i < a->num_arrays; ++i) {
+ for (int j = 0; j < AMAP_MAX_ARRAY_LENGTH; ++j) {
+ if (a->arrays[i][j])
+ cb(a->arrays[i][j]);
+ }
+ }
+}
+
+void amap_print(amap_s* a)
+{
+ Put("amap_s (%p):", (void*)a);
+ Put("\tmmapped: %d", a->mmapped);
+ Put("\tmax_array_length: %d", AMAP_MAX_ARRAY_LENGTH);
+ Put("\tnum_arrays: %d", a->num_arrays);
+ Put("\tsize: %lu", a->size);
+ Out("\toccupied slots: ");
+ for (int i = 0; i < a->num_arrays; ++i) {
+ for (int j = 0; j < AMAP_MAX_ARRAY_LENGTH; ++j) {
+ if (a->arrays[i][j] != NULL) {
+ Out("%d:%d ", i, j);
+ }
+ }
+ }
+ Out("\n");
+}
+
+void _amap_test(amap_s *a)
+{
+ assert(0 == amap_set(a, 0, (void*)10));
+ assert(0 == amap_set(a, 1, (void*)11));
+ assert(0 == amap_set(a, 2, (void*)12));
+ assert(0 == amap_set(a, 3, (void*)a));
+ assert(10 == (long) amap_get(a, 0));
+ assert(11 == (long) amap_get(a, 1));
+ assert(12 == (long) amap_get(a, 2));
+ assert(a == amap_get(a, 3));
+
+ assert(0 == amap_set(a, AMAP_MAX_ARRAY_LENGTH-1, (void*) 23));
+ assert(23 == (long) amap_get(a, AMAP_MAX_ARRAY_LENGTH-1));
+
+ assert(0 == amap_set(a, AMAP_MAX_ARRAY_LENGTH, (void*) 42));
+ assert(42 == (long) amap_get(a, AMAP_MAX_ARRAY_LENGTH));
+
+ assert(0 == amap_set(a, AMAP_MAX_ARRAY_LENGTH*2-1, (void*) (23+42)));
+ assert(42+23 == (long) amap_get(a, AMAP_MAX_ARRAY_LENGTH*2-1));
+ assert(0 == amap_set(a, AMAP_MAX_ARRAY_LENGTH*2, (void*) 23));
+
+
+ assert(NULL == amap_get(a, 1024*1024*9-1));
+ assert(0 == amap_set(a, 1024*1024*9-1, (void*) 0x1));
+ assert(0x1 == (long) amap_get(a, 1024*1024*9-1));
+ assert(0x1 == (long) amap_unset(a, 1024*1024*9-1));
+ assert(NULL == amap_get(a, 1024*1024*9-1));
+
+ assert(0 == amap_set(a, 1024*1024*9, (void*) 100));
+ assert(100 == (long) amap_get(a, 1024*1024*9));
+
+ assert(0 == amap_set(a, 1024*1024*9+1, (void*) 101));
+ assert(101 == (long) amap_get(a, 1024*1024*9+1));
+
+ assert(0 == amap_set(a, 1024*1024*10-2, (void*) 102));
+ assert(102 == (long) amap_get(a, 1024*1024*10-2));
+
+ assert(0 == amap_set(a, 1024*1024*10-1, a));
+ assert(a == amap_get(a, 1024*1024*10-1));
+ //amap_print(a);
+
+ assert(a == amap_unset(a, 1024*1024*10-1));
+ assert(a != amap_unset(a, 1024*1024*10-1));
+ //amap_print(a);
+}
+
+void amap_test(void)
+{
+ // First test the non-mmapped version
+ amap_s* a = amap_new(1024*1024*10);
+ _amap_test(a);
+ amap_destroy(a);
+
+ // Now test the mapped version
+ a = amap_new_mmapped(1024*1024*10);
+ _amap_test(a);
+ amap_destroy(a);
+
+ // Another test with non-alligned size
+ a = amap_new(1024*1024*10+1);
+ _amap_test(a);
+ amap_destroy(a);
+}
+
diff --git a/ioreplay/src/datas/amap.h b/ioreplay/src/datas/amap.h
new file mode 100644
index 0000000..882a7c5
--- /dev/null
+++ b/ioreplay/src/datas/amap.h
@@ -0,0 +1,49 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef AMAP_H
+#define AMAP_H
+
+#include "../defaults.h"
+
+#define AMAP_MAX_ARRAY_LENGTH 1024*8
+
+/**
+ * @brief Implements an array map data structure
+ *
+ * This array map can hold a HUGE amount of entries by allocating multiple
+ * smaller arrays. There are two version of the amap data structure available:
+ * a memory mapped (mmap) and a normal version. The memory mapped version can
+ * be used for IPC between various processes.
+ */
+typedef struct amap_s_ {
+ void*** arrays; /**< The pointers to the amap arrays */
+ int num_arrays; /**< The amount of arrays used in the amap */
+ long size; /**< The total size/capacity of the amap */
+ bool mmapped; /**< True if amap is memory mapped */
+ void (*data_destroy)(void *data); /**< Callback to destroy all elements */
+} amap_s;
+
+amap_s* amap_new(const long size);
+amap_s* amap_new_mmapped(const long size);
+int amap_set(amap_s *a, const long position, void* value);
+void* amap_get(amap_s *a, const long position);
+void* amap_unset(amap_s *a, const long position);
+void amap_print(amap_s *a);
+void amap_destroy(amap_s *a);
+void amap_reset(amap_s *a);
+void amap_run_cb(amap_s *a, void (*cb)(void *data));
+void amap_test(void);
+
+#endif // AMAP_H
diff --git a/ioreplay/src/datas/btree.c b/ioreplay/src/datas/btree.c
new file mode 100644
index 0000000..da5da48
--- /dev/null
+++ b/ioreplay/src/datas/btree.c
@@ -0,0 +1,169 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "btree.h"
+
+btree_s* btree_new()
+{
+ btree_s *b = Malloc(btree_s);
+ *b = (btree_s) {
+ .root = NULL, .size = 0
+ };
+ return b;
+}
+
+void btree_destroy(btree_s* b)
+{
+ if (b->root)
+ btreelem_destroy_r(b->root);
+ free(b);
+}
+
+void btree_destroy2(btree_s* b)
+{
+ if (b->root)
+ btreelem_destroy_r2(b->root);
+ free(b);
+}
+
+int btree_insert(btree_s* b, int key, void *data)
+{
+ int ret = 1;
+
+ if (b->root == NULL) {
+ b->root = btreelem_new(key, data);
+ ret = 0;
+ } else {
+ ret = btreelem_insert_r(b->root, key, data);
+ }
+
+ if (ret == 0) {
+ b->size++;
+ }
+
+ return ret;
+}
+
+void* btree_get(btree_s* b, int key)
+{
+ if (b->root == NULL)
+ return NULL;
+
+ return btreelem_get_r(b->root, key);
+}
+
+void btree_print(btree_s* b)
+{
+ btreelem_print_r(b->root, 0);
+}
+
+btreelem_s* btreelem_new(int key, void *data)
+{
+ btreelem_s *e = Malloc(btreelem_s);
+ *e = (btreelem_s) {
+ .key = key, .data = data, .left = NULL, .right = NULL
+ };
+ return e;
+}
+
+void btreelem_destroy_r(btreelem_s* e)
+{
+ if (e->left) {
+ btreelem_destroy_r(e->left);
+ }
+ if (e->right) {
+ btreelem_destroy_r(e->right);
+ }
+
+ free(e);
+}
+
+void btreelem_destroy_r2(btreelem_s* e)
+{
+ if (e->left)
+ btreelem_destroy_r(e->left);
+ if (e->right)
+ btreelem_destroy_r(e->right);
+ if (e->data)
+ btree_destroy(e->data);
+
+ free(e);
+}
+
+int btreelem_insert_r(btreelem_s* e, int key, void *data)
+{
+ int ret = 0;
+
+ if (e->key == key) {
+ ret = 1;
+ }
+
+ else if (e->key > key) {
+ if (e->left == NULL) {
+ e->left = btreelem_new(key, data);
+ } else {
+ ret = btreelem_insert_r(e->left, key, data);
+ }
+ }
+
+ else {
+ if (e->right == NULL) {
+ e->right = btreelem_new(key, data);
+ } else {
+ ret = btreelem_insert_r(e->right, key, data);
+ }
+ }
+
+ return ret;
+}
+
+void* btreelem_get_r(btreelem_s* e, int key)
+{
+ void *data = NULL;
+
+ if (e->key == key) {
+ data = e->data;
+ }
+
+ else if (e->key > key) {
+ if (e->left) {
+ data = btreelem_get_r(e->left, key);
+ }
+ }
+
+ else {
+ if (e->right) {
+ data = btreelem_get_r(e->right, key);
+ }
+ }
+
+ return data;
+}
+
+void btreelem_print_r(btreelem_s* e, int depth)
+{
+ for (int i = 0; i < depth; ++i) {
+ Out(" ");
+ }
+ Put("%d\n", e->key);
+
+ if (e->left) {
+ btreelem_print_r(e->left, depth);
+ }
+
+ if (e->right) {
+ btreelem_print_r(e->right, depth+1);
+ }
+}
+
diff --git a/ioreplay/src/datas/btree.h b/ioreplay/src/datas/btree.h
new file mode 100644
index 0000000..55da560
--- /dev/null
+++ b/ioreplay/src/datas/btree.h
@@ -0,0 +1,52 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef BTREE_H
+#define BTREE_H
+
+#include "../defaults.h"
+
+/**
+ * @brief This defines an element of the binary tree data structure
+ */
+typedef struct btreelem_ {
+ struct btreelem_ *left; /**< The next element to the left */
+ struct btreelem_ *right; /**< The next element to the right */
+ int key; /**< The key of the element */
+ void *data; /**< A pointer to the data stored in this element */
+} btreelem_s;
+
+/**
+ * @brief This defines a binary tree data structure.
+ */
+typedef struct btree_s_ {
+ btreelem_s *root; /**< The root element */
+ int size; /**< The current size of the binary tree */
+} btree_s;
+
+btree_s* btree_new();
+void btree_destroy(btree_s *b);
+void btree_destroy2(btree_s *b);
+int btree_insert(btree_s *b, int key, void *data);
+void* btree_get(btree_s *b, int key);
+void btree_print(btree_s *b);
+
+btreelem_s* btreelem_new(int key, void *data);
+void btreelem_destroy_r(btreelem_s *e);
+void btreelem_destroy_r2(btreelem_s *e);
+int btreelem_insert_r(btreelem_s *e, int key, void *data);
+void* btreelem_get_r(btreelem_s *e, int key);
+void btreelem_print_r(btreelem_s *e, int depth);
+
+#endif // BTREE_H
diff --git a/ioreplay/src/datas/hmap.c b/ioreplay/src/datas/hmap.c
new file mode 100644
index 0000000..d0e1d70
--- /dev/null
+++ b/ioreplay/src/datas/hmap.c
@@ -0,0 +1,364 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "hmap.h"
+
+#define _Using_string_keys h->keys != NULL
+
+unsigned int hmap_get_addr(hmap_s *h, char *key)
+{
+ unsigned long hash = 5381;
+ int len = strlen(key);
+
+ for (int i = 0; i < len; ++i) {
+ hash = ((hash << 5) + hash) + key[i]; /* hash * 33 + c */
+ }
+
+ return (unsigned int) (hash % h->size);
+}
+
+unsigned int hmap_get_addr_l(hmap_s *h, const long key)
+{
+ return (unsigned int) (key % h->size);
+}
+
+hmap_s *_hmap_new(unsigned int init_size)
+{
+ hmap_s *h = Malloc(hmap_s);
+
+ h->size = init_size;
+ h->data = Calloc(init_size, void*);
+ h->l = Calloc(init_size, list_s*);
+ h->data_destroy = NULL;
+ h->keys = NULL;
+ h->keys_l = NULL;
+
+ Mset(h->data, 0, init_size, void*);
+ Mset(h->l, 0, init_size, list_s*);
+
+ return h;
+}
+
+hmap_s *hmap_new(unsigned int init_size)
+{
+ hmap_s *h = _hmap_new(init_size);
+ h->keys = Calloc(init_size, char*);
+ Mset(h->keys, 0, init_size, char*);
+
+ return h;
+}
+
+hmap_s *hmap_new_l(unsigned int init_size)
+{
+ hmap_s *h = _hmap_new(init_size);
+ h->keys_l = Calloc(init_size, int);
+ Mset(h->keys_l, -1, init_size, int);
+
+ return h;
+}
+
+void hmap_destroy(hmap_s *h)
+{
+ for (int i = 0; i < h->size; ++i) {
+ if (h->l[i]) {
+ list_s *l = h->l[i];
+ if (h->data_destroy)
+ l->data_destroy = h->data_destroy;
+ list_destroy(h->l[i]);
+ }
+ if (h->data[i] && h->data_destroy) {
+ h->data_destroy(h->data[i]);
+ }
+ }
+
+ free(h->data);
+ if (h->keys)
+ free(h->keys);
+ if (h->keys_l)
+ free(h->keys_l);
+ free(h->l);
+ free(h);
+
+ return;
+}
+
+int hmap_insert(hmap_s *h, char *key, void *data)
+{
+ if (data == NULL) {
+ Error("insert data can not be NULL");
+ }
+
+ int addr = hmap_get_addr(h, key);
+
+ if (h->data[addr]) {
+
+ if (strcmp(key, h->keys[addr]) == 0) {
+ // Key already exists
+ return 0;
+ }
+
+ // There is already data, collision, create a linked list
+ list_s *l = h->l[addr] = list_new();
+ list_key_insert(l, h->keys[addr], h->data[addr]);
+ list_key_insert(l, key, data);
+
+ // Not needed anymore, as the elements are in the linked list now.
+ free(h->keys[addr]);
+ h->data[addr] = h->keys[addr] = NULL;
+
+ return 1;
+
+ } else if (h->l[addr]) {
+ // There was a collision at this address before. Insert
+ // the element to the linked list. Returns 0 if key is already
+ // in the list (no additional insert made) or 1 otherwise.
+ return list_key_insert(h->l[addr], key, data);
+ }
+
+ // New entry on a collision free address
+ h->data[addr] = data;
+ h->keys[addr] = Clone(key);
+
+ return 1;
+}
+
+int hmap_insert_l(hmap_s *h, const long key, void *data)
+{
+ if (data == NULL) {
+ Error("insert data can not be NULL");
+ }
+
+ int addr = hmap_get_addr_l(h, key);
+
+ if (h->data[addr]) {
+
+ if (key == h->keys_l[addr]) {
+ // Key already exists
+ return 0;
+ }
+
+ // There is already data, collision, create a linked list
+ list_s *l = h->l[addr] = list_new_l();
+ list_key_insert_l(l, h->keys_l[addr], h->data[addr]);
+ list_key_insert_l(l, key, data);
+
+ // Not needed anymore, as the elements are in the linked list now.
+ h->data[addr] = NULL;
+ h->keys_l[addr] = -1;
+
+ return 1;
+
+ } else if (h->l[addr]) {
+ // There was a collision at this address before. Insert
+ // the element to the linked list. Returns 0 if key is already
+ // in the list (no additional insert made) or 1 otherwise.
+ return list_key_insert_l(h->l[addr], key, data);
+ }
+
+ // New entry on a collision free address
+ h->data[addr] = data;
+ h->keys_l[addr] = key;
+
+ return 1;
+}
+
+void* hmap_remove(hmap_s *h, char *key)
+{
+ int addr = hmap_get_addr(h, key);
+
+ if (h->data[addr] != NULL) {
+ void *data = h->data[addr];
+ free(h->keys[addr]);
+ h->data[addr] = h->keys[addr] = NULL;
+ return data;
+
+ } else if (h->l[addr] != NULL) {
+ // There was a collision at this address before. Remove
+ // the element to the linked list. Returns the object if key is
+ // already in the list (no additional insert made) or NULL
+ // otherwise.
+ return list_key_remove(h->l[addr], key);
+ }
+
+ // Key is not present
+ return NULL;
+}
+
+void* hmap_remove_l(hmap_s *h, const long key)
+{
+ int addr = hmap_get_addr_l(h, key);
+
+ if (h->data[addr] != NULL) {
+ void *data = h->data[addr];
+ h->data[addr] = NULL;
+ h->keys_l[addr] = -1;
+ return data;
+
+ } else if (h->l[addr] != NULL) {
+ // There was a collision at this address before. Remove
+ // the element to the linked list. Returns the object if key is
+ // already in the list (no additional insert made) or NULL
+ // otherwise.
+ return list_key_remove_l(h->l[addr], key);
+ }
+
+ // Key is not present
+ return NULL;
+}
+
+void* hmap_get(hmap_s *h, char *key)
+{
+ int addr = hmap_get_addr(h, key);
+ if (h->data[addr] && strcmp(h->keys[addr], key) == 0) {
+ return h->data[addr];
+
+ } else if (h->l[addr]) {
+ return list_key_get(h->l[addr], key);
+ }
+
+ return NULL;
+}
+
+void* hmap_get_l(hmap_s *h, const long key)
+{
+ int addr = hmap_get_addr_l(h, key);
+ if (h->data[addr] && h->keys_l[addr] == key) {
+ return h->data[addr];
+
+ } else if (h->l[addr]) {
+ return list_key_get_l(h->l[addr], key);
+ }
+
+ return NULL;
+}
+
+void hmap_run_cb(hmap_s* h, void (*cb)(void *data))
+{
+ for (int i = 0; i < h->size; ++i) {
+ if (h->l[i]) {
+ list_s *l = h->l[i];
+ list_run_cb(l, cb);
+ }
+ if (h->data[i]) {
+ cb(h->data[i]);
+ }
+ }
+}
+
+void hmap_run_cb2(hmap_s* h, void (*cb)(void *data, void *data2), void *data_)
+{
+ for (int i = 0; i < h->size; ++i) {
+ if (h->l[i]) {
+ list_s *l = h->l[i];
+ list_run_cb2(l, cb, data_);
+ }
+ if (h->data[i]) {
+ cb(h->data[i], data_);
+ }
+ }
+}
+
+void hmap_print(hmap_s *h)
+{
+ for (int i = 0; i < h->size; ++i) {
+ if (h->data[i]) {
+ if (_Using_string_keys) {
+ Put("hmap:%p addr:%d key:'%s'", (void*)h, i, h->keys[i]);
+ } else {
+ Put("hmap:%p addr:%d key:%d", (void*)h, i, h->keys_l[i]);
+ }
+ } else if (h->l[i]) {
+ Put("hmap:%p addr:%d LIST", (void*)h, i);
+ list_print(h->l[i]);
+ }
+ }
+}
+
+static void _hmap_test(hmap_s *h)
+{
+ void* somedata = (void*)h;
+
+ assert(1 == hmap_insert(h, "someval", (void*)23));
+ assert(1 == hmap_insert(h, "another value", (void*)123));
+
+ assert(1 == hmap_insert(h, "mimecast", somedata));
+ assert(0 == hmap_insert(h, "mimecast", somedata));
+ assert(1 == hmap_insert(h, "is", somedata));
+ assert(1 == hmap_insert(h, "hiring", somedata));
+
+ assert(NULL != hmap_get(h, "mimecast"));
+ assert(NULL == hmap_get(h, "Mimecast"));
+
+ assert(NULL != hmap_remove(h, "mimecast"));
+ assert(NULL == hmap_remove(h, "mimecast"));
+
+ assert(1 == hmap_insert(h, "mimecast", somedata));
+ assert(NULL != hmap_get(h, "mimecast"));
+
+ assert(23 == (long)hmap_get(h, "someval"));
+ assert(23 == (long)hmap_get(h, "someval"));
+
+ assert(123 == (long)hmap_remove(h, "another value"));
+ assert(0 == (long)hmap_remove(h, "another value"));
+ assert(NULL == hmap_get(h, "another value"));
+
+ //hmap_print(h);
+}
+
+static void _hmap_test_l(hmap_s *h)
+{
+ void* somedata = (void*)h;
+
+ assert(1 == hmap_insert_l(h, 1, (void*)23));
+
+ assert(1 == hmap_insert_l(h, 1, (void*)23));
+ assert(1 == hmap_insert_l(h, 5, (void*)123));
+
+ assert(1 == hmap_insert_l(h, 3, somedata));
+ assert(0 == hmap_insert_l(h, 3, somedata));
+ assert(1 == hmap_insert_l(h, 4, somedata));
+ assert(1 == hmap_insert_l(h, 6, somedata));
+
+ assert(NULL != hmap_get_l(h, 3));
+ assert(NULL == hmap_get_l(h, 7));
+
+ assert(NULL != hmap_remove_l(h, 3));
+ assert(NULL == hmap_remove_l(h, 3));
+
+ assert(1 == hmap_insert_l(h, 3, somedata));
+ assert(NULL != hmap_get_l(h, 3));
+
+ assert(23 == (long)hmap_get_l(h, 1));
+ assert(23 == (long)hmap_get_l(h, 1));
+
+ assert(123 == (long)hmap_remove_l(h, 5));
+ assert(0 == (long)hmap_remove_l(h, 5));
+ assert(NULL == hmap_get_l(h, 5));
+}
+
+void hmap_test(void)
+{
+ hmap_s* h = hmap_new(1024);
+ _hmap_test(h);
+ hmap_destroy(h);
+
+ h = hmap_new(2);
+ _hmap_test(h);
+ hmap_destroy(h);
+
+ h = hmap_new_l(1024);
+ _hmap_test_l(h);
+ hmap_print(h);
+ hmap_destroy(h);
+}
diff --git a/ioreplay/src/datas/hmap.h b/ioreplay/src/datas/hmap.h
new file mode 100644
index 0000000..9d1978b
--- /dev/null
+++ b/ioreplay/src/datas/hmap.h
@@ -0,0 +1,56 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef HMAP_H
+#define HMAP_H
+
+#include "../defaults.h"
+#include "list.h"
+
+/**
+ * @brief A hash map data structure
+ *
+ * There are two version of this hmap data structure. One version is utilising
+ * string keys and the other one is utilising long keys.
+ *
+ * On hash collision the data structure will make use of a "named" linked list,
+ * whereas every member of the linked list has either a string key or a long
+ * key associated.
+ */
+typedef struct hmap_s_ {
+ char **keys; /**< List of all keys, NULL if nothing at a address */
+ int *keys_l; /**< Same as keys, but for long keys */
+ void **data; /**< Pointers to the stored data, NULL if nothing there */
+ list_s **l; /**< Pointers to the linked lists, used on hash collision */
+ void (*data_destroy)(void *data); /**< Callback to destroy all data */
+ unsigned int size; /**< Size of the hmap */
+} hmap_s;
+
+hmap_s* hmap_new(unsigned int init_size);
+hmap_s* hmap_new_l(unsigned int init_size);
+void hmap_destroy(hmap_s* h);
+void hmap_run_cb(hmap_s* h, void (*cb)(void *data));
+void hmap_run_cb2(hmap_s* h, void (*cb)(void *data, void *data2), void *data_);
+int hmap_insert_l(hmap_s* h, const long key, void *data);
+int hmap_insert(hmap_s* h, char* key, void *data);
+void* hmap_remove_l(hmap_s* h, const long key);
+void* hmap_remove(hmap_s* h, char* key);
+void* hmap_get_l(hmap_s* h, const long key);
+void* hmap_get(hmap_s* h, char* key);
+unsigned int hmap_get_addr_l(hmap_s* h, const long key);
+unsigned int hmap_get_addr(hmap_s* h, char* key);
+void hmap_print(hmap_s* h);
+void hmap_test(void);
+
+#endif // HMAP_H
diff --git a/ioreplay/src/datas/list.c b/ioreplay/src/datas/list.c
new file mode 100644
index 0000000..9cc78db
--- /dev/null
+++ b/ioreplay/src/datas/list.c
@@ -0,0 +1,279 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "list.h"
+
+
+list_s *list_new()
+{
+ list_s *l = Malloc(list_s);
+ *l = (list_s) {
+ .first = NULL, .data_destroy = NULL
+ };
+ return l;
+}
+
+list_s *list_new_l()
+{
+ return list_new();
+}
+
+void list_destroy(list_s *l)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (current->key)
+ free(current->key);
+ if (current->data && l->data_destroy)
+ l->data_destroy(current->data);
+ list_elem_s *next = current->next;
+ free(current);
+ current = next;
+ }
+
+ free(l);
+}
+
+int list_key_insert(list_s *l, char *key, void *data)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ // Already in the list
+ if (strcmp(current->key, key) == 0)
+ return 0;
+ current = current->next;
+ }
+
+ list_elem_s *e = Malloc(list_elem_s);
+
+ e->prev = NULL;
+ e->next = l->first;
+ e->key = Clone(key);
+ e->key_l = -1;
+ e->data = data;
+
+ if (l->first) {
+ l->first->prev = e;
+ l->first = e;
+
+ } else {
+ l->first = e;
+ }
+
+ return 1;
+}
+
+int list_key_insert_l(list_s *l, const long key, void *data)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (current->key_l == key)
+ return 0;
+ current = current->next;
+ }
+
+ list_elem_s *e = Malloc(list_elem_s);
+
+ e->prev = NULL;
+ e->next = l->first;
+ e->key = NULL;
+ e->key_l = key;
+ e->data = data;
+
+ if (l->first) {
+ l->first->prev = e;
+ l->first = e;
+
+ } else {
+ l->first = e;
+ }
+
+ return 1;
+}
+
+void _list_elem_remove(list_s *l, list_elem_s *e)
+{
+ if (l->first == e) {
+ list_elem_s *first = e->next;
+ if (first)
+ first->prev = NULL;
+ l->first = first;
+
+ } else {
+ list_elem_s *prev = e->prev;
+ list_elem_s *next = e->next;
+
+ prev->next = next;
+ if (next)
+ next->prev = prev;
+ }
+
+ if (e->key)
+ free(e->key);
+ free(e);
+}
+
+void* list_key_remove(list_s *l, char *key)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (strcmp(current->key, key) == 0) {
+ void *data = current->data;
+ _list_elem_remove(l, current);
+ return data;
+ }
+ current = current->next;
+ }
+
+ return NULL;
+}
+
+void* list_key_remove_l(list_s *l, const long key)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (current->key_l == key) {
+ void *data = current->data;
+ _list_elem_remove(l, current);
+ return data;
+ }
+ current = current->next;
+ }
+
+ return NULL;
+}
+
+void* list_key_get(list_s *l, char *key)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (strcmp(current->key, key) == 0)
+ return current->data;
+ current = current->next;
+ }
+
+ return NULL;
+}
+
+void* list_key_get_l(list_s *l, const long key)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (current->key_l == key)
+ return current->data;
+ current = current->next;
+ }
+
+ return NULL;
+}
+
+void list_run_cb(list_s* l, void (*cb)(void *data))
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (current->data)
+ cb(current->data);
+ current = current->next;
+ }
+}
+
+void list_run_cb2(list_s* l, void (*cb)(void *data, void *data2), void *data_)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (current->data)
+ cb(current->data, data_);
+ current = current->next;
+ }
+}
+
+void list_print(list_s *l)
+{
+ list_elem_s *current = l->first;
+
+ while (current) {
+ if (current->key != NULL) {
+ Put("list:%p key:'%s' data:%p", (void*)l,
+ current->key, current->data);
+ } else {
+ Put("list:%p key:%ld data:%p", (void*)l,
+ current->key_l, current->data);
+ }
+ current = current->next;
+ }
+}
+
+void list_test(void)
+{
+ list_s *l = list_new();
+ void* somedata = (void*)l;
+
+ assert(1 == list_key_insert(l, "foo", (void*)1));
+ assert(1 == list_key_insert(l, "bar", (void*)2));
+ assert(1 == list_key_insert(l, "baz", (void*)3));
+ assert(2 == (long)list_key_remove(l, "bar"));
+ assert(1 == (long)list_key_remove(l, "foo"));
+ assert(3 == (long)list_key_remove(l, "baz"));
+
+ assert(1 == list_key_insert(l, "I/O replay", somedata));
+ assert(1 == list_key_insert(l, "for", somedata));
+ assert(1 == list_key_insert(l, "benchmarking your server", somedata));
+ assert(0 == list_key_insert(l, "for", somedata));
+
+ assert(NULL != list_key_get(l, "benchmarking your server"));
+ assert(NULL == list_key_get(l, "Mimecast"));
+
+ assert(NULL != list_key_remove(l, "benchmarking your server"));
+ assert(NULL == list_key_remove(l, "benchmarking your server"));
+ assert(1 == list_key_insert(l, "benchmarking your server", somedata));
+
+ assert(1 == list_key_insert(l, "MiMecast", (void*)42));
+ assert(42 == (long)list_key_get(l, "MiMecast"));
+
+ l = list_new_l();
+
+ assert(1 == list_key_insert_l(l, 1, (void*)1));
+ assert(1 == list_key_insert_l(l, 2, (void*)2));
+ assert(1 == list_key_insert_l(l, 3, (void*)3));
+ assert(1 == (long)list_key_get_l(l, 1));
+ assert(1 == (long)list_key_remove_l(l, 1));
+ assert(1 != (long)list_key_remove_l(l, 1));
+ assert(3 == (long)list_key_remove_l(l, 3));
+
+ assert(1 == list_key_insert_l(l, 1234, somedata));
+ assert(1 == list_key_insert_l(l, 13, somedata));
+ assert(1 == list_key_insert_l(l, 666, somedata));
+ assert(0 == list_key_insert_l(l, 13, somedata));
+
+ assert(NULL != list_key_get_l(l, 666));
+ assert(NULL == list_key_get_l(l, 777));
+
+ assert(NULL != list_key_remove_l(l, 666));
+ assert(NULL == list_key_remove_l(l, 666));
+ assert(1 == list_key_insert_l(l, 666, somedata));
+
+ assert(1 == list_key_insert_l(l, 42, (void*)42));
+ assert(42 == (long)list_key_get_l(l, 42));
+
+ //list_print(l);
+}
diff --git a/ioreplay/src/datas/list.h b/ioreplay/src/datas/list.h
new file mode 100644
index 0000000..385333c
--- /dev/null
+++ b/ioreplay/src/datas/list.h
@@ -0,0 +1,56 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef LIST_H
+#define LIST_H
+
+#include "../defaults.h"
+
+/**
+ * @brief Definition of a linked list element
+ */
+typedef struct list_elem_s_ {
+ struct list_elem_s_ *prev; /**< The previous element */
+ struct list_elem_s_ *next; /**< The next element */
+ char *key; /**< The key of the lemenet */
+ long key_l; /**< The same as key, but for long keys */
+ void *data; /**< Pointer to the stored data */
+} list_elem_s;
+
+/**
+ * @brief Definition of a named linked list data structure
+ *
+ * There are two version of this list data structure. One version is utilising
+ * string keys and the other one is utilising long keys.
+ */
+typedef struct list_s_ {
+ list_elem_s *first; /**< The first element, NULL if list empty */
+ void (*data_destroy)(void *data); /**< Callback to destroy all data */
+} list_s;
+
+list_s* list_new();
+list_s* list_new_l();
+void list_destroy(list_s* l);
+void list_run_cb(list_s* l, void (*cb)(void *data));
+void list_run_cb2(list_s* l, void (*cb)(void *data, void *data2), void *data_);
+int list_key_insert(list_s* l, char *key, void *data);
+int list_key_insert_l(list_s* l, const long key, void *data);
+void* list_key_remove(list_s* l, char *key);
+void* list_key_remove_l(list_s* l, const long key);
+void* list_key_get(list_s* l, char *key);
+void* list_key_get_l(list_s* l, const long key);
+void list_print(list_s* l);
+void list_test();
+
+#endif // LIST_H
diff --git a/ioreplay/src/datas/rbuffer.c b/ioreplay/src/datas/rbuffer.c
new file mode 100644
index 0000000..c019e6c
--- /dev/null
+++ b/ioreplay/src/datas/rbuffer.c
@@ -0,0 +1,147 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "rbuffer.h"
+
+rbuffer_s *rbuffer_new(const int size)
+{
+ rbuffer_s *r = Malloc(rbuffer_s);
+
+ r->size = size;
+ r->read_pos = size-1;
+ r->write_pos = 0;
+ r->ring = Calloc(size, void*);
+
+ Mset(r->ring, 0, size, void*);
+
+ return r;
+}
+
+void rbuffer_destroy(rbuffer_s *r)
+{
+ if (r) {
+ free(r->ring);
+ free(r);
+ }
+}
+
+bool rbuffer_insert(rbuffer_s* r, void *data)
+{
+ if (r->write_pos == r->read_pos)
+ // Ring buffer is full
+ return false;
+
+ r->ring[r->write_pos] = data;
+ r->write_pos = (r->write_pos+1) % r->size;
+
+ return true;
+}
+
+bool rbuffer_has_next(rbuffer_s* r)
+{
+ sig_atomic_t read_pos = (r->read_pos+1) % r->size;
+
+ if (read_pos == r->write_pos)
+ // No more items to read, buffer is empty
+ {
+ return false;
+ }
+
+ return true;
+}
+
+void* rbuffer_get_next(rbuffer_s* r)
+{
+ sig_atomic_t read_pos = (r->read_pos+1) % r->size;
+
+ if (read_pos == r->write_pos)
+ // No more items to read, buffer is empty
+ {
+ return NULL;
+ }
+
+ void *data = r->ring[read_pos];
+ r->ring[read_pos] = NULL;
+ r->read_pos = read_pos;
+
+ return data;
+}
+
+void rbuffer_print(rbuffer_s* r)
+{
+ Put("rbuffer_s (%p):", (void*)r);
+ Put("\tsize: %d", (int)r->size);
+ Put("\tread_pos: %d", r->read_pos);
+ Put("\twrite_pos: %d", r->write_pos);
+ Out("\toccupied slots: ");
+ for (int i = 0; i < r->size; ++i)
+ if (r->ring[i]) {
+ Out("%d:%p ", i, r->ring[i]);
+ }
+ Out("\n");
+}
+
+void rbuffer_test(void)
+{
+ rbuffer_s *r = rbuffer_new(5);
+ assert(NULL == rbuffer_get_next(r));
+
+ assert(rbuffer_insert(r, (void*)1));
+ assert(rbuffer_insert(r, (void*)2));
+ assert(rbuffer_insert(r, (void*)3));
+ assert(rbuffer_insert(r, (void*)4));
+ assert(!rbuffer_insert(r, (void*)5));
+ rbuffer_print(r);
+
+ assert(rbuffer_has_next(r));
+ assert(1 == (long) rbuffer_get_next(r));
+ assert(2 == (long) rbuffer_get_next(r));
+ assert(3 == (long) rbuffer_get_next(r));
+ assert(4 == (long) rbuffer_get_next(r));
+ assert(!rbuffer_has_next(r));
+ assert(NULL == rbuffer_get_next(r));
+
+ assert(rbuffer_insert(r, (void*)1));
+ assert(1 == (long) rbuffer_get_next(r));
+ assert(rbuffer_insert(r, (void*)2));
+ assert(2 == (long) rbuffer_get_next(r));
+ assert(rbuffer_insert(r, (void*)3));
+ assert(3 == (long) rbuffer_get_next(r));
+ assert(rbuffer_insert(r, (void*)4));
+ assert(4 == (long) rbuffer_get_next(r));
+ assert(rbuffer_insert(r, (void*)5));
+ assert(5 == (long) rbuffer_get_next(r));
+ assert(NULL == rbuffer_get_next(r));
+ rbuffer_print(r);
+
+ assert(rbuffer_insert(r, (void*)1));
+ rbuffer_print(r);
+ assert(rbuffer_insert(r, (void*)2));
+ assert(1 == (long) rbuffer_get_next(r));
+ rbuffer_print(r);
+ assert(rbuffer_insert(r, (void*)3));
+ assert(2 == (long) rbuffer_get_next(r));
+ rbuffer_print(r);
+ assert(rbuffer_insert(r, (void*)4));
+ assert(3 == (long) rbuffer_get_next(r));
+ rbuffer_print(r);
+ assert(rbuffer_insert(r, (void*)5));
+ rbuffer_print(r);
+ assert(4 == (long) rbuffer_get_next(r));
+ rbuffer_print(r);
+ assert(5 == (long) rbuffer_get_next(r));
+ assert(NULL == rbuffer_get_next(r));
+
+ rbuffer_destroy(r);
+}
diff --git a/ioreplay/src/datas/rbuffer.h b/ioreplay/src/datas/rbuffer.h
new file mode 100644
index 0000000..fa634de
--- /dev/null
+++ b/ioreplay/src/datas/rbuffer.h
@@ -0,0 +1,102 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef RBUFFER_H
+#define RBUFFER_H
+
+#include "signal.h"
+
+#include "../defaults.h"
+
+/**
+ * @brief An atomic ring buffer data type definition
+ *
+ * This data structure can be used for the common producer/consumer problem.
+ * As long as there is only max one producer thread and max one consumer thread
+ * it can be used without any mutex locking. All the operations are atomic.
+ */
+typedef struct rbuffer_s_ {
+ /**
+ * The positions are atomic, means the ring buffer can be accessed from
+ * multiple threads concurrently (one producer and one consumer thread).
+ * This is the current read position.
+ */
+ sig_atomic_t read_pos;
+ /**
+ * This is the current write position.
+ */
+ sig_atomic_t write_pos;
+ /**
+ * Holds the pointers to the actual ring data stored in the ring buffer
+ */
+ void **ring;
+ /**
+ * Determines how many elements the ring buffer can hold. The capacity
+ * will be size-1 though, as we need one empty slot.
+ */
+ int size;
+} rbuffer_s;
+
+/**
+ * @brief Creates a new ring buffer
+ *
+ * @param size The size of the ring buffer
+ * @return The new ring buffer object
+ */
+rbuffer_s* rbuffer_new(const int size);
+
+/**
+ * @brief Destroys a ring buffer
+ *
+ * @param r The ring buffer object
+ */
+void rbuffer_destroy(rbuffer_s* r);
+
+/**
+ * @brief Inserts data pointer to the ring buffer
+ *
+ * @param r The ring buffer object
+ * @param data The data pointer
+ */
+bool rbuffer_insert(rbuffer_s* r, void *data);
+
+/**
+ * @brief Determines whether there is any data in the ring buffer
+ *
+ * @param r The ring buffer object
+ * @return True if there is any data, false otherwise
+ */
+bool rbuffer_has_next(rbuffer_s* r);
+
+/**
+ * @brief Returns and removes the next element from the ring buffer
+ *
+ * @param r The ring buffer object
+ * @return The data pointer
+ */
+void* rbuffer_get_next(rbuffer_s* r);
+
+/**
+ * @brief Prints a ring buffer
+ *
+ * @param r The ring buffer object
+ */
+void rbuffer_print(rbuffer_s* r);
+
+/**
+ * @brief Unit tests the ring buffer
+ */
+void rbuffer_test(void);
+
+#endif // RBUFFER_H
diff --git a/ioreplay/src/datas/stack.c b/ioreplay/src/datas/stack.c
new file mode 100644
index 0000000..94e83e3
--- /dev/null
+++ b/ioreplay/src/datas/stack.c
@@ -0,0 +1,85 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "stack.h"
+
+
+stack_s *stack_new()
+{
+ stack_s *s = Malloc(stack_s);
+ *s = (stack_s) {
+ .top = NULL, .size = 0
+ };
+ return s;
+}
+
+void stack_destroy(stack_s *s)
+{
+ stack_elem_s *current = s->top;
+
+ while (current) {
+ stack_elem_s *next = current->next;
+ free(current);
+ current = next;
+ }
+
+ free(s);
+}
+
+void stack_push(stack_s *s, void *data)
+{
+ stack_elem_s *new_top = Malloc(stack_elem_s);
+
+ *new_top = (stack_elem_s) {
+ .next = s->top,
+ .data = data
+ };
+
+ s->top = new_top;
+ s->size++;
+}
+
+void* stack_pop(stack_s *s)
+{
+ if (s->top == NULL) {
+ return NULL;
+ }
+
+ stack_elem_s *old_top = s->top;
+
+ void *data = old_top->data;
+ s->top = old_top->next;
+ free(old_top);
+ s->size--;
+
+ return data;
+}
+
+int stack_is_empty(stack_s *s)
+{
+ return s->top == NULL;
+}
+
+stack_s* stack_new_reverse_from(stack_s *s)
+{
+ stack_s* r = stack_new();
+
+ while (!stack_is_empty(s)) {
+ stack_push(r, stack_pop(s));
+ }
+
+ stack_destroy(s);
+
+ return r;
+}
diff --git a/ioreplay/src/datas/stack.h b/ioreplay/src/datas/stack.h
new file mode 100644
index 0000000..87e0974
--- /dev/null
+++ b/ioreplay/src/datas/stack.h
@@ -0,0 +1,43 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef STACK_H
+#define STACK_H
+
+#include "../defaults.h"
+
+/**
+ * @brief Definition of a stack element
+ */
+typedef struct stack_elem_s_ {
+ struct stack_elem_s_ *next; /**< The next element */
+ void *data; /**< Pointer to the stored data in the current element */
+} stack_elem_s;
+
+/**
+ * @brief Definition of a stack data structure
+ */
+typedef struct stack_s_ {
+ stack_elem_s *top; /**< The top element of the stack, NULL if empty */
+ unsigned long size; /**< A count how many elements are in the stack */
+} stack_s;
+
+stack_s* stack_new();
+stack_s* stack_new_reverse_from(stack_s* s);
+void stack_destroy(stack_s* s);
+void stack_push(stack_s* s, void *data);
+void* stack_pop(stack_s* s);
+int stack_is_empty(stack_s* s);
+
+#endif // STACK_H
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-17 19:01:07 +0000