/* ---------------------------------------------------------------------------
 * 
 * Lock-Free List : "A Pragmatic Implementation of Non-Blocking Linked-Lists" Timothy L. Harris 
 *
 * author: suzuki hironobu (hironobu@interdb.jp) 2009.Dec.02
 * Copyright (C) 2009  suzuki hironobu
 *
 * ---------------------------------------------------------------------------
 */
#ifndef _NONBLOCKINGLIST_H_
#define _NONBLOCKINGLIST_H_

#include "common.h"


typedef enum {UNMARKED = 0, MARKED = 1} node_stat;

typedef struct _next_ref {
  node_stat mark;
  void *node_ptr;
}__attribute__((packed)) next_ref;


typedef struct _node_t
{
  lkey_t key;                   /* key */
  val_t val;                    /* 値 */
  next_ref next;                /* 次のnodeへのリファレンス */
}__attribute__((packed)) node_t;

typedef struct _list_t
{
  node_t *head;
  node_t *tail;
} list_t;

bool_t add (list_t *, const lkey_t, const val_t);
bool_t delete (list_t *, const lkey_t, val_t *);
bool_t find (list_t *, const lkey_t);
list_t * init_list (void);
void free_list (list_t *);

void show_list(const list_t *);

#endif