rsys

commit c67e2216d78d9e723107d5ff7c63ae6075f25812
parent 2f4bf95d429a17f0bc24eb0c1c63754b936ab7f5
Author: vaplv <vaplv@free.fr>
Date:   Wed, 27 Nov 2013 12:57:25 +0100

Finalize a first generic version of the free list container

Diffstat:
M
src/CMakeLists.txt
 | 
4
++++
M
src/free_list.h
 | 
114
++++++++++++++++++++++++++++++++++++++++++++++++++-----------------------------
A
src/test_free_list.c
 | 
68
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 144 insertions(+), 42 deletions(-)
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -57,6 +57,10 @@ add_executable(test_list test_list.c)
 target_link_libraries(test_list rsys)
 add_test(test_list test_list)
 
+add_executable(test_free_list test_free_list.c)
+target_link_libraries(test_free_list rsys)
+add_test(test_free_list test_free_list)
+
 add_executable(test_mem_allocator test_mem_allocator.c)
 target_link_libraries(test_mem_allocator rsys)
 add_test(test_mem_allocator test_mem_allocator)
diff --git a/src/free_list.h b/src/free_list.h
@@ -1,30 +1,42 @@
-#ifndef FREE_LIST_H
-#define FREE_LIST_H
+#ifndef FITEM_TYPE
+# ifndef FREE_LIST_H
+# define FREE_LIST_H
 
-#ifndef FREE_ITEM_TYPE
-  #error Missing arguments
-#endif
+#include "rsys.h"
 
