[cogl/wip/wl-list: 1/7] Add a copy of the Wayland embedded linked list implementation

[Neil Roberts <nroberts src gnome org>]

commit f315e70b6937fb42d660569258469a31c03e14f2
Author: Neil Roberts <neil linux intel com>
Date:   Sat Jun 8 23:03:25 2013 +0100

    Add a copy of the Wayland embedded linked list implementation
    
    The intention is to start using this in favour of the BSD list
    implementation which we are currently using. The advantage of the
    Wayland model is that it is much simpler and so it is easier to
    follow. It also doesn't require defining a typedef for every list
    type.
    
    The downside is that there is only one list type which is a
    doubly-linked list where the head has a pointer to both the beginning
    and the end. The BSD implementation has many more combinations some of
    which we were taking advantage of to reduce the size of critical
    structs where we didn't need a pointer to the end of the list.

 cogl/Makefile.am |    2 +
 cogl/cogl-list.c |   94 +++++++++++++++++++++++++++++++++++++++++
 cogl/cogl-list.h |  123 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 219 insertions(+), 0 deletions(-)
---
diff --git a/cogl/Makefile.am b/cogl/Makefile.am
index 323239d..11820dc 100644
--- a/cogl/Makefile.am
+++ b/cogl/Makefile.am
@@ -376,6 +376,8 @@ cogl_sources_c = \
        $(srcdir)/cogl-point-in-poly.c                  \
        $(srcdir)/cogl-clutter.c                        \
        $(srcdir)/cogl-queue.h                          \
+       $(srcdir)/cogl-list.c                           \
+       $(srcdir)/cogl-list.h                           \
        $(srcdir)/winsys/cogl-winsys-stub-private.h     \
        $(srcdir)/winsys/cogl-winsys-stub.c             \
        $(srcdir)/cogl-config-private.h                 \
