can use btree to store file data ranges for file hole support

6 files changed, 176 insertions, 57 deletions

diff --git a/ioriot/src/datas/btree.c b/ioriot/src/datas/btree.c
index b150066..90cb889 100644
--- a/ioriot/src/datas/btree.c
+++ b/ioriot/src/datas/btree.c
@@ -37,7 +37,7 @@ void btree_destroy2(btree_s* b)
     free(b);
 }
 
-int btree_insert(btree_s* b, int key, void *data)
+int btree_insert(btree_s* b, long key, void *data)
 {
     int ret = 0;
 
@@ -48,13 +48,13 @@ int btree_insert(btree_s* b, int key, void *data)
         ret = btreelem_insert_r(b->root, key, data);
     }
 
-    if (ret == 0)
+    if (ret == 1)
         b->size++;
 
     return ret;
 }
 
-void* btree_get(btree_s* b, int key)
+void* btree_get(btree_s* b, long key)
 {
     if (b->root == NULL)
         return NULL;
@@ -62,9 +62,29 @@ void* btree_get(btree_s* b, int key)
     return btreelem_get_r(b->root, key);
 }
 
+long btree_get_l(btree_s* b, long key)
+{
+    void *data = btree_get(b, key);
+    if (data)
+        return (long)data;
+    else
+        return -1;
+}
+
+void btree_ensure_range_l(btree_s* b, long from, long to)
+{
+    if (b->root == NULL) {
+        btree_insert(b, from, (void*)to);
+    } else {
+        if (1 == btreelem_ensure_range_lr(b->root, from, to))
+            b->size++;
+    }
+}
+
 void btree_print(btree_s* b)
 {
-    btreelem_print_r(b->root, 0);
+    Put("btree:%p size:%d", (void*)b, b->size);
+    btreelem_print_r(b->root, 1);
 }
 
 void btree_run_cb2(btree_s* b, void (*cb)(void *data, void *data2))
@@ -72,7 +92,7 @@ void btree_run_cb2(btree_s* b, void (*cb)(void *data, void *data2))
     btreelem_run_cb2_r(b->root, cb);
 }
 
-btreelem_s* btreelem_new(int key, void *data)
+btreelem_s* btreelem_new(long key, void *data)
 {
     btreelem_s *e = Malloc(btreelem_s);
 
@@ -105,7 +125,7 @@ void btreelem_destroy_r2(btreelem_s* e)
     free(e);
 }
 
-int btreelem_insert_r(btreelem_s* e, int key, void *data)
+int btreelem_insert_r(btreelem_s* e, long key, void *data)
 {
     int ret = 1;
 
@@ -130,19 +150,58 @@ int btreelem_insert_r(btreelem_s* e, int key, void *data)
     return ret;
 }
 
