蜊俶婿蜷代Μ繧ｹ繝�: 荳ｦ陦悟�逅�ｷｨ Part 4

繧ｽ繝ｼ繧ｹ縺ｯGitHub縺ｫ遘ｻ陦後＠縺ｾ縺励◆縲�

Non-Blocking Singly-linked List 2(Non-Blocking蜊俶婿蜷代Μ繧ｹ繝�)

Non-Blocking Slingly-Linked List縺ｫ縺､縺�※縲� T.L.Harris迚�縺ｮ謾ｹ濶ｯ縺ｧ縺ゅｋ "Lock-Free Linked Lists and Skip Lists" Mikhail Fomitchev, Eric Ruppert 繧貞ｮ溯｣�＠縺溘€�

繧ｽ繝ｼ繧ｹ縺ｯGitHub縺ｫ遘ｻ陦後＠縺ｾ縺励◆縲�

繝��繧ｿ讒矩€�

繝��繧ｿ讒矩€�list_t縺ｨnode_t繧貞ｮ夂ｾｩ縺吶ｋ縲� list_t縺ｯList縺ｮ譛ｬ菴薙€］ode_t縺ｯList縺ｫ騾｣邨舌☆繧杵ode縺ｮ繝��繧ｿ讒矩€�縺ｧ縺ゅｋ縲�

node縺ｨlist縺ｮ繝��繧ｿ讒矩€�繧堤､ｺ縺吶€�

NonBlockingList.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;

list_t縺ｫ縺ｯ縲√Μ繧ｹ繝医�蜈磯�ｭhead縺ｨ譛ｫ蟆ｾtail縺檎｢ｺ菫昴＆繧後ｋ縲�

蝓ｺ譛ｬ髢｢謨ｰ

list縺ｮ逕滓�
/*
 * list_t *init_list(void)
 *
 * list繧堤函謌舌☆繧九€�
 *
 * 謌仙粥縺吶ｌ縺ｰlist縺ｸ縺ｮ繝昴う繝ｳ繧ｿ繧定ｿ斐☆縲ょ､ｱ謨励↑繧丑ULL繧定ｿ斐☆縲�
 *
 */
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;
  }
  
  if ((list->tail = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
    elog("calloc error");
    goto end;
  }

  list->head->key = INT_MIN;
  list->head->succ.mark = UNMARKED;
  list->head->succ.node_ptr = (void *)list->tail;

  list->tail->key = INT_MAX;
  list->tail->succ.mark = UNMARKED;
  list->tail->succ.node_ptr = NULL;

  return list;

 end:
  free (list->head);
  free (list);
  return NULL;
}
繝弱�繝峨�讀懃ｴ｢

inline bool_t
cas64(next_ref * addr, const next_ref oldp, const next_ref newp)
{
  char result;
  __asm__ __volatile__("lock; cmpxchg8b %0; setz %1":"=m"(*addr),
		       "=q"(result)
		       :"m"(*addr), "a"(oldp.mark), "d"(oldp.node_ptr),
			"b"(newp.mark), "c"(newp.node_ptr)
		       :"memory");
  return (((int)result == 0) ? false:true);
}
#define is_marked_ref(ref)      ((ref.mark & MARKED_MASK) == MARKED ? true:false)
#define is_unmarked_ref(ref)    ((ref.mark & MARKED_MASK) == UNMARKED ? true:false)
#define is_flagged_ref(ref)     ((ref.mark & FLAGGED_MASK) == FLAGGED ? true:false)
#define is_unflagged_ref(ref)   ((ref.mark & FLAGGED_MASK) == UNFLAGGED ? true:false)


static next_ref make_ref(node_t * node_ptr, const int marked, const int flagged)
{
    next_ref ref;
    assert(!(marked == MARKED && flagged == FLAGGED));
    ref.mark = (marked | flagged);
    ref.node_ptr = (node_t *) node_ptr;
    return ref;
}

#define get_unmarked_ref(node_ptr)  make_ref (node_ptr, UNMARKED, UNFLAGGED)
#define get_marked_ref(node_ptr)  make_ref (node_ptr, MARKED, UNFLAGGED)

static void
helpMarked (node_t *prev_node, node_t *del_node)
{
  node_t *next_node;
  assert (del_node->succ.node_ptr != NULL);
  next_node = del_node->succ.node_ptr;
  
  cas64(&prev_node->succ, 
	make_ref(del_node, UNMARKED, FLAGGED), 
	make_ref(next_node, UNMARKED, UNFLAGGED));
}

