linkedlist.c

一个很好的例子-基于Linux的消息传输系统

#include "LinkedList.h"
#include "transform.h"

/**
* Create a LinkedList object. Note: If elements in the list don't need to be destroyed,
* please pass a dummy function.
* @param destroyElement Destroy Function of stored element type.
* @return Created LinkedList object
*/
LinkedList* createLinkedList(void (* destroyElement)(void*)) {
   LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
   if(list == NULL) {
      return NULL;
   }
   
   list->head = NULL;
   list->destroyElement = destroyElement;
   list->length = 0;
   return list;
}

/**
* Destroy a LinkedList object
* @param list LinkedList object waiting for being destroyed
*/
void destroyLinkedList(void* list_) {
   LinkedList* list = (LinkedList*)list_;
   if(list == NULL) {
        return;
   }
   while(list->head != NULL) {
      removeNode(list, list->head);
   }

   free(list);
}

/**
* Search in the list, if the return value of fun(theNode->value) is not 0, then return
* the node pointer for further operation, e.g. add, remove... 
* If no value match the reqirement, return NULL.
* @param list LinkedList object being searched.
* @param fun Judging function
* @param funArg1 The first argument of fun(void*, void*)
* @return the node pointer, whose value makes fun() return a non-zero
*/
Node* search(LinkedList* list, int(*fun)(void*, void*), void* funArg1) {
   Node* temp = NULL;
   if(list == NULL || list->head == NULL) {
      return NULL;
   }
   
   temp = list->head;
   while(temp != NULL) {
        if(fun(funArg1, temp->value) != 0) {
           return temp;
        } else {
           temp= temp->next;
        }
   }
   return NULL;
}

/**
* Return the value of specified node and remove the node from list.
* @param list LinkedList object being poped
* @param node The node being poped
* @return The value of poped node
*/
void* pop(LinkedList* list, Node* node) {
   void* temp = NULL;
   
   if(list == NULL || list->head == NULL || node == NULL) {
      return NULL;
   }

   temp = node->value;   
   
   if(node == list->head) {
      list->head = list->head->next;
          if(list->head != NULL) {
         list->head->pre = NULL;
          }
      
   } else if(node->next == NULL){
      node->pre->next = NULL;
   } else {
      node->pre->next = node->next;
      node->next->pre = node->pre;
   }
   
   destroyNode(node);
   list->length--;
   return temp;
}

/**
* Return the value of head node and remove the node from list.
* @param list LinkedList object being poped
* @return The value of poped node
*/
void* popHead(LinkedList* list) {
  return pop(list, list->head);
}

/**
* Remove a specified node from the list.
* @param list LinkedList object whose node being removed
* @param node The being removed node
*/
void removeNode(LinkedList* list, Node* node) {
   list->destroyElement(pop(list, node));       
}

/**
* Add a node created by specified value to the list before the specified node.
* @param list LinkedList object acts this action
* @param node add a new node before this node
* @/param value The value of new node
* @return The newly created node
*/
Node * addBefore(LinkedList *list, Node* node, void* value) {
   Node* temp = NULL;
   if(node == NULL) {
      return NULL;
   }
   list->length ++;
   temp = createNode(value, node->pre, node);
   node->pre = temp;
   
   if(node == list->head) {
      list->head = temp;
      return list->head;
   }
   
   temp->pre->next = temp;
   return list->head;
}

/**
* Add a node created by specified value to the list after the specified node.
* @param list LinkedList object acts this action
* @param node add a new node after this node
* @param value The value of new node
* @return The newly created node
*/
Node* addAfter(LinkedList* list, Node* node, void* value) {
   Node* temp = NULL;
   if(node == NULL) {
      return NULL;
   }

   list->length ++;
   temp = createNode(value, node, node->next);
   node->next = temp;
   
   if(node->next == NULL) {
      return temp;
   }
   
   temp->next->pre = temp;
   return temp;
}

