list.c

mobile ip 在linux下的一种实现

/* $Id: list.c,v 1.23 2001/02/16 18:27:22 jm Exp $
 * Efficient list module, functions do not need any memory allocations
 *
 * Dynamic hierarchial IP tunnel
 * Copyright (C) 1998-2001, Dynamics group
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation. See README and COPYING for
 * more details.
 */

#include <stdlib.h>
#include <assert.h>

#define DEBUG_FLAG 'L'

/* Uncommend the following if you want the list functions to verify that
 * a node isn't added twice or removed twice
 */

#define LIST_ADDITIONAL_VERIFICATIONS

#include "debug.h"
#include "list.h"

/* defines */

#define ASSERT assert

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

#define HEXFMT "0x%p"
#if 0
#define INTFMT "%ld"
#endif
#define INTFMT "%d"

/******************************************************************************
 *
 * WARNING & NOTE!
 *
 * This is a very fast and efficient list module. These functions are very
 * simple and fast, but they have no way to verify the sanity of the input
 * values. The use of this module is simple, but the user has to keep in mind
 * the following rules:
 *
 * - Every list structure must be initialized before use => list_init()
 * - Every node structure must be initialized (once) => list_init_node()
 * - Initializing an already used list or node structure is not allowed.
 * - Each node structure is used to link the structure onto the list.
 * - Don't add any node structure twice without removing it on the same list.
 * - Don't use the same node structure to add a structure already on another
 *   list to another.
 * - Don't remove a node from list twice
 * - Very low-level list implementation
 * - => Checking that parameters are valid is not possible
 * - => You must be careful when using the module
 * - Meant for low-level purpose
 * - => Impossible to fail if the parameters are valid
 * - Clearly invalid parameters will cause assertions to fail
 *
 *****************************************************************************/

/* "Mxx" are test case IDs to help in the design of the test module */

/* Initialize a list structure
 *
 * INPUT VALUES:
 *
 * M01) all the list structures are handled the same way
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 *
 */

/**
 * list_init:
 * @list: 
 * 
 * Initialize a list structure
 */
void list_init(struct list *list)
{
	/* DEBUG(DEBUG_FLAG, "list_init, list = " HEXFMT "\n", list); */
	ASSERT(list != NULL);
	list->head = (struct node *) &list->tail;
	list->tail = NULL;
	list->tailpred = (struct node *) &list->head;
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
}

/* Initialize a node structure
 *
 * INPUT VALUES:
 *
 * M02) all the node structures are handled the same way
 *    ) ILLEGAL: node is a null pointer (no test case will be done)
 *
 */

/**
 * list_init_node:
 * @node: 
 * 
 * Initialize a node structure.
 */
void list_init_node(struct node *node)
{
	DEBUG(DEBUG_FLAG, "list_init_node, node = " HEXFMT "\n", node);
	ASSERT(node != NULL);
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	node->succ = NULL;
	node->pred = NULL;
#endif
}

/* Add a node to the beginning of the list
 *
 * INPUT VALUES:
 *
 * M03) List is empty
 * M04) List is not empty
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 *    ) ILLEGAL: node is a null pointer (no test case will be done)
 */

/**
 * list_add_head:
 * @list: 
 * @node: 
 * 
 * Add a node to the beginning of the list.
 */
