linklist.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include "linklist.h"

#define _empty(list)   ((list)->tail ? AD_FALSE : AD_TRUE)
#define    APPEND        1
#define    PREPEND       !(APPEND)

/* Linklist */
struct _LLNODE
{
  struct _LLNODE *next;
  void *data;
};

struct _LINKLIST
{
    unsigned int count;
    struct _LLNODE *tail;     /* tail of the circular linklist */
    pthread_mutex_t mutex;
};

typedef struct _LLNODE LLNODE;
#define LLNODE_SIZE    sizeof(LLNODE)

LINKLIST *ll_init(void)
{
    LINKLIST *list;
    
    if ((list = calloc(1, LINKLIST_SIZE)))
   pthread_mutex_init(&(list->mutex), NULL);
    
    return list;
}

AD_BOOLEAN ll_empty(LINKLIST *list)
{
    if (!list) return AD_TRUE;

    return _empty(list);
}

static LINKLIST *_add(LINKLIST *list, void *newdata, int insertType)
{
    LLNODE *newnode;


    if (list != NULL) {
   pthread_mutex_lock(&(list->mutex));

   if ((newnode = malloc(LLNODE_SIZE))) {
       newnode->data = newdata;
   
       if (_empty(list) == AD_TRUE) {
      newnode->next = newnode;
      list->tail = newnode;
       } else {
      newnode->next = list->tail->next;
      list->tail->next = newnode;
      if (insertType == APPEND)
          list->tail = list->tail->next;
       }
       
       list->count++;
   }

   pthread_mutex_unlock(&(list->mutex));
    }

    return list;
}

LINKLIST *ll_prepend (LINKLIST *list, void *newdata)
{
    return _add(list, newdata, PREPEND);
}

LINKLIST *ll_append (LINKLIST *list, void *newdata)
{
    return _add(list, newdata, APPEND);
}

static LLNODE *find_node(LINKLIST *list, void *key, AD_COMPARE_FUNC *match, LLNODE **prev)
{
    LLNODE *current, *head, *find = NULL;
    

    /* begin current at the start of the list */
    current = head = list->tail->next;
    *prev = list->tail;
    
    do {
   if (match(current->data, key) == AD_EQUAL) {
       find = current;
       break;
   }
   
   *prev = current;   
   current = current->next;
    } while (current != head); /* end when you return to head */

    return find;
}

int ll_swapline(LINKLIST *list, void *k1, void *k2, AD_LOCK lock_f, AD_COMPARE_FUNC *match)
{
    LLNODE *key1_prev, *key1, *key2_prev, *key2, *tmp;
    LLNODE *prev;
    int result = -1;

    
    if (list) {
   if (lock_f)
       pthread_mutex_lock(&(list->mutex));    

   if (_empty(list) == AD_FALSE) {
       if ((key1 = find_node(list, k1, match, &prev))) {      
      /* 5 */
       key1_prev = prev;
      
      /* ex:          */
      /* k1:6 <=========> k2:9  */
      /*      first find 6, and 9   */
      if ((key2 = find_node(list, k2, match, &prev))) {
          if (key1 == list->tail)
         list->tail = key2;
          else if (key2 == list->tail)
         list->tail = key1;              
      
          /* 8 */
          key2_prev = prev;
          /* 1. 5->next = 9, 8->next = 6 */
          key1_prev->next = key2, key2_prev->next = key1;
          
          /* 2. 9->next <=> 6->next */
          tmp = key2->next;
          key2->next = key1->next;
          key1->next = tmp;
          
          result = 0;
      }
       }
   }

   if (lock_f)
       pthread_mutex_unlock(&(list->mutex));    
    }    
    
    return result;
}

void *ll_find(LINKLIST *list, void *key, AD_LOCK lock_f, AD_COMPARE_FUNC *match)
{
    LLNODE *current, *head;
    void *data = NULL;


    if (!list) return NULL;

    if (lock_f)
   pthread_mutex_lock(&(list->mutex));

    if (_empty(list) == AD_FALSE) {
   /* begin current at the start of the list */
   current = head = list->tail->next;
   
   do {
       if (match(current->data, key) == AD_EQUAL) {
      data = current->data;
      break;
       }
   
       current = current->next;
   } while (current != head); /* end when you return to head */
    }

    if (lock_f)
   pthread_mutex_unlock(&(list->mutex));

    return data;
}

