rsys

commit c90715fbeee729ea113063c9d06426144fd245b0
parent 9702af707dbb1f763be2b02f20ac2c46e3c5d0b9
Author: vaplv <vaplv@free.fr>
Date:   Wed, 14 Oct 2015 17:41:41 +0200

Improve the free list API

The free list items are registered into a linked list of "in-use" items.
One can iterate over these items with the FLIST_FOR_EACH macro. Add the
flist_<TYPE>_clear function that cleans up all "in-use" items and reset
the free list state.

Diffstat:
M
src/free_list.h
 | 
67
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
M
src/test_free_list.c
 | 
70
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 131 insertions(+), 6 deletions(-)
diff --git a/src/free_list.h b/src/free_list.h
@@ -23,23 +23,39 @@
 
 #include "rsys.h"
 
+/* A free list item must be a structure with a FITEM field */
 #define FITEM                                                                  \
   struct {                                                                     \
     struct fid id;                                                             \
     uint32_t next;                                                             \
+    uint32_t prev;                                                             \
   } fitem__
 
+/* Unique identifier of a free list item */
 struct fid {
   uint32_t index; /* Index into the free list */
   uint32_t name; /* Unique id that identifies this item */
 };
 
 static const struct fid FID_NULL = { UINT32_MAX, UINT32_MAX };
+
+/* Helper macros that define if a free list identifier is NULL or not */
 #define IS_FID_NULL(Fid) ((Fid).index == UINT32_MAX)
+
+/* Compare 2 free list identifiers */
 #define FID_EQ(Fid0, Fid1) \
   ((Fid0).index == (Fid1).index && (Fid0).name == (Fid1).name)
 
+/* Helper macro that iterates over the items of the free list */
+#define FLIST_FOR_EACH(Item, List)                                             \
+  for((Item) = (List)->tail != UINT32_MAX                                      \
+        ? (List)->items + (List)->tail : NULL;                                 \
+      (Item) != NULL;                                                          \
+      (Item) = (Item)->fitem__.prev != UINT32_MAX                              \
+        ? (List)->items + (Item)->fitem__.prev : NULL)
+
 # endif /* FREE_LIST_H */
+
 #else
 /*
  * Free list API generated with respect to the FITEM_TYPE macro.
@@ -57,8 +73,9 @@ static const struct fid FID_NULL = { UINT32_MAX, UINT32_MAX };
 #include <string.h>
 
 struct FLIST_TYPE__ {
-  uint32_t head;
-  uint32_t name_next;
+  uint32_t head; /* Index toward the first free item */
+  uint32_t tail; /* Index toward the last created item */
+  uint32_t name_next; /* Next unique free list item name */
   struct FITEM_TYPE* items;
   uint32_t nitems;
   struct mem_allocator* allocator;
@@ -71,6 +88,7 @@ FLIST_FUNC__(init)
 {
   ASSERT(list);
   list->head = UINT32_MAX;
+  list->tail = UINT32_MAX;
   list->name_next = 0;
   list->items = NULL;
   list->nitems = 0;
@@ -112,9 +130,8 @@ FLIST_FUNC__(add)(struct FLIST_TYPE__* list)
   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 {
+  } else { /* Increase the free list size */
     const uint32_t nitems_new = list->nitems ? list->nitems * 2 : 16;
     uint32_t iitem = 0;
     struct FITEM_TYPE item;
@@ -127,14 +144,23 @@ FLIST_FUNC__(add)(struct FLIST_TYPE__* list)
        nitems_new * sizeof(struct FITEM_TYPE));
     if(!list->items)
       FATAL("Unsufficient memory\n");
-    FOR_EACH(iitem, list->nitems, nitems_new - 1) {
+    FOR_EACH(iitem, list->nitems, nitems_new) {
+      list->items[iitem].fitem__.prev = iitem - 1;
       list->items[iitem].fitem__.next = iitem + 1;
+      list->items[iitem].fitem__.id.name = UINT32_MAX;
     }
-    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;
   }
+  list->items[id.index].fitem__.id = id;
+
+  /* Add the item in the linked list of valid element */
+  if(list->tail != UINT32_MAX)
+    list->items[list->tail].fitem__.next = id.index;
+  list->items[id.index].fitem__.prev = list->tail;
+  list->items[id.index].fitem__.next = UINT32_MAX;
+  list->tail = id.index;
   return id;
 }
 
