「データ構造とアルゴリズム」再入門

単方向リスト: 超基本編

Coarse-Grained Synchronization Singly-linked List(粗粒度同期 単方向リスト)

最も簡単な単方向リスト(Singly-linked List)から復習する。

データ構造

データ構造list_tとnode_tを定義する。 list_tはListの本体、node_tはListに連結するnodeのデータ構造である。

以降、共通のデータ型として"common.h"に"bool_t"、"lkey_t"、"val_t"を定義する。 "bool_t"は自明、 "lkey_t"はnodeのkey、"val_t"はnodeのvalを保持する。

common.h:

typedef bool bool_t;
typedef int32_t lkey_t;
typedef int32_t  val_t;

次に、nodeとlistのデータ構造を示す。

CoarseGrainedSynchroList .h:

typedef struct _node_t
{
  lkey_t key;            /* key */
  val_t val;             /* 値  */
  struct _node_t *next;  /* 次のnodeへのポインタ */
} node_t;

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

node_tは(key,val)のペアと、次のnodeへのポインタを保持する。

list_tには、リストの先頭headと末尾tail、およびlockのためのmutex変数が確保される。
末尾tailは必須でないが、以降でアルゴリズムを改造する際に必要となるので、 はじめから準備しておく。

基本関数

listの生成

/*
 * list_t *init_list(void)
 *
 * listを生成する。
 *
 * 成功すればlistへのポインタを返す。失敗ならNULLを返す。
 *
 */
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->next = list->tail;
  list->tail->next = NULL;
  list->mtx = (pthread_mutex_t) PTHREAD_MUTEX_INITIALIZER;
  
  return list;
  
 end:
  free(list->head);
  free(list);
  return NULL;
}

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 *pred, *curr;
  node_t *newNode;
  bool_t ret = true;
  
  if ((newNode = create_node(key, val)) == NULL)
    return false;
  
  lock(list->mtx);
  
  pred = list->head;
  curr = pred->next;
  
  if (curr == list->tail) {
    list->head->next = newNode;
    newNode->next = list->tail;
  } else {
    while (curr != list->tail && curr->key < key) {
      pred = curr;
      curr = curr->next;
    }
    
    if (curr != list->tail && key == curr->key) {
      free_node(newNode);
      ret = false;
    } else {
      newNode->next = curr;
      pred->next = newNode;
    }
  }
  
  unlock(list->mtx);

  return ret;
}

/*
 * 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 = calloc(1, sizeof(node_t))) == NULL) {
    elog("calloc error");
    return NULL;
  }
  node->key = key;
  node->val = val;
  
  return node;
}

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 *pred, *curr;
  bool_t ret = true;
  
  lock(list->mtx);
  
  pred = list->head;
  curr = pred->next;
  
  if (curr == list->tail) {
    ret = false;
  } else {
    while (curr->key < key && curr != list->tail) {
      pred = curr;
      curr = curr->next;
    }
    
    if (key == curr->key) {
      *val = curr->val;
      
      pred->next = curr->next;
      free_node(curr);
    } else
      ret = false;
  }
  
  unlock(list->mtx);
  return ret;
}

nodeの検索

/*
 * 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(list_t * list, const lkey_t key, val_t *val)
{
  node_t *pred, *curr;
  bool_t ret = true;
  
  lock(list->mtx);
  
  pred = list->head;
  curr = pred->next;
  
  if (curr == list->tail) {
    ret = false;
  } else {
    while (curr != list->tail && curr->key < key) {
      pred = curr;
      curr = curr->next;
    }
    if (curr != list->tail && key == curr->key) {
      *val = curr->val;
      ret = true;
    }
    else
      ret = false;
  }
  
  unlock(list->mtx);
  return ret;
}

実行