Formers simgrid fifo : when real O(1) is needed... The way I'm gonna use

that in the L.P. solver is so dirty (and therefore so beautiful) ! You're
gonna like it !

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

diff --git a/include/xbt/fifo.h b/include/xbt/fifo.h
new file mode 100644 (file)
index 0000000..b59e0b1
--- /dev/null
+++ b/include/xbt/fifo.h
@@ -0,0 +1,45 @@
+/* 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. */
+
+#ifndef _XBT_FIFO_H
+#define _XBT_FIFO_H
+
+/* Bucket structure */
+typedef struct xbt_fifo_item *xbt_fifo_item_t;
+
+/* FIFO structure */
+typedef struct xbt_fifo *xbt_fifo_t;
+
+/* API */
+xbt_fifo_t xbt_fifo_new(void);
+void xbt_fifo_free(xbt_fifo_t);
+
+void xbt_fifo_push(xbt_fifo_t, void *);
+void *xbt_fifo_pop(xbt_fifo_t);
+void xbt_fifo_unshift(xbt_fifo_t, void *);
+void *xbt_fifo_shift(xbt_fifo_t);
+
+void xbt_fifo_remove(xbt_fifo_t, void *);
+void xbt_fifo_remove_item(xbt_fifo_t, xbt_fifo_item_t);
+
+int xbt_fifo_is_in(xbt_fifo_t, void *);
+
+void **xbt_fifo_to_array(xbt_fifo_t);
+xbt_fifo_t xbt_fifo_copy(xbt_fifo_t);
+
+xbt_fifo_item_t xbt_fifo_newitem(void);
+void xbt_fifo_set_item_content(xbt_fifo_item_t, void *);
+void *xbt_fifo_get_item_content(xbt_fifo_item_t);
+void xbt_fifo_freeitem(xbt_fifo_item_t);
+
+int xbt_fifo_size(xbt_fifo_t);
+
+/* #define xbt_fifo_foreach(f,i,n,type)                  \ */
+/*    for(i=xbt_fifo_getFirstitem(f);                    \ */
+/*      ((i)?(n=(type)(i->content)):(NULL));             \ */
+/*        i=xbt_fifo_getNextitem(i)) */
+
+
+#endif                         /* _XBT_FIFO_H */

