Сергей Деревяго

Вы научитесь создавать всевозможные структуры данных в любом доступном key-value store: массивы, списки, деревья, графы, маркизы... В общем, все что угодно!

Но угодно должно быть не все.

Т.к. главным открытием станет ders::mdb_deque -- Дек, на базе ders::mem_db. Этот вектор с двумя концами в Мире in-memory database -- он как швейцарский нож в Мире пластика!

Юзкейсы сумбурные, команда не может договориться? Молча достаньте нож...

С уважением, Сергей Деревяго.

2. Краеугольное

2.1. Структуры данных

Структуры данных второго порядка -- это о чем вообще?

В нашем случае, речь идет о структурах данных, реализованных внутри других структур данных.

А, ну типа вставляем в карту список и получаем диковинный map<list<int>>?

Гы! Все гораздо интереснее: мы в буквальном смысле создаем другую структуру данных на некоторых элементах базовой. И для стороннего наблюдателя это самый обычный контейнер. Но мы-то знаем... Но не расскажем!

Ну-ка, ну-ка. Давайте подробнее!

Ну вот смотрите. Допустим, где-то есть ассоциативный массив с тремя полезными лично для нас элементами:

cust1 data1 cust2 data2 cust3 data3

Типичный key-value store, все просто прекрасно! Пока кто-то не скажет, а дай-ка мне список твоих клиентов...

Гмм, key-value store за это не отвечает! Нашли дурака.

Ах так?! Ща ответят вторые порядки!

Список им подавай... Кому список -- наддайте ссылок:

Ого! И теперь:

Как найти начало списка "customers"? Добавляем префикс "|Head|" к имени "customers" и смотрим нет ли такого ключа. Есть! Значит первый элемент списка "customers" -- это "cust1".
А второй элемент? Добавляем префикс "|Next|" к первому элементу и проверяем ключ "|Next|cust1". Есть! Значит в списке как минимум два элемента.
А любой другой элемент? Добавляем префикс "|Next|" к текущему. Не нашли? Значит список закончился. Мы, например, не нашли "|Next|cust3", а значит "cust3" последний.

Так, хорошо. А если двусвязный список?

Используйте "|Next|" и "|Prev|":

Нужно наоборот? Стартуете с "|Tail|" и несетесь по "|Prev|"-ам никуда не сворачивая.

Шикарно! А если дерево?

Так ведь халява, сэр! Если в качестве базовой структуры использовать хеш-таблицу с транзакциями, то все структуры второго порядка автоматически становятся транзакционными:

Snapshot isolation? Пожалуйста! Вы никого не блокируя читаете snapshot всех структур сколько угодно времени.
Optimistic locking? Не вопрос! Разные транзакции одновременно изменяют разные части структуры не мешая друг другу.
Screwed up? Откатите транзакцию и никто не заметит.

Ну разве не Чудо?

2.2. Пример Customers/Orders

Все это конечно хорошо, но давайте подумаем, как мог бы выглядеть классический пример Customers/Orders в этом вашем key-value store с другими порядками. Функциональный аналог вот этих вот двух таблиц:

Customers

PK Id int AUTO_INCREMENT

Fields1 types1

Orders

PK Id int AUTO_INCREMENT

FK CustomerId int

Fields2 types2

С примерно такими вот данными:

Customers

Id Fields1

0 data0

1 data1

2 data2

Orders

Id CustomerId Fields2

0 0 data3

1 0 data4

2 0 data5

3 1 data6

4 1 data7

5 1 data8

6 2 data9

7 2 data10

8 2 data11

Ну что же, на первый взгляд:

Нам нужно дерево для Customers, упорядоченное по Id.
Нам нужен счетчик для Customers.Id.
Нам нужно дерево для Orders, упорядоченное по Id.
Нам нужен счетчик для Orders.Id.
Необходимо дополнить дерево Customers для хранения ссылок на соответствующие элементы Orders -- вы же заметили foreign key?

Да, кстати! Все ли здесь понимают, что добавление клиентов и заказов всегда происходит только с одной стороны?

В результате чего деревья будут вынуждены постоянно ребалансироваться, что приведет к существенным проблемам производительности!

Ой, беда... Если забыть про массивы!

Так почему бы нам вместо дерева не использовать массив Customers и присвоить Customers[0]=data0? А data1 загнать в Customers[1]. И так далее... Наш друг AUTO_INCREMENT великолепно подходит массиву: никаких дополнительных ссылок, забудьте балансировки. Даже сам счетчик не нужен -- песня!

Гмм, интересно. А как же Orders?

А Orders, ребята, растут из Customers[N]: мы юзаем массив массивов!

Смотрите. У нас есть массив Customers, содержащий данные по клиентам. Но каждый его элемент Customers[N] еще и определяет имя массива OrdersN, содержащего заказы клиента:

Customers: [
  [0]: data0,  ->  Orders0: [ data3, data4,  data5  ]
  [1]: data1,  ->  Orders1: [ data6, data7,  data8  ]
  [2]: data2   ->  Orders2: [ data9, data10, data11 ]
]

Таким образом, вместо сложных деревьев и счетчиков мы используем горстку простых массивов: Customers, Orders0, Orders1 и Orders2.

Красиво? Изумительно!

Но погодите бежать за пивом, пока не увидели Дек. Вот уж где Шедеврально!

3. Структуры на базе `ders::mem_db`

3.1. Общие сведения

В этом разделе описаны структуры данных второго порядка, созданные на базе ders::mem_db -- хеш-таблицы с транзакциями.

Конечно, все то же самое можно бы сделать и в std::unordered_map. Гы! Формально пригодны даже дрова std::map. Но мы не ищем глупых путей!

Итак, сразу самое важное. Прежде всего нужно четко понять, что ни объекты ders::mdb_deque, ни объекты ders::mdb_list НЕ являются хранилищем своих элементов! Все элементы всех структур живут в самом ders::mem_db.

Это можно себе представить как файлы на диске:

Вы создаете объект mdb_xxx (открываете файл).
Добавляете в него элементы (пишете в файл).
Удаляете объект mdb_xxx (закрываете файл).
Объект умер, но дело его живет!

Теперь ваши новые элементы лежат в mem_db, как и данные файла на диске. А чтобы их еще раз изменить/прочитать, вам снова понадобится объект mdb_xxx -- точно так же, как нужен объект file для доступа к файлу.

И как в случае файла, структура имеет имя (т.е. идентификатор). При этом, идентификаторы Деков и Списков никак не мешают друг другу, т.к. живут в разных пространствах имен (типа файлы из разных папок).

По функционалу, интерфейс каждой структуры всегда разбит на две части: mdb_xxx и mdb_xxx_reader. Старайтесь явно использовать mdb_xxx_reader там, где не предполагаются изменения.

Вдобавок, у всех структур есть одинаковый набор статических функций:

bool exists(mem_pool* mp, ptrsz id, const reader* rd) -- существует ли структура id в rd.
bool remove(mem_pool* mp, ptrsz id, writer* wr) -- удаляет структуру id из wr.
un_ptr<blob> obj_key(mem_pool* mp, ptrsz id) -- ключ структуры id.
un_ptr<mdb_xxx_reader> open_rd(mem_pool* mp, ptrsz id, const reader* rd) -- открывает структуру id для чтения, если она существует.
un_ptr<mdb_xxx> open(mem_pool* mp, bool create, ptrsz id, writer* wr) -- создает/открывает структуру id для чтения/записи. Будет создана, если create==true.

3.2. Дек `ders::mdb_deque`

Итак, знакомьтесь: Его Величество mdb_deque! Гениальная в своей простоте структура.

Он эффективно покрывает процентов 90 всех потребностей! А если кажется, что не подходит, то нужно подумать о вложенных/дополнительных Деках и косвенной адресации.

derslib/inc/ders/mdb/deque.hpp