void list_add_head(struct list *list, struct node *node)
{
	DEBUG(DEBUG_FLAG,
	      "list_add_head, list = " HEXFMT ", node = " HEXFMT "\n",
	      list, node);
	ASSERT(list != NULL);
	ASSERT(node != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	ASSERT(node->succ == NULL);
	ASSERT(node->pred == NULL);
#endif
	list_insert(list, node, NULL);
	ASSERT(list->head == node);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
	ASSERT(node->succ != NULL);
	ASSERT(node->pred == (struct node *) &list->head);
}

/* Add a node to the end of the list
 *
 * INPUT VALUES:
 *
 * M05) List is empty
 * M06) List is not empty
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 *    ) ILLEGAL: node is a null pointer (no test case will be done)
 */

/**
 * list_add_tail:
 * @list: 
 * @node: 
 * 
 * Add a node to the end of the list.
 */
void list_add_tail(struct list *list, struct node *node)
{
	DEBUG(DEBUG_FLAG, "list_add_tail, list = " HEXFMT ", node = " HEXFMT
	      "\n", list, node);
	ASSERT(list != NULL);
	ASSERT(node != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	ASSERT(node->succ == NULL);
	ASSERT(node->pred == NULL);
#endif
	list_insert(list, node, list->tailpred);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred == node);
	ASSERT(node->succ == (struct node *) &list->tail);
	ASSERT(node->pred != NULL);
}

/* Insert the node AFTER the specified node on the list
 *
 * INPUT VALUES:
 *
 * M07) Listnode is NULL, use list_add_head()
 * M08) Listnode is a valid node
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 *    ) ILLEGAL: node is a null pointer (no test case will be done)
 */

/**
 * list_insert:
 * @list: 
 * @node: 
 * @listnode: 
 * 
 * Insert the node AFTER the specified node on the list.
 */
void list_insert(struct list *list, struct node *node, struct node *listnode)
{
	DEBUG(DEBUG_FLAG,
	      "list_insert, list = " HEXFMT ", node = " HEXFMT ", listnode = "
	      HEXFMT "\n", list, node, listnode);
	ASSERT(node != NULL);
	ASSERT(list != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	ASSERT(node->succ == NULL);
	ASSERT(node->pred == NULL);
#endif
	if (listnode == NULL) {
		DEBUG(DEBUG_FLAG,
		      "list_insert: listnode == NULL -> list_add_head\n");
		node->succ = list->head;
		node->pred = (struct node *) &list->head;
		list->head = node;
		node->succ->pred = node;
		return;
	}
	ASSERT(listnode->succ != NULL);
	node->succ = listnode->succ;
	node->pred = listnode;
	listnode->succ = node;
	node->succ->pred = node;
	ASSERT(node->succ != NULL);
	ASSERT(node->pred == listnode);
	ASSERT(node->pred->succ == node);
	ASSERT(node->succ->pred == node);
}

#if 0
/* list_enqueue - insert node with priority */

void list_enqueue(struct list *list, struct node *node)
{
	struct node *temp;

	DEBUG(DEBUG_FLAG, "enqueue_node, list = " HEXFMT ", node = " HEXFMT
	      ", priority = " INTFMT "\n", list, node, node->pri);
	ASSERT(list != NULL);
	ASSERT(node != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
	temp = list->tailpred;
	while(temp->pred != NULL) {
		if (temp->pri <= node->pri) {
			ASSERT(temp->succ != NULL);
			list_insert(list, node, temp);
			return;
		}
	}
	ASSERT(temp == (struct node *) &list->head);
	list_insert(list, node, NULL);
}
#endif

/* Get the first node in the list, NULL if empty
 *
 * See list_remove_first() for more details about the return value.
 *
 * INPUT VALUES:
 *
 * M09) List is empty
 * M10) List is not empty
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 */

/**
 * list_get_first:
 * @list: 
 * 
 * Get the first node in the list.
 * 
 * Returns: The first node or NULL if empty. See list_remove_first()
 * for more details about the return value.
 */
struct node * list_get_first(struct list *list)
{
	struct node *first;
	ASSERT(list != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
	first = list->head;
	if (first->succ == NULL) return NULL;
	return first;
}

/* Get the next node in the list, NULL if no more nodes
 *
 * See list_remove_first() for more details about the return value.
 *
 * INPUT VALUES:
 *
 * M11) No more nodes in the list
 * M12) There are still nodes in the list
 *    ) ILLEGAL: node is a null pointer (no test case will be done)
 */

/**
 * list_get_next:
 * @node: 
 * 
 * Get the next node in the list.
 * 
 * Returns: Next node, or NULL if no more nodes.
 * See list_remove_first() for more details about the
 * return value.
 */
struct node * list_get_next(struct node *node)
{
	struct node *next;
	ASSERT(node != NULL);
	next = node->succ;
	if (next->succ == NULL) return NULL;
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	ASSERT(node->pred != NULL);
#endif
	return next;
}

/**
 * list_get_first_node:
 * @node: 
 * 
 * Get the first node in the list without the list structure argument 
 * 
 * Returns: 
 */
struct node * list_get_first_node(struct node *node)
{
	struct node *prev;
	ASSERT(node != NULL);
	prev = node;
	while (prev->pred != NULL) {
		prev = prev->pred;
#ifdef LIST_ADDITIONAL_VERIFICATIONS
		ASSERT(prev->succ != NULL);
#endif
	}
	return prev;
}

/* Remove the first node from the list
 *
 * The same pointer that was used when the node was inserted into the list
 * is returned. Usually the node structure should be in the beginning of the
 * structure to be inserted:
 *
 * struct myown *own = (struct myown *) list_remove_first(list);
 *
 * If it is not in the beginning, you have to calculate the beginning of the
 * actual structure:
 *
 * struct node *n = list_remove_first(list);
 * if (node != NULL) {
 *         struct myown *own = (struct myown *)
 *                             (((char *) n) - offsetof(struct myown, node));
 * }
 *
 * If the list is empty, NULL is returned.
 *
 * INPUT VALUES:
 *
 * M13) List is empty
 * M14) List is not empty
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 */

struct node * list_remove_first(struct list *list)
{
	struct node *node;

	ASSERT(list != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
	if (list_is_empty(list) == TRUE) return NULL;
	node = list->head;
	ASSERT(node != NULL);
	ASSERT(node->succ != NULL);
	ASSERT(node->pred != NULL);
	list_remove(node);
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	ASSERT(node->succ == NULL);
	ASSERT(node->pred == NULL);
#endif
	return node;
}

/* Remove the last node from the list
 *
 * See list_remove_first() for more details about the return value.
 *
 * INPUT VALUES:
 *
 * M15) List is empty
 * M16) List is not empty
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 */

struct node * list_remove_last(struct list *list)
{
	struct node *node;

	ASSERT(list != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
	if (list_is_empty(list) == TRUE) return NULL;
	node = list->tailpred;
	ASSERT(node->succ != NULL);
	ASSERT(node->pred != NULL);
	ASSERT(node != NULL);
	list_remove(node);
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	ASSERT(node->succ == NULL);
	ASSERT(node->pred == NULL);
#endif
	return node;
}

/* Remove a node from the list
 *
 * INPUT VALUES:
 *
 * M17) The node is the first one in the list
 * M18) The node is in the middle of the list
 * M19) The node is the last one in the list
 *    ) ILLEGAL: node is a null pointer (no test case will be done)
 */

void list_remove(struct node *node)
{
	ASSERT(node != NULL);
	ASSERT(node->succ != NULL);
	ASSERT(node->pred != NULL);
	node->pred->succ = node->succ;
	node->succ->pred = node->pred;
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	node->succ = NULL;
        node->pred = NULL;
#endif
}

#if 0
/* Find a node by name from given list */

struct node * list_find_name(const struct list *list, const char *name)
{
	DEBUG(DEBUG_FLAG, "list_find_name, list = " HEXFMT ", name = '%s'\n",
	      list, name);
	ASSERT(list != NULL);
	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
	ASSERT(name != NULL);
	return find_name_node((struct node *) &list->head, name);
}

/* Find a node by name from given node on the list */

struct node * list_find_name_node(struct node *node, const char *name)
{
	DEBUG(DEBUG_FLAG,
	      "list_find_name_node, node = " HEXFMT ", name = '%s'\n",
	      node, name);
	ASSERT(node != NULL);
	ASSERT(name != NULL);
	if (node->succ != NULL) {
		node = node->succ;
		while(node->succ != NULL) {
			if (node->name != NULL
			    && strcmp(node->name, name) == 0) {
				DEBUG(DEBUG_FLAG,
				      "list_find_name_node successful, node = "
				      HEXFMT ", name = '%s'\n",
				      node, node->name);
				return node;
			}
			node = node->succ;
		}
	}
	DEBUG(DEBUG_FLAG, "list_find_name_node unsuccessful\n");
	return NULL;
}
#endif

/* Is the list empty?
 *
 * INPUT VALUES:
 *
 * M20) The list is empty
 * M21) The list is not empty
 *    ) ILLEGAL: list is a null pointer (no test case will be done)
 */

int list_is_empty(const struct list *list)
{
#ifdef LIST_ADDITIONAL_VERIFICATIONS
	struct node *node;
#endif

	ASSERT(list->head != NULL);
	ASSERT(list->tail == NULL);
	ASSERT(list->tailpred != NULL);
	if (list->tailpred != (struct node *) &list->head) {
#ifdef LIST_ADDITIONAL_VERIFICATIONS
		node = list->head;
		ASSERT(node->succ != NULL);
		ASSERT(node->pred != NULL);
#endif
		return FALSE;
	}
	return TRUE;
}