static bool_t searchFrom2 (const lkey_t key, node_t *curr_node, node_t **curr, node_t **next)
{
  node_t *next_node = curr_node->succ.node_ptr;
  
  while (next_node->key < key) {

    while (is_marked_ref(next_node->succ)
	   && (is_unmarked_ref(curr_node->succ) || (curr_node->succ.node_ptr != next_node))
	       ) {
	     
      if (curr_node->succ.node_ptr == next_node)
	helpMarked(curr_node, next_node);
      next_node = curr_node->succ.node_ptr;
    }

    if (next_node->key < key) {
      curr_node = next_node;
      next_node = curr_node->succ.node_ptr;
    }    
  }
  
  *curr = curr_node;
  *next = next_node;

  return true;
}

static bool_t
tryFlag (node_t *prev_node, node_t *target_node, node_t **result_node)
{
  bool_t ret = true;
  node_t *del_node;
  next_ref result;

  *result_node = NULL;

  while (1) {

    if (prev_node->succ.node_ptr == target_node
	&& (is_unmarked_ref(prev_node->succ) && is_flagged_ref(prev_node->succ))) {
      *result_node = prev_node;
      return false;
    }

    if (cas64(&prev_node->succ, 
	      make_ref(target_node, UNMARKED, UNFLAGGED),
	      make_ref(target_node, UNMARKED, FLAGGED)) == true) {
      *result_node = prev_node;
      return true;
    }
    result = prev_node->succ;
      
    if ((result.node_ptr == target_node) && (is_unmarked_ref(result)) && (is_flagged_ref(result))) {
      *result_node = prev_node;
      return false;
    }

    while (is_marked_ref(prev_node->succ)) {
      prev_node = prev_node->backlink;
    }
  }

  searchFrom2(target_node->key, prev_node, &prev_node, &del_node);

  if (del_node != target_node) {
    ret = false;
    *result_node = NULL;
  }
    
  return ret;
}


static void
tryMark(node_t *del_node) 
{
  node_t *next_node;
  next_ref result;
  do {
    next_node = del_node->succ.node_ptr;
    
    cas64(&del_node->succ, make_ref(next_node, UNMARKED, UNFLAGGED),
	  make_ref(next_node, MARKED, UNFLAGGED));

    result = del_node->succ;
    if (is_unmarked_ref(result) && is_flagged_ref(result)) {
      helpFlagged(del_node, result.node_ptr);
    }
  } while (is_unmarked_ref(del_node->succ));
}

static void
helpFlagged (node_t *prev_node, node_t *del_node)
{
  del_node->backlink = prev_node;

  if (is_unmarked_ref(del_node->succ)) {
    tryMark(del_node);
  }
  helpMarked(prev_node, del_node);
}
繝弱�繝峨�霑ｽ蜉�

/*
 * bool_t add(list_t * list, const lkey_t key, const val_t val)
 *
 * list縺ｫnode(key,val)繧定ｿｽ蜉�縺吶ｋ縲�
 * 霑ｽ蜉�菴咲ｽｮ縺ｯkey縺ｮ譏���↓蠕薙≧縲ゅ☆縺ｧ縺ｫ蜷後§key繧呈戟縺､node縺後≠繧句�ｴ蜷医�螟ｱ謨励€�
 *
 * 謌仙粥縺吶ｌ縺ｰtrue縲∝､ｱ謨励☆繧後�false繧定ｿ斐☆縲�
 */
