list.h

包括ＥＰＡ协议栈

/*------------------------------------------------------------------------------*
 *- Tail pointer cycle list
 *------------------------------
 *- This list has a tructure as below:
 *-                                                        ┌───────┐
 *-                                                        │  hdr  │
 *-                                                        └───┬───┘
 *-        0            1            2            3           4│
 *-    ┌───────┐    ┌───────┐    ┌───────┐    ┌───────┐    ┌───────┐
 *- ┌─>│ head  │ -> │  2nd  │ -> │  3rd  │ -> │  ...  │ -> │ tail  │─┐
 *- │  └───────┘    └───────┘    └───────┘    └───────┘    └───────┘ │
 *- └────────────────────────────────────────────────────────────────┘
 *- Position of node in list is assumpt to be start with 0.
 *- Example: position of head node is 0, and is 4 of tail node.
 *- Each node has a 32-bit tag, and the list is organised as rising-order of tag.
 *- There is also a 32-bit id for each node, which is unique in list.
 *------------------------------------------------------------------------------*/

#ifndef _List_H
#define _List_H

#include "global.h"

#define LIST_ENTRY(NODE, TYPE, MEMBER)  (TYPE*)((char*)NODE - (unsigned int)(&(((TYPE*)0)->MEMBER)))
#define LIST_INIT(HDR)                  (HDR).tag = 0;(HDR).id = 1;(HDR).next = 0
#define LIST_HEAD(HDR)                  (((HDR).next)->next)
#define LIST_TAIL(HDR)                  ((HDR).next)
#define LIST_CNT(HDR)                   ((HDR).tag)
#define LIST_IS_EMPTY(HDR)              (!((HDR).tag))

typedef struct Linker {
	struct Linker* next;
	uint32         tag;
	uint32         id;
} Foo, *PFoo;

/*------------------------------------------------------------------------------*
 *- Function name: SeekID
 *- Parameter: phdr, destignate a list to be seeked
 *-            id, id of a node to be find in list
 *-            pos, when seek finished, pos gives position of node in the list
 *- Return value: Pointer of destignate node
 *- Brief: Seek an node which has same id with the given, search order is:
 *-        head->...->tail. Position of node in list start with 0.
 *------------------------------------------------------------------------------*/
__inline PFoo SeekID(PFoo phdr, uint32 id, uint32* pos) {
	uint32 idx = 0;
	
	phdr = phdr->next;
	while(idx < phdr->tag) {
		phdr = phdr->next;
		idx += 1;
		if(phdr->id == id) {
			*pos = idx;
			return (phdr);
		}
	}
	return (0);
}

/*------------------------------------------------------------------------------*
 *- Function name: SeekTag
 *- Parameter: phdr, destignate a list to be seeked
 *-            tag, tag of a node to be find in list
 *-            pos, when seek finished, pos gives position of node in the list
 *- Return value: Pointer of destignate node
 *- Brief: Seek the first node which has same tag with the given, search order is:
 *-        head->...->tail. Position of node in list start with 0.
 *------------------------------------------------------------------------------*/
__inline PFoo SeekTag(PFoo phdr, uint32 tag, uint32* pos) {
	uint32 idx = 0;
	
	phdr = phdr->next;
	while(idx < phdr->tag) {
		phdr = phdr->next;
		idx += 1;
		if(phdr->tag == tag) {
			*pos = idx;
			return (phdr);
		}
	}
	return (0);
}

/*------------------------------------------------------------------------------*
 *- Function name: SeekNextTag
 *- Parameter: phdr, destignate a node to start seek
 *-            tag, tag of a node to be find in list
 *-            cnt, how many node to be seek
 *-            pos, when seek finished, pos gives offset of node from given
 *- Return value: Pointer of destignate node
 *- Brief: Seek the next node which has same tag with the given after specified
 *         node, search order is: the one after given node->...->given.
 *-        Position of node in list start with 0.
 *------------------------------------------------------------------------------*/
__inline PFoo SeekNextTag(PFoo phdr, uint32 tag, uint32 cnt, uint32* pos) {
	uint32 idx = 0;
	
	while(idx < cnt) {
		phdr = phdr->next;
		idx += 1;
		if(phdr->tag == tag) {
			*pos = idx;
			return (phdr);
		}
	}
	return (0);
}

/*------------------------------------------------------------------------------*
 *- Function name: Push
 *- Parameter: phdr, destignate a list to push a node
 *-            pnode, pointer of node to be push into list
 *-            tag, tag to be given to the added node
 *- Return value: id of the pushed node
 *- Brief: Push a node to the tail of list
 *------------------------------------------------------------------------------*/
__inline uint32 Push(PFoo phdr, PFoo pnode, uint32 tag) {
	PFoo ptr;
	
	ptr = phdr->next;
	if(ptr) {
		pnode->next = ptr->next;
		ptr->next = pnode;
	}
	else {
		pnode->next = pnode;
	}
	phdr->next = pnode;
	phdr->tag += 1;
	phdr->id += 2;
	pnode->tag = tag;
	pnode->id = phdr->id;
	return (phdr->id);
}

/*------------------------------------------------------------------------------*
 *- Function name: Pop
 *- Parameter: phdr, destignate a list to pop a node
 *- Return value: pointer of poped node
 *- Brief: Pop a node from head of list
 *------------------------------------------------------------------------------*/
__inline PFoo Pop(PFoo phdr) {
	PFoo tail, head;
	
	tail = phdr->next;
	if(phdr->tag < 2) {
		phdr->next = 0;
		phdr->tag -= 1;
		return (tail);
	}
	else {
		head = tail->next;
		tail->next = head->next;
		phdr->tag -= 1;
		return (head);
	}
}