diff --git a/src/xbt/fifo.c b/src/xbt/fifo.c
new file mode 100644 (file)
index 0000000..fc0bb91
--- /dev/null
+++ b/src/xbt/fifo.c
@@ -0,0 +1,261 @@
+/* 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. */
+
+#include <stdlib.h>
+#include "xbt_fifo_private.h"
+
+/*
+ * xbt_fifo_new()
+ */
+xbt_fifo_t xbt_fifo_new(void)
+{
+  xbt_fifo_t fifo;
+  fifo = (xbt_fifo_t) calloc(1, sizeof(struct xbt_fifo));
+  return fifo;
+}
+
+/*
+ * xbt_fifo_free()
+ */
+void xbt_fifo_free(xbt_fifo_t l)
+{
+  xbt_fifo_item_t b, tmp;
+
+  for (b = xbt_fifo_getFirstitem(l); b;
+       tmp = b, b = b->next, xbt_fifo_freeitem(tmp));
+  free(l);
+  return;
+}
+
+/*
+ * xbt_fifo_push()
+ * at the tail
+ */
+void xbt_fifo_push(xbt_fifo_t l, void *t)
+{
+  xbt_fifo_item_t new;
+
+  (l->count)++;
+  new = xbt_fifo_newitem();
+  new->content = t;
+  if (l->head == NULL) {
+    l->head = new;
+    l->tail = new;
+    return;
+  }
+  new->prev = l->tail;
+  new->prev->next = new;
+  l->tail = new;
+  return;
+}
+
+/*
+ * xbt_fifo_pop()
+ * from the tail
+ */
+void *xbt_fifo_pop(xbt_fifo_t l)
+{
+  xbt_fifo_item_t item;
+  void *content;
+
+  if (l->tail == NULL)
+    return NULL;
+
+  item = l->tail;
+  content = item->content;
+
+  l->tail = item->prev;
+  if (l->tail == NULL)
+    l->head = NULL;
+  else
+    l->tail->next = NULL;
+
+  xbt_fifo_freeitem(item);
+  (l->count)--;
+  return content;
+}
+
+/*
+ * xbt_fifo_unshift()
+ * at the head
+ */
+void xbt_fifo_unshift(xbt_fifo_t l, void *t)
+{
+  xbt_fifo_item_t new;
+
+  (l->count)++;
+  new = xbt_fifo_newitem();
+  new->content = t;
+  if (l->head == NULL) {
+    l->head = new;
+    l->tail = new;
+    return;
+  }
+  new->next = l->head;
+  new->next->prev = new;
+  l->head = new;
+  return;
+}
+
+/*
+ * xbt_fifo_shift()
+ * from the head
+ */
+void *xbt_fifo_shift(xbt_fifo_t l)
+{
+  xbt_fifo_item_t item;
+  void *content;
+
+  if (l->head == NULL)
+    return NULL;
+
+  item = l->head;
+  content = item->content;
+
+  l->head = item->next;
+  if (l->head == NULL)
+    l->tail = NULL;
+  else
+    l->head->prev = NULL;
+
+  xbt_fifo_freeitem(item);
+  (l->count)--;
+  return content;
+}
+
+/*
+ * xbt_fifo_remove()
+ *   removes an xbt_fifo_item_t using its content from the xbt_fifo 
+ */
+void xbt_fifo_remove(xbt_fifo_t l, void *t)
+{
+  xbt_fifo_item_t current, current_next;
+
+
+  for (current = l->head; current; current = current_next) {
+    current_next = current->next;
+    if (current->content != t)
+      continue;
+    /* remove the item */
+    xbt_fifo_remove_item(l, current);
+    /* WILL NOT REMOVE DUPLICATES */
+    break;
+  }
+  return;
+}
+
+/*
+ * xbt_fifo_remove_item()
+ *   removes a given xbt_fifo_item_t from the xbt_fifo
+ */
+void xbt_fifo_remove_item(xbt_fifo_t l, xbt_fifo_item_t current)
+{
+  if (l->head == l->tail) {    /* special case */
+      l->head = NULL;
+      l->tail = NULL;
+      xbt_fifo_freeitem(current);
+      (l->count)--;
+      return;
+    }
+
+    if (current == l->head) {  /* It's the head */
+      l->head = current->next;
+      l->head->prev = NULL;
+      xbt_fifo_freeitem(current);
+    } else if (current == l->tail) {   /* It's the tail */
+      l->tail = current->prev;
+      l->tail->next = NULL;
+      xbt_fifo_freeitem(current);
+    } else {                   /* It's in the middle */
+      current->prev->next = current->next;
+      current->next->prev = current->prev;
+      xbt_fifo_freeitem(current);
+    }
+    (l->count)--;
+}
+
+/*
+ * xbt_fifo_is_in()
+ */
+int xbt_fifo_is_in(xbt_fifo_t f, void *content)
+{
+  xbt_fifo_item_t item = xbt_fifo_getFirstitem(f);
+  while (item) {
+    if (item->content == content)
+      return 1;
+    item = item->next;
+  }
+  return 0;
+}
+
+/*
+ * xbt_fifo_to_array()
+ */
+void **xbt_fifo_to_array(xbt_fifo_t f)
+{
+  void **array;
+  xbt_fifo_item_t b;
+  int i;
+
+  if (f->count == 0)
+    return NULL;
+  else
+    array = (void **) calloc(f->count, sizeof(void *));
+
+  for (i = 0, b = xbt_fifo_getFirstitem(f); b; i++, b = b->next) {
+    array[i] = b->content;
+  }
+  return array;
+}
+
+/*
+ * xbt_fifo_Copy()
+ */
+xbt_fifo_t xbt_fifo_copy(xbt_fifo_t f)
+{
+  xbt_fifo_t copy = NULL;
+  xbt_fifo_item_t b;
+
+  copy = xbt_fifo_new();
+
+  for (b = xbt_fifo_getFirstitem(f); b; b = b->next) {
+    xbt_fifo_push(copy, b->content);
+  }
+  return copy;
+}
+
+/*
+ * xbt_fifo_newitem()
+ */
+xbt_fifo_item_t xbt_fifo_newitem(void)
+{
+  return (xbt_fifo_item_t) calloc(1, sizeof(struct xbt_fifo_item));
+}
+
+void xbt_fifo_set_item_content(xbt_fifo_item_t i , void *v)
+{
+  xbt_fifo_setItemcontent(i,v);
+}
+
+void *xbt_fifo_get_item_content(xbt_fifo_item_t i)
+{
+  return xbt_fifo_getItemcontent(i);
+}
+
+/*
+ * xbt_fifo_freeitem()
+ */
+void xbt_fifo_freeitem(xbt_fifo_item_t b)
+{
+  free(b);
+  return;
+}
+
+int xbt_fifo_size(xbt_fifo_t f)
+{
+  return f->count;
+}
+
+

diff --git a/src/xbt/fifo_private.h b/src/xbt/fifo_private.h
new file mode 100644 (file)
index 0000000..26f5cc0
--- /dev/null
+++ b/src/xbt/fifo_private.h
@@ -0,0 +1,47 @@
+/* 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. */
+
+#ifndef _XBT_FIFO_PRIVATE_H
+#define _XBT_FIFO_PRIVATE_H
+#include "xbt_fifo.h"
+
+/* Bucket structure */
+typedef struct xbt_fifo_item {
+  void *content;
+  struct xbt_fifo_item *next;
+  struct xbt_fifo_item *prev;
+} s_xbt_fifo_item_t;
+
+/* FIFO structure */
+typedef struct xbt_fifo {
+  int count;
+  xbt_fifo_item_t head;
+  xbt_fifo_item_t tail;
+} s_xbt_fifo_t;
+
+
+#define xbt_fifo_getFirstitem(l) ((l)?(l)->head:NULL)
+#define xbt_fifo_getNextitem(i) ((i)?(i)->next:NULL)
+#define xbt_fifo_getPrevitem(i) ((i)?(i)->prev:NULL)
+#define xbt_fifo_getItemcontent(i) ((i)?(i)->content:NULL)
+#define xbt_fifo_setItemcontent(i,v) (i->content=v)
+
+
+/* static __inline__ xbt_fifo_item_t xbt_fifo_getFirstitem(xbt_fifo_t l) */
+/* { */
+/*   return l->head; */
+/* } */
+/* static __inline__ xbt_fifo_item_t xbt_fifo_getNextitem(xbt_fifo_item_t i)  */
+/* { */
+/*   if(i) return i->next; */
+/*   return NULL; */
+/* } */
+/* static __inline__ xbt_fifo_item_t xbt_fifo_getPrevitem(xbt_fifo_item_t i) */
+/* { */
+/*   if(i) return i->prev; */
+/*   return NULL; */
+/* } */
+
+#endif                         /* _XBT_FIFO_PRIVATE_H */