From 0ff69767ac5366173bd114a5dffae5414dcd1635 Mon Sep 17 00:00:00 2001 From: alegrand Date: Fri, 5 Nov 2004 21:11:11 +0000 Subject: [PATCH 1/1] 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 --- include/xbt/swag.h | 43 ++++++++++++++++++ src/xbt/swag.c | 90 ++++++++++++++++++++++++++++++++++++++ testsuite/xbt/swag_usage.c | 48 ++++++++++++++++++++ 3 files changed, 181 insertions(+) create mode 100644 include/xbt/swag.h create mode 100644 src/xbt/swag.c create mode 100644 testsuite/xbt/swag_usage.c diff --git a/include/xbt/swag.h b/include/xbt/swag.h new file mode 100644 index 0000000000..75ce3451ae --- /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 index 0000000000..36df2b9cfb --- /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 +#include +#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 index 0000000000..1814724e83 --- /dev/null +++ b/testsuite/xbt/swag_usage.c @@ -0,0 +1,48 @@ +#include +#include +#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; +} -- 2.20.1