-void* btreelem_get_r(btreelem_s* e, int key)
+int btreelem_ensure_range_lr(btreelem_s *e, const long from, const long to)
+{
+    int ret = 0;
+    long value = (long) e->data;
+
+    if (e->key == from) {
+        if (value < to) {
+            e->data = (void*) to;
+        } else {
+            // Nothing to do, range already present
+        }
+
+    } else if (e->key > from) {
+        if (e->left == NULL) {
+            e->left = btreelem_new(from, (void*)to);
+            ret = 1;
+        } else {
+            ret = btreelem_ensure_range_lr(e->left, from, to);
+        }
+
+    } else { // if (e->key < from)
+        if (value >= from) {
+            if (value < to) {
+                e->data = (void*) to;
+            } else {
+                // Nothing to do, range already present
+            }
+        } else {
+            if (e->right == NULL) {
+                e->right = btreelem_new(from, (void*)to);
+                ret = 1;
+            } else {
+                ret = btreelem_ensure_range_lr(e->right, from, to);
+            }
+        }
+    }
+
+    return ret;
+}
+
+void* btreelem_get_r(btreelem_s* e, long key)
 {
     void *data = NULL;
 
-    if (e->key == key)
+    if (e->key == key) {
         data = e->data;
 
-    else if (e->key > key) {
+    } else if (e->key > key) {
         if (e->left)
             data = btreelem_get_r(e->left, key);
-    }
 
-    else {
+    } else {
         if (e->right)
             data = btreelem_get_r(e->right, key);
     }
@@ -157,7 +216,7 @@ void btreelem_print_r(btreelem_s* e, int depth)
 
     for (int i = 0; i < depth; ++i)
         Out(" ");
-    Put("key:%d data:%ld\n", e->key, (long) e->data);
+    Put("key:%ld data:%ld", e->key, (long) e->data);
 
     if (e->left)
         btreelem_print_r(e->left, depth);
@@ -186,14 +245,21 @@ void btree_test(void)
     void* somedata = (void*)b;
 
     assert(1 == btree_insert(b, 1, (void*)1));
+    assert(1 == b->size);
     assert(1 == btree_insert(b, 2, (void*)2));
+    assert(2 == b->size);
     assert(1 == btree_insert(b, 3, (void*)3));
+    assert(3 == b->size);
     assert(1 == (long)btree_get(b, 1));
 
     assert(1 == btree_insert(b, 1234, somedata));
+    assert(4 == b->size);
     assert(1 == btree_insert(b, 13, somedata));
+    assert(5 == b->size);
     assert(1 == btree_insert(b, 666, somedata));
+    assert(6 == b->size);
     assert(0 == btree_insert(b, 13, somedata));
+    assert(6 == b->size);
 
     assert(NULL != btree_get(b, 666));
     assert(NULL == btree_get(b, 777));
@@ -203,6 +269,35 @@ void btree_test(void)
     assert(42 == (long)btree_get(b, 42));
 
     btree_print(b);
+    btree_destroy(b);
+
+    b = btree_new();
+    assert(0 == b->size);
+
+    btree_ensure_range_l(b, 0, 23);
+    assert(btree_get_l(b, 0) == (long) btree_get(b, 0));
+    assert(23 == btree_get_l(b, 0));
+
+    btree_ensure_range_l(b, 0, 23);
+    btree_ensure_range_l(b, 10, 10);
+    btree_ensure_range_l(b, 22, 25);
+    assert(25 == btree_get_l(b, 0));
+    assert(1 == b->size);
+
+    btree_ensure_range_l(b, 300, 25);
+    assert(2 == b->size);
+
+    btree_ensure_range_l(b, 200, 25);
+    assert(3 == b->size);
+    assert(25 == btree_get_l(b, 200));
+
+    btree_ensure_range_l(b, 200, 1000);
+    assert(3 == b->size);
+    assert(1000 == btree_get_l(b, 200));
+
+    btree_print(b);
 
     btree_destroy(b);
+
+    exit(0);
 }
diff --git a/ioriot/src/datas/btree.h b/ioriot/src/datas/btree.h
index acc5477..a1ca7ef 100644
--- a/ioriot/src/datas/btree.h
+++ b/ioriot/src/datas/btree.h
@@ -23,7 +23,7 @@
 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 */
+    long key; /**< The key of the element */
     void *data; /**< A pointer to the data stored in this element */
 } btreelem_s;
 
@@ -38,17 +38,20 @@ typedef struct 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);
+int btree_insert(btree_s *b, long key, void *data);
+void* btree_get(btree_s *b, long key);
+long btree_get_l(btree_s *b, long key);
+void btree_ensure_range_l(btree_s *b, const long from, const long to);
 void btree_print(btree_s *b);
 void btree_run_cb2(btree_s* b, void (*cb)(void *data, void *data2));
 void btree_test(void);
 
-btreelem_s* btreelem_new(int key, void *data);
+btreelem_s* btreelem_new(long 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);
+int btreelem_insert_r(btreelem_s *e, long key, void *data);
+void* btreelem_get_r(btreelem_s *e, long key);
+int btreelem_ensure_range_lr(btreelem_s *e, const long from, const long to);
 void btreelem_print_r(btreelem_s *e, int depth);
 void btreelem_run_cb2_r(btreelem_s* e, void (*cb)(void *data, void *data2));
 