void *ll_delete(LINKLIST *list, void *key, AD_COMPARE_FUNC *match)
{
    LLNODE *current, *prev, *head;
    void *data = NULL;

    
    if (!list) return NULL;

    pthread_mutex_lock(&(list->mutex));
    
    if (_empty(list) == AD_FALSE) {
   current = head = list->tail->next;
   prev = list->tail;
   
   do {
       if (match(current->data, key) == AD_EQUAL) {
      if (current == prev)  /* only node */
          list->tail = NULL;
      else {
          prev->next = current->next;  /* unlink the node to be deleted */
          
          if (current == list->tail)   /* last node is to be deleted */
         list->tail = prev;
      }
      
      list->count--;
      data = current->data;
      free(current);    
      break;
       }

       prev = current;
       current = current->next;
   } while (current != head); 
    }

    pthread_mutex_unlock(&(list->mutex));

    return data;
}

void *ll_get(LINKLIST *list, void **n, AD_LOCK lock_f)
{
    void *data = NULL;
    LLNODE *current, **node = (LLNODE **)n;


    if (!list || (*node == list->tail))
   return NULL;
    
    if (lock_f)
   pthread_mutex_lock(&(list->mutex));
    
    if (_empty(list) == AD_FALSE) {
   current = (*node == NULL) ? list->tail->next : (*node)->next;
   
   data = current->data;
   *node = (void *) current;
    }

    if (lock_f)
   pthread_mutex_unlock(&(list->mutex));

    return data;    
}

AD_BOOLEAN ll_traverse(LINKLIST *list, AD_LOCK lock_f, AD_TRAV_FUNC  *travFunc, void *param)
{
    LLNODE *current, *head;
    AD_BOOLEAN FIN_OK = AD_FALSE;
  

    if (!list) return AD_FALSE;
    
    if (lock_f)
   pthread_mutex_lock(&(list->mutex));
    
    if (_empty(list) == AD_FALSE) {
   FIN_OK = AD_TRUE;

   head = list->tail->next;
   current = head;
   
   do {
       if (travFunc(current->data, param) == AD_FALSE) {
      FIN_OK = AD_FALSE;
      break;
       }
       
       current = current->next;
   } while (current != head);
    }
    
    if (lock_f)
   pthread_mutex_unlock(&(list->mutex));
    
    return FIN_OK;
}

void ll_free(LINKLIST *list)
{
    LLNODE *current, *temp;


    if (!list) return;

    pthread_mutex_lock(&(list->mutex));
    
    if (_empty(list) == AD_FALSE) {
         /* initialise */
      current = list->tail->next;   /* start at the head */
      list->tail->next = NULL;      /* break the circular nature */
      
      while(current != NULL) {
         temp = current;
         current = current->next;
         free(temp);
      }
    }
   
    pthread_mutex_unlock(&(list->mutex));
    pthread_mutex_destroy(&(list->mutex));
    
    free(list);
    list = NULL;
}

/* to be used by the deque data type */
void *ll_delete_head(LINKLIST *list)
{
    void *outdata = NULL;
    LLNODE *head;


    if (!list) return NULL;

    pthread_mutex_lock(&(list->mutex));
    
    if (_empty(list) == AD_FALSE) {
   head = list->tail->next;
   outdata = head->data;

   if (head == list->tail)           /* only one node */
       list->tail = NULL;
   else                              /* more than one one */
       list->tail->next = head->next;
       
   list->count--;

   free(head);    
    }

    pthread_mutex_unlock(&(list->mutex));

    return outdata;
}

void *ll_delete_tail(LINKLIST *list)
{
    LLNODE *previous;
    void *data = NULL;


    if (!list) return NULL;

    pthread_mutex_lock(&(list->mutex));
    
    if (_empty(list) == AD_FALSE) {
   data = list->tail->data;
   
   /* locate the node prior to the tail */
   previous = list->tail;
   do {
       previous = previous->next;
   } while (previous->next != list->tail);

   /* only one element in the list */
   if(previous == list->tail) {
       free(list->tail);
       list->tail = NULL;
   }
        /* general case of more than one element */
   else {
       previous->next = list->tail->next;
       free(list->tail);
       list->tail = previous;
   }
   
   list->count--;
    }

    pthread_mutex_unlock(&(list->mutex));
    
    return data;
}

void *ll_head(LINKLIST *list)
{
    void *data = NULL;
    

    if (!list) return NULL;

    pthread_mutex_lock(&(list->mutex));

    if (_empty(list) == AD_FALSE)
   data = list->tail->next->data;

    pthread_mutex_unlock(&(list->mutex));
    
    return data;
}

void *ll_tail(LINKLIST *list)
{
    void *data = NULL;
    

    if (!list) return NULL;

    pthread_mutex_lock(&(list->mutex));

    if (_empty(list) == AD_FALSE)
   data = list->tail->data;

    pthread_mutex_unlock(&(list->mutex));
    
    return data;   
}

unsigned ll_count(LINKLIST *list)
{
    unsigned count = 0;

    if (list != NULL) {
   pthread_mutex_lock(&(list->mutex));

   count = list->count;

   pthread_mutex_unlock(&(list->mutex));
    }
    
    return count;
}