/*------------------------------------------------------------------------------*
 *- Function name: InsertAt
 *- Parameter: phdr, destignate a list to insert a node
 *-            pnode, pointer of node to be push into list
 *-            pos, where to insert the node
 *-            tag, tag to be given to the added node
 *- Return value: id of inserted node if insert succeed. Otherwise return 0.
 *- Brief: Insert a node into list at given position. If pos is 0, node is insert
 *-        as head, and if pos == current number of node in list, node is insert
 *-        as tail. pos 
 *------------------------------------------------------------------------------*/
__inline uint32 InsertAt(PFoo phdr, PFoo pnode, uint32 pos, uint32 tag) {
	PFoo ptr;
	
	if(pos > phdr->tag) {
		return (0);
	}
	ptr = phdr->next;
	phdr->next = (pos == phdr->tag ? pnode : phdr->next);
	while(pos) {
		ptr = ptr->next;
		pos -= 1;
	}
	if(ptr) {
		pnode->next = ptr->next;
		ptr->next = pnode;
	}
	else {
		pnode->next = pnode;
	}
	phdr->tag += 1;
	phdr->id += 2;
	pnode->tag = tag;
	pnode->id = phdr->id;
	return (phdr->id);
}

/*------------------------------------------------------------------------------*
 *- Function name: DeletAt
 *- Parameter: phdr, destignate a list to delete a node
 *-            pos, position of node to delete
 *- Return value: pointer of deleted node if succeed. Otherwise return 0.
 *- Brief: Delete a node in list at given position. If pos is 0, head node is
 *-        delete, and if pos == current number of node in list, tail is delete.
 *------------------------------------------------------------------------------*/
__inline PFoo DeleteAt(PFoo phdr, uint32 pos) {
	PFoo p1, p2;
	
	if(pos >= phdr->tag) {
		return (0);
	}
	p1 = phdr->next;
	while(pos) {
		p1 = p1->next;
		pos -= 1;
	}
	p2 = p1->next;
	phdr->next = (p2 == phdr->next ?  p1 : phdr->next);
	phdr->tag -= 1;
	return (p2);
}

/*------------------------------------------------------------------------------*
 *- Function name: InsertByTag
 *- Parameter: phdr, destignate a list to insert a node
 *-            pnode, node to insert
 *-            tag, tag to be given to the added node
 *- Return value: pointer of deleted node if succeed. Otherwise return 0.
 *- Brief: Insert a node into list. Node will be insert just before the first
 *-        node, whose tag is larger than given, from beginning.
 *------------------------------------------------------------------------------*/
__inline uint32 InsertByTag(PFoo phdr, PFoo pnode, uint32 tag) {
	PFoo   ptr;
		
	ptr = phdr->next;
	if(ptr == 0) {
		phdr->next = pnode;
		pnode->next = pnode;
		phdr->tag += 1;
		pnode->tag = tag;
		phdr->id += 2;
		pnode->id = phdr->id;
		return (phdr->id);
	}
	if(tag >= ptr->tag) {
		phdr->next = pnode;
		pnode->next = ptr->next;
		ptr->next = pnode;
		phdr->tag += 1;
		pnode->tag = tag;
		phdr->id += 2;
		pnode->id = phdr->id;
		return (phdr->id);
	}
	else {
		while(tag > ptr->next->tag) {
			ptr = ptr->next;
		}
		pnode->next = ptr->next;
		ptr->next = pnode;
		phdr->tag += 1;
		pnode->tag = tag;
		phdr->id += 2;
		pnode->id = phdr->id;
		return (phdr->id);
	}
}

/*------------------------------------------------------------------------------*
 *- Function name: InsertByTag
 *- Parameter: phdr, destignate a list to insert a node
 *-            pnode, node to insert
 *-            tag, tag to be given to the added node
 *- Return value: pointer of deleted node if succeed. Otherwise return 0.
 *- Brief: Insert a node into list. Node will be insert just before the first
 *-        node, whose tag is larger than given, from beginning.
 *------------------------------------------------------------------------------*/
__inline PFoo DeleteByID(PFoo phdr, uint32 id) {
	PFoo   ptr1, ptr2;
	uint32 idx;
	
	idx = phdr->tag;
	ptr1 = phdr->next;
	while(idx > 1) {
		if(ptr1->next->id == id) {
			ptr2 = ptr1->next;
			ptr1->next = ptr2->next;
			if(ptr2 == phdr->next) {
				phdr->next = ptr1;
			}
			phdr->tag -= 1;
			return (ptr2);
		}
		idx--;
		ptr1 = ptr1->next;
	}
	return ((PFoo)0);
}

/*------------------------------------------------------------------------------*
 *- Function name: InsertBehind
 *- Parameter: phdr, destignate a list to insert a node
 *-            pformer, behind which node to insert
 *-            pnode, node to insert
 *-            tag, tag to be given to the added node
 *-            btail, is insert node the of new tail of list
 *- Return value: pointer of deleted node if succeed. Otherwise return 0.
 *- Brief: Insert a node into list just behind given one. And list head pointer
 *-        will be adjust to the inserted node if btail is true.
 *------------------------------------------------------------------------------*/
__inline uint32 InsertBehind(PFoo phdr, PFoo pformer, PFoo pnode, uint32 tag, uint8 btail) {
		
	pnode->next = pformer->next;
	pformer->next = pnode;
	phdr->tag += 1;
	pnode->tag = tag;
	phdr->id += 2;
	pnode->id = phdr->id;
	if(btail) {
		phdr->next = pnode;
	}
	return (phdr->id);
}

#endif	// _List_H