user mode용 list.h
http://www.mcs.anl.gov/~kazutomo/list/list.h
/**
*
* I grub it from linux kernel source code and fix it for user space
* program. Of course, this is a GPL licensed header file.
*
* Here is a recipe to cook list.h for user space program
*
* 1. copy list.h from linux/include/list.h
* 2. remove
* - #ifdef __KERNE__ and its #endif
* - all #include line
* - prefetch() and rcu related functions
* 3. add macro offsetof() and container_of
*
* - kazutomo@mcs.anl.gov
*/
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
/**
* @name from other kernel headers
*/
/*@{*/
/**
* Get offset of a member
*/
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
/**
* Casts a member of a structure out to the containing structure
* @param ptr the pointer to the member.
* @param type the type of the container struct this is embedded in.
* @param member the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
/*@}*/
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)
/**
* 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.
*/
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
/*
* 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_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/**
* 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.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/**
* 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.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, 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_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/**
* 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 inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
/**
* 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 inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
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 inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
static inline void __list_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head);
INIT_LIST_HEAD(list);
}
}
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); \
pos = pos->next)
/**
* __list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*
* This variant differs from list_for_each() in that it's the
* simplest possible list iteration code, no prefetching is done.
* Use this for code that knows the list to be very short (empty
* or 1 entry) most of the time.
*/
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
pos = pos->prev)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop counter.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop counter.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_reverse - iterate backwards over list of given type.
* @pos: the type * to use as a loop counter.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
/**
* list_prepare_entry - prepare a pos entry for use as a start point in
* list_for_each_entry_continue
* @pos: the type * to use as a start point
* @head: the head of the list
* @member: the name of the list_struct within the struct.
*/
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
/**
* list_for_each_entry_continue - iterate over list of given type
* continuing after existing point
* @pos: the type * to use as a loop counter.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_continue(pos, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop counter.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_continue - iterate over list of given type
* continuing after existing point safe against removal of list entry
* @pos: the type * to use as a loop counter.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe_continue(pos, n, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
* removal of list entry
* @pos: the type * to use as a loop counter.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe_reverse(pos, n, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member), \
n = list_entry(pos->member.prev, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.prev, typeof(*n), member))
/*
* Double linked lists with a single pointer list head.
* Mostly useful for hash tables where the two pointer list head is
* too wasteful.
* You lose the ability to access the tail in O(1).
*/
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
static inline int hlist_unhashed(const struct hlist_node *h)
{
return !h->pprev;
}
static inline int hlist_empty(const struct hlist_head *h)
{
return !h->first;
}
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}
static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n);
n->next = LIST_POISON1;
n->pprev = LIST_POISON2;
}
static inline void hlist_del_init(struct hlist_node *n)
{
if (n->pprev) {
__hlist_del(n);
INIT_HLIST_NODE(n);
}
}
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
{
n->pprev = next->pprev;
n->next = next;
next->pprev = &n->next;
*(n->pprev) = n;
}
static inline void hlist_add_after(struct hlist_node *n,
struct hlist_node *next)
{
next->next = n->next;
n->next = next;
next->pprev = &n->next;
if(next->next)
next->next->pprev = &next->next;
}
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
pos = pos->next)
#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
pos = n)
/**
* hlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop counter.
* @pos: the &struct hlist_node to use as a loop counter.
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry(tpos, pos, head, member) \
for (pos = (head)->first; \
pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
/**
* hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
* @tpos: the type * to use as a loop counter.
* @pos: the &struct hlist_node to use as a loop counter.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_continue(tpos, pos, member) \
for (pos = (pos)->next; \
pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
/**
* hlist_for_each_entry_from - iterate over a hlist continuing from existing point
* @tpos: the type * to use as a loop counter.
* @pos: the &struct hlist_node to use as a loop counter.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_from(tpos, pos, member) \
for (; pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
/**
* hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @tpos: the type * to use as a loop counter.
* @pos: the &struct hlist_node to use as a loop counter.
* @n: another &struct hlist_node to use as temporary storage
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
for (pos = (head)->first; \
pos && ({ n = pos->next; 1; }) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = n)
#endifhttp://pages.cs.wisc.edu/~swift/classes/cs537-fa07/Projects/P3/list-sample.c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
//
// Define a data structure that contains a list_head
//
typedef struct queue_s {
struct list_head next;
int data;
} queue_t;
//
// Define a list of structures
//
struct list_head request_q;
//
// Add an element to the end of the list, so it will be the last one popped
//
queue_t * queue_add_fifo(int data)
{
queue_t * next;
next = (queue_t *) malloc(sizeof(queue_t));
next->data = data;
//
// Add to the tail for FIFO queueing
//
list_add_tail(&next->next, &request_q );
return(next);
}
//
// Add an element to the head of the list, so it will be the next one popped
//
queue_t * queue_add_lifo(int data)
{
queue_t * next;
next = (queue_t *) malloc(sizeof(queue_t));
next->data = data;
//
// Add to the head for LIFO (stack) queueing
//
list_add(&next->next, &request_q );
return(next);
}
//
// Pop an element off the head of the queue
//
queue_t * queue_pop(void)
{
//
// Check if the queue is empty
//
if (!list_empty(&request_q)) {
queue_t * next;
//
// Get the first entry on the list. This is the one that request_q.next points to.
//
next = list_entry(request_q.next,queue_t,next);
list_del(&next->next);
return(next);
} else {
return(NULL);
}
}
//
// Pop an element off the tail of the queue
//
queue_t * queue_pop_tail(void)
{
//
// Check if the queue is empty
//
if (!list_empty(&request_q)) {
queue_t * next;
//
// Get the last entry on the list. This is the one that request_q.prev points to.
//
next = list_entry(request_q.prev,queue_t,next);
list_del(&next->next);
return(next);
} else {
return(NULL);
}
}
//
// Find the first entry in the list with a matching data value
//
queue_t * find_queue_entry(int data)
{
struct list_head * next;
//
// Iterate over the list
//
list_for_each(next, &request_q) {
queue_t * elem;
//
// Get a pointer to the element on the list
//
elem = list_entry(next, queue_t, next);
if (elem->data == data) {
return(elem);
}
}
return(NULL);
}
//
// Delete all entries from the queue that match the data value
//
void del_queue_entry(int data)
{
struct list_head * next;
struct list_head * temp;
//
// Iterate over the list. We need to use the safe iterator because we may want to
// remove things.
//
list_for_each_safe(next, temp, &request_q) {
queue_t * elem;
//
// Get a pointer to the element on the list
//
elem = list_entry(next, queue_t, next);
//
// Delete the element if the data field matches
//
if (elem->data == data) {
list_del(&elem->next);
}
}
}
void print_queue(void)
{
struct list_head * next;
//
// Iterate over the list
//
printf("Queue:\n");
list_for_each(next, &request_q) {
queue_t * elem;
//
// Get a pointer to the element on the list
//
elem = list_entry(next, queue_t, next);
printf("\t%d\n",elem->data);
}
}
int main(int argc, char * argv[])
{
INIT_LIST_HEAD(&request_q);
queue_t * elem;
queue_add_fifo(1);
queue_add_fifo(2);
queue_add_fifo(3);
queue_add_fifo(4);
queue_add_fifo(5);
printf("Should be 1,2,3,4,5\n");
print_queue();
elem =queue_pop(); // should be 1
printf("Should be 1: %d\n",elem->data);
elem = queue_pop_tail();
printf("Should be 5: %d\n",elem->data);
printf("Should be 2,3,4\n");
print_queue();
queue_pop();
queue_pop();
queue_pop();
printf("Should be empty\n");
print_queue();
queue_add_lifo(10);
queue_add_lifo(20);
queue_add_lifo(30);
queue_add_lifo(40);
printf("Should be 40,30,20,10\n");
print_queue();
elem = find_queue_entry(20);
printf("Should be non-NULL: %p\n",elem);
elem = find_queue_entry(50);
printf("Should be NULL: %p\n",elem);
del_queue_entry(20);
printf("Should be 40,30,10\n");
print_queue();
del_queue_entry(40);
del_queue_entry(10);
del_queue_entry(30);
printf("Should be empty\n");
print_queue();
}http://www.mcs.anl.gov/~kazutomo/list/
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct a_list
{
struct list_head list;
int val;
const char* str;
};
static void append(struct a_list* ptr,const char* str, int val)
{
struct a_list* tmp;
tmp = (struct a_list*)malloc(sizeof(struct a_list));
if(!tmp) {
perror("malloc");
exit(1);
}
tmp->str = str;
tmp->val = val;
list_add_tail( &(tmp->list), &(ptr->list) );
}
int main()
{
struct a_list blist;
struct a_list* iter;
INIT_LIST_HEAD(&blist.list);
/* add item to list */
append(&blist, "NM", 87501);
append(&blist, "CA", 94041);
append(&blist, "IL", 60561);
/* iterates list */
list_for_each_entry(iter,&blist.list,list) {
printf("%s %d\n", iter->str, iter->val);
}
/* remove all items in the list */
while( !list_empty(&blist.list) ) {
iter = list_entry(blist.list.next,struct a_list,list);
list_del(&iter->list);
free(iter);
}
return 0;
}
Posted by 칠두지룡
