Swag : another name for O(1) set

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@488 48e7efb5-ca39-0410-a469-dd3cf9ba447f

diff --git a/include/xbt/swag.h b/include/xbt/swag.h
new file mode 100644 (file)
index 0000000..75ce345
--- /dev/null
+++ b/include/xbt/swag.h
@@ -0,0 +1,43 @@
+/* Authors: Arnaud Legrand                                                  */
+
+/* This program is free software; you can redistribute it and/or modify it
+   under the terms of the license (GNU LGPL) which comes with this package. */
+
+/* Warning, this module is done to be efficient and performs tons of
+   cast and dirty things. So avoid using it unless you really know
+   what you are doing. */
+
+/* This type should be added to a type that is to be used in such a swag */
+/* Whenever a new object with this struct is created, all fields have to be swag to NULL */
+
+typedef struct xbt_swag_hookup {
+  void *next;
+  void *prev;
+} s_xbt_swag_hookup_t, *xbt_swag_hookup_t;
+
+typedef struct xbt_swag {
+  void *head;
+  void *tail;
+  size_t offset;
+  int count;
+} s_xbt_swag_t, *xbt_swag_t;
+
+xbt_swag_t xbt_swag_new(size_t offset);
+void  xbt_swag_insert(void *obj,xbt_swag_t swag);
+void xbt_swag_extract(void *obj, xbt_swag_t swag);
+int  xbt_swag_size(xbt_swag_t swag);
+int  xbt_swag_belongs(void *obj,xbt_swag_t swag);
+
+static __inline__ void *xbt_swag_getFirst(xbt_swag_t swag)
+{
+  return(swag->head);
+}
+
+#define xbt_swag_getNext(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->prev)
+#define xbt_swag_getPrev(obj,offset) (((xbt_swag_hookup_t)(((char *) (obj)) + (offset)))->next)
+
+
+#define xbt_swag_foreach(obj,swag)                            \
+   for(obj=xbt_swag_getFirst(swag);                           \
+       obj!=NULL;                                           \
+       obj=xbt_swag_getNext(obj,swag->offset))

diff --git a/src/xbt/swag.c b/src/xbt/swag.c
new file mode 100644 (file)
index 0000000..36df2b9
--- /dev/null
+++ b/src/xbt/swag.c
@@ -0,0 +1,90 @@
+/* Authors: Arnaud Legrand                                                  */
+
+/* This program is free software; you can redistribute it and/or modify it
+   under the terms of the license (GNU LGPL) which comes with this package. */
+
+/* Warning, this module is done to be efficient and performs tons of
+   cast and dirty things. So avoid using it unless you really know
+   what you are doing. */
+
+/* This type should be added to a type that is to be used in such a swag */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "swag.h"
+
+#define PREV(obj,offset) xbt_swag_getPrev(obj,offset)
+#define NEXT(obj,offset) xbt_swag_getNext(obj,offset)
+
+/*
+  Usage : xbt_swag_new(&obj.setA-&obj.setA);
+ */
+
+xbt_swag_t xbt_swag_new(size_t offset)
+{
+  xbt_swag_t swag = calloc(1, sizeof(s_xbt_swag_t));
+
+  swag->offset = offset;
+
+  return swag;
+}
+
+void xbt_swag_insert(void *obj, xbt_swag_t swag)
+{
+  (swag->count)++;
+  if (swag->head == NULL) {
+    swag->head = obj;
+    swag->tail = obj;
+    return;
+  }
+
+  PREV(obj, swag->offset) = swag->tail;
+  NEXT(PREV(obj, swag->offset), swag->offset) = obj;
+
+/*   new->prev = l->tail; */
+/*   new->prev->next = new; */
+
+  swag->tail = obj;
+}
+
+void xbt_swag_extract(void *obj, xbt_swag_t swag)
+{
+  size_t offset = swag->offset;
+
+  if (swag->head == swag->tail) {      /* special case */
+    if (swag->head != obj) {
+      fprintf(stderr,
+             "Tried to remove an object that was not in this swag\n");
+      abort();
+    }
+    swag->head = NULL;
+    swag->tail = NULL;
+    (swag->count)--;
+    return;
+  }
+
+  if (obj == swag->head) {     /* It's the head */
+    swag->head = NEXT(obj, offset);
+    PREV(swag->head, offset) = NULL;
+    NEXT(obj, offset) = NULL;
+  } else if (obj == swag->tail) {      /* It's the tail */
+    swag->tail = PREV(obj, offset);
+    NEXT(swag->tail, offset) = NULL;
+    PREV(obj, offset) = NULL;
+  } else {                     /* It's in the middle */
+    NEXT(PREV(obj, offset), offset) = NEXT(obj, offset);
+    PREV(NEXT(obj, offset), offset) = PREV(obj, offset);
+    PREV(obj, offset) = NEXT(obj, offset) = NULL;
+  }
+  (swag->count)--;
+}
+
+int xbt_swag_size(xbt_swag_t swag)
+{
+  return (swag->count);
+}
+
+int xbt_swag_belongs(void *obj, xbt_swag_t swag)
+{
+  return ((NEXT(obj, swag->offset)) || (PREV(obj, swag->offset)) || (swag->head==obj));
+}

diff --git a/testsuite/xbt/swag_usage.c b/testsuite/xbt/swag_usage.c
new file mode 100644 (file)
index 0000000..1814724
--- /dev/null
+++ b/testsuite/xbt/swag_usage.c
@@ -0,0 +1,48 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "swag.h"
+
+typedef struct {
+  s_xbt_swag_hookup_t setA;
+  s_xbt_swag_hookup_t setB;
+  char *name;
+} shmurtz, s_shmurtz_t, *shmurtz_t;
+
+int main(void)
+{
+  shmurtz_t obj1, obj2, obj;
+  xbt_swag_t setA,setB;
+
+  obj1 = calloc(1,sizeof(s_shmurtz_t));
+  obj2 = calloc(1,sizeof(s_shmurtz_t));
+
+  obj1->name="Obj 1";
+  obj2->name="Obj 2";
+
+  printf("%p %p %d\n",obj1,&(obj1->setB),
+        (char *)&(obj1->setB) - (char *)obj1);
+
+  setA = xbt_swag_new((char *)&(obj1->setA) - (char *)obj1);
+  setB = xbt_swag_new((char *)&(obj1->setB) - (char *)obj1);
+
+  xbt_swag_insert(obj1, setA);
+  xbt_swag_insert(obj1, setB);
+  xbt_swag_insert(obj2, setA);
+  xbt_swag_insert(obj2, setB);
+
+  xbt_swag_extract(obj1, setB);
+  //  xbt_swag_extract(obj2, setB);
+
+  xbt_swag_foreach(obj,setA) {
+    printf("\t%s\n",obj->name);
+  }
+
+  xbt_swag_foreach(obj,setB) {
+    printf("\t%s\n",obj->name);
+  }
+
+  printf("Belongs : %d\n", xbt_swag_belongs(obj2,setB));
+
+  printf("%d %d\n", xbt_swag_size(setA),xbt_swag_size(setB));
+  return 0;
+}