Refine list related functions.

Make the list related functions more clear and readable.

Signed-off-by: Junyan He <junyan.he@intel.com>
Reviewed-by: Yang Rong <rong.r.yang@intel.com>

10 files changed, 138 insertions, 112 deletions

diff --git a/src/cl_base_object.c b/src/cl_base_object.c
index 00c4b356..af537cc4 100644
--- a/src/cl_base_object.c
+++ b/src/cl_base_object.c
@@ -29,7 +29,7 @@ cl_object_init_base(cl_base_object obj, cl_ulong magic)
   pthread_mutex_init(&obj->mutex, NULL);
   pthread_cond_init(&obj->cond, NULL);
   obj->owner = invalid_thread_id;
-  list_init(&obj->node);
+  list_node_init(&obj->node);
 }
 
 LOCAL void
@@ -54,9 +54,9 @@ cl_object_destroy_base(cl_base_object obj)
     assert(0);
   }
 
-  if (!list_empty(&obj->node)) {
+  if (!list_node_out_of_list(&obj->node)) {
     DEBUGP(DL_ERROR, "CL object %p, call destroy while still belong to some object %p",
-           obj, obj->node.prev);
+           obj, obj->node.p);
     assert(0);
   }
 
diff --git a/src/cl_base_object.h b/src/cl_base_object.h
index 4e643dfe..d064a826 100644
--- a/src/cl_base_object.h
+++ b/src/cl_base_object.h
@@ -47,7 +47,7 @@ typedef struct _cl_base_object {
   DEFINE_ICD(dispatch);  /* Dispatch function table for icd */
   cl_ulong magic;        /* Magic number for each CL object */
   atomic_t ref;          /* Reference for each CL object */
-  list_head node;        /* CL object node belong to some container */
+  list_node node;        /* CL object node belong to some container */
   pthread_mutex_t mutex; /* THe mutex to protect this object MT safe */
   pthread_cond_t cond;   /* Condition to wait for getting the object */
   pthread_t owner;       /* The thread which own this object */
diff --git a/src/cl_command_queue_enqueue.c b/src/cl_command_queue_enqueue.c
index 32545b3d..8bf05a24 100644
--- a/src/cl_command_queue_enqueue.c
+++ b/src/cl_command_queue_enqueue.c
@@ -29,8 +29,8 @@ worker_thread_function(void *Arg)
   cl_command_queue queue = worker->queue;
   cl_event e;
   cl_uint cookie = -1;
-  list_head *pos;
-  list_head *n;
+  list_node *pos;
+  list_node *n;
   list_head ready_list;
   cl_int exec_status;
 
@@ -63,8 +63,8 @@ worker_thread_function(void *Arg)
     {
       e = list_entry(pos, _cl_event, enqueue_node);
       if (cl_event_is_ready(e) <= CL_COMPLETE) {
-        list_del(&e->enqueue_node);
-        list_add_tail(&e->enqueue_node, &ready_list);
+        list_node_del(&e->enqueue_node);
+        list_add_tail(&ready_list, &e->enqueue_node);
       }
     }
 
@@ -105,7 +105,7 @@ worker_thread_function(void *Arg)
     list_for_each_safe(pos, n, &ready_list)
     {
       e = list_entry(pos, _cl_event, enqueue_node);
-      list_del(&e->enqueue_node);
+      list_node_del(&e->enqueue_node);
       cl_event_delete(e);
     }
 
@@ -138,8 +138,8 @@ cl_command_queue_enqueue_event(cl_command_queue queue, cl_event event)
   assert(CL_OBJECT_IS_COMMAND_QUEUE(queue));
   CL_OBJECT_LOCK(queue);
   assert(queue->worker.quit == CL_FALSE);
-  assert(list_empty(&event->enqueue_node));
-  list_add_tail(&event->enqueue_node, &queue->worker.enqueued_events);
+  assert(list_node_out_of_list(&event->enqueue_node));
+  list_add_tail(&queue->worker.enqueued_events, &event->enqueue_node);
   queue->worker.cookie++;
   CL_OBJECT_NOTIFY_COND(queue);
   CL_OBJECT_UNLOCK(queue);
@@ -167,8 +167,8 @@ LOCAL void
 cl_command_queue_destroy_enqueue(cl_command_queue queue)
 {
   cl_command_queue_enqueue_worker worker = &queue->worker;
-  list_head *pos;
-  list_head *n;
+  list_node *pos;
+  list_node *n;
   cl_event e;
 
   assert(worker->queue == queue);
@@ -190,7 +190,7 @@ cl_command_queue_destroy_enqueue(cl_command_queue queue)
     list_for_each_safe(pos, n, &worker->enqueued_events)
     {
       e = list_entry(pos, _cl_event, enqueue_node);
-      list_del(&e->enqueue_node);
+      list_node_del(&e->enqueue_node);
       cl_event_set_status(e, -1); // Give waiters a chance to wakeup.
       cl_event_delete(e);
     }
@@ -202,7 +202,7 @@ LOCAL cl_event *
 cl_command_queue_record_in_queue_events(cl_command_queue queue, cl_uint *list_num)
 {
   int event_num = 0;
-  list_head *pos;
+  list_node *pos;
   cl_command_queue_enqueue_worker worker = &queue->worker;
   cl_event *enqueued_list = NULL;
   int i;
diff --git a/src/cl_context.c b/src/cl_context.c
index edff8a2c..6b6cd624 100644
--- a/src/cl_context.c
+++ b/src/cl_context.c
@@ -46,7 +46,7 @@ cl_context_add_queue(cl_context ctx, cl_command_queue queue) {
   cl_context_add_ref(ctx);
 
   CL_OBJECT_LOCK(ctx);
-  list_add_tail(&queue->base.node, &ctx->queues);
+  list_add_tail(&ctx->queues, &queue->base.node);
   ctx->queue_num++;
   ctx->queue_cookie++;
   CL_OBJECT_UNLOCK(ctx);
@@ -58,7 +58,7 @@ LOCAL void
 cl_context_remove_queue(cl_context ctx, cl_command_queue queue) {
   assert(queue->ctx == ctx);
   CL_OBJECT_LOCK(ctx);
-  list_del(&queue->base.node);
+  list_node_del(&queue->base.node);
   ctx->queue_num--;
   ctx->queue_cookie++;
   CL_OBJECT_UNLOCK(ctx);
@@ -73,7 +73,7 @@ cl_context_add_mem(cl_context ctx, cl_mem mem) {
   cl_context_add_ref(ctx);
 
   CL_OBJECT_LOCK(ctx);
-  list_add_tail(&mem->base.node, &ctx->mem_objects);
+  list_add_tail(&ctx->mem_objects, &mem->base.node);
   ctx->mem_object_num++;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -86,7 +86,7 @@ cl_context_add_svm(cl_context ctx, cl_mem mem) {
   cl_context_add_ref(ctx);
 
   CL_OBJECT_LOCK(ctx);
-  list_add_tail(&mem->base.node, &ctx->svm_objects);
+  list_add_tail(&ctx->svm_objects, &mem->base.node);
   ctx->svm_object_num++;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -97,7 +97,7 @@ LOCAL void
 cl_context_remove_mem(cl_context ctx, cl_mem mem) {
   assert(mem->ctx == ctx);
   CL_OBJECT_LOCK(ctx);
-  list_del(&mem->base.node);
+  list_node_del(&mem->base.node);
   ctx->mem_object_num--;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -111,7 +111,7 @@ cl_context_add_sampler(cl_context ctx, cl_sampler sampler) {
   cl_context_add_ref(ctx);
 
   CL_OBJECT_LOCK(ctx);
-  list_add_tail(&sampler->base.node, &ctx->samplers);
+  list_add_tail(&ctx->samplers, &sampler->base.node);
   ctx->sampler_num++;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -122,7 +122,7 @@ LOCAL void
 cl_context_remove_sampler(cl_context ctx, cl_sampler sampler) {
   assert(sampler->ctx == ctx);
   CL_OBJECT_LOCK(ctx);
-  list_del(&sampler->base.node);
+  list_node_del(&sampler->base.node);
   ctx->sampler_num--;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -136,7 +136,7 @@ cl_context_add_event(cl_context ctx, cl_event event) {
   cl_context_add_ref(ctx);
 
   CL_OBJECT_LOCK(ctx);
-  list_add_tail(&event->base.node, &ctx->events);
+  list_add_tail(&ctx->events, &event->base.node);
   ctx->event_num++;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -147,7 +147,7 @@ LOCAL void
 cl_context_remove_event(cl_context ctx, cl_event event) {
   assert(event->ctx == ctx);
   CL_OBJECT_LOCK(ctx);
-  list_del(&event->base.node);
+  list_node_del(&event->base.node);
   ctx->event_num--;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -161,7 +161,7 @@ cl_context_add_program(cl_context ctx, cl_program program) {
   cl_context_add_ref(ctx);
 
   CL_OBJECT_LOCK(ctx);
-  list_add_tail(&program->base.node, &ctx->programs);
+  list_add_tail(&ctx->programs, &program->base.node);
   ctx->program_num++;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -172,7 +172,7 @@ LOCAL void
 cl_context_remove_program(cl_context ctx, cl_program program) {
   assert(program->ctx == ctx);
   CL_OBJECT_LOCK(ctx);
-  list_del(&program->base.node);
+  list_node_del(&program->base.node);
   ctx->program_num--;
   CL_OBJECT_UNLOCK(ctx);
 
@@ -474,7 +474,7 @@ unlock:
 cl_mem
 cl_context_get_svm_from_ptr(cl_context ctx, const void * p)
 {
-  struct list_head *pos;
+  struct list_node *pos;
   cl_mem buf;
 
   list_for_each (pos, (&ctx->mem_objects)) {
diff --git a/src/cl_event.c b/src/cl_event.c
index 0804dbd8..8a588067 100644
--- a/src/cl_event.c
+++ b/src/cl_event.c
@@ -99,7 +99,7 @@ cl_event_new(cl_context ctx, cl_command_queue queue, cl_command_type type,
   e->queue = queue;
 
   list_init(&e->callbacks);
-  list_init(&e->enqueue_node);
+  list_node_init(&e->enqueue_node);
 
   assert(type >= CL_COMMAND_NDRANGE_KERNEL && type <= CL_COMMAND_FILL_IMAGE);
   e->event_type = type;
@@ -132,7 +132,7 @@ cl_event_delete(cl_event event)
 
   cl_enqueue_delete(&event->exec_data);
 
-  assert(list_empty(&event->enqueue_node));
+  assert(list_node_out_of_list(&event->enqueue_node));
 
   if (event->depend_events) {
     assert(event->depend_event_num);
@@ -144,8 +144,8 @@ cl_event_delete(cl_event event)
 
   /* Free all the callbacks. Last ref, no need to lock. */
   while (!list_empty(&event->callbacks)) {
-    cb = list_entry(event->callbacks.next, _cl_event_user_callback, node);
-    list_del(&cb->node);
+    cb = list_entry(event->callbacks.head_node.n, _cl_event_user_callback, node);
+    list_node_del(&cb->node);
     cl_free(cb);
   }
 
@@ -261,7 +261,7 @@ cl_event_set_callback(cl_event event, cl_int exec_type, cl_event_notify_cb pfn_n
       break;
     }
 
-    list_init(&cb->node);
+    list_node_init(&cb->node);
     cb->pfn_notify = pfn_notify;
     cb->user_data = user_data;
     cb->status = exec_type;
@@ -269,7 +269,7 @@ cl_event_set_callback(cl_event event, cl_int exec_type, cl_event_notify_cb pfn_n
 
     CL_OBJECT_LOCK(event);
     if (event->status > exec_type) {
-      list_add_tail(&cb->node, &event->callbacks);
+      list_add_tail(&event->callbacks, &cb->node);
       cb = NULL;
     } else {
       /* The state has already OK, call it immediately. */
@@ -293,8 +293,8 @@ LOCAL cl_int
 cl_event_set_status(cl_event event, cl_int status)
 {
   list_head tmp_callbacks;
-  list_head *n;
-  list_head *pos;
+  list_node *n;
+  list_node *pos;
   cl_bool notify_queue = CL_FALSE;
   cl_event_user_callback cb;
 
@@ -324,8 +324,7 @@ cl_event_set_status(cl_event event, cl_int status)
     do {
       status = event->status;
       list_init(&tmp_callbacks);
-      list_replace(&event->callbacks, &tmp_callbacks);
-      list_init(&event->callbacks);
+      list_move(&event->callbacks, &tmp_callbacks);
       /* Call all the callbacks without lock. */
       CL_OBJECT_UNLOCK(event);
 
@@ -338,7 +337,7 @@ cl_event_set_status(cl_event event, cl_int status)
         if (cb->status < status)
           continue;
 
-        list_del(&cb->node);
+        list_node_del(&cb->node);
         cb->executed = CL_TRUE;
         cb->pfn_notify(event, status, cb->user_data);
         cl_free(cb);
@@ -347,7 +346,7 @@ cl_event_set_status(cl_event event, cl_int status)
       CL_OBJECT_LOCK(event);
 
       // Set back the uncalled callbacks.
-      list_splice_tail(&tmp_callbacks, &event->callbacks);
+      list_merge(&event->callbacks, &tmp_callbacks);
 
       /* Status may changed because we unlock. need to check again. */
     } while (status != event->status);
diff --git a/src/cl_event.h b/src/cl_event.h
index f67299c4..d36a8c6f 100644
--- a/src/cl_event.h
+++ b/src/cl_event.h
@@ -32,7 +32,7 @@ typedef struct _cl_event_user_callback {
   cl_bool executed;              /* Indicat the callback function been called or not */
   cl_event_notify_cb pfn_notify; /* Callback function */
   void *user_data;               /* Callback user data */
-  list_head node;                /* Event callback list node */
+  list_node node;                /* Event callback list node */
 } _cl_event_user_callback;
 
 typedef _cl_event_user_callback *cl_event_user_callback;
@@ -47,7 +47,7 @@ typedef struct _cl_event {
   cl_event *depend_events;    /* The events must complete before this. */
   cl_uint depend_event_num;   /* The depend events number. */
   list_head callbacks;        /* The events The event callback functions */
-  list_head enqueue_node;     /* The node in the enqueue list. */
+  list_node enqueue_node;     /* The node in the enqueue list. */
   cl_ulong timestamp[4];      /* The time stamps for profiling. */
   cl_ulong queued_timestamp;
   enqueue_data exec_data; /* Context for execute this event. */
diff --git a/src/cl_mem.c b/src/cl_mem.c
index d105bff5..b45bc045 100644
--- a/src/cl_mem.c
+++ b/src/cl_mem.c
@@ -269,7 +269,7 @@ error:
 LOCAL cl_int
 cl_mem_is_valid(cl_mem mem, cl_context ctx)
 {
-  struct list_head *pos;
+  struct list_node *pos;
   cl_base_object pbase_object;
 
   CL_OBJECT_LOCK(ctx);
@@ -1229,8 +1229,8 @@ cl_mem_delete(cl_mem mem)
 
   /* First, call all the callbacks registered by user. */
   while (!list_empty(&mem->dstr_cb_head)) {
-    cb = list_entry(mem->dstr_cb_head.next, _cl_mem_dstr_cb, node);
-    list_del(&cb->node);
+    cb = list_entry(mem->dstr_cb_head.head_node.n, _cl_mem_dstr_cb, node);
+    list_node_del(&cb->node);
     cb->pfn_notify(mem, cb->user_data);
     cl_free(cb);
   }
@@ -2470,12 +2470,12 @@ cl_mem_set_destructor_callback(cl_mem memobj,
   }
 
   memset(cb, 0, sizeof(_cl_mem_dstr_cb));
-  list_init(&cb->node);
+  list_node_init(&cb->node);
   cb->pfn_notify = pfn_notify;
   cb->user_data = user_data;
 
   CL_OBJECT_LOCK(memobj);
-  list_add(&cb->node, &memobj->dstr_cb_head, memobj->dstr_cb_head.next);
+  list_add(&memobj->dstr_cb_head, &cb->node);
   CL_OBJECT_UNLOCK(memobj);
   return CL_SUCCESS;
 }
diff --git a/src/cl_mem.h b/src/cl_mem.h
index dbe4becd..43d30aa2 100644
--- a/src/cl_mem.h
+++ b/src/cl_mem.h
@@ -64,8 +64,8 @@ typedef struct _cl_mapped_ptr {
 }cl_mapped_ptr;
 
 typedef struct _cl_mem_dstr_cb {
-  list_head node;    /* Mem callback list node */
-  void (CL_CALLBACK *pfn_notify)(cl_mem memobj, void *user_data);
+  list_node node; /* Mem callback list node */
+  void(CL_CALLBACK *pfn_notify)(cl_mem memobj, void *user_data);
   void *user_data;
 } _cl_mem_dstr_cb;
 typedef _cl_mem_dstr_cb* cl_mem_dstr_cb;
diff --git a/src/cl_utils.c b/src/cl_utils.c
index 0d0a12f5..bc62feb7 100644
--- a/src/cl_utils.c
+++ b/src/cl_utils.c
@@ -18,6 +18,57 @@
 
 #include "cl_utils.h"
 #include <string.h>
+#include <assert.h>
+
+LOCAL void
+list_node_insert_before(struct list_node *node, struct list_node *the_new)
+{
+  list_node *before_node = node->p;
+  the_new->p = before_node;
+  the_new->n = node;
+  node->p = the_new;
+  before_node->n = the_new;
+}
+
+LOCAL void
+list_node_insert_after(struct list_node *node, struct list_node *the_new)
+{
+  list_node *after_node = node->n;
+  the_new->n = after_node;
+  the_new->p = node;
+  node->n = the_new;
+  after_node->p = the_new;
+}
+
+LOCAL void
+list_move(struct list_head *the_old, struct list_head *the_new)
+{
+  assert(list_empty(the_new));
+  if (list_empty(the_old)) {
+    return;
+  }
+
+  memcpy(&the_new->head_node, &the_old->head_node, sizeof(list_node));
+  the_new->head_node.n->p = &the_new->head_node;
+  the_new->head_node.p->n = &the_new->head_node;
+  list_init(the_old);
+}
+
+LOCAL void
+list_merge(struct list_head *head, struct list_head *to_merge)
+{
+  if (list_empty(to_merge))
+    return;
+
+  list_node *merge_last_node = to_merge->head_node.p;
+  list_node *merge_first_node = to_merge->head_node.n;
+
+  merge_last_node->n = &head->head_node;
+  merge_first_node->p = head->head_node.p;
+  head->head_node.p->n = merge_first_node;
+  head->head_node.p = merge_last_node;
+  list_init(to_merge);
+}
 
 LOCAL cl_int
 cl_get_info_helper(const void *src, size_t src_size, void *dst, size_t dst_size, size_t *ret_size)
diff --git a/src/cl_utils.h b/src/cl_utils.h
index 829b774b..2d242072 100644
--- a/src/cl_utils.h
+++ b/src/cl_utils.h
@@ -359,79 +359,55 @@ static INLINE int atomic_read(atomic_t *v) {
 static INLINE int atomic_inc(atomic_t *v) { return atomic_add(v, 1); }
 static INLINE int atomic_dec(atomic_t *v) { return atomic_add(v, -1); }
 
-/* The list. */
+/* Define one list node. */
+typedef struct list_node {
+  struct list_node *n;
+  struct list_node *p;
+} list_node;
 typedef struct list_head {
-  struct list_head *next, *prev;
+  list_node head_node;
 } list_head;
 
-static inline void list_init(struct list_head *head)
+static inline void list_node_init(list_node *node)
 {
-  head->next = head->prev = head;
+  node->n = node;
+  node->p = node;
 }
-static inline void list_add(struct list_head *the_new,
-                            struct list_head *prev, struct list_head *next)
+static inline int list_node_out_of_list(const struct list_node *node)
 {
-  next->prev = the_new;
-  the_new->next = next;
-  the_new->prev = prev;
-  prev->next = the_new;
+  return node->n == node;
 }
-static inline void list_add_tail(struct list_head *the_new, struct list_head *head)
+static inline void list_init(list_head *head)
 {
-  list_add(the_new, head->prev, head);
+  head->head_node.n = &head->head_node;
+  head->head_node.p = &head->head_node;
 }
-static inline void list_del(struct list_head *node)
+extern void list_node_insert_before(list_node *node, list_node *the_new);
+extern void list_node_insert_after(list_node *node, list_node *the_new);
+static inline void list_node_del(struct list_node *node)
 {
-  node->next->prev = node->prev;
-  node->prev->next = node->next;
-  node->prev = node->next = node;
+  node->n->p = node->p;
+  node->p->n = node->n;
+  /* And all point to self for safe. */
+  node->p = node;
+  node->n = node;
 }
-static inline void list_replace(struct list_head *the_old, struct list_head *the_new)
+static inline void list_add(list_head *head, list_node *the_new)
 {
-  the_new->next = the_old->next;
-  the_new->next->prev = the_new;
-  the_new->prev = the_old->prev;
-  the_new->prev->next = the_new;
+  list_node_insert_after(&head->head_node, the_new);
 }
-static inline int list_empty(const struct list_head *head)
-{
-  return head->next == head;
-}
-static inline int list_is_last(const struct list_head *list, const struct list_head *head)
-{
-  return list->next == head;
-}
-static inline void __list_splice(struct list_head *list,
-                                 struct list_head *prev, struct list_head *next)
-{
-  struct list_head *first = list->next;
-  struct list_head *last = list->prev;
-
-  first->prev = prev;
-  prev->next = first;
-
-  last->next = next;
-  next->prev = last;
-
-  list_init(list);
-}
-/**
- * list_splice - join two lists
- */
-static inline void list_splice(struct list_head *list, struct list_head *head)
+static inline void list_add_tail(list_head *head, list_node *the_new)
 {
-  if (!list_empty(list))
-    __list_splice(list, head, head->next);
+  list_node_insert_before(&head->head_node, the_new);
 }
-
-/**
- * list_splice_tail - join two lists, each list being a queue
- */
-static inline void list_splice_tail(struct list_head *list, struct list_head *head)
+static inline int list_empty(const struct list_head *head)
 {
-  if (!list_empty(list))
-    __list_splice(list, head->prev, head);
+  return head->head_node.n == &head->head_node;
 }
+/* Move the content from one head to another. */
+extern void list_move(struct list_head *the_old, struct list_head *the_new);
+/* Merge the content of the two lists to one head. */
+extern void list_merge(struct list_head *head, struct list_head *to_merge);
 
 #undef offsetof
 #ifdef __compiler_offsetof
@@ -439,17 +415,17 @@ static inline void list_splice_tail(struct list_head *list, struct list_head *he
 #else
 #define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER)
 #endif
-#define container_of(ptr, type, member) ({                      \
-      const typeof( ((type *)0)->member ) *__mptr = (ptr);      \
+#define list_entry(ptr, type, member) ({                      \
+      const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
       (type *)( (char *)__mptr - offsetof(type,member) ); })
-#define list_entry(ptr, type, member) container_of(ptr, type, member)
 
 #define list_for_each(pos, head) \
-  for (pos = (head)->next; pos != (head); pos = pos->next)
+  for (pos = (head)->head_node.n; pos != &((head)->head_node); pos = pos->n)
 
-#define list_for_each_safe(pos, n, head)                 \
-  for (pos = (head)->next, n = pos->next; pos != (head); \
-       pos = n, n = pos->next)
+#define list_for_each_safe(pos, ne, head)                                   \
+  for (pos = (head)->head_node.n, ne = pos->n; pos != &((head)->head_node); \
+       pos = ne, ne = pos->n)
 
-extern cl_int cl_get_info_helper(const void *src, size_t src_size, void *dst, size_t dst_size, size_t *ret_size);
+extern cl_int cl_get_info_helper(const void *src, size_t src_size, void *dst,
+                                 size_t dst_size, size_t *ret_size);
 #endif /* __CL_UTILS_H__ */