path: root/src/MESA_list.c

#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