bool_t add(list_t * list, const lkey_t key, const val_t val)
{
    node_t *newNode;
    
    node_t *prev_node, *next_node;
    next_ref prev_succ, result;
    
    if (searchFrom2(key, list->head, &prev_node, &next_node) != true)
      return false;
    
    if (prev_node->key == key)
      return false;
    
    if ((newNode = create_node(key, val)) == NULL)
      return false;
    
    while (1) {
      prev_succ = prev_node->succ;
      
      if ((prev_succ.mark & FLAGGED_MASK) == FLAGGED) {
	helpFlagged(prev_node, prev_succ.node_ptr);
      }
      else {
	newNode->succ = make_ref(next_node, UNMARKED, UNFLAGGED);
	if (cas64(&prev_node->succ, make_ref(next_node, UNMARKED, UNFLAGGED), 
		  make_ref(newNode, UNMARKED, UNFLAGGED)) == true) {
	  return true;  // return newNode;
	}
	else {
	  result = prev_node->succ;

	  if (is_unmarked_ref(result) && is_flagged_ref(result)) {
	    helpFlagged(prev_node, result.node_ptr);
	  }
	  while (is_marked_ref(prev_node->succ)) {
	    prev_node = prev_node->backlink;
	  }
	}
      }
      
      searchFrom2(key, list->head, &prev_node, &next_node);
      
      if (prev_node->key == key) {
	free (newNode);
	return false;
      }
    }
}
髢｢謨ｰadd()蜀�Κ縺ｧ蜻ｼ縺ｶnode逕滓�髢｢謨ｰcreate_node()繧堤､ｺ縺吶€� 
/*
 * node_t *create_node(const lkey_t key, const val_t val)
 *
 * (key, val)繧呈戟縺､node繧堤函謌舌☆繧九€�
 *
 * 謌仙粥縺吶ｌ縺ｰnode縺ｸ縺ｮ繝昴う繝ｳ繧ｿ繧定ｿ斐☆縲ょ､ｱ謨励☆繧後�NULL繧定ｿ斐☆縲�
 */
static node_t *create_node(const lkey_t key, const val_t val)
{
    node_t *node;

    if ((node = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
      elog("calloc error");
      return NULL;
    }

    node->next = make_ref(NULL, UNMARKED);

    node->key = key;
    node->val = val;

    return node;
}
繝弱�繝峨�蜑企勁

繝弱�繝峨�蜑企勁繧ょ渕譛ｬ謌ｦ逡･縺ｯ霑ｽ蜉�縺ｨ蜷後§縺ｧ縺ゅｋ縲� 

/*
 * 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 * list, const lkey_t key, val_t *val)
{  
  node_t *prev_node, *del_node;
  node_t *result_node;
  bool_t result;

  searchFrom2(key, list->head, &prev_node, &del_node);

  if (del_node->key != key)
    return false;
  
  result = tryFlag(prev_node, del_node, &result_node);

  if (result_node != NULL) {
    helpFlagged(result_node, del_node);
  }

  if (result == false)
    return false;

  *val = del_node->val;
  free_node(del_node);
    
  return true;
}
繝弱�繝峨�讀懃ｴ｢
/*
 * bool_t find(list_t * list, const lkey_t key, val_t *val)
 *
 * list縺九ｉkey繧呈戟縺､node繧呈､懃ｴ｢縺励€√◎縺ｮnode縺ｮval繧�*val縺ｫ譖ｸ縺崎ｾｼ繧€縲�
 * key縺悟ｭ伜惠縺励↑縺��ｴ蜷医�螟ｱ謨励€�
 *
 * 謌仙粥縺吶ｌ縺ｰtrue縲∝､ｱ謨励☆繧後�false繧定ｿ斐☆縲�
 */
bool_t delete(list_t * list, const lkey_t key, val_t *val)
{  
  node_t *prev_node, *del_node;
  node_t *result_node;
  bool_t result;

  searchFrom2(key, list->head, &prev_node, &del_node);

  if (del_node->key != key)
    return false;
  
  result = tryFlag(prev_node, del_node, &result_node);

  if (result_node != NULL) {
    helpFlagged(result_node, del_node);
  }

  if (result == false)
    return false;

  *val = del_node->val;
  free_node(del_node);
    
  return true;
}


/*
 * bool_t find(list_t * list, const lkey_t key, val_t *val)
 *
 * list縺九ｉkey繧呈戟縺､node繧呈､懃ｴ｢縺励€√◎縺ｮnode縺ｮval繧�*val縺ｫ譖ｸ縺崎ｾｼ繧€縲�
 * key縺悟ｭ伜惠縺励↑縺��ｴ蜷医�螟ｱ謨励€�
 *
 * 謌仙粥縺吶ｌ縺ｰtrue縲∝､ｱ謨励☆繧後�false繧定ｿ斐☆縲�
 */
bool find(list_t * l, const lkey_t key)
{
    node_t *curr;

    curr = search(l, key);
    if ((curr == l->tail) || (curr->key != key))
	return false;

    return true;
}

螳溯｡�

繧ｽ繝ｼ繧ｹ縺ｯGitHub縺ｫ遘ｻ陦後＠縺ｾ縺励◆縲�

Last-modified: 2014-7-6