/*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2013 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 <thread>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/scoped_ptr.hpp>
-#include <boost/shared_ptr.hpp>
+#include <memory>
#include <glog/logging.h>
#include "folly/ConcurrentSkipList-inl.h"
}
// create a shared_ptr skiplist object with initial head height.
- static boost::shared_ptr<SkipListType> createInstance(int height=1) {
- return boost::shared_ptr<SkipListType>(new SkipListType(height));
+ static std::shared_ptr<SkipListType> createInstance(int height=1) {
+ return std::shared_ptr<SkipListType>(new SkipListType(height));
}
// create a unique_ptr skiplist object with initial head height.
//===================================================================
~ConcurrentSkipList() {
- LOG_IF(FATAL, recycler_.refs() > 0)
- << "number of accessors is not 0, " << recycler_.refs() << " instead!"
- << " This shouldn't have happened!";
+ CHECK_EQ(recycler_.refs(), 0);
while (NodeType* current = head_.load(std::memory_order_relaxed)) {
NodeType* tmp = current->skip(0);
NodeType::destroy(current);
// list with the same key.
// pair.second stores whether the data is added successfully:
// 0 means not added, otherwise reutrns the new size.
- std::pair<NodeType*, size_t> addOrGetData(const value_type &data) {
+ template<typename U>
+ std::pair<NodeType*, size_t> addOrGetData(U &&data) {
NodeType *preds[MAX_HEIGHT], *succs[MAX_HEIGHT];
NodeType *newNode;
size_t newSize;
}
// locks acquired and all valid, need to modify the links under the locks.
- newNode = NodeType::create(nodeHeight, data);
+ newNode = NodeType::create(nodeHeight, std::forward<U>(data));
for (int layer = 0; layer < nodeHeight; ++layer) {
newNode->setSkip(layer, succs[layer]);
preds[layer]->setSkip(layer, newNode);
{ // need to guard the head node in case others are adding/removing
// nodes linked to the head.
ScopedLocker g = oldHead->acquireGuard();
- newHead->promoteFrom(oldHead);
+ newHead->copyHead(oldHead);
NodeType* expected = oldHead;
if (!head_.compare_exchange_strong(expected, newHead,
std::memory_order_release)) {
typedef typename SkipListType::const_iterator const_iterator;
typedef typename SkipListType::Skipper Skipper;
- explicit Accessor(boost::shared_ptr<ConcurrentSkipList> skip_list)
+ explicit Accessor(std::shared_ptr<ConcurrentSkipList> skip_list)
: slHolder_(std::move(skip_list))
{
sl_ = slHolder_.get();
const_iterator cbegin() const { return begin(); }
const_iterator cend() const { return end(); }
- std::pair<iterator, bool> insert(const key_type &data) {
- auto ret = sl_->addOrGetData(data);
+ template<typename U,
+ typename=typename std::enable_if<std::is_convertible<U, T>::value>::type>
+ std::pair<iterator, bool> insert(U&& data) {
+ auto ret = sl_->addOrGetData(std::forward<U>(data));
return std::make_pair(iterator(ret.first), ret.second);
}
size_t erase(const key_type &data) { return remove(data); }
private:
SkipListType *sl_;
- boost::shared_ptr<SkipListType> slHolder_;
+ std::shared_ptr<SkipListType> slHolder_;
};
// implements forward iterator concept.
typedef T* pointer;
typedef ptrdiff_t difference_type;
- Skipper(const boost::shared_ptr<SkipListType>& skipList) :
+ Skipper(const std::shared_ptr<SkipListType>& skipList) :
accessor_(skipList) {
init();
}