Status CASDList::InsertBefore()

in src/double-linked-list/doubly_linked_list.cc [98:155]

• 47 lines of code
• 5 McCabe index (conditional complexity)

Status CASDList::InsertBefore(DListNode* next, DListNode* node, bool) {
  RAW_CHECK(!((uint64_t)next & kNodeDeleted), "invalid next pointer state");
#ifdef PMEM
  RAW_CHECK(!((uint64_t)node & kDirtyFlag), "dirty node pointer");
  RAW_CHECK(!((uint64_t)next & kDirtyFlag), "dirty next pointer");
#endif

  if (next == &head_) {
    return InsertAfter(next, node);
  }

  DListNode* prev = nullptr;
  // Persist the payload
#ifdef PMEM
  NVRAM::Flush(node->payload_size, node->GetPayload());
#endif

  while (true) {
    prev = DereferenceNodePointer(&next->prev);
    // If the guy supposed to be behind me got deleted, fast
    // forward to its next node and retry
#ifdef PMEM
    auto* next_next = ReadPersist(&next->next);
#else
    auto* next_next = next->next;
#endif
    if ((uint64_t)next_next & kNodeDeleted) {
      next = GetNext(next);
#ifdef PMEM
      RAW_CHECK(!((uint64_t)next & kDirtyFlag), "dirty next pointer");
#endif
      prev = CorrectPrev(prev, next);  // using the new next
#ifdef PMEM
      RAW_CHECK(!((uint64_t)prev & kDirtyFlag), "dirty prev pointer");
#endif
      continue;
    }

    node->prev = (DListNode*)((uint64_t)prev & ~kNodeDeleted);
    node->next = (DListNode*)((uint64_t)next & ~kNodeDeleted);
#ifdef PMEM
    // Flush node.prev and node.next before installing
    NVRAM::Flush(sizeof(node->prev) + sizeof(node->next), &node->prev);
#endif

    // Install [node] on prev->next
    DListNode* expected = (DListNode*)((uint64_t)next & ~kNodeDeleted);
    if (expected == CompareExchange64Ptr(&prev->next, node, expected)) {
      break;
    }
    // Failed, get a new hopefully-correct prev
    prev = CorrectPrev(prev, next);
    backoff();
  }
  RAW_CHECK(prev, "invalid prev pointer");
  CorrectPrev(prev, next);
  return Status::OK();
}