@@ -144,12 +170,41 @@ FLIST_FUNC__(del)(struct FLIST_TYPE__* list, struct fid id)
   ASSERT(list);
   if(FLIST_FUNC__(hold)(list, id)) {
      struct FITEM_TYPE* item = FLIST_FUNC__(get)(list, id);
+
+     /* Unlink the item from the double linked list of valid items */
+     if(item->fitem__.prev != UINT32_MAX)
+       list->items[item->fitem__.prev].fitem__.next = item->fitem__.next;
+     if(item->fitem__.next != UINT32_MAX) {
+       list->items[item->fitem__.next].fitem__.prev = item->fitem__.prev;
+     } else {
+       ASSERT(item->fitem__.id.index == list->tail);
+       list->tail = item->fitem__.prev;
+     }
+
+     /* Add the item to the single linked list of free items */
      item->fitem__.id.name = UINT32_MAX;
      item->fitem__.next = list->head;
      list->head = item->fitem__.id.index;
   }
 }
 
+static FINLINE void
+FLIST_FUNC__(clear)(struct FLIST_TYPE__* list)
+{
+  uint32_t iitem;
+  ASSERT(list);
+  FOR_EACH(iitem, 0, list->nitems) {
+    list->items[iitem].fitem__.next = iitem + 1;
+    list->items[iitem].fitem__.next = iitem - 1;
+    list->items[iitem].fitem__.id.name = UINT32_MAX;
+  }
+  if(list->nitems)
+    list->items[list->nitems - 1].fitem__.next = UINT32_MAX;
+
+  list->head = list->tail = UINT32_MAX;
+  list->name_next = 0;
+}
+
 static FINLINE struct fid
 CONCAT(FITEM_TYPE, _id_get)(const struct FITEM_TYPE* item)
 {
diff --git a/src/test_free_list.c b/src/test_free_list.c
@@ -31,6 +31,8 @@ main(int argc, char** argv)
   struct flist_object list;
   struct object* obj = NULL;
   struct fid id[NB_OBJ];
+  char find[NB_OBJ];
+  size_t nitems;
   int i = 0;
   (void)argc, (void)argv;
 
@@ -80,6 +82,74 @@ main(int argc, char** argv)
   }
 
   flist_object_release(&list);
+  flist_object_init(NULL, &list);
+
+  FOR_EACH(i, 0, NB_OBJ) {
+    id[i] = flist_object_add(&list);
+    obj = flist_object_get(&list, id[i]);
+    obj->i = (unsigned)i;
+  }
+
+  nitems = 0;
+  memset(find, 0, NB_OBJ * sizeof(char));
+  FLIST_FOR_EACH(obj, &list) {
+    CHECK(find[obj->i], 0);
+    find[obj->i] = 1;
+    ++nitems;
+  }
+  CHECK(nitems, NB_OBJ);
+
+  FOR_EACH(i, 0, NB_OBJ / 2)
+    flist_object_del(&list, id[i*2]);
+
+  nitems = 0;
+  memset(find, 0, NB_OBJ * sizeof(char));
+  FLIST_FOR_EACH(obj, &list) {
+    CHECK(find[obj->i], 0);
+    find[obj->i] = 1;
+    ++nitems;
+  }
+  CHECK(nitems, NB_OBJ/2);
+  FOR_EACH(i, 0, NB_OBJ) {
+    if(i%2) {
+      CHECK(flist_object_hold(&list, id[i]), 1);
+      CHECK(find[i], 1);
+    } else {
+      CHECK(flist_object_hold(&list, id[i]), 0);
+      CHECK(find[i], 0);
+    }
+  }
+
+  flist_object_clear(&list);
+  nitems = 0;
+  FLIST_FOR_EACH(obj, &list)
+    ++nitems;
+  CHECK(nitems, 0);
+
+  FOR_EACH(i, 0, NB_OBJ)
+    CHECK(flist_object_hold(&list, id[i]), 0);
+
+  FOR_EACH(i, 0, NB_OBJ/4) {
+    id[i] = flist_object_add(&list);
+    obj = flist_object_get(&list, id[i]);
+    obj->i = (unsigned)i*2;
+  }
+
+  nitems = 0;
+  memset(find, 0, NB_OBJ * sizeof(char));
+  FLIST_FOR_EACH(obj, &list) {
+    CHECK(obj->i % 2, 0);
+    find[obj->i/2] = 1;
+    ++nitems;
+  }
+  CHECK(nitems, NB_OBJ / 4);
+  FOR_EACH(i, 0, NB_OBJ/4) {
+    CHECK(find[i], 1);
+    CHECK(flist_object_hold(&list, id[i]), 1);
+    CHECK(flist_object_get(&list, id[i])->i, (unsigned)i * 2);
+  }
+
+  flist_object_release(&list);
   CHECK(MEM_ALLOCATED_SIZE(&mem_default_allocator), 0);
   return 0;
 }