title: Shortening critical sections in thread-safe (unbalanced) Binary Tree
body: <p>I'm implementing a set of thread-safe functions that update and search an unbalanced binary tree with Pthreads (see <a href="https://www.nostarch.com/tlpi" rel="nofollow noreferrer">The Linux Programming Interface</a>: Exercise <a href="https://books.google.com/books?id=2SAQAQAAQBAJ&amp;lpg=PP1&amp;dq=TLPI%20exercise%2030.2&amp;pg=PA653#v=onepage&amp;q&amp;f=false" rel="nofollow noreferrer">30.2</a>).</p>
  
  <p>It's easy to implement a working tree that locks the entire body of functions like <code>add</code> or <code>delete</code>, but I believe it possible to implement an unbalanced binary (search) tree with a fine-grained locking strategy.</p>
  
  <p>I've tried to 'port' a variety of hand-over-hand locking schemes from other data structures described in '<a href="https://rads.stackoverflow.com/amzn/click/com/0123705916" rel="nofollow noreferrer" rel="nofollow noreferrer">The Art of Multiprocessor Programming</a>' but each requires that I transform the tree into a different primitive data structure (I'd like this to <em>use</em> an unbalanced binary tree as it's primitive data type, not just provide the same interface)</p>
  
  <p>For clarity, here is the data structure used to represent the nodes of this tree.</p>
  
  
  
  <pre><code>typedef struct bt_node {
      Key key;
      int value;
      struct bt_node *left;
      struct bt_node *right;
      pthread_mutex_t mutex;
  } bt_node;
  </code></pre>
  
  <p>(I also maintain a <code>bt_root</code> structure for bookkeeping purposes, which you may see in some functions below)</p>
  
  <p>The <code>add</code> function is essentially single-threaded as I end up locking the root node almost at the beginning of <code>add</code> and unlocking it after it's work is complete. Is it possible to do better here? (<code>lock</code> and <code>unlock</code> are wrappers around <a href="https://linux.die.net/man/3/pthread_mutex_lock" rel="nofollow noreferrer"><code>pthread_mutex_lock</code></a> and <a href="https://linux.die.net/man/3/pthread_mutex_unlock" rel="nofollow noreferrer"><code>pthread_mutex_unlock</code></a> for the structure above)</p>
  
  
  
  <pre><code>// This function is responsible for finding the last node that is going to be the parent of whichever node we are inserting.
  bt_node *closest_leaf(bt_node *root, Key key) {
      bt_node *current = root;
      bt_node *prev = NULL;
      while (current != NULL) {
          prev = current;
          if      (key &lt; current-&gt;key)  current = current-&gt;left;
          else if (key &gt; current-&gt;key)  current = current-&gt;right;
          else  {
              prev = current;
              break;
          }
      }
  
      return prev;
  }
  
  int add(bt_root *root_tree, Key key, int value) {
      bt_node *new_node = create_node(key, value);
      bt_node *current = root_tree-&gt;root;
  
      // this root creation code is not and need not be thread-safe.
      if (current == NULL) {
          root_tree-&gt;root = new_node;
          root_tree-&gt;node_count = 1;
          return 1;
      }
  
      lock(current);
      // just locking `leaf` &amp; `current` inside closest_leaf is incorrect
      bt_node *leaf = closest_leaf(current, key);
      if (key &lt; leaf-&gt;key) {
          leaf-&gt;left = new_node;
          ++root_tree-&gt;node_count;
      }
      else if (key &gt; leaf-&gt;key) {
          leaf-&gt;right = new_node;
          ++root_tree-&gt;node_count;
      } else {
          free(new_node);
      }
      unlock(current);
  
  
      return 1;
  }
  </code></pre>
  
  <p>Deletion shares this problem: successful deletion schemes effectively lock the entire tree. The code shown below omits mutex acquisition and relinquishment code (but the concept is the same as above).</p>
  
  
  
  <pre><code>// splice is the function responsible for actually removing a node from the tree
  void splice(bt_node *node, bt_node *parent) {
      // if it's a leaf, destroy it.
      if (!node-&gt;left &amp;&amp; !node-&gt;right) {
               replace_parent(parent, node, NULL);
  
      // if it has one child, have them be adopted by their grandparent
      } else if (node-&gt;left &amp;&amp; !node-&gt;right) {
              replace_parent(parent, node, node-&gt;left);
      } else if (node-&gt;right &amp;&amp; !node-&gt;left) {
              replace_parent(parent, node, node-&gt;right);
  
      /* if it has two children, take the smallest value of the right tree and
         replace the node with that one. */
      } else if (node-&gt;right &amp;&amp; node-&gt;left) {
          // find the smallest element of the right tree
          bt_node *smallest_parent = node;
          bt_node *smallest = node-&gt;right;
          while (smallest-&gt;left) {
              smallest_parent = smallest;
              // left is the smaller side
              smallest = smallest-&gt;left;
          }
  
          // "swap" the smallest.
          node-&gt;key = smallest-&gt;key;
          node-&gt;value = smallest-&gt;value;
  
          // unsure if this is correct -- seems to be only sensible thing to do
          smallest_parent-&gt;left = smallest-&gt;right;
          free(smallest);
      }
  }
  
  // search the tree depth-first for the node to remove
  int delete_dfs(bt_node *node, bt_node *parent, Key key) {
      if (node == NULL) return 0;
      Key node_key = node-&gt;key;
  
      // we've found the key, let's actually splice it out of the tree
      if (node_key == key) {
          splice(node, parent);
          return 1;
      }
  
      // otherwise we should search (depth first).
      if (key &lt; node_key) {
          return delete_dfs(node-&gt;left, node, key);
      } else if (key &gt; node_key) {
          return delete_dfs(node-&gt;right, node, key);
      }
  
      return 0;
  }
  
  void delete(bt_root *root_tree, Key key) {
      if (delete_dfs(root_tree-&gt;root, NULL, key)) root_tree-&gt;node_count--;
  }
  </code></pre>
  
  <p>Is there a better way?</p>