diff --git a/cogl/cogl-list.c b/cogl/cogl-list.c
new file mode 100644
index 0000000..3fbc675
--- /dev/null
+++ b/cogl/cogl-list.c
@@ -0,0 +1,94 @@
+/*
+ * Copyright © 2008-2011 Kristian Høgsberg
+ * Copyright © 2011, 2012 Intel Corporation
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that copyright
+ * notice and this permission notice appear in supporting documentation, and
+ * that the name of the copyright holders not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission.  The copyright holders make no representations
+ * about the suitability of this software for any purpose.  It is provided "as
+ * is" without express or implied warranty.
+ *
+ * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
+ * OF THIS SOFTWARE.
+ */
+
+/* This list implementation is based on the Wayland source code */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "cogl-list.h"
+
+void
+_cogl_list_init (CoglList *list)
+{
+  list->prev = list;
+  list->next = list;
+}
+
+void
+_cogl_list_insert (CoglList *list, CoglList *elm)
+{
+  elm->prev = list;
+  elm->next = list->next;
+  list->next = elm;
+  elm->next->prev = elm;
+}
+
+void
+_cogl_list_remove (CoglList *elm)
+{
+  elm->prev->next = elm->next;
+  elm->next->prev = elm->prev;
+  elm->next = NULL;
+  elm->prev = NULL;
+}
+
+int
+_cogl_list_length (CoglList *list)
+{
+  CoglList *e;
+  int count;
+
+  count = 0;
+  e = list->next;
+  while (e != list)
+    {
+      e = e->next;
+      count++;
+    }
+
+  return count;
+}
+
+int
+_cogl_list_empty (CoglList *list)
+{
+  return list->next == list;
+}
+
+void
+_cogl_list_insert_list (CoglList *list,
+                        CoglList *other)
+{
+  if (_cogl_list_empty (other))
+    return;
+
+  other->next->prev = list;
+  other->prev->next = list->next;
+  list->next->prev = other->prev;
+  list->next = other->next;
+}
diff --git a/cogl/cogl-list.h b/cogl/cogl-list.h
new file mode 100644
index 0000000..7d716a8
--- /dev/null
+++ b/cogl/cogl-list.h
@@ -0,0 +1,123 @@
+/*
+ * Copyright © 2008 Kristian Høgsberg
+ * Copyright © 2012, 2013 Intel Corporation
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that copyright
+ * notice and this permission notice appear in supporting documentation, and
+ * that the name of the copyright holders not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission.  The copyright holders make no representations
+ * about the suitability of this software for any purpose.  It is provided "as
+ * is" without express or implied warranty.
+ *
+ * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
+ * OF THIS SOFTWARE.
+ */
+
+/* This list implementation is based on the Wayland source code */
+
+#ifndef COGL_LIST_H
+#define COGL_LIST_H
+
+/**
+ * CoglList - linked list
+ *
+ * The list head is of "CoglList" type, and must be initialized
+ * using cogl_list_init().  All entries in the list must be of the same
+ * type.  The item type must have a "CoglList" member. This
+ * member will be initialized by cogl_list_insert(). There is no need to
+ * call cogl_list_init() on the individual item. To query if the list is
+ * empty in O(1), use cogl_list_empty().
+ *
+ * Let's call the list reference "CoglList foo_list", the item type as
+ * "item_t", and the item member as "CoglList link". The following code
+ *
+ * The following code will initialize a list:
+ *
+ *      cogl_list_init (foo_list);
+ *      cogl_list_insert (foo_list, item1);      Pushes item1 at the head
+ *      cogl_list_insert (foo_list, item2);      Pushes item2 at the head
+ *      cogl_list_insert (item2, item3);         Pushes item3 after item2
+ *
+ * The list now looks like [item2, item3, item1]
+ *
+ * Will iterate the list in ascending order:
+ *
+ *      item_t *item;
+ *      cogl_list_for_each(item, foo_list, link) {
+ *              Do_something_with_item(item);
+ *      }
+ */
+
+typedef struct _CoglList CoglList;
+
+struct _CoglList
+{
+  CoglList *prev;
+  CoglList *next;
+};
+
+void
+_cogl_list_init (CoglList *list);
+
+void
+_cogl_list_insert (CoglList *list,
+                   CoglList *elm);
+
+void
+_cogl_list_remove (CoglList *elm);
+
+int
+_cogl_list_length (CoglList *list);
+
+int
+_cogl_list_empty (CoglList *list);
+
+void
+_cogl_list_insert_list (CoglList *list,
+                        CoglList *other);
+
+#ifdef __GNUC__
+#define _cogl_container_of(ptr, sample, member)                         \
+  (__typeof__(sample))((char *)(ptr)    -                               \
+                       ((char *)&(sample)->member - (char *)(sample)))
+#else
+#define _cogl_container_of(ptr, sample, member)                 \
+  (void *)((char *)(ptr)        -                               \
+           ((char *)&(sample)->member - (char *)(sample)))
+#endif
+
+#define _cogl_list_for_each(pos, head, member)                          \
+  for (pos = 0, pos = _cogl_container_of((head)->next, pos, member);    \
+       &pos->member != (head);                                          \
+       pos = _cogl_container_of(pos->member.next, pos, member))
+
+#define _cogl_list_for_each_safe(pos, tmp, head, member)                \
+  for (pos = 0, tmp = 0,                                                \
+         pos = _cogl_container_of((head)->next, pos, member),           \
+         tmp = _cogl_container_of((pos)->member.next, tmp, member);     \
+       &pos->member != (head);                                          \
+       pos = tmp,                                                       \
+         tmp = _cogl_container_of(pos->member.next, tmp, member))
+
+#define _cogl_list_for_each_reverse(pos, head, member)                  \
+  for (pos = 0, pos = _cogl_container_of((head)->prev, pos, member);    \
+       &pos->member != (head);                                          \
+       pos = _cogl_container_of(pos->member.prev, pos, member))
+
+#define _cogl_list_for_each_reverse_safe(pos, tmp, head, member)        \
+  for (pos = 0, tmp = 0,                                                \
+         pos = _cogl_container_of((head)->prev, pos, member),           \
+         tmp = _cogl_container_of((pos)->member.prev, tmp, member);     \
+       &pos->member != (head);                                          \
+       pos = tmp,                                                       \
+         tmp = _cogl_container_of(pos->member.prev, tmp, member))
+
+#endif /* COGL_LIST_H */