-struct free_id {
+#define FITEM                                                                 \
+  struct {                                                                    \
+    struct fid id;                                                            \
+    uint32_t next;                                                            \
+  } fitem__
+
+struct fid {
   uint32_t index; /* Index into the free list */
   uint32_t name; /* Unique id that identifies this item */
 };
 
-#define FREE_ITEM                                                              \
-  struct {                                                                     \
-    struct free_id id;                                                         \
-    uint32_t next;                                                             \
-  } free_item__
+static const struct fid FID_NULL = { UINT32_MAX, UINT32_MAX };
+#define IS_FID_NULL(Fid) ((Fid).index == UINT32_MAX)
+
+# endif /* FREE_LIST_H */
+#else
+
+#define FLIST_FUNC__(Func) CONCAT(CONCAT(CONCAT(flist_, FITEM_TYPE), _), Func)
+#define FLIST_TYPE__ CONCAT(flist_, FITEM_TYPE)
 
-struct free_list {
+#include "mem_allocator.h"
+#include <stdbool.h>
+#include <string.h>
+
+struct FLIST_TYPE__ {
   uint32_t head;
   uint32_t name_next;
-  FREE_ITEM_TYPE* items;
+  struct FITEM_TYPE* items;
   uint32_t nitems;
 };
 
 static FINLINE void
-free_list_init(struct free_list* list)
+FLIST_FUNC__(init)(struct FLIST_TYPE__* list)
 {
   ASSERT(list);
   list->head = UINT32_MAX;
@@ -33,61 +45,79 @@ free_list_init(struct free_list* list)
   list->nitems = 0;
 }
 
+static FINLINE void
+FLIST_FUNC__(release)(struct FLIST_TYPE__* list)
+{
+  ASSERT(list);
+  MEM_FREE(&mem_default_allocator, list->items);
+}
+
 static FINLINE bool
-free_list_hold(struct free_list* list, struct free_id* id)
+FLIST_FUNC__(hold)(struct FLIST_TYPE__* list, struct fid* id)
 {
   ASSERT(list && id);
-  return list->items[id->index].free_item__.id.name == id->name;
+  return id->index < list->nitems
+      && list->items[id->index].fitem__.id.name == id->name;
 }
 
-static FINLINE FREE_ITEM_TYPE*
-free_list_get(struct free_list* list, struct free_id* id)
+static FINLINE struct FITEM_TYPE*
+FLIST_FUNC__(get)(struct FLIST_TYPE__* list, struct fid* id)
 {
   ASSERT(list && id);
-  if(free_list_hold(list, id)) {
-    return list->mem[id->index];
+  if(FLIST_FUNC__(hold)(list, id)) {
+    return list->items + id->index;
   } else {
     return NULL;
   }
 }
 
-static FINLINE struct free_id
-free_list_add(struct free_list* list)
+static INLINE struct fid
+FLIST_FUNC__(add)(struct FLIST_TYPE__* list)
 {
-  struct free_id id;
+  struct fid id;
   ASSERT(list);
 
-  id.name = list.name_next++;
-  if(list.head != UINT32_MAX) {
-    id.index = list.head;
-    list.head = list.items[list.head].free_item__.next;
+  id.name = list->name_next++;
+  if(list->head != UINT32_MAX) {
+    id.index = list->head;
+    list->items[id.index].fitem__.id = id;
+    list->head = list->items[list->head].fitem__.next;
   } else {
-    const uint32_t nitems_new = nitems ? nitems * 2 : 16;
-    FREE_ITEM_TYPE item;
-    memset(&item, 0, sizeof(FREE_ITEM));
+    const uint32_t nitems_new = list->nitems ? list->nitems * 2 : 16;
+    struct FITEM_TYPE item;
+    memset(&item, 0, sizeof(struct FITEM_TYPE));
 
     id.index = list->nitems;
-    item.free_item__.id = id;
-    list.items = MEM_REALLOC(list.items, nitems_new * sizeof(FREE_ITEM_TYPE));
-    FOR_EACH(uint32_t, iitem, nitems, nitems_new - 1) {
-      list->items[iitem].free_item__.next = iitem + 1;
+    list->items = MEM_REALLOC
+      (&mem_default_allocator,
+       list->items,
+       nitems_new * sizeof(struct FITEM_TYPE));
+    FOR_EACH(uint32_t, iitem, list->nitems, nitems_new - 1) {
+      list->items[iitem].fitem__.next = iitem + 1;
     }
-    list->items[nitems_new - 1].free_item__.next = UINT32_MAX;
-    list->head = nitems + 1;
+    list->items[id.index].fitem__.id = id;
+    list->items[nitems_new - 1].fitem__.next = UINT32_MAX;
+    list->head = list->nitems + 1;
     list->nitems = nitems_new;
   }
   return id;
 }
 
 static FINLINE void
-free_list_del(struct free_list* list, struct free_id* id)
+FLIST_FUNC__(del)(struct FLIST_TYPE__* list, struct fid* id)
 {
   ASSERT(list && id);
-  FREE_ITEM* item = free_list_get(list, id);
-  item->free_item__.id.name = UINT32_MAX;
-  item->free_item__.next = list->head;
-  list->head = item->free_item__.id.index;
+  if(FLIST_FUNC__(hold)(list, id)) {
+     struct FITEM_TYPE* item = FLIST_FUNC__(get)(list, id);
+     item->fitem__.id.name = UINT32_MAX;
+     item->fitem__.next = list->head;
+     list->head = item->fitem__.id.index;
+  }
 }
 
-#endif /* FREE_LIST_H */
+#undef FLIST_TYPE__
+#undef FLIST_FUNC__
+#undef FITEM_TYPE
+
+#endif /* ifdef FITEM_TYPE */
 
diff --git a/src/test_free_list.c b/src/test_free_list.c
@@ -0,0 +1,68 @@
+#include "rsys.h"
+#include "free_list.h"
+
+struct object {
+  FITEM;
+  unsigned int i;
+};
+
+#define FITEM_TYPE object
+#include "free_list.h"
+
+int
+main(int argc, char** argv)
+{
+  #define NB_OBJ 1024
+  struct flist_object list;
+  struct object* obj = NULL;
+  struct fid id[NB_OBJ];
+  (void)argc, (void)argv;
+
+  FOR_EACH(int, i, 0, NB_OBJ) {
+    id[i] = FID_NULL;
+  }
+
+  flist_object_init(&list);
+  CHECK(flist_object_hold(&list, &id[0]), false);
+  CHECK(flist_object_get(&list, &id[0]), NULL);
+
+  FOR_EACH(int, i, 0, NB_OBJ / 2) {
+    id[i] = flist_object_add(&list);
+    CHECK(flist_object_hold(&list, &id[i]), true);
+    obj = flist_object_get(&list, &id[i]);
+    NCHECK(obj, NULL);
+    obj->i = 0xDECAF000 + (unsigned)i;
+  }
+
+  FOR_EACH(int, i, 0, NB_OBJ * 2 / 3) {
+    const float rand_f /* in [0, 1] */ = (float)rand() / (float)RAND_MAX;
+    const int i = (int)(rand_f * (NB_OBJ - 1));
+    flist_object_del(&list, &id[i]);
+    id[i] = FID_NULL;
+  }
+
+  FOR_EACH(int, i, NB_OBJ / 2, NB_OBJ) {
+    id[i] = flist_object_add(&list);
+    CHECK(flist_object_hold(&list, &id[i]), true);
+    obj = flist_object_get(&list, &id[i]);
+    NCHECK(obj, NULL);
+    obj->i = 0xDECAF000 + (unsigned)i;
+  }
+
+  FOR_EACH(int, i, 0, NB_OBJ) {
+    if(IS_FID_NULL(id[i])) {
+      CHECK(flist_object_hold(&list, &id[i]), false);
+      CHECK(flist_object_get(&list, &id[i]), NULL);
+    } else {
+      CHECK(flist_object_hold(&list, &id[i]), true);
+      obj = flist_object_get(&list, &id[i]);
+      CHECK(obj->i, 0xDECAF000 + (unsigned)i);
+    }
+  }
+
+  flist_object_release(&list);
+
+  CHECK(MEM_ALLOCATED_SIZE(&mem_default_allocator), 0);
+
+  return 0;
+}