lnklist.c

Jan 04, 2007 1. Add SPI support, see spi.h and spi.c 2. Add driver.h 3. Modified keyboard modu

/**
 * Copyright (c) 2006-2008 iWESUN (ShenZhen) Inf.
 * All rights reserved. 
 * 
 * Redistribution and use in source and binary forms, with or without modification, 
 * are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT 
 * SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY 
 * OF SUCH DAMAGE.
 *
 * This file is part of the AvrcX MTOS
 * 
 * Author: Winter Hu  <[e-mail]>
 * Create: Nov 27, 2006
 */


#include "lnklist.h"

void _insert(LinkedList*, Node*, unsigned char);

/**
 * Retrieves the first Node in the LinkedList
 * If return NULL, means the list is empty
 *
 * @param LinkedList*, The pointer to the LinkedList
 * @return Node*, the pointer to the first Node
 */
INTERFACE Node* get_first(LinkedList* pList){
  return pList->head;
}

/**
 * Remove the first Node from the LinkedList
 * If return NULL, means the list is empty
 *
 * @param LinkedList*, The pointer to the LinkedList
 * @return Node*, The pointer to the first Node
 */
INTERFACE Node* remove_first(LinkedList* pList){
  Node* node = pList->head;
  pList->head = (node == NULL) ? NULL : node->next;
  return node;
}

/**
 * Remove the Node from the LinkedList
 * If return NULL, no Node had been removed
 *
 * @param LinkedList*, The pointer to the LinkedList
 * @param Node*, The pointer to the Node need to be removed
 * @return Node*, The pointer to the Node that be removed
 */
INTERFACE Node* remove(LinkedList* pList, Node* delNode){
  if ( delNode == NULL ) return delNode;

  Node* Np = NULL;
  Node* Nn = pList->head;

  while(Nn != NULL){
    if (Nn == delNode){
      if (Np != NULL){
	Np->next = Nn->next;
      }else{
	// The first
	pList->head = Nn->next;
      }
      break;
    }else{
      Np = Nn;
      Nn = Nn->next;
    }
  }
  return Nn;
}

/**
 * Insert a Node into the order of priority LinkedList
 *
 * @param LinkedList*, The pointer to the LinkedList
 * @param Node*, The pointer to the Node that need to insert
 * @return 
 */
INTERFACE void  insert_ordered(LinkedList* pList, Node* newNode){
  _insert(pList, newNode, 0);
}

/**
 * Insert a Node into the order of relative priority LinkedList 
 * This method could be useful to create a scheduler queue or 
 * a timer queue.
 *
 * @param LinkedList*, The pointer to the LinkedList
 * @param Node*, The pointer to the Node that need to insert
 * @return none
 */
INTERFACE void insert_relative(LinkedList* pList, Node* newNode){
  _insert(pList, newNode, 1);
}

/**
 * Append the node to the end of the LinkedList
 * The priority of Node is ignored
 *
 * @param LinkedList*, The pointer to the LinkedList
 * @param Node*, The pointer to the Node
 */
INTERFACE void append(LinkedList* pList, Node* newNode){
  if (newNode == NULL) return;

  newNode->next = NULL;

  Node* node = pList->head;
  if (node == NULL){
    pList->head = newNode;
  }else{
    while(node->next != NULL){
      node = node->next;
    }
    node->next = newNode;
  }
}

/** */
void _insert(LinkedList* pList, Node* newNode, unsigned char b){
  if (newNode == NULL) return;

  newNode->next = NULL;
  
  Node* Np = NULL;
  Node* Nn = pList->head;

  while(Nn != NULL){
    if (newNode->priority < Nn->priority){
      newNode->next = Nn;
      if (Np != NULL) Np->next = newNode;
      if (b) Nn->priority -= newNode->priority;
      break;
    }else{// n.p >= Nn.p
      newNode->priority -= Nn->priority;
      Np = Nn;
      Nn = Nn->next;
    }
  }

  if (Np == NULL){
    pList->head = newNode;
  }else if (Nn == NULL) {
    Np->next = newNode;
  }
}