// ======================================================================== //
// Copyright 2009-2012 Intel Corporation //
// //
// Licensed under the Apache License, Version 2.0 (the "License"); //
// you may not use this file except in compliance with the License. //
// You may obtain a copy of the License at //
// //
// http://www.apache.org/licenses/LICENSE-2.0 //
// //
// Unless required by applicable law or agreed to in writing, software //
// distributed under the License is distributed on an "AS IS" BASIS, //
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. //
// See the License for the specific language governing permissions and //
// limitations under the License. //
// ======================================================================== //
#ifndef __EMBREE_ATOMIC_SET_H__
#define __EMBREE_ATOMIC_SET_H__
#include "sys/intrinsics.h"
namespace embree
{
/*! An atomic set. Insert calls are atomic and take calls are atomic
but only when not called intermixed. Thus one can only
atomically remove or insert items. */
template<typename T>
class __align(64) atomic_set
{
ALIGNED_CLASS;
public:
/*! set item */
class item : public T
{
public:
/*! default constructor */
item () : next(NULL) {}
public:
item* next;
};
/*! Iterator for the set. */
class iterator
{
public:
/*! default constructor */
__forceinline iterator ()
: root(NULL) {}
/*! initialize the iterator from a set */
__forceinline iterator (atomic_set& other)
: root(other.root) {}
/*! return next element */
__forceinline item* next()
{
item* ptr;
while (!try_take(ptr));
return ptr;
}
private:
__forceinline bool try_take(item*& ptr)
{
ptr = root;
if (ptr == NULL) return true;
return atomic_cmpxchg(&root,ptr->next,ptr) == ptr;
}
private:
item* root;
};
/*! Not thread safe iterator for iterating over elements of a list of blocks. */
class block_iterator_unsafe
{
typedef typename T::T Type;
public:
__forceinline block_iterator_unsafe (atomic_set& other)
: root(other.root), pos(0)
{
next();
}
__forceinline void operator++(int)
{
pos++;
next();
}
size_t size()
{
size_t s = 0;
while (root) {
s += root->size();
root = root->next;
}
return s;
}
__forceinline operator bool( ) const { return root; }
__forceinline const Type& operator*( ) const { return (*root)[pos]; }
__forceinline Type& operator*( ) { return (*root)[pos]; }
private:
__forceinline void next()
{
while (root && pos >= root->size()) {
root = root->next;
pos = 0;
}
}
private:
item* root;
size_t pos;
};
public:
/*! default constructor */
__forceinline atomic_set () : root(NULL) {}
/*! copy constructor */
__forceinline atomic_set (atomic_set& other) {
this->root = other.root; other.root = NULL;
}
/*! assignment operator */
__forceinline atomic_set& operator=(atomic_set& other) {
this->root = other.root; other.root = NULL;
return *this;
}
/*! add element to front of list */
__forceinline item* insert(item* ptr) {
while (!try_insert(ptr)); return ptr;
}
/*! remove element from front of list */
__forceinline item* take()
{
item* ptr;
while (!try_take(ptr));
return ptr;
}
/*! add element to front of list */
__forceinline item* insert_unsafe(item* ptr) {
ptr->next = root;
root = ptr;
return ptr;
}
/*! remove element from front of list */
__forceinline item* take_unsafe()
{
if (root == NULL) return NULL;
item* cur = root;
root = cur->next;
return cur;
}
private:
__forceinline bool try_insert(item* ptr)
{
if (ptr == NULL) return true;
item* cur = root;
ptr->next = cur;
return atomic_cmpxchg(&root,ptr,cur) == cur;
}
__forceinline bool try_take(item*& ptr)
{
ptr = root;
if (ptr == NULL) return true;
return atomic_cmpxchg(&root,ptr->next,ptr) == ptr;
}
private:
item* root;
};
}
#endif