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

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

1. Введение

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

Вы научитесь создавать всевозможные структуры данных в любом доступном 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 за это не отвечает! Нашли дурака.

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

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

|Head|customers  cust1
cust1            data1
|Next|cust1      cust2
cust2            data2
|Next|cust2      cust3
cust3            data3

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

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

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

|Head|customers  cust1
cust1            data1
|Next|cust1      cust2
|Prev|cust2      cust1
cust2            data2
|Next|cust2      cust3
|Prev|cust3      cust2
cust3            data3
|Tail|customers  cust3

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

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

А для дерева вам понадобятся "|Left|", "|Right|" и "|Parent|". Но таблички с примером уже не будет, т.к. мы вплотную подошли к Основному вопросу Философии: А НАФИГА??

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

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

2.2. Пример Customers/Orders

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

Customers
PKIdint AUTO_INCREMENT
Fields1types1
Orders
PKIdint AUTO_INCREMENT
FKCustomerIdint
Fields2types2

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

Customers
IdFields1
0data0
1data1
2data2
Orders
IdCustomerIdFields2
00data3
10data4
20data5
31data6
41data7
51data8
62data9
72data10
82data11

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

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

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

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

Так почему бы нам вместо дерева не использовать массив 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.

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

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

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

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

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

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, mem_db::reader* rd);
    static bool remove(mem_pool* mp, ptrsz id, mem_db::writer* wr);

    static un_ptr<mdb_deque_reader> open_rd(mem_pool* mp, ptrsz id, 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
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, mem_db::reader* rd);
    static bool remove(mem_pool* mp, ptrsz id, mem_db::writer* wr);

    static un_ptr<mdb_list_reader> open_rd(mem_pool* mp, ptrsz id, 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
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);
}

После первого вызова 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

А именно:

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

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

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!

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

Как вы уже поняли, "единственно верного" способа не существует. Все зависит от цели: 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, mem_db::reader* rd);
bool getCustomer(mem_pool* mp, 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, mem_db::reader* rd, int custN);
bool getOrder(mem_pool* mp, 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);

    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
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

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

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

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

Да, можно и код показать. Лучше конечно смотреть самому и сразу же запускать примеры. Но мелкий кусочек не повредит:

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);
}

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

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

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

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);
}

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

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);

    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

А именно:

Как можно видеть, отсутствие ключей в 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

О! Теперь 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

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

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

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

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

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

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

Например?

Но для всех бед один ответ! И вы его видели -- изменение данных в колбэке:
  1. Сначала вы медленно и печально формируете список всех изменений "транзакции" и их зависимостей.
  2. А затем, с помощью 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 { deleted, modified, other };

    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(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<mem_db> copy(mem_pool* mp) const=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;

    mem_db& operator=(const mem_db&)=delete;
};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И это значит...

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

Copyright © С. Деревяго, 2024-2025

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