/* ---------------------------------------------------------------------------
 * Lock-Free list
 *
 * "Lock-Free Linked Lists and Skip Lists" Mikhail Fomitchev, Eric Ruppert
 * http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf
 *
 * author: suzuki hironobu (hironobu@interdb.jp) 2009.Nov.16
 * Copyright (C) 2009  suzuki hironobu
 *
 * ---------------------------------------------------------------------------
 */

#ifndef _NONBLOCKINGLIST_H_
#define _NONBLOCKINGLIST_H_

#include "common.h"

#define MARKED        0x0001
#define UNMARKED      0x0000
#define MARKED_MASK   0x0001

#define FLAGGED       0x0002
#define UNFLAGGED     0x0000
#define FLAGGED_MASK  0x0002



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

typedef struct _node_t
{
  lkey_t key;                   /* key */
  val_t val;                    /* 値 */

  struct _node_t *backlink;

  next_ref succ;                /* 次の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