struct mdb_deque_reader : deletable { virtual int beg() const=0; virtual int end() const=0; bool empty() const { return beg()==end(); } virtual bool get(int pos, ptrsz* pval) const=0; virtual un_ptr<blob> key(int pos) const=0; virtual bool get_front(ptrsz* pval) const=0; virtual bool get_back(ptrsz* pval) const=0; mdb_deque_reader& operator=(const mdb_deque_reader&)=delete; }; struct mdb_deque : mdb_deque_reader { static bool exists(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static bool remove(mem_pool* mp, ptrsz id, mem_db::writer* wr); static un_ptr<blob> obj_key(mem_pool* mp, ptrsz id); static un_ptr<mdb_deque_reader> open_rd(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static un_ptr<mdb_deque> open(mem_pool* mp, bool create, ptrsz id, mem_db::writer* wr); virtual void resize(int new_beg, int new_end)=0; virtual void clear()=0; virtual void set(int pos, ptrsz val)=0; virtual void del(int pos)=0; virtual int add_front(ptrsz val)=0; virtual int add_back(ptrsz val)=0; virtual bool del_front()=0; virtual bool del_back()=0; virtual void trim_front()=0; virtual void trim_back()=0; };

derslib/inc/ders/mdb/deque.hpp
struct mdb_deque_reader : deletable { virtual int beg() const=0; virtual int end() const=0; bool empty() const { return beg()==end(); } virtual bool get(int pos, ptrsz* pval) const=0; virtual un_ptr<blob> key(int pos) const=0; virtual bool get_front(ptrsz* pval) const=0; virtual bool get_back(ptrsz* pval) const=0; mdb_deque_reader& operator=(const mdb_deque_reader&)=delete; }; struct mdb_deque : mdb_deque_reader { static bool exists(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static bool remove(mem_pool* mp, ptrsz id, mem_db::writer* wr); static un_ptr<blob> obj_key(mem_pool* mp, ptrsz id); static un_ptr<mdb_deque_reader> open_rd(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static un_ptr<mdb_deque> open(mem_pool* mp, bool create, ptrsz id, mem_db::writer* wr); virtual void resize(int new_beg, int new_end)=0; virtual void clear()=0; virtual void set(int pos, ptrsz val)=0; virtual void del(int pos)=0; virtual int add_front(ptrsz val)=0; virtual int add_back(ptrsz val)=0; virtual bool del_front()=0; virtual bool del_back()=0; virtual void trim_front()=0; virtual void trim_back()=0; };

Сам объект mdb_deque -- это всего пара индексов: первого и запоследнего элементов. Их возвращают функции beg() и end(). Таким образом, при работе с get(), set() и del(), нужно указывать индексы в диапазоне [beg(), end()-1].

Интерфейс mdb_deque_reader

int beg() const индекс первого элемента

int end() const индекс запоследнего элемента

bool get(int pos, ptrsz* pval) присваивает *pval элемент pos, если он существует

un_ptr<blob> key(int pos) const ключ элемента pos

bool get_front(ptrsz* pval) const присваивает *pval первый элемент, если он существует

bool get_back(ptrsz* pval) const присваивает *pval последний элемент, если он существует

Интерфейс `mdb_deque_reader`
`int beg() const`	индекс первого элемента
`int end() const`	индекс запоследнего элемента
`bool get(int pos, ptrsz* pval)`	присваивает `*pval` элемент `pos`, если он существует
`un_ptr<blob> key(int pos) const`	ключ элемента `pos`
`bool get_front(ptrsz* pval) const`	присваивает `*pval` первый элемент, если он существует
`bool get_back(ptrsz* pval) const`	присваивает `*pval` последний элемент, если он существует

Интерфейс mdb_deque

void resize(int new_beg, int new_end) изменяет границы Дека, удаляя элементы за их пределами

void clear() удаляет все элементы и устанавливает нулевые границы

void set(int pos, ptrsz val) присваивает val элементу pos

void del(int pos) удаляет элемент pos

int add_front(ptrsz val) добавляет val в начало Дека и возвращает индекс. изменяет границу

int add_back(ptrsz val) добавляет val в конец Дека и возвращает индекс. изменяет границу

bool del_front() удаляет первый элемент, если он существует. изменяет границу

bool del_back() удаляет последний элемент, если он существует. изменяет границу

void trim_front() изменяет начальную границу, отбрасывая несуществующие элементы

void trim_back() изменяет конечную границу, отбрасывая несуществующие элементы

Интерфейс `mdb_deque`
`void resize(int new_beg, int new_end)`	изменяет границы Дека, удаляя элементы за их пределами
`void clear()`	удаляет все элементы и устанавливает нулевые границы
`void set(int pos, ptrsz val)`	присваивает `val` элементу `pos`
`void del(int pos)`	удаляет элемент `pos`
`int add_front(ptrsz val)`	добавляет `val` в начало Дека и возвращает индекс. изменяет границу
`int add_back(ptrsz val)`	добавляет `val` в конец Дека и возвращает индекс. изменяет границу
`bool del_front()`	удаляет первый элемент, если он существует. изменяет границу
`bool del_back()`	удаляет последний элемент, если он существует. изменяет границу
`void trim_front()`	изменяет начальную границу, отбрасывая несуществующие элементы
`void trim_back()`	изменяет конечную границу, отбрасывая несуществующие элементы

3.3. Список `ders::mdb_list`

А это mdb_list -- двусвязный список уникальных ключей. Сгодятся даже несуществующие.

derslib/inc/ders/mdb/list.hpp

struct mdb_list_reader : deletable { virtual bool empty() const=0; virtual bool belongs(ptrsz key) const=0; virtual bool key_front(ptrsz* front) const=0; virtual bool key_back(ptrsz* back) const=0; virtual bool key_prev(ptrsz pos, ptrsz* prev) const=0; virtual bool key_next(ptrsz pos, ptrsz* next) const=0; mdb_list_reader& operator=(const mdb_list_reader&)=delete; }; struct mdb_list : mdb_list_reader { static bool exists(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static bool remove(mem_pool* mp, ptrsz id, mem_db::writer* wr); static un_ptr<blob> obj_key(mem_pool* mp, ptrsz id); static un_ptr<mdb_list_reader> open_rd(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static un_ptr<mdb_list> open(mem_pool* mp, bool create, ptrsz id, mem_db::writer* wr); virtual void add_front(ptrsz key)=0; virtual void add_back(ptrsz key)=0; virtual void add_before(ptrsz pos, ptrsz key)=0; virtual void add_after(ptrsz pos, ptrsz key)=0; virtual bool del_front()=0; virtual bool del_back()=0; virtual void del(ptrsz key)=0; virtual int clear()=0; };

derslib/inc/ders/mdb/list.hpp
struct mdb_list_reader : deletable { virtual bool empty() const=0; virtual bool belongs(ptrsz key) const=0; virtual bool key_front(ptrsz* front) const=0; virtual bool key_back(ptrsz* back) const=0; virtual bool key_prev(ptrsz pos, ptrsz* prev) const=0; virtual bool key_next(ptrsz pos, ptrsz* next) const=0; mdb_list_reader& operator=(const mdb_list_reader&)=delete; }; struct mdb_list : mdb_list_reader { static bool exists(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static bool remove(mem_pool* mp, ptrsz id, mem_db::writer* wr); static un_ptr<blob> obj_key(mem_pool* mp, ptrsz id); static un_ptr<mdb_list_reader> open_rd(mem_pool* mp, ptrsz id, const mem_db::reader* rd); static un_ptr<mdb_list> open(mem_pool* mp, bool create, ptrsz id, mem_db::writer* wr); virtual void add_front(ptrsz key)=0; virtual void add_back(ptrsz key)=0; virtual void add_before(ptrsz pos, ptrsz key)=0; virtual void add_after(ptrsz pos, ptrsz key)=0; virtual bool del_front()=0; virtual bool del_back()=0; virtual void del(ptrsz key)=0; virtual int clear()=0; };

Обратите внимание, что ключ может принадлежать сразу нескольким Спискам. Поэтому добавление/удаление ключа никак не влияет на сам элемент в mem_db (если он вообще существует).

Интерфейс mdb_list_reader

bool empty() const пустой ли

bool belongs(ptrsz key) const принадлежит ли key

bool key_front(ptrsz* front) const присваивает первый ключ, если он существует

bool key_back(ptrsz* back) const присваивает последний ключ, если он существует

bool key_prev(ptrsz pos, ptrsz* prev) const присваивает предшествующий pos ключ, если он существует

bool key_next(ptrsz pos, ptrsz* next) const присваивает следующий за pos ключ, если он существует

Интерфейс `mdb_list_reader`
`bool empty() const`	пустой ли
`bool belongs(ptrsz key) const`	принадлежит ли `key`
`bool key_front(ptrsz* front) const`	присваивает первый ключ, если он существует
`bool key_back(ptrsz* back) const`	присваивает последний ключ, если он существует
`bool key_prev(ptrsz pos, ptrsz* prev) const`	присваивает предшествующий `pos` ключ, если он существует
`bool key_next(ptrsz pos, ptrsz* next) const`	присваивает следующий за `pos` ключ, если он существует

Интерфейс mdb_list

void add_front(ptrsz key) добавляет key в начало

void add_back(ptrsz key) добавляет key в конец

void add_before(ptrsz pos, ptrsz key) добавляет key перед pos

void add_after(ptrsz pos, ptrsz key) добавляет key после pos

bool del_front() удаляет первый ключ, если он существует

bool del_back() удаляет последний ключ, если он существует

void del(ptrsz key) удаляет key

int clear() удаляет все элементы и возвращает количество

Интерфейс `mdb_list`
`void add_front(ptrsz key)`	добавляет `key` в начало
`void add_back(ptrsz key)`	добавляет `key` в конец
`void add_before(ptrsz pos, ptrsz key)`	добавляет `key` перед `pos`
`void add_after(ptrsz pos, ptrsz key)`	добавляет `key` после `pos`
`bool del_front()`	удаляет первый ключ, если он существует
`bool del_back()`	удаляет последний ключ, если он существует
`void del(ptrsz key)`	удаляет `key`
`int clear()`	удаляет все элементы и возвращает количество

4. Примеры использования

4.1. `mdb_deque`: основы

Пример первый, базовый. Здесь мы попробуем на зуб функциональность и аккуратно заглянем под крышечку.

deque/example1.cpp

strsz DQ_NAME1("custs"); void cb1(mem_db::writer* wr, void* arg) { auto mp=(mem_pool*)arg; auto md=mdb_deque::open(mp, true, DQ_NAME1, wr); md->add_back(strsz("cust1")); md->add_front(strsz("cust2")); md->add_back(strsz("cust3")); md->add_front(strsz("cust4")); } void cb2(mem_db::writer* wr, void* arg) { auto mp=(mem_pool*)arg; auto md=mdb_deque::open(mp, false, DQ_NAME1, wr); assert(md); md->del(-1); md->set(0, strsz("updated")); } void cb3(mem_db::writer* wr, void* arg) { auto mp=(mem_pool*)arg; auto md=mdb_deque::open(mp, false, DQ_NAME1, wr); assert(md); md->resize(md->beg()+1, md->end()-1); } void example1(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); mdb->write(cb1, mp); prnDeque(out, mdb, DQ_NAME1); prnDb(out, mdb); mdb->write(cb2, mp); prnDeque(out, mdb, DQ_NAME1); prnDb(out, mdb); mdb->write(cb3, mp); prnDeque(out, mdb, DQ_NAME1); prnDb(out, mdb); }

deque/example1.cpp
strsz DQ_NAME1("custs"); void cb1(mem_db::writer* wr, void* arg) { auto mp=(mem_pool)arg; auto md=mdb_deque::open(mp, true, DQ_NAME1, wr); md->add_back(strsz("cust1")); md->add_front(strsz("cust2")); md->add_back(strsz("cust3")); md->add_front(strsz("cust4"));* } void cb2(mem_db::writer* wr, void* arg) { auto mp=(mem_pool)arg; auto md=mdb_deque::open(mp, false, DQ_NAME1, wr); assert(md); md->del(-1); md->set(0, strsz("updated"));* } void cb3(mem_db::writer* wr, void* arg) { auto mp=(mem_pool)arg; auto md=mdb_deque::open(mp, false, DQ_NAME1, wr); assert(md); md->resize(md->beg()+1, md->end()-1);* } void example1(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); mdb->write(cb1, mp); prnDeque(out, mdb, DQ_NAME1); prnDb(out, mdb); mdb->write(cb2, mp); prnDeque(out, mdb, DQ_NAME1); prnDb(out, mdb); mdb->write(cb3, mp); prnDeque(out, mdb, DQ_NAME1); prnDb(out, mdb); }

После первого вызова mdb->write(cb1, mp) мы видим такую картину:

prnDeque(custs) prnDb()

beg()=-2 end()=2 -2 cust4 -1 cust2 0 cust1 1 cust3

|D|BE|custs FEFFFFFF02000000 |D|E|custs|FEFFFFFF cust4 |D|E|custs|FFFFFFFF cust2 |D|E|custs|00000000 cust1 |D|E|custs|01000000 cust3

`prnDeque(custs)`	`prnDb()`
beg()=-2 end()=2 -2 cust4 -1 cust2 0 cust1 1 cust3	\|D\|BE\|custs FEFFFFFF02000000 \|D\|E\|custs\|FEFFFFFF cust4 \|D\|E\|custs\|FFFFFFFF cust2 \|D\|E\|custs\|00000000 cust1 \|D\|E\|custs\|01000000 cust3

А именно:

Объект mdb_deque с идентификатором custs сохранен по ключу |D|BE|custs. Его ключ -- это custs с префиксом |Deque|BegEnd|. Его данные -- это два int: -2 и 2.
Начальный элемент сохранен по ключу |D|E|custs|FEFFFFFF. Его ключ -- это int(-2) с префиксом |Deque|Elem|custs|. Его данные -- cust4.
Конечный элемент сохранен по ключу |D|E|custs|01000000. Его ключ -- int(1) с тем же префиксом. Его данные -- cust3.

Как видите, ничего лишнего: два int в |D|BE|custs плюс элементы. У людей грабли сложнее!

А после всех изменений мы обнаружим:

prnDeque(custs) prnDb()

beg()=-1 end()=1 -1 0 updated

|D|BE|custs FFFFFFFF01000000 |D|E|custs|00000000 updated

`prnDeque(custs)`	`prnDb()`
beg()=-1 end()=1 -1 0 updated	\|D\|BE\|custs FFFFFFFF01000000 \|D\|E\|custs\|00000000 updated

И здесь важно заметить один ключевой момент: ключа |D|E|custs|FFFFFFF больше не существует! Мы его удалили с помощью md->del(-1), и там теперь дырка от бублика.

Тем не менее, prnDeque(custs) выводит строку и для индекса -1 (без значения), т.к. beg()=-1. Т.е. несмотря на отсутствие самого элемента custs[-1], Дек начинается с индекса -1!

Если это проблема, то:

Всегда можно вызвать trim_front() -- он скорректирует начальную границу.
Или сразу использовать del_front() -- и элементы будут уходить с границей!

Как вы уже поняли, "единственно верного" способа не существует. Все зависит от цели: del() сразу дырявит, не ищет крайнего!

4.2. `mdb_deque`: реальный пример

Ура, дождались!

Прошу любить и жаловать: реальный пример Customers/Orders с полным набором функций:

deque/example2.cpp

int addCustomer(mem_pool* mp, mem_db* mdb, ptrsz val); un_ptr<mdb_deque_reader> getCustomers(mem_pool* mp, const mem_db::reader* rd); bool getCustomer(mem_pool* mp, const mem_db::reader* rd, int custN, ptrsz* pval); void setCustomer(mem_pool* mp, mem_db* mdb, int custN, ptrsz val); void delCustomer(mem_pool* mp, mem_db* mdb, int custN); void delCustomers(mem_pool* mp, mem_db* mdb); int addOrder(mem_pool* mp, mem_db* mdb, int custN, ptrsz val); un_ptr<mdb_deque_reader> getOrders(mem_pool* mp, const mem_db::reader* rd, int custN); bool getOrder(mem_pool* mp, const mem_db::reader* rd, int custN, int ordN, ptrsz* pval); void setOrder(mem_pool* mp, mem_db* mdb, int custN, int ordN, ptrsz val); void delOrder(mem_pool* mp, mem_db* mdb, int custN, int ordN); void delOrders(mem_pool* mp, mem_db* mdb, int custN); void example2(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); Listener lnr(out); mdb->set_listener(&lnr); int bk=addCustomer(mp, mdb, strsz("Brian Kernighan")); int dr=addCustomer(mp, mdb, strsz("Dennis Ritchie")); int bs=addCustomer(mp, mdb, strsz("Bjarne Stroustrup")); prnDeques(out, mdb); prnDb(out, mdb); addOrder(mp, mdb, bk, strsz("Somewhere Far Beyond")); addOrder(mp, mdb, bk, strsz("Imaginations from the Other Side")); addOrder(mp, mdb, dr, strsz("Seventh Son of a Seventh Son")); addOrder(mp, mdb, dr, strsz("Brave New World")); addOrder(mp, mdb, bs, strsz("Walls of Jericho")); addOrder(mp, mdb, bs, strsz("Keeper of the Seven Keys")); prnDeques(out, mdb); prnDb(out, mdb); setCustomer(mp, mdb, bk, strsz("updated customer")); setOrder(mp, mdb, bk, 1, strsz("updated order")); delOrder(mp, mdb, dr, 0); delCustomer(mp, mdb, bs); prnDeques(out, mdb); prnDb(out, mdb); }

deque/example2.cpp
int addCustomer(mem_pool* mp, mem_db* mdb, ptrsz val); un_ptr<mdb_deque_reader> getCustomers(mem_pool* mp, const mem_db::reader* rd); bool getCustomer(mem_pool* mp, const mem_db::reader* rd, int custN, ptrsz* pval); void setCustomer(mem_pool* mp, mem_db* mdb, int custN, ptrsz val); void delCustomer(mem_pool* mp, mem_db* mdb, int custN); void delCustomers(mem_pool* mp, mem_db* mdb); int addOrder(mem_pool* mp, mem_db* mdb, int custN, ptrsz val); un_ptr<mdb_deque_reader> getOrders(mem_pool* mp, const mem_db::reader* rd, int custN); bool getOrder(mem_pool* mp, const mem_db::reader* rd, int custN, int ordN, ptrsz* pval); void setOrder(mem_pool* mp, mem_db* mdb, int custN, int ordN, ptrsz val); void delOrder(mem_pool* mp, mem_db* mdb, int custN, int ordN); void delOrders(mem_pool* mp, mem_db* mdb, int custN); void example2(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); Listener lnr(out); mdb->set_listener(&lnr); int bk=addCustomer(mp, mdb, strsz("Brian Kernighan")); int dr=addCustomer(mp, mdb, strsz("Dennis Ritchie")); int bs=addCustomer(mp, mdb, strsz("Bjarne Stroustrup")); prnDeques(out, mdb); prnDb(out, mdb); addOrder(mp, mdb, bk, strsz("Somewhere Far Beyond")); addOrder(mp, mdb, bk, strsz("Imaginations from the Other Side")); addOrder(mp, mdb, dr, strsz("Seventh Son of a Seventh Son")); addOrder(mp, mdb, dr, strsz("Brave New World")); addOrder(mp, mdb, bs, strsz("Walls of Jericho")); addOrder(mp, mdb, bs, strsz("Keeper of the Seven Keys")); prnDeques(out, mdb); prnDb(out, mdb); setCustomer(mp, mdb, bk, strsz("updated customer")); setOrder(mp, mdb, bk, 1, strsz("updated order")); delOrder(mp, mdb, dr, 0); delCustomer(mp, mdb, bs); prnDeques(out, mdb); prnDb(out, mdb); }

Как и следовало ожидать, добавление странных клиентов в Дек cust/ord с помощью addCustomer() создает привычную картину:

prnDeques() prnDb()

beg()=0 end()=3 0 Brian Kernighan 1 Dennis Ritchie 2 Bjarne Stroustrup

|D|BE|cust/ord 0000000003000000 |D|E|cust/ord|00000000 Brian Kernighan |D|E|cust/ord|01000000 Dennis Ritchie |D|E|cust/ord|02000000 Bjarne Stroustrup

`prnDeques()`	`prnDb()`
beg()=0 end()=3 0 Brian Kernighan 1 Dennis Ritchie 2 Bjarne Stroustrup	\|D\|BE\|cust/ord 0000000003000000 \|D\|E\|cust/ord\|00000000 Brian Kernighan \|D\|E\|cust/ord\|01000000 Dennis Ritchie \|D\|E\|cust/ord\|02000000 Bjarne Stroustrup

А вот заказы -- это весело! Наконец-то мы видим Дек Деков в интимных подробностях:

prnDeques() prnDb()

beg()=0 end()=3 0 Brian Kernighan 0 beg()=0 end()=2 0 0 Somewhere Far Beyond 0 1 Imaginations from the Other Side 1 Dennis Ritchie 1 beg()=0 end()=2 1 0 Seventh Son of a Seventh Son 1 1 Brave New World 2 Bjarne Stroustrup 2 beg()=0 end()=2 2 0 Walls of Jericho 2 1 Keeper of the Seven Keys

|D|BE|cust/ord 0000000003000000 |D|E|cust/ord|00000000 Brian Kernighan |D|BE||D|E|cust/ord|00000000 0000000002000000 |D|E||D|E|cust/ord|00000000|00000000 Somewhere Far Beyond |D|E||D|E|cust/ord|00000000|01000000 Imaginations from the Other Side |D|E|cust/ord|01000000 Dennis Ritchie |D|BE||D|E|cust/ord|01000000 0000000002000000 |D|E||D|E|cust/ord|01000000|00000000 Seventh Son of a Seventh Son |D|E||D|E|cust/ord|01000000|01000000 Brave New World |D|E|cust/ord|02000000 Bjarne Stroustrup |D|BE||D|E|cust/ord|02000000 0000000002000000 |D|E||D|E|cust/ord|02000000|00000000 Walls of Jericho |D|E||D|E|cust/ord|02000000|01000000 Keeper of the Seven Keys

`prnDeques()`	`prnDb()`
beg()=0 end()=3 0 Brian Kernighan 0 beg()=0 end()=2 0 0 Somewhere Far Beyond 0 1 Imaginations from the Other Side 1 Dennis Ritchie 1 beg()=0 end()=2 1 0 Seventh Son of a Seventh Son 1 1 Brave New World 2 Bjarne Stroustrup 2 beg()=0 end()=2 2 0 Walls of Jericho 2 1 Keeper of the Seven Keys	\|D\|BE\|cust/ord 0000000003000000 \|D\|E\|cust/ord\|00000000 Brian Kernighan \|D\|BE\|\|D\|E\|cust/ord\|00000000 0000000002000000 \|D\|E\|\|D\|E\|cust/ord\|00000000\|00000000 Somewhere Far Beyond \|D\|E\|\|D\|E\|cust/ord\|00000000\|01000000 Imaginations from the Other Side \|D\|E\|cust/ord\|01000000 Dennis Ritchie \|D\|BE\|\|D\|E\|cust/ord\|01000000 0000000002000000 \|D\|E\|\|D\|E\|cust/ord\|01000000\|00000000 Seventh Son of a Seventh Son \|D\|E\|\|D\|E\|cust/ord\|01000000\|01000000 Brave New World \|D\|E\|cust/ord\|02000000 Bjarne Stroustrup \|D\|BE\|\|D\|E\|cust/ord\|02000000 0000000002000000 \|D\|E\|\|D\|E\|cust/ord\|02000000\|00000000 Walls of Jericho \|D\|E\|\|D\|E\|cust/ord\|02000000\|01000000 Keeper of the Seven Keys

Впечатляет? Погнали!

Здесь живут сразу четыре Дека. Они легко определяются по префиксу |D|BE|:
1. |D|BE|cust/ord
2. |D|BE||D|E|cust/ord|00000000
3. |D|BE||D|E|cust/ord|01000000
4. |D|BE||D|E|cust/ord|02000000
Первый Дек мы уже показали. В нем известные имена.
Имя второго Дека -- |D|E|cust/ord|00000000. Это ключ нулевого элемента клиентов. Таким образом, ключ объекта второго Дека -- это префикс плюс имя: |D|BE| + |D|E|cust/ord|00000000.
Аналогично для всех остальных: |D|E|cust/ord|01000000 и |D|E|cust/ord|02000000. Просто добавьте префикс.
Ключи заказов формируются схожим образом, но кроме префикса работает и суффикс:
- Если имя Дека клиентов cust/ord, то ключ второго элемента: |D|E| + cust/ord + |02000000. Это Bjarne Stroustrup.
- Значит имя Дека его заказов: |D|E|cust/ord|02000000. А ключ первого элемента: |D|E| + |D|E|cust/ord|02000000 + |01000000. Это Keeper of the Seven Keys.

Короче, простая понятная схема. Хотя и рябит в глазах.

Что-что, говорите?

Да, можно и код показать. Хотя лучше, конечно, смотреть самому -- дерзновенно изменять и запускать! Но фрагментик не повредит:

deque/example2.cpp

strsz DQ_NAME2("cust/ord"); struct ArgSetOrder { mem_pool* mp; int custN; int ordN; ptrsz val; }; void cbSetOrder(mem_db::writer* wr, void* arg) { auto a=(ArgSetOrder*)arg; auto mp=a->mp; auto mdc=mdb_deque::open_rd(mp, DQ_NAME2, wr); checkPos(mp, FLLN, get(mdc), a->custN); auto mdo=mdb_deque::open(mp, false, mdc->key(a->custN)->ptr(), wr); checkPos(mp, FLLN, get(mdo), a->ordN); mdo->set(a->ordN, a->val); } void setOrder(mem_pool* mp, mem_db* mdb, int custN, int ordN, ptrsz val) { ArgSetOrder arg{mp, custN, ordN, val}; mdb->write(cbSetOrder, &arg); }

deque/example2.cpp
strsz DQ_NAME2("cust/ord"); struct ArgSetOrder { mem_pool* mp; int custN; int ordN; ptrsz val; }; void cbSetOrder(mem_db::writer* wr, void* arg) { auto a=(ArgSetOrder)arg; auto mp=a->mp; auto mdc=mdb_deque::open_rd(mp, DQ_NAME2, wr);* checkPos(mp, FLLN, get(mdc), a->custN); auto mdo=mdb_deque::open(mp, false, mdc->key(a->custN)->ptr(), wr); checkPos(mp, FLLN, get(mdo), a->ordN); mdo->set(a->ordN, a->val); } void setOrder(mem_pool* mp, mem_db* mdb, int custN, int ordN, ptrsz val) { ArgSetOrder arg{mp, custN, ordN, val}; mdb->write(cbSetOrder, &arg); }

Все достаточно прямолинейно:

Определяем структуру ArgSetOrder для передачи аргументов в колбэк.
Пишем колбэк cbSetOrder() -- он, собственно, и выполняет работу:
1. Открываем Дек клиентов по чтению: open_rd(mp, DQ_NAME2, wr).
2. Генерируем id Дека заказов и открываем по записи: open(mp, false, mdc->key(a->custN)->ptr(), wr).
3. Устанавливаем значение: mdo->set(a->ordN, a->val).
А, ну еще и сама setOrder(). Просто обертка.

Все остальные функции реализованы по той же схеме. Конечно, не без нюансов, но все станет понятно по ходу работы.

А пока можно брать как есть. Даже нужно.

4.3. `mdb_deque`: дополнительные индексы

Ага, все похоже на взрослую Базу!

Вот только дополнительные индексы... Например, таблица пользователей форума: уникальный номер юзера -- это конечно круто, но хотелось бы и уникальный ник! Ну вот представьте Бритни Спирс на форуме домохозяек -- все программисты сразу разбегутся!

В общем, хотелось бы индекс по users.NickName.

Эх, без ножа ты меня режешь... Ну, то есть, даже не нужен "швейцарский нож"!

Любой key-value store обеспечивает поиск по ключу? Прекрасно! Значит сохраняем ники прямо в базу: есть там уже |UI|users|bs? Кто-то с песней проходит мимо:

deque/example3.cpp

strsz PR_UNIQ_IND("|UI|"); strsz DQ_NAME3("users"); struct ArgAddUser { mem_pool* mp; const UserBlob* ub; int ret; }; void cbAddUser(mem_db::writer* wr, void* arg) { auto a=(ArgAddUser*)arg; auto mp=a->mp; auto key=new_blob(mp, PR_UNIQ_IND, DQ_NAME3, strsz("|"), a->ub->getNickName()); ptrsz val; if (wr->get(key->ptr(), &val)) throw newExc<Exception>(mp, mp, FLLN, tx_buf(mp)+"Duplicate index: "+a->ub->getNickName()); auto md=mdb_deque::open(mp, true, DQ_NAME3, wr); a->ret=md->add_back(a->ub->getBlob()); wr->set(key->ptr(), {&a->ret, sizeof(a->ret)}); } int addUser(mem_pool* mp, mem_db* mdb, const UserBlob* ub) { ArgAddUser arg{mp, ub}; mdb->write(cbAddUser, &arg); return arg.ret; } void example3(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); UserBlob bk(mp, "bk", "Brian Kernighan", 19420130); addUser(mp, mdb, &bk); UserBlob dr(mp, "dr", "Dennis Ritchie", 19410909); addUser(mp, mdb, &dr); UserBlob bs(mp, "bs", "Bjarne Stroustrup", 19501230); addUser(mp, mdb, &bs); prnUsers(out, mdb); prnDb(out, mdb); UserBlob dup(mp, "bs", "Britney Spears", 19811202); // UserBlob dup(mp, "spears1981", "Britney Spears", 19811202); addUser(mp, mdb, &dup); prnUsers(out, mdb); prnDb(out, mdb); }

deque/example3.cpp
strsz PR_UNIQ_IND("\|UI\|"); strsz DQ_NAME3("users"); struct ArgAddUser { mem_pool* mp; const UserBlob* ub; int ret; }; void cbAddUser(mem_db::writer* wr, void* arg) { auto a=(ArgAddUser)arg; auto mp=a->mp; auto key=new_blob(mp, PR_UNIQ_IND, DQ_NAME3, strsz("\|"), a->ub->getNickName());* ptrsz val; if (wr->get(key->ptr(), &val)) throw newExc<Exception>(mp, mp, FLLN, tx_buf(mp)+"Duplicate index: "+a->ub->getNickName()); auto md=mdb_deque::open(mp, true, DQ_NAME3, wr); a->ret=md->add_back(a->ub->getBlob()); wr->set(key->ptr(), {&a->ret, sizeof(a->ret)}); } int addUser(mem_pool* mp, mem_db* mdb, const UserBlob* ub) { ArgAddUser arg{mp, ub}; mdb->write(cbAddUser, &arg); return arg.ret; } void example3(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); UserBlob bk(mp, "bk", "Brian Kernighan", 19420130); addUser(mp, mdb, &bk); UserBlob dr(mp, "dr", "Dennis Ritchie", 19410909); addUser(mp, mdb, &dr); UserBlob bs(mp, "bs", "Bjarne Stroustrup", 19501230); addUser(mp, mdb, &bs); prnUsers(out, mdb); prnDb(out, mdb); UserBlob dup(mp, "bs", "Britney Spears", 19811202); // UserBlob dup(mp, "spears1981", "Britney Spears", 19811202); addUser(mp, mdb, &dup); prnUsers(out, mdb); prnDb(out, mdb); }

Поначалу все идет хорошо:

prnUsers() prnDb()

beg()=0 end()=3 0 bk Brian Kernighan 19420130 1 dr Dennis Ritchie 19410909 2 bs Bjarne Stroustrup 19501230

|D|BE|users 0000000003000000 |D|E|users|00000000 02000F00E2S(01bkBrian Kernighan |UI|users|bk 00000000 |D|E|users|01000000 02000E00DD/(01drDennis Ritchie |UI|users|dr 01000000 |D|E|users|02000000 02001100AE90)01bsBjarne Stroustrup |UI|users|bs 02000000

`prnUsers()`	`prnDb()`
beg()=0 end()=3 0 bk Brian Kernighan 19420130 1 dr Dennis Ritchie 19410909 2 bs Bjarne Stroustrup 19501230	\|D\|BE\|users 0000000003000000 \|D\|E\|users\|00000000 02000F00E2S(01bkBrian Kernighan \|UI\|users\|bk 00000000 \|D\|E\|users\|01000000 02000E00DD/(01drDennis Ritchie \|UI\|users\|dr 01000000 \|D\|E\|users\|02000000 02001100AE90)01bsBjarne Stroustrup \|UI\|users\|bs 02000000

Но UserBlob dup(mp, "bs", "Britney Spears", 19811202) уже приводит к исключению:

ders::Exception [example3.cpp:102], message: Duplicate index: bs

Фанатки предлагают spears1981.

4.4. `mdb_list`: основы

А вот и Список! И ему тоже есть кое-что показать. Потрясти, так сказать, элементами.

И зачем этот Список, когда видели Дек? Ну, бывает приходится:

Эффективно вставлять элементы в середину длинной последовательности.
И удалять их потом без дырок.

А для начала мы создадим два Списка list1 и list2 с ключами несуществующих элементов:

list/example.cpp

strsz LST_ID1("list1"); strsz LST_ID2("list2"); void cb1(mem_db::writer* wr, void* arg) { auto mp=(mem_pool*)arg; auto lst1=mdb_list::open(mp, true, LST_ID1, wr); lst1->add_back(strsz("key1")); lst1->add_back(strsz("key2")); auto lst2=mdb_list::open(mp, true, LST_ID2, wr); lst2->add_back(strsz("key2")); lst2->add_back(strsz("key3")); } void cb2(mem_db::writer* wr, void*) { wr->set(strsz("key1"), strsz("val1")); wr->set(strsz("key2"), strsz("val2")); wr->set(strsz("key3"), strsz("val3")); } void cb3(mem_db::writer* wr, void* arg) { auto mp=(mem_pool*)arg; wr->set(strsz("key2"), strsz("updated")); auto lst1=mdb_list::open(mp, true, LST_ID1, wr); lst1->add_before(strsz("key2"), strsz("key1.5")); auto lst2=mdb_list::open(mp, true, LST_ID2, wr); lst2->del(strsz("key3")); } void example(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); Listener lnr(out); mdb->set_listener(&lnr); mdb->write(cb1, mp); prnLst(out, mdb, LST_ID1); prnLst(out, mdb, LST_ID2); prnDb(out, mdb); mdb->write(cb2, 0); prnLst(out, mdb, LST_ID1); prnLst(out, mdb, LST_ID2); prnDb(out, mdb); mdb->write(cb3, mp); prnLst(out, mdb, LST_ID1); prnLst(out, mdb, LST_ID2); prnDb(out, mdb); }

list/example.cpp
strsz LST_ID1("list1"); strsz LST_ID2("list2"); void cb1(mem_db::writer* wr, void* arg) { auto mp=(mem_pool)arg; auto lst1=mdb_list::open(mp, true, LST_ID1, wr); lst1->add_back(strsz("key1")); lst1->add_back(strsz("key2"));* auto lst2=mdb_list::open(mp, true, LST_ID2, wr); lst2->add_back(strsz("key2")); lst2->add_back(strsz("key3")); } void cb2(mem_db::writer* wr, void) { wr->set(strsz("key1"), strsz("val1")); wr->set(strsz("key2"), strsz("val2")); wr->set(strsz("key3"), strsz("val3"));* } void cb3(mem_db::writer* wr, void* arg) { auto mp=(mem_pool)arg; wr->set(strsz("key2"), strsz("updated"));* auto lst1=mdb_list::open(mp, true, LST_ID1, wr); lst1->add_before(strsz("key2"), strsz("key1.5")); auto lst2=mdb_list::open(mp, true, LST_ID2, wr); lst2->del(strsz("key3")); } void example(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); Listener lnr(out); mdb->set_listener(&lnr); mdb->write(cb1, mp); prnLst(out, mdb, LST_ID1); prnLst(out, mdb, LST_ID2); prnDb(out, mdb); mdb->write(cb2, 0); prnLst(out, mdb, LST_ID1); prnLst(out, mdb, LST_ID2); prnDb(out, mdb); mdb->write(cb3, mp); prnLst(out, mdb, LST_ID1); prnLst(out, mdb, LST_ID2); prnDb(out, mdb); }

После первого вызова mdb->write(cb1, mp) мы видим непривычную картину:

prnDb()

prnLst(list1) key1 key2 prnLst(list2) key2 key3

|L|HT|list1 04000400key1key2 |L|PN|list1|key1 00000400key2 |L|PN|list1|key2 04000000key1 |L|HT|list2 04000400key2key3 |L|PN|list2|key2 00000400key3 |L|PN|list2|key3 04000000key2

	`prnDb()`
prnLst(list1) key1 key2 prnLst(list2) key2 key3	\|L\|HT\|list1 04000400key1key2 \|L\|PN\|list1\|key1 00000400key2 \|L\|PN\|list1\|key2 04000000key1 \|L\|HT\|list2 04000400key2key3 \|L\|PN\|list2\|key2 00000400key3 \|L\|PN\|list2\|key3 04000000key2

А именно:

Первый объект mdb_list с идентификатором list1 сохранен по ключу |L|HT|list1. Его ключ -- это list1 с префиксом |List|HeadTail|. Его данные -- это два ключа сразу: key1 и key2.
Как вы уже догадались, формат данных -- это два short (длина ключей) плюс сами ключи друг за другом. Обозначим для краткости (4, 4, "key1", "key2").
Элемента key1 пока не существует. Так что prnLst() выводит ключ без значения, а prnDb() вообще ничего не выводит.
Ссылки первого элемента сохранены по ключу |L|PN|list1|key1. Его ключ -- это значение key1 с префиксом |List|PrevNext|list1|. Его данные -- (0, 4, "", "key2").
Ссылки последнего элемента сохранены по ключу |L|PN|list1|key2. Его данные -- (4, 0, "key1", "").
Второй объект list2 устроен аналогично. Но содержит key2 и key3.

Как можно видеть, отсутствие ключей в mem_db никак не влияет на их наличие в одном или нескольких Списках. Что, собственно, уже и говорилось.

А сейчас мы вызовем mdb->write(cb2, 0) и добавим все три ключа в базу:

prnDb()

prnLst(list1) key1 val1 key2 val2 prnLst(list2) key2 val2 key3 val3

|L|HT|list1 04000400key1key2 key1 val1 |L|PN|list1|key1 00000400key2 key2 val2 |L|PN|list1|key2 04000000key1 |L|HT|list2 04000400key2key3 key2 val2 |L|PN|list2|key2 00000400key3 key3 val3 |L|PN|list2|key3 04000000key2

	`prnDb()`
prnLst(list1) key1 val1 key2 val2 prnLst(list2) key2 val2 key3 val3	\|L\|HT\|list1 04000400key1key2 key1 val1 \|L\|PN\|list1\|key1 00000400key2 key2 val2 \|L\|PN\|list1\|key2 04000000key1 \|L\|HT\|list2 04000400key2key3 key2 val2 \|L\|PN\|list2\|key2 00000400key3 key3 val3 \|L\|PN\|list2\|key3 04000000key2

О! Теперь prnLst() выводит значения. В полном соответствии с prnDb().

И в завершение результаты mdb->write(cb3, 0) -- череды бессмысленных изменений:

prnDb()

prnLst(list1) key1 val1 key1.5 key2 updated prnLst(list2) key2 updated

|L|HT|list1 04000400key1key2 key1 val1 |L|PN|list1|key1 00000600key1.5 |L|PN|list1|key1.5 04000400key1key2 key2 updated |L|PN|list1|key2 06000000key1.5 |L|HT|list2 04000400key2key2 key2 updated |L|PN|list2|key2 00000000

	`prnDb()`
prnLst(list1) key1 val1 key1.5 key2 updated prnLst(list2) key2 updated	\|L\|HT\|list1 04000400key1key2 key1 val1 \|L\|PN\|list1\|key1 00000600key1.5 \|L\|PN\|list1\|key1.5 04000400key1key2 key2 updated \|L\|PN\|list1\|key2 06000000key1.5 \|L\|HT\|list2 04000400key2key2 key2 updated \|L\|PN\|list2\|key2 00000000

5. Транзакции

Все было вкусно, особенно хлеб. Но где же транзакции? Любимые наши commit() и rollback()??

Ну, любишь коммитить -- люби и депенденси! Но ни Список, ни Дек depend_val()/depend_del() не используют...

Обалдеть!! Т.е. два mdb_deque в разных транзакциях могут тупо переписать друг друга?!

А как же! Да, ножом и порезаться можно. Удивил? Вместе с Силой приходит Ответственность.

Это ваша задача следить за зависимостями! Т.к. примитивы depend_val()/depend_del() были созданы для предыдущего уровня абстракции.

Например?

Ну, например, для эффективности по одному ключу могут жить сразу два разных значения: next и prev. Но вы не можете указать depend_val()-у, что зависите только от next.
Или обычное дело: конкурентные транзакции добавляют элементы в общий Дек. Т.е. конечная граница изменяется в каждой транзакции, и optimistic locking вам ничего не даст...

Но для всех бед один ответ! Вы уже его видели -- изменение данных в колбэке:

Сначала вы медленно и печально формируете список всех изменений "транзакции" и их зависимостей.
А затем, с помощью mem_db::write(), вызываете свой колбэк, в котором быстро проверяете все зависимости и вносите изменения.

Точка! "Транзакция" завершена. Или отброшена из-за зависимостей.

Ведь, по сути, mem_db::transaction делает то же самое: не спеша собирает в сторонке все зависимости/изменения, а потом быстро их применяет в commit(). Плюс у write() есть возможность все сделать быстрее!

Что еще?

А, ну да. Старый добрый commit() и rollback() не отняли! Так что можно задействовать Деки и Списки в транзакциях, где изменения не конфликтуют. Тем паче, добавился check_cb -- колбэк для проверки зависимостей:

derslib/inc/ders/mdb/mdb.hpp

struct mem_db : deletable { enum error_code { chk_failed, rec_deleted, rec_inserted, rec_updated }; struct error : deletable { virtual error_code code() const=0; virtual ptrsz key() const=0; virtual ptrsz val() const=0; error& operator=(const error&)=delete; }; struct reader : deletable { virtual bool get(ptrsz key, ptrsz* pval) const=0; virtual void all(std::vector<ptrsz>* keys, std::vector<ptrsz>* vals) const=0; reader& operator=(const reader&)=delete; }; struct writer : reader { virtual void set(ptrsz key, ptrsz val)=0; virtual void del(ptrsz key)=0; }; using check_cb=bool(const reader* rd, void* arg); using write_cb=void(writer* wr, void* arg); struct transaction : writer { virtual void depend_val(ptrsz key, ptrsz val)=0; virtual void depend_del(ptrsz key)=0; virtual un_ptr<error> commit(write_cb wrt=0, void* wrt_arg=0, check_cb chk=0, void* chk_arg=0)=0; virtual void rollback()=0; }; virtual un_ptr<reader> start_rd(mem_pool* mp)=0; virtual un_ptr<transaction> start_tr(mem_pool* mp)=0; virtual void write(write_cb wrt, void* arg=0)=0; };

derslib/inc/ders/mdb/mdb.hpp
struct mem_db : deletable { enum error_code { chk_failed, rec_deleted, rec_inserted, rec_updated }; struct error : deletable { virtual error_code code() const=0; virtual ptrsz key() const=0; virtual ptrsz val() const=0; error& operator=(const error&)=delete; }; struct reader : deletable { virtual bool get(ptrsz key, ptrsz* pval) const=0; virtual void all(std::vector<ptrsz>* keys, std::vector<ptrsz>* vals) const=0; reader& operator=(const reader&)=delete; }; struct writer : reader { virtual void set(ptrsz key, ptrsz val)=0; virtual void del(ptrsz key)=0; }; *using check_cb=bool(const reader rd, void* arg);** using write_cb=void(writer* wr, void* arg); struct transaction : writer { virtual void depend_val(ptrsz key, ptrsz val)=0; virtual void depend_del(ptrsz key)=0; virtual un_ptr<error> commit(write_cb wrt=0, void* wrt_arg=0, *check_cb chk=0, void chk_arg=0*)=0; virtual void rollback()=0; }; virtual un_ptr<reader> start_rd(mem_pool mp)=0; virtual un_ptr<transaction> start_tr(mem_pool* mp)=0; virtual void write(write_cb wrt, void* arg=0)=0; };

Таким образом, вместе с привычным колбэком для записи, вы теперь можете передать в commit() и bool check_cb(const reader* rd, void* arg) -- он будет сразу же вызван для проверки зависимостей. И если вернете false, то транзакция будет отброшена с ошибкой mem_db::chk_failed. Удобно? Отменно!

Да, здесь есть много пространства для творчества, но убедитесь сначала, что оно того стоит! По сравнению с вызовом write().

6. Отслеживание изменений

Мы не гонимся за удачей. Мы ее в засаде ждём!

Как все вы прекрасно знаете, в больших серьезных Базах Данных все всегда было классно с транзакциями! Можно даже сказать, с рождения.

Но вот с отслеживанием изменений...

-- Я хочу сразу же знать, как появится новая запись! Я хочу сразу же знать, как изменится!
-- Лупи, Вася, в цикле SELECT-ы... Или слезно проси себе TRIGGER... Или как там еще вдруг "получится".

Конечно, можно как-то попытаться имитировать транзакции и поверх голой хеш-таблицы. Но надежно работать они не будут.

Или снаружи как-то обнаружить изменения... Только криво и медленно!

Но хватит ужасов, когда вы можете комфортно возлежать в засаде:

derslib/inc/ders/mdb/mdb.hpp

struct mem_db : deletable { struct changes : reader { virtual bool is_mod(ptrsz key) const=0; virtual std::vector<ptrsz> mod_keys() const=0; }; struct listener { virtual void on_commit(const changes* chs)=0; virtual ~listener() {} }; virtual listener* set_listener(listener* lnr)=0; };

derslib/inc/ders/mdb/mdb.hpp
struct mem_db : deletable { struct changes : reader { virtual bool is_mod(ptrsz key) const=0; virtual std::vector<ptrsz> mod_keys() const=0; }; struct listener { virtual void on_commit(const changes* chs)=0; virtual ~listener() {} }; virtual listener* set_listener(listener* lnr)=0; };

Да, ситуацию спасает вызов set_listener(). Вы его даже видели выше.

В общем и целом, все изменения приходят в метод on_commit() в виде объекта changes. Ну а далее дело техники: используйте is_mod()/mod_keys() для проверки одного ключа или получения всех изменений сразу.

А сейчас вернемся к предыдущему примеру:

deque/example2.cpp

struct Listener : mem_db::listener { fd_file* out; Listener(fd_file* out_) : out(out_) {} void on_commit(const mem_db::changes* chs) override { out->ex_write("__ on_commit() __\n"); auto mp=out->pool(); ptrsz val; strsz del("<deleted>"); auto keys=chs->mod_keys(); for (int i=0, e=keys.size(); i<e; i++) { out->ex_write(tx_buf(mp)+to_text(mp, keys[i])+"\t"+ (chs->get(keys[i], &val) ? to_text(mp, val)->str() : del)+"\n"); } if (chs->is_mod(mdb_deque::obj_key(mp, DQ_NAME2)->ptr())) { out->ex_write(tx_buf(mp)+"deque("+DQ_NAME2+"): "); auto mdc=getCustomers(mp, chs); if (mdc) out->ex_write(tx_buf(mp)+"beg()="+mdc->beg()+" end()="+mdc->end()+"\n"); else out->ex_write(tx_buf(mp)+del+"\n"); } } }; void example2(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); Listener lnr(out); mdb->set_listener(&lnr); int bk=addCustomer(mp, mdb, strsz("Brian Kernighan")); int dr=addCustomer(mp, mdb, strsz("Dennis Ritchie")); // ... addOrder(mp, mdb, bk, strsz("Somewhere Far Beyond")); addOrder(mp, mdb, bk, strsz("Imaginations from the Other Side")); }

deque/example2.cpp
struct Listener : mem_db::listener { fd_file* out; Listener(fd_file* out_) : out(out_) {} void on_commit(const mem_db::changes* chs) override { out->ex_write("__ on_commit() __\n"); auto mp=out->pool(); ptrsz val; strsz del("<deleted>"); auto keys=chs->mod_keys(); for (int i=0, e=keys.size(); i<e; i++) { out->ex_write(tx_buf(mp)+to_text(mp, keys[i])+"\t"+ (chs->get(keys[i], &val) ? to_text(mp, val)->str() : del)+"\n"); } if (chs->is_mod(mdb_deque::obj_key(mp, DQ_NAME2)->ptr())) { out->ex_write(tx_buf(mp)+"deque("+DQ_NAME2+"): "); auto mdc=getCustomers(mp, chs); if (mdc) out->ex_write(tx_buf(mp)+"beg()="+mdc->beg()+" end()="+mdc->end()+"\n"); else out->ex_write(tx_buf(mp)+del+"\n"); } } }; void example2(fd_file* out) { auto mp=out->pool(); auto umdb=new_mem_db(mp); auto mdb=get(umdb); Listener lnr(out); mdb->set_listener(&lnr); int bk=addCustomer(mp, mdb, strsz("Brian Kernighan")); int dr=addCustomer(mp, mdb, strsz("Dennis Ritchie")); // ... addOrder(mp, mdb, bk, strsz("Somewhere Far Beyond")); addOrder(mp, mdb, bk, strsz("Imaginations from the Other Side")); }

Мы наследуемся от mem_db::listener и определяем свой on_commit(), в котором:

Получаем все изменившиеся ключи с помощью mod_keys() и выводим их на экран: или значение, или "<deleted>".
Проверяем с помощью is_mod() изменился ли Дек cust/ord, используя вызов mdb_deque::obj_key(mp, DQ_NAME2) для получения его ключа.
Вызываем привычную getCustomers(), если он изменился, и выводим значения beg() и end().

И вот так это страшно выглядит:

__ on_commit() __ |D|E|cust/ord|00000000 Brian Kernighan |D|BE|cust/ord 0000000001000000 deque(cust/ord): beg()=0 end()=1 __ on_commit() __ |D|E|cust/ord|01000000 Dennis Ritchie |D|BE|cust/ord 0000000002000000 deque(cust/ord): beg()=0 end()=2 ... __ on_commit() __ |D|E||D|E|cust/ord|00000000|00000000 Somewhere Far Beyond |D|BE||D|E|cust/ord|00000000 0000000001000000 __ on_commit() __ |D|E||D|E|cust/ord|00000000|01000000 Imaginations from the Other Side |D|BE||D|E|cust/ord|00000000 0000000002000000 ... __ on_commit() __ |D|E|cust/ord|00000000 updated customer __ on_commit() __ |D|E||D|E|cust/ord|00000000|01000000 updated order __ on_commit() __ |D|E||D|E|cust/ord|01000000|00000000 <deleted> |D|BE||D|E|cust/ord|01000000 0100000002000000 __ on_commit() __ |D|E|cust/ord|02000000 <deleted> |D|E||D|E|cust/ord|02000000|00000000 <deleted> |D|E||D|E|cust/ord|02000000|01000000 <deleted> |D|BE||D|E|cust/ord|02000000 <deleted> __ prnDeques() __ beg()=0 end()=3 0 updated customer 0 beg()=0 end()=2 0 0 Somewhere Far Beyond 0 1 updated order 1 Dennis Ritchie 1 beg()=1 end()=2 1 1 Brave New World 2 __ prnDb() __ |D|BE|cust/ord 0000000003000000 |D|E|cust/ord|00000000 updated customer |D|BE||D|E|cust/ord|00000000 0000000002000000 |D|E||D|E|cust/ord|00000000|00000000 Somewhere Far Beyond |D|E||D|E|cust/ord|00000000|01000000 updated order |D|E|cust/ord|01000000 Dennis Ritchie |D|BE||D|E|cust/ord|01000000 0100000002000000 |D|E||D|E|cust/ord|01000000|01000000 Brave New World

Что еще? Ну конечно дедлок!

Вы его несомненно получите прямо в on_commit(), если вдруг попытаетесь начать/завершить транзакцию или что-то подобное. Не забывайте, что колбэки эффективны, но с особенностями!

7. Заключение

Уж вечер близится, а вывода все нет...

Меня часто спрашивают, а что же такое маркиз? Если честно, не знаю! Что-то выше товарища графа. Вероятно, богаче владения.

Но это хороший вопрос! Это значит, что все остальное усвоено. И Дек вам станет ненаглядным инструментом. Может статься, и на других языках.

И все же только mem_db вам предоставит уникальные возможности! Не упускайте шанс себя порадовать. И заработать лишнюю копейку из засады.

8. P.S. Обыкновенное чудо

Чудо заказывали? Хорошее честное чудо, без перьев.

А пока процитируем Классика: "off_pool -- это хитрый кусок памяти, четыре гигабайта максимум. В 32 бита уже больше не лезет".

И чудо в том, что я запихнул тридцать два гигабайта в те же самые 32 бита. Пользуйтесь на здоровье.

Э-э... Ы-ы... НЕ МОЖЕТ БЫТЬ!!!

Ни у кого не может, кроме у меня. Смотрите:

UINT32_MAX*sizeof(char) = 4294967295 -- все хорошо, обычные 4 гигабайта.
UINT32_MAX*sizeof(void*) = 34359738360 -- а это уже 32!

Так, ничего не понял! Причем тут sizeof(void*)?

Все гениальное просто: ders::off_pool выравнивает блоки памяти по границе sizeof(void*), т.е. мы можем использовать не raw_offset (в байтах), а raw_offset/sizeof(void*).

И это значит... Что максимальный размер ders::mem_db внезапно вырос В ВОСЕМЬ РАЗ!

Ерунда, говорите? Могли б и на два указателя??

Спасибо на добром слове! Пусть будет на два указателя: 64 гигабайта из 32 бит.

9. P.P.S. perf7: производительность int_map

Что делать, когда чуть ли не каждый день вас просят об одном и том же? А если несколько раз за день??

Настал тот день, и оправданий не заметно! Так что и в этой статье вдруг появятся тесты производительности.

Но сначала мы выберем жертву. Очень злую и наглую!

Пусть это будет std::unordered_map для простых целочисленных типов. Тем более, что unordered_map<uint32_t, uint32_t> и unordered_map<void*, size_t> я и правда использую в коде. А производительность метода off_pool::merge_freed() и вовсе связана с хеш-таблицей!

Как вы давно уже знаете, thread-local allocators (на основе моих mem_pool и off_pool) существенно ускоряют работу STL контейнеров. Поэтому избивать младенцев мы будем немного иначе.

А пока план таков:

Жертвуя обеденным перерывом, на коленке набрасываем простейший int_map.
Замеряем производительность...
Посыпаем голову пеплом и нижайше извиняемся перед авторами unordered_map!

Бить врага его собственным кирпичем? Так давайте напишем int_map на основе двух векторов. И тупее уже не придумаешь:

derslib\inc\ders\int_map.hpp

template<class K, class V> struct int_map { // ... private: struct node { int next; K key; V val; }; std::vector<int> heads; std::vector<node> nodes; // ... };

derslib\inc\ders\int_map.hpp
template<class K, class V> struct int_map { // ... private: struct node { int next; K key; V val; }; std::vector<int> heads; std::vector<node> nodes; // ... };

Абсолютно стандартные тесты:

perf7\main.cpp

void start_std(latch* l1, latch* l2) { unordered_map<int, int> um; l1->arrive_and_wait(); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { auto ret=um.emplace(j, j); perm_assert(ret.second); } for (int j=0; j<M; j++) { auto ret=um.find(j); perm_assert(ret!=um.end()); ret=um.find(M+j); perm_assert(ret==um.end()); } for (int j=0; j<M; j++) { auto ret=um.erase(j); perm_assert(ret==1); } } l2->arrive_and_wait(); } void start_ders(latch* l1, latch* l2) { int_map<int, int> im; l1->arrive_and_wait(); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { auto ret=im.findsert(j, j); perm_assert(ret==-1); } for (int j=0; j<M; j++) { auto ret=im.find(j); perm_assert(ret!=-1); ret=im.find(M+j); perm_assert(ret==-1); } for (int j=0; j<M; j++) { auto ret=im.erase(j); perm_assert(ret); } } l2->arrive_and_wait(); }

perf7\main.cpp
void start_std(latch* l1, latch* l2) { unordered_map<int, int> um; l1->arrive_and_wait(); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { auto ret=um.emplace(j, j); perm_assert(ret.second); } for (int j=0; j<M; j++) { auto ret=um.find(j); perm_assert(ret!=um.end()); ret=um.find(M+j); perm_assert(ret==um.end()); } for (int j=0; j<M; j++) { auto ret=um.erase(j); perm_assert(ret==1); } } l2->arrive_and_wait(); } void start_ders(latch* l1, latch* l2) { int_map<int, int> im; l1->arrive_and_wait(); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { auto ret=im.findsert(j, j); perm_assert(ret==-1); } for (int j=0; j<M; j++) { auto ret=im.find(j); perm_assert(ret!=-1); ret=im.find(M+j); perm_assert(ret==-1); } for (int j=0; j<M; j++) { auto ret=im.erase(j); perm_assert(ret); } } l2->arrive_and_wait(); }

Вижу, вы догадались, что дальше...

Обеда мне не хватило! На все про все ушло почти два часа, но результат того стоил:

Ubuntu 16, g++ 5.4.0 Windows 10, g++ 12.2.0

num_threads 1 2 3 4 8 16 32 64 1 2 3 4 8 16 32 64

std/ders 2.0 2.0 2.1 2.1 2.2 2.2 2.3 3.1 3.3 3.4 3.6 3.7 4.7 4.3 4.5 4.9

Опа! На коленке набросанная хеш-таблица сразу же демонстрирует 2-5 кратный рост производительности!! И это в лоб, стандартными кирпичами.

Ах, да! Обещали ж кому-то и пеплом. Ну так вот, Уважаемые Профессионалы! Вся прогрессивная общественность твердым шагом приходит к выводу, что:

Ассоциативные контейнеры STL созданы недоумками!
Те же самые граждане написали и все остальное.

Ха! Вы бы там без обеда еще и не так сказали.

Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.

	Ubuntu 16, g++ 5.4.0								Windows 10, g++ 12.2.0
num_threads	1	2	3	4	8	16	32	64	1	2	3	4	8	16	32	64
std/ders	2.0	2.0	2.1	2.1	2.2	2.2	2.3	3.1	3.3	3.4	3.6	3.7	4.7	4.3	4.5	4.9

Сергей Деревяго

Структуры данных второго порядка

1. Введение