/* ---------------------------------------------------------------------------
 * Lazy Synchronization Singly-linked List: pthread_mutex version
 * 
 * author: suzuki hironobu (hironobu@interdb.jp) 2009.Oct.25
 * Copyright (C) 2009  suzuki hironobu
 *
 * ---------------------------------------------------------------------------
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <limits.h>
#include <assert.h>
#include <inttypes.h>
#include <pthread.h>

#include "LazySynchroList.h"

static node_t *create_node(const lkey_t, const val_t);

#define lock(mtx) pthread_mutex_lock(mtx)
#define unlock(mtx) pthread_mutex_unlock(mtx)


static node_t *create_node(const lkey_t key, const val_t val)
{
  node_t *node;
  
  if ((node = calloc(1, sizeof(node_t))) == NULL) {
    elog("calloc error ");
    return NULL;
  }
    
  node->key = key;
  node->val = val;
  node->marked = false;
  node->mtx = (pthread_mutex_t) PTHREAD_MUTEX_INITIALIZER;

  return node;
}

#ifdef _FREE_
#define free_node(_node)   do {			                  \
                            pthread_mutex_destroy(&(_node->mtx));  \
			    free(_node);}while(0);
#else
#define free_node(_node)  ;
#endif


/*
 * bool_t add(list_t * list, const lkey_t key, const val_t val)
 *
 * listにnode(key,val)を追加する。
 * 追加位置はkeyの昇順に従う。すでに同じkeyを持つnodeがある場合は失敗。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
#define validate(pred, curr) (!pred->marked && !curr->marked && pred->next == curr)

bool_t add(list_t * l, const lkey_t key, const val_t val)
{
    node_t *pred, *curr;
    node_t *newNode;
    bool_t ret = true;

    if ((newNode = create_node(key, val)) == NULL)
      return false;

    while (1) {
      pred = l->head;
      curr = pred->next;
      
      /* 目的のノードまで走査 */	
      while (curr->key < key && curr != l->tail) {
	pred = curr;
	curr = pred->next; 
      }
      
      /* 
       * この間に、他のスレッドがpredやcurrを削除、変更、または
       * ノードを追加する可能性がある
       */
      
      if (lock(&pred->mtx) != 0) {      /* lockが成功しなければ、最初からやりなおし */	
	continue;
      } else if (lock(&curr->mtx) != 0) {
	unlock(&pred->mtx);
	continue;
      }
      
      /* この時点で成立する条件式: (pred->key) < (newNode->key) <= (curr->key) */
      assert ((pred->key < key) && (key <= curr->key));
      
      /* クリティカルセクション開始 */
      if (validate(pred, curr)) {
	if (key == curr->key) {
	  ret = false;
	  free_node(newNode);
	} else {
	  newNode->next = curr;
	  pred->next = newNode;
	}
	/* クリティカルセクション終了 */
	unlock(&pred->mtx);	unlock(&curr->mtx);
	break;
      }
      unlock(&pred->mtx);      unlock(&curr->mtx);
    }
    return ret;
}

/*
 * bool_t delete(list_t * list, const lkey_t key, val_t *val)
 *
 * listからkeyを持つnodeを削除し、そのnodeのvalを*valに書き込む。
 * keyが存在しない場合は失敗。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
bool_t delete(list_t * l, const lkey_t key, val_t *val)
{
  node_t *pred, *curr;
  bool_t ret = true;
  
  while(1) {
    pred = l->head;
    curr = pred->next;
    
    if (curr == l->tail) {
      ret = false;
      break;
    } else {
      /* 目的のノードまで走査 */
      while (curr->key < key && curr != l->tail) {
	pred = curr;
	curr = pred->next;
      }
      
      /* 
       * この間に、他のスレッドがpredやcurrを削除、変更、または
       * ノードを追加する可能性がある
       */
      
      if (lock(&pred->mtx) != 0) {	/* lockが成功しなければ、最初からやりなおし */
	continue;
      } else if (lock(&curr->mtx) != 0) {
	unlock(&pred->mtx);
	continue;
      }
      if (!(pred->key < key) || !(key <= curr->key)) {
	unlock(&pred->mtx);	unlock(&curr->mtx);
	continue;
      }
      /* この時点で成立する条件式: (pred->key) < (newNode->key) <= (curr->key) */
      assert ((pred->key < key) && (key <= curr->key));
      
      /* クリティカルセクション開始 */
      if (validate(pred, curr)) { 
	if (key == curr->key) {
	  curr->marked = true;
	  *val = curr->val;
	  pred->next = curr->next;
	  free_node(curr);
	} else {
	  ret = false;
	}
	/* クリティカルセクション終了 */
	unlock(&pred->mtx);	unlock(&curr->mtx);
	break;
      }
      unlock(&pred->mtx);      unlock(&curr->mtx);
    }
  }
  return ret;
}


/*
 * bool_t find(list_t * list, const lkey_t key, val_t *val)
 *
 * listからkeyを持つnodeを検索し、そのnodeのvalを*valに書き込む。
 * keyが存在しない場合は失敗。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
bool_t find(const list_t * list, const lkey_t key)
{

    node_t *curr;

    curr = list->head;
    while (curr->key < key) {
	curr = curr->next;
    }
    
    return (curr->key == key && !curr->marked);
}

list_t *init_list(void)
{
  list_t *list;
  
  if ((list = (list_t *) calloc(1, sizeof(list_t))) == NULL) {
    elog("calloc error");
    return NULL;
  }
  
  if ((list->head = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
    elog("calloc error");
    goto end;
  }
  list->head->mtx = (pthread_mutex_t) PTHREAD_MUTEX_INITIALIZER;
  
  if ((list->tail = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
    elog("calloc error");
    goto end;
  }
  list->tail->mtx = (pthread_mutex_t) PTHREAD_MUTEX_INITIALIZER;
  
  list->head->next = list->tail;
  list->tail->next = NULL;

  list->head->key = INT_MIN;
  list->tail->key = INT_MAX;

    return list;

 end:
    free (list->head);
    free (list);
    return NULL;
}

void free_list(list_t * list)
{
  node_t *curr, *next;

  curr = list->head->next;
  while (curr != list->tail)
    {
      next = curr->next;
      free (curr);
      curr = next;
    }
  
  free(list->head);
  free(list->tail);
  free(list);
}

void show_list(const list_t * list)
{
    node_t *pred, *curr;

    pred = list->head;
    curr = pred->next;

    printf ("list:\n\t");
    while (curr != list->tail) {
      printf(" [%lu:%ld]", (unsigned long int) curr->key, (long int)curr->val);
      pred = curr;
      curr = curr->next;
    }
    printf("\n");
}

#ifdef _SINGLE_THREAD_


list_t *list;

int main (int argc, char **argv)
{
  lkey_t i;
  val_t g;

  list = init_list();

  show_list (list);

  for (i = 0; i < 10; i++) 
    {
      add (list, (lkey_t)i, (val_t) i * 10);
    }

  show_list (list);

  for (i = 0; i < 5; i++) {
    delete (list, (lkey_t)i, &g);
    printf ("ret = %ld\n", (long int)g);
  }

  show_list (list);

  free_list (list);

  return 0;
}

#endif