diff options
Diffstat (limited to 'src/MESA_list.c')
| -rw-r--r-- | src/MESA_list.c | 472 |
1 files changed, 472 insertions, 0 deletions
diff --git a/src/MESA_list.c b/src/MESA_list.c new file mode 100644 index 0000000..8832e14 --- /dev/null +++ b/src/MESA_list.c @@ -0,0 +1,472 @@ +#include <linux/types.h>
+#include <linux/stddef.h>
+#include <assert.h>
+#include "MESA_list.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+/*************************** �ڲ�ʵ�ֽӿ� ********************************/
+
+/*
+ * Simple doubly linked list implementation.
+ *
+ * Some of the internal functions ("__xxx") are useful when
+ * manipulating whole lists rather than single entries, as
+ * sometimes we already know the next/prev entries and we can
+ * generate better code by using them directly rather than
+ * using the generic single-entry routines.
+ */
+
+static void INIT_LIST_HEAD(struct list_index *head)
+{
+ head->nextele = head;
+ head->preele = head;
+}
+
+
+/*
+ * Insert a new entry between two known consecutive entries.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_add(struct list_index *new_list,
+ struct list_index *prev,
+ struct list_index *next)
+{
+ next->preele = new_list;
+ new_list->nextele = next;
+ new_list->preele = prev;
+ prev->nextele = new_list;
+}
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ * lijia comment: list_add()���½ڵ����head��head->next֮��.
+ */
+void list_add(struct list_index *new_list, struct list_index *head)
+{
+ __list_add(new_list, head, head->nextele);
+}
+
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ * lijia comment: list_add_tail()���½ڵ����head��head->prev֮��.
+ */
+void list_add_tail(struct list_index *new_list, struct list_index *head)
+{
+ __list_add(new_list, head->preele, head);
+}
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_del(struct list_index * prev, struct list_index * next)
+{
+ next->preele = prev;
+ prev->nextele = next;
+}
+
+static inline void __list_del_entry(struct list_index *entry)
+{
+ __list_del(entry->preele, entry->nextele);
+ entry->nextele = NULL;
+ entry->preele = NULL;
+}
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty() on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+
+static void list_del(struct list_index *entry)
+{
+ __list_del(entry->preele, entry->nextele);
+ entry->nextele = NULL;
+ entry->preele = NULL;
+}
+
+
+/**
+ * list_move - delete from one list and add as another's head
+ * @list: the entry to move
+ * @head: the head that will precede our entry
+ */
+static void list_move(struct list_index *list, struct list_index *head)
+{
+ __list_del_entry(list);
+ list_add(list, head);
+}
+
+/**
+ * list_move_tail - delete from one list and add as another's tail
+ * @list: the entry to move
+ * @head: the head that will follow our entry
+ */
+static void list_move_tail(struct list_index *list, struct list_index *head)
+{
+ __list_del_entry(list);
+ list_add_tail(list, head);
+}
+
+#if 0
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static int list_empty(const struct list_index *head)
+{
+ return head->nextele == head;
+}
+#endif
+
+/**
+ * list_empty_careful - tests whether a list is empty and not being modified
+ * @head: the list to test
+ *
+ * Description:
+ * tests whether a list is empty _and_ checks that no other CPU might be
+ * in the process of modifying either member (next or prev)
+ *
+ * NOTE: using list_empty_careful() without synchronization
+ * can only be safe if the only activity that can happen
+ * to the list entry is list_del_init(). Eg. it cannot be used
+ * if another CPU could re-list_add() it.
+ */
+static int list_empty_careful(const struct list_index *head)
+{
+ MESA_queue_head_t *next = head->nextele;
+ return (next == head) && (next == head->preele);
+}
+
+static inline void list_count_init(void **list_count)
+{
+ long *p_c = (long *)list_count;
+ *p_c = 0;
+}
+
+static inline void list_count_inc(void **list_count)
+{
+ long *p_c = (long *)list_count;
+ long c = *p_c;
+ *p_c = c + 1;
+}
+
+static inline void list_count_dec(void **list_count)
+{
+ long *p_c = (long *)list_count;
+ long c = *p_c;
+ *p_c = c - 1;
+}
+
+#if MESA_LIST_CHECK != 0
+/*Function:Check the intergrity of the list,to dectect memory mess.
+*Input: Queue Head,data check call back function
+*Output: return a number below zero,if the queue got a problem,else return 0;
+*Author:[email protected] at 20100913
+*/
+#if 0
+static int MESA_q_list_check(const MESA_queue_head_t *qhead_obj,int(*quiddity_check)(const void *))
+{
+ MESA_list_index_t *p=NULL, *head=NULL;
+// int linked_ele_number=0;
+ int ret=0;
+// return 0;
+ if(qhead_obj->listcount==0)
+ {
+ if(qhead_obj->head!=NULL||qhead_obj->head!=NULL)
+ {
+ ret=-1;
+ }
+ goto exit;
+ }
+
+ if(qhead_obj->head==NULL||qhead_obj->tail==NULL)
+ {
+ ret=-2;
+ goto exit;
+ }
+ if(qhead_obj->listcount>1){
+ if(qhead_obj->head->preele!=NULL||qhead_obj->head->nextele==NULL)
+ {
+ ret=-3;
+ goto exit;
+ }
+ if(qhead_obj->tail->preele==NULL||qhead_obj->tail->nextele!=NULL)
+ {
+ ret=-4;
+ goto exit;
+ }
+
+ head = p = qhead_obj->head;
+ p = p->nextele;
+ while(p != head)
+ {
+ if(p == NULL) break;
+ if(p == head){
+ ret = -5; /* has a cycle */
+ goto exit;
+ }
+ p = p->nextele;
+ }
+ }
+ /*
+ pre=qhead_obj->head;
+ p=pre->nextele;
+ while(p!=NULL){
+ linked_ele_number++;
+
+ //Is the declared size equal to element linked number;
+ if(linked_ele_number > qhead_obj->listcount)
+ {
+ ret=-5;
+ goto exit;
+ }
+
+ //Is element's preele pointer equal to its preele
+ if(pre!=p->preele)
+ {
+ ret=-6;
+ goto exit;
+ }
+ if(quiddity_check!=NULL){
+ if(0>quiddity_check(p->quiddity))
+ {
+ ret =-7;
+ goto exit;
+ }
+ }
+ pre=p;
+ p=p->nextele;
+ }
+ //Is the last element equal to tail
+ if(pre!=qhead_obj->tail)
+ {
+ ret=-8;
+ goto exit;
+ }
+ if(linked_ele_number !=qhead_obj->listcount-1)
+ {
+ ret=-9;
+ goto exit;
+ }
+ */
+exit:
+ if(ret<0)
+ {
+ return ret;
+ }
+ else
+ {
+ return 1;
+ }
+
+}
+#endif
+
+#if 2==MESA_LIST_CHECK
+/*Simple check,not raversal*/
+static int MESA_q_is_item_in_list(MESA_queue_head_t *qhead_obj, MESA_list_index_t *lindex_obj){
+// MESA_list_index_t* pre=lindex_obj->preele;
+// MESA_list_index_t*next=lindex_obj->nextele;
+ MESA_list_index_t*p=NULL;
+ int i, num;
+
+ if(list_empty_careful(qhead_obj)){
+ return 0;
+ }
+
+ p = qhead_obj->nextele;
+ num = MESA_get_list_count(qhead_obj);
+ i = 0;
+ while((p != qhead_obj) && (i <= num))
+ {
+ if(p == lindex_obj)
+ {
+ return 1;
+ }
+ p=p->nextele;
+ i++;
+ }
+
+ return 0;
+
+}
+#endif
+
+/*every MESA_list_index_t leaves list,its pre and next will be set NULL
+ * In Configuration Transmiiter project, not null element will consider in list,
+ * pre and next is NULL only if there's one element in list only*/
+static int MESA_q_is_item_in_list_quick(MESA_queue_head_t *qhead_obj, MESA_list_index_t *lindex_obj)
+{
+ //empty list
+ if(list_empty_careful(qhead_obj)){
+ return 0;
+ }
+
+ //have more element
+ if(lindex_obj->nextele==NULL || lindex_obj->preele==NULL){
+ return 0;
+ }
+ if(lindex_obj->nextele->preele != lindex_obj){
+ return 0;
+ }
+ if(lindex_obj->preele->nextele != lindex_obj){
+ return 0;
+ }
+
+ return 1;
+
+}
+#endif
+
+/*************************** �ⲿ���ýӿ� ********************************/
+
+
+/*
+ ��һ��ʹ��MESA_listģ��ʱ��������ô˳�ʼ��ģ��.
+*/
+int MESA_list_init(MESA_queue_head_t *head)
+{
+ INIT_LIST_HEAD(head);
+ list_count_init(&head->quiddity);
+ return 0;
+}
+
+/* ��Ϊheadʹ��ʱ, "quiddity"��Ϊһ��long�ͱ���,���ڴ洢����Ԫ������ */
+long MESA_get_list_count(const MESA_queue_head_t *head)
+{
+ return (long)head->quiddity;
+}
+
+MESA_list_index_t *MESA_q_read_head(const MESA_queue_head_t *qhead_obj)
+{
+ if(list_empty_careful(qhead_obj)){
+ return NULL;
+ }
+ return qhead_obj->nextele;
+}
+
+
+MESA_list_index_t *MESA_q_get_head(MESA_queue_head_t *qhead_obj)
+{
+ MESA_list_index_t *out;
+ if(list_empty_careful(qhead_obj)){
+ return NULL;
+ }
+ out = qhead_obj->nextele;
+ list_del(out);
+ list_count_dec(&qhead_obj->quiddity);
+
+ return out;
+}
+
+MESA_list_index_t *MESA_q_get_tail(MESA_queue_head_t *qhead_obj)
+{
+ MESA_list_index_t *out;
+ if(list_empty_careful(qhead_obj)){
+ return NULL;
+ }
+ out = qhead_obj->preele;
+ list_del(out);
+ list_count_dec(&qhead_obj->quiddity);
+
+ return out;
+}
+
+MESA_list_index_t *MESA_q_join_tail(MESA_queue_head_t *qhead_obj, MESA_list_index_t *lindex_obj)
+{
+ list_add_tail(lindex_obj, qhead_obj);
+ list_count_inc(&qhead_obj->quiddity);
+
+ return lindex_obj;
+}
+
+MESA_list_index_t *MESA_q_join_head(MESA_queue_head_t *qhead_obj, MESA_list_index_t *lindex_obj)
+{
+ list_add(lindex_obj, qhead_obj);
+ list_count_inc(&qhead_obj->quiddity);
+
+ return lindex_obj;
+}
+
+MESA_list_index_t *MESA_q_leave_list(MESA_queue_head_t *qhead_obj, MESA_list_index_t *lindex_obj)
+{
+#if 1==MESA_LIST_CHECK
+ if(0 == MESA_q_is_item_in_list_quick(qhead_obj, lindex_obj)){
+ //return NULL;
+ assert(0); //critical
+ }
+#elif 2==MESA_LIST_CHECK
+ if(0 == MESA_q_is_item_in_list(qhead_obj, lindex_obj)){
+ //return NULL;
+ assert(0); //critical
+ }
+#endif
+ list_del(lindex_obj);
+ list_count_dec(&qhead_obj->quiddity);
+
+ return lindex_obj;
+}
+
+MESA_list_index_t *MESA_q_move_head(MESA_queue_head_t *qhead_obj, MESA_list_index_t *lindex_obj)
+{
+#if 1==MESA_LIST_CHECK
+ if(0 == MESA_q_is_item_in_list_quick(qhead_obj, lindex_obj)){
+ //return NULL;
+ assert(0); //critical
+ }
+#elif 2==MESA_LIST_CHECK
+ if(0 == MESA_q_is_item_in_list(qhead_obj, lindex_obj)){
+ //return NULL;
+ assert(0); //critical
+ }
+#endif
+ list_move(lindex_obj, qhead_obj);
+
+ return lindex_obj;
+}
+
+MESA_list_index_t *MESA_q_move_tail(MESA_queue_head_t *qhead_obj, MESA_list_index_t *lindex_obj)
+{
+#if 1==MESA_LIST_CHECK
+ if(0 == MESA_q_is_item_in_list_quick(qhead_obj,lindex_obj)){
+ //return NULL;
+ assert(0); //critical
+ }
+#elif 2==MESA_LIST_CHECK
+ if(0 == MESA_q_is_item_in_list(qhead_obj, lindex_obj)){
+ //return NULL;
+ assert(0); //critical
+ }
+#endif
+ list_move_tail(lindex_obj, qhead_obj);
+
+ return lindex_obj;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+
|