diff --git a/ioriot/src/generate/generate.c b/ioriot/src/generate/generate.c
index ee7178c..baff401 100644
--- a/ioriot/src/generate/generate.c
+++ b/ioriot/src/generate/generate.c
@@ -196,7 +196,7 @@ void generate_write_init_cb(void *data)
 
     if (l->required && strlen(l->path) > 0) {
         fprintf(g->replay_fd, "%d|%d|%ld|%s|\n",
-                l->is_dir, l->is_file, -l->vsize_deficit, l->path);
+                l->is_dir, l->is_file, 666L, l->path);
     }
 }
 
diff --git a/ioriot/src/generate/gioop.c b/ioriot/src/generate/gioop.c
index 01701bc..df48ef8 100644
--- a/ioriot/src/generate/gioop.c
+++ b/ioriot/src/generate/gioop.c
@@ -27,7 +27,7 @@ status_e gioop_run(gwriter_s *w, gtask_s *t)
     generate_s *g = w->generate;
 
     // Get the virtual process data object from the virtual PID space and store
-    // a pointer to it to t->gprocess
+    // a pointer to it at t->gprocess
     generate_gprocess_by_realpid(g, t);
 
     // One of the open syscalls may openes a file handle succesfully
diff --git a/ioriot/src/generate/vsize.c b/ioriot/src/generate/vsize.c
index f2d56ba..93be77b 100644
--- a/ioriot/src/generate/vsize.c
+++ b/ioriot/src/generate/vsize.c
@@ -35,14 +35,13 @@ vsize_s* vsize_new(char *file_path, const unsigned long id,
     v->inserted = false;
     v->is_dir = false;
     v->is_file = false;
-    v->offset = -1;
     v->path = Clone(file_path);
     v->renamed = false;
     v->required = false;
     v->unsure = false;
     v->updates = 0;
     v->vsize = 0;
-    v->vsize_deficit = 0;
+    v->ranges = NULL;
 
     return v;
 }
@@ -52,6 +51,9 @@ void vsize_destroy(vsize_s *v)
     if (!v)
         return;
 
+    if (v->ranges)
+        btree_destroy(v->ranges);
+
     free(v->path);
     free(v);
 }
