/*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2015 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#include <boost/iterator/iterator_facade.hpp>
#include <glog/logging.h>
-#include "folly/ConcurrentSkipList-inl.h"
-#include "folly/Likely.h"
-#include "folly/Memory.h"
-#include "folly/SmallLocks.h"
+#include <folly/ConcurrentSkipList-inl.h>
+#include <folly/Likely.h>
+#include <folly/Memory.h>
+#include <folly/SmallLocks.h>
namespace folly {
bool found = false;
while (!found) {
// stepping down
- for (; ht > 0 && less(data, pred->skip(ht - 1)); --ht) {}
- if (ht == 0) return std::make_pair(pred->skip(0), 0); // not found
+ for (; ht > 0 && less(data, node = pred->skip(ht - 1)); --ht) {}
+ if (ht == 0) return std::make_pair(node, 0); // not found
+ // node <= data now, but we need to fix up ht
+ --ht;
- node = pred->skip(--ht); // node <= data now
// stepping right
while (greater(data, node)) {
pred = node;
findInsertionPoint(preds_[lyr], lyr, data, preds_, succs_);
if (foundLayer < 0) return false;
- DCHECK(succs_[0] != nullptr) << "lyr=" << lyr << "; max_layer=" << max_layer;
+ DCHECK(succs_[0] != nullptr) << "lyr=" << lyr
+ << "; max_layer=" << max_layer;
return !succs_[0]->markedForRemoval();
}