/**
* Add a node created by specified value to the list as the head node.
* @param list LinkedList object acts this action
* @param node Added node as head node
* @param value The value of new node
* @return The newly created node
*/
Node* addAsHead(LinkedList* list, void* value) {
   Node* temp = NULL;
   if(list == NULL) {
      return NULL;
   }

   list->length ++;

   if(list->head == NULL) {
      list->head = createNode(value, NULL, NULL);
      return list->head;
   }
   
   temp = createNode(value, NULL, list->head);
   list->head->pre = temp;
   list->head = temp;
   return list->head;
}

/**
* Add a node created by specified value to tail of list
* @param list LinkedList object acts this action
* @param node Added node as tail node
* @param value The value of new node
* @return The newly created node
*/
Node *  append(LinkedList* list, void* value) {
   Node* temp = NULL;
   if(list == NULL) {
      return NULL;
   }

   list->length ++;

   if(list->head == NULL) {
      list->head = createNode(value, NULL, NULL);
	
            return  list->head;
   }
   temp = list->head;
   while(temp->next != NULL) {
      temp = temp->next;
   }
   
   temp->next = createNode(value, temp, NULL);
   return list->head;
}

/**
* Create a new node. Note: The function should olny be invocked by LinkedList
* @param value The value of the node.
* @param pre The previous node of this node
* @param next The next node of this node
* @return The newly created node
*/
Node* createNode(void* value, Node* pre, Node* next) {
   Node* node = (Node*)malloc(sizeof(Node));
   if(node == NULL) {
      return NULL;
   }
   
   node->value = value;
   node->pre = pre;
   node->next = next;
   
   return node;
}

/**
* Destroy a node object.
* @param node Node object waiting to be destroyed
*/
void destroyNode(void* node_) {
   Node* node = (Node*)node_;
   if(node == NULL) {
      return;
   } 
 //  free(((DataMsgContent*)(((SendPack*)(node->value))->msg->content))->data);  
  
 //  free(((SendPack*)(node->value))->msg->content); 
 //  free(node->value); 
  
   free(node);
 //  free(((DataMsgContent*)(node->value->msg->content))->data);  
}

/**
* Print LinkedList object data feild.
* @param list the LinkedList object being printed
* @param printfun The 'printXXX()' function for XXX element type
*/
void printLinkedList(LinkedList* list, void(*printfun)(void*)) {
   Node* temp = NULL;
   if(list == NULL) {
      printf("LinkedList: NULL\n");
      return;
   }
   printf("LinkedList: %p\n[length: %d,\n", list, list->length);
   
   temp = list->head;
   while(temp != NULL) {
      printNode(temp, printfun);

      temp = temp->next;
   }
   printf("]\n");
}

/**
* Print Node object data feild.
* @param node the Node object being printed
* @param printfun The 'printXXX()' function for XXX element type
*/
void printNode(Node* node, void(*printfun)(void*)) {
   if(node == NULL) {
      printf("Node: NULL\n");
      return;
   }
   
   printf("Node: %p\n[pre: %p, next: %p", node, node->pre, node->next);
 //  printf("Node: %p\n[pre: %p, next: %p ,data : %p", node, node->pre, node->next,((DataMsgContent *)(((Message*)(node->value))->content))->data);
   printf("vale: ");
   printfun(node->value);
   printf("]\n");

        
}


void destroyA(void* a) {
   //free(a);
}

void printASendPack(void* a1) {
   SendPack* a = (SendPack*)a1;
   if(a1 == NULL) {
      printf("A: NULL");
          return;
   }
   printf("%d,%d\n", a->msg->type,a->msg->priority);
}
void printAMessage(void* a1) {
   Message* a = (Message*)a1;
   if(a1 == NULL) {
      printf("A: NULL");
          return;
   }
   printf("%d,%d\n", a->type,a->priority);
}

int compareSendPack(void* a_, void* a1_) {
	SendPack* a = (SendPack*) a_;
	SendPack* a1 = (SendPack*)a1_;
    
	if(a->msg->priority > a1->msg->priority) {
       return 1;
	}
	return 0;
}
int compareMessage(void* a_, void* a1_) {
	Message* a = (Message*) a_;
	Message* a1 = (Message*)a1_;
    
	if(a->priority > a1->priority) {
       return 1;
	}
	return 0;
}