@@ -91,9 +93,9 @@ void init_parent_dir(vsize_s *v, const char *path)
 void vsize_open(vsize_s *v, void *vfd, const char *path, const int flags)
 {
 
-    // v->first_encounter == false means, that this is the first occurance of
+    // v->updates == 0 means, that this is the first occurance of
     // this path and we didn't initialise it (means we didn't ensure that
-    // we want to create all parent directories etc.
+    // we want to create all parent directories etc.)
 
     if (v->updates == 0) {
         // We may use a recycled vfd object! When opening a file we always
@@ -161,56 +163,78 @@ void vsize_rename(vsize_s *v, vsize_s *v2,
         // We are not 100% sure that this is really a file,
         // the path might be still a directory though!
         _Set_unsure(v2);
+        v2->updates++;
 
         // For debugging purposes only
         _Set_renamed(v2);
-        v2->updates++;
     }
 }
 
-void vsize_adjust(vsize_s *v, vfd_s* vfd)
+void vsize_ensure_data_range(vsize_s *v, const long from, const long to)
 {
-    if (v->vsize >= vfd->offset)
-        return;
+    if (v->ranges == NULL) {
+        if (from == 0) {
+            if (v->vsize < to) {
+                // No file hole, just set the new (larger) vsize
+                v->vsize = to;
+            } else {
+                // Nothing to do, vsize is already sufficient
+            }
+
+        } else { // if (from > 0)
+            if (from <= v->vsize) {
+                // We won't add a hole to the file here either
+                if (v->vsize < to) {
+                    // No file hole, just set the new (larger) vsize
+                    v->vsize = to;
+                } else {
+                    // Nothing to do, vsize is already sufficient
+                }
+            } else { // if (from > v->vsize)
+                // From offset larger than vsize, we have a hole in the file!
+                v->ranges = btree_new();
+
+                // Insert root data range
+                btree_insert(v->ranges, 0, (void*)v->vsize);
+
+                // This value is not used anymore, we use the btree instead from now
+                // to store all used data ranges of a file.
+                v->vsize = -1;
+
+                // Rerun this function with a data range btree initialised
+                vsize_ensure_data_range(v, from, to);
+            }
+        }
 
-    long deficit = v->vsize - vfd->offset;
-    if (deficit < v->vsize_deficit) {
-        v->vsize_deficit = deficit;
-        _Set_required(v);
-        _Set_file(v);
+    } else { // if (v->ranges != NULL)
+        btree_ensure_range_l(v->ranges, from, to);
     }
 }
 
 void vsize_read(vsize_s *v, void *vfd, const char *path, const int bytes)
 {
     vfd_s *vfd_ = vfd;
+    // We may try to read data from a file with holes!
+    vsize_ensure_data_range(v, vfd_->offset, bytes);
     vfd_->offset += bytes;
-    vsize_adjust(v, vfd_);
     v->updates++;
 }
 
 void vsize_seek(vsize_s *v, void *vfd, const long new_offset)
 {
-    //vfd_s *vfd_ = vfd;
+    vfd_s *vfd_ = vfd;
 
     // The file's offset can be greater than the file's current size, in which
     // case the next write to the file will extend the file. This is referred
-    // to as creating a hole in a file and is allowed. However, this behaviour
-    // does not suit the estimation of the file size before we want to run the
-    // test.
-
-    // TODO: Implement file hole support!
-    //v->updates++;
+    // to as creating a hole in a file.
+    vfd_->offset = new_offset;
+    v->updates++;
 }
 
 void vsize_write(vsize_s *v, void *vfd, const char *path, const int bytes)
 {
     vfd_s *vfd_ = vfd;
     vfd_->offset += bytes;
-
-    if (v->vsize < vfd_->offset)
-        v->vsize = vfd_->offset;
-
     v->updates++;
 }
 
diff --git a/ioriot/src/generate/vsize.h b/ioriot/src/generate/vsize.h
index 8556ec0..d0111fa 100644
--- a/ioriot/src/generate/vsize.h
+++ b/ioriot/src/generate/vsize.h
@@ -16,7 +16,7 @@
 #define VSIZE_H
 
 #include "../utils/utils.h"
-#include "../datas/hmap.h"
+#include "../datas/btree.h"
 #include "../vfd.h"
 
 /**
@@ -30,11 +30,10 @@
  */
 typedef struct vsize_s_ {
     char *path; /**< The path to the file/directory */
-    off_t offset; /**< The current file offset */
+    long vsize; /**< The virtual size */
+    btree_s *ranges; /**< Used to store used data ranges in a file with holes */
     unsigned long id; /**< The vsize id */
     void *generate; /**< A pointer to the generate object */
-    long vsize; /**< The virtual size */
-    long vsize_deficit; /**< Size to use for file creating during init mode */
     bool renamed; /**< True if file/dir has been renamed */
     bool required; /**< True if init mode will create this file/dir */
     bool is_dir; /**< True if this file/dir is a directory */
@@ -72,19 +71,17 @@ void vsize_destroy(vsize_s *v);
 void init_parent_dir(vsize_s *v, const char *path);
 
 /**
- * @brief Adjusts the vsize
+ * @brief Ensure that we have a data range in the virtual file
  *
  * Compares the virtual file size of the file in the vsize
- * object to the the offset in the virtual file descriptor.
- * In case the offset is higher we have a size deficit and
- * we need to mark it. That way ioriot can ensure that
- * during init mode it will create a file with the correct
- * size prior of running the test!
+ * object to the the given offsets. This is required just in case
+ * we have holes in the file to be replayed.
  *
  * @param v The virtual size object
- * @param vfd The virtual file descriptor object
+ * @param from The start offset
+ * @param to The end offset
  */
-void vsize_adjust(vsize_s *v, vfd_s* vfd);
+void vsize_ensure_data_range(vsize_s *v, const long from, const long to);
 
 /**
  * @brief Adjust vsize on open