Навязчивый, круговой, без ветвлений, двусвязный список — как получить список для идентификации полей члена узла?
Код размещен здесь: https://ideone.com/ul2PiS
Я пытаюсь разрешить пользователю указывать узлы списка как поля членов классов, которые будут добавлены в списки. В настоящее время это делается с помощью макроса с использованием offsetof (), что означает, что узлы-члены должны быть открытыми. В идеале мне бы хотелось как-то указать, как часть каждого объявления connected_list, в качестве параметра шаблона, какое поле члена следует использовать в качестве узла. повышение :: навязчивым кажется чтобы справиться с этим, но я не совсем понимаю, как они это делают.
Требуется, чтобы функции списков были без ветвлений (без сравнения указателей, у платформы очень и очень медленный механизм ветвления) и чтобы список был навязчивым и позволял объектам быть членами нескольких списков одновременно.
//////////////////////////////////////////////////////////////////////
// linked_list.h
#pragma once
//////////////////////////////////////////////////////////////////////
#include <cstddef>
#include <functional>
//////////////////////////////////////////////////////////////////////
struct list_node
{
list_node *next;
list_node *prev;
};
//////////////////////////////////////////////////////////////////////
template<typename T, size_t off> struct linked_list
{
//////////////////////////////////////////////////////////////////////
static list_node const *get_node(T const *o)
{
return reinterpret_cast<list_node const *>(reinterpret_cast<char const *>(o) + off);
}
//////////////////////////////////////////////////////////////////////
static list_node *get_node(T *o)
{
return reinterpret_cast<list_node *>(reinterpret_cast<char *>(o) + off);
}
//////////////////////////////////////////////////////////////////////
static T const *get_object(list_node const *node)
{
return reinterpret_cast<T const *>(reinterpret_cast<char const *>(node) - off);
}
//////////////////////////////////////////////////////////////////////
static T *get_object(list_node *node)
{
return reinterpret_cast<T *>(reinterpret_cast<char *>(node) - off);
}
//////////////////////////////////////////////////////////////////////
list_node root;
//////////////////////////////////////////////////////////////////////
linked_list()
{
root.next = &root;
root.prev = &root;
}
//////////////////////////////////////////////////////////////////////
void push_front(T *obj)
{
list_node *node = get_node(obj);
root.next->prev = node;
node->next = root.next;
node->prev = &root;
root.next = node;
}
//////////////////////////////////////////////////////////////////////
void push_front(T &obj)
{
list_node *node = get_node(&obj);
root.next->prev = node;
node->next = root.next;
node->prev = &root;
root.next = node;
}
//////////////////////////////////////////////////////////////////////
void push_back(T *obj)
{
list_node *node = get_node(obj);
node->prev = root.prev;
node->next = &root;
root.prev->next = node;
root.prev = node;
}
//////////////////////////////////////////////////////////////////////
void push_back(T &obj)
{
list_node *node = get_node(&obj);
node->prev = root.prev;
node->next = &root;
root.prev->next = node;
root.prev = node;
}
//////////////////////////////////////////////////////////////////////
void insert_before(T *pos, T *obj)
{
list_node *node = get_node(obj);
list_node *n = get_node(pos);
n->prev->next = node;
node->prev = n->prev;
n->prev = node;
node->next = n;
}
//////////////////////////////////////////////////////////////////////
void insert_before(T &pos, T &obj)
{
list_node *node = get_node(&obj);
list_node *n = get_node(&pos);
n->prev->next = node;
node->prev = n->prev;
n->prev = node;
node->next = n;
}
//////////////////////////////////////////////////////////////////////
void insert_after(T *pos, T *obj)
{
list_node *node = get_node(obj);
list_node *n = get_node(pos);
n->next->prev = node;
node->next = n->next;
n->next = node;
node->prev = n;
}
//////////////////////////////////////////////////////////////////////
void insert_after(T &pos, T &obj)
{
list_node *node = get_node(&obj);
list_node *n = get_node(&pos);
n->next->prev = node;
node->next = n->next;
n->next = node;
node->prev = n;
}
//////////////////////////////////////////////////////////////////////
void remove(T *obj)
{
list_node *node = get_node(obj);
node->prev->next = node->next;
node->next->prev = node->prev;
}
//////////////////////////////////////////////////////////////////////
void remove(T &obj)
{
list_node *node = get_node(&obj);
node->prev->next = node->next;
node->next->prev = node->prev;
}
//////////////////////////////////////////////////////////////////////
T *pop_back()
{
list_node *node = root.prev;
node->prev->next = node->next;
node->next->prev = node->prev;
return get_object(node);
}
//////////////////////////////////////////////////////////////////////
T *pop_front()
{
list_node *node = root.next;
node->next->prev = node->prev;
node->prev->next = node->next;
return get_object(node);
}
//////////////////////////////////////////////////////////////////////
bool empty() const
{
return root.next == &root;
}
//////////////////////////////////////////////////////////////////////
void clear()
{
root.next = root.prev = &root;
}
//////////////////////////////////////////////////////////////////////
T *head() const
{
return get_object(root.next);
}
//////////////////////////////////////////////////////////////////////
T *tail() const
{
return get_object(root.prev);
}
//////////////////////////////////////////////////////////////////////
T const *end()
{
return get_object(&root);
}
//////////////////////////////////////////////////////////////////////
T *next(T *i) const
{
return get_object(get_node(i)->next);
}
//////////////////////////////////////////////////////////////////////
T *prev(T *i) const
{
return get_object(get_node(i)->prev);
}
//////////////////////////////////////////////////////////////////////
bool for_each(std::function<bool (T *)> func)
{
for(T *i = head(); i != end(); i = next(i))
{
if(!func(i))
{
return false;
}
}
return true;
}
//////////////////////////////////////////////////////////////////////
T *find(std::function<bool (T *)> func)
{
for(T *i = head(); i != end(); i = next(i))
{
if(func(i))
{
return i;
}
}
return nullptr;
}
//////////////////////////////////////////////////////////////////////
};
//////////////////////////////////////////////////////////////////////
// Yuck:
#define declare_linked_list(type_name, node_name) \
linked_list<type_name, offsetof(type_name, node_name)>
#define typedef_linked_list(type_name, node_name) \
typedef declare_linked_list(type_name, node_name)
И код клиента выглядит так:
//////////////////////////////////////////////////////////////////////
// main.cpp
#include <stdio.h>
#include <random>
#include "linked_list.h"
struct foo
{
foo() : i(rand() % 10) { }
int i;
list_node node1; // would like it if these could be made private
list_node node2; // but the nasty macros need to see inside...
list_node node3; // getting rid of the macros would be even better
};
// None of these 3 options are very nice:
// 1. declare a list with the macro
declare_linked_list(foo, node1) list1;
// 2. or via a typedef
typedef_linked_list(foo, node2) list2_t;
list2_t list2;
// 3. or very wordy non-macro declaration
linked_list<foo, offsetof(foo, node3)> list3;
int main(int, char **)
{
printf("Begin\n");
foo foos[10];
for(int i=0; i<10; ++i)
{
list1.push_back(foos[i]);
list2.push_back(foos[i]);
list3.push_back(foos[i]);
}
int sum = 0;
int n = 0;
// but this for loop is clear and readable and has very low overhead
for(foo *i = list1.head(); i != list1.end(); i = list1.next(i))
{
sum += i->i;
}
printf("Total: %d\n", sum);
list2.remove(foos[2]);
n = 0;
sum = 0;
for(foo *i = list2.head(); i != list2.end(); i = list2.next(i))
{
sum += i->i;
}
printf("Total2: %d\n", sum);
getchar();
return 0;
}
template<typename T, list_node T::* node> struct linked_list
{
//////////////////////////////////////////////////////////////////////
static list_node const *get_node(T const *o)
{
return reinterpret_cast<list_node const *>
(reinterpret_cast<char const *>(o) + offsetof(T, *node));
}
//////////////////////////////////////////////////////////////////////
static list_node *get_node(T *o)
{
return reinterpret_cast<list_node *>
(reinterpret_cast<char *>(o) + offsetof(T, *node));
}
//////////////////////////////////////////////////////////////////////
static T const *get_object(list_node const *n)
{
return reinterpret_cast<T const *>
(reinterpret_cast<char const *>(n) - offsetof(T, *node));
}
//////////////////////////////////////////////////////////////////////
static T *get_object(list_node *n)
{
return reinterpret_cast<T *>
(reinterpret_cast<char *>(n) - offsetof(T, *node));
}
так что вы можете объявить списки как:
linked_list<foo, &foo::node1> list1;
поэтому мы (в основном) избавляемся от уродливого синтаксиса объявлений, хотя я до сих пор не могу найти способ разрешить им быть закрытыми. Похоже, boost :: intrusive требует, чтобы они были публичными.
Решение
Вот что-то вроде хака, который позволит сделать биективное отображение между членом и структурой, выполнив простую арифметику указателя для констант во время выполнения. static_assert( std::is_pod<T>::value, "POD needed!" ); может быть хорошей идеей:
template<typename T, typename N, N T::* member>
struct member_access {
static N& ContainerToMember( T& t ) { return t.*member; }
static N const& ContainerToMember( T const& t ) { return t.*member; }
template<T* ptr=nullptr>
static constexpr std::size_t offset_of() {
return reinterpret_cast<std::size_t>(reinterpret_cast<char*>(&((ptr)->*member)));
}
static T& MemberToContainer( N& n ) {
return *reinterpret_cast<T*>(reinterpret_cast<char*>(&n)-offset_of());
}
static T const& MemberToContainer( N const& n ) {
return *reinterpret_cast<T const*>(reinterpret_cast<char const*>(&n)-offset_of());
}
};
который избавляется от вашего offsetof требование.
Конфиденциальность это сложно. В системе типов конфиденциальности существует дыра с явным побочным эффектом специализации, но это приводит к указателям на элементы среды выполнения, и мы хотим скомпилировать значения времени.
Лучшим подходом может быть включение связанных списков в метапрограммирование:
template< typename T, unsigned index >
struct list_node:list_node<T, index-1> {
list_node* next;
list_node* prev;
T* self() { static_cast<T*>(this); }
T const* self() const { static_cast<T const*>(this); }
};
template<typename T>
struct list_node<T, 0> {
list_node* next;
list_node* prev;
T* self() { static_cast<T*>(this); }
T const* self() const { static_cast<T const*>(this); }
};
template<typename T, unsigned N>
struct listable : list_node<T, N-1> {};
template<typename T>
struct listable<T, 0> {};
затем просто создайте свои данные для списка, например:
struct data: listable<data, 10> {
std::string s;
};
Затем мы можем сделать это:
template<unsigned N, typename T>
list_node<T, N>& get_node( T& t ) { return t; }
template<unsigned N, typename T>
list_node<T, N> const& get_node( T const& t ) { return t; }
template<unsigned N, typename T>
T& get_data( list_node<T, N>& n ) { return *n.self(); }
template<unsigned N, typename T>
T const& get_data( list_node<T, N> const& n ) { return *n.self(); }
что все законно C ++ 11.
template<typename T, unsigned index>
struct linked_list {
typedef list_node<T, index> node;
};
что вроде приятно. Недостаток: list_node для каждого linked_list это другой тип. Обойти это немного сложно.
Мы могли бы оставаться в сфере определенного поведения, подталкивая все next а также prev указатели на массив POD за корнем самого верхнего list_node, Затем мы работаем с указателями на это. Мы можем юридически сделать арифметику указателей в этом массиве, и указатель на первый элемент самой наследственной структуры может быть юридически истолкован как указатель на эту структуру.
Из этого мы можем static_cast до T* напрямую (что, вероятно, вообще не является двоичным изменением значения указателя).
struct link { link* next; link* prev; };
template<typename T, unsigned N>
struct listable {
std::array<link, N> links;
static listable* array_to_list( std::array<link, N>* a ) { return reinterpret_cast<listable>(a); }
template<unsigned I>
static listable* link_to_list( link* l ) {
return array_to_list( reinterpret_cast<std::array<link, N>>(l - I) );
}
template<unsigned I>
link* get_link() { return &links[I]; }
T* listable_to_T() {
static_assert( std::is_base_of< listable, T >::value, "CRTP vailure" );
return static_cast<T*>(this);
}
template<unsigned I>
static T* link_to_T(link* l) {
return link_to_list<I>(l)->listable_to_T()
}
};
который в большинстве случаев требует, чтобы указатель на первый элемент и указатель на массив были совместимы с макетом (я надеюсь, что так!)
Опять же, в соответствии с этой моделью ваши данные для ссылок могут:
struct Bob : listable<Bob, 10> {};
сказать, что есть 10 встроенных списков в Bob, Преобразование из Bob к link* включает в себя обращение bob.get_link<5>()при конвертации из link* к Bob* является listable<Bob, 10>::link_to_T<5>( l )Предполагая, что речь идет о подсписке 5.
Другие решения
Других решений пока нет …