C & C++ - учебная задача : трансляция страниц

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

C & C++ - учебная задача : трансляция страниц

Непрочитанное сообщение Olej » 25 июл 2021, 13:33

Есть такая задача, она подобна 3-х уровневому (в новых 64-бит процессорах) аппаратному механизму трансляции виртуальных страниц RAM в физические...
Задача довольно любопытная.
Её можно вполне (и нужно) включить в копилку Подборки задач по C и C++

Такую задачу предлагает одна из фирм (из числа разработчиков MySQL) соискателям на работу в их команде - вот их формулировка ideone.com.
Но я здесь повторю их формулировку:
// Написать (компилировать не нужно) вставку и поиск для дерева остатков
// (radix tree)
//
// Ключом является целое беззнаковое 32-битное число. Высота дерева должна
// определяться константой, т.е. в зависимости от значения этой константы мы
// получаем корректно работающее дерево различной высоты.
//
// Дерево остатков - это дерево высотой N (степень двойки), хранящее в листьях
// значения V по целочисленным беззнаковым ключам K. Пусть bits(X) - это число
// всех бит в X или sizeof(X) * 8 в терминах C. Каждый узел дерева хранит
// 2 ^ (bits(K) / N) (`^` - возведение в степень) указателей на узел следующего
// уровня или значение (если узел является листом). На i-м уровне указатель на
// узел (i + 1)'го уровня определяется в массиве i'го узла как (при адресации, в
// которой менее значимые биты ключа определяют индексы в верхних уровнях дерева).

#define N 4

typedef struct {
// ......
} RtNode;

RtNode rt_root;

void rt_insert(unsigned int key, void *val) {
// ...
}

/* Returns NULL if there is no element with such key. */
void *rt_lookup(unsigned int key) {
// ...
}
Формулировка (в комментарии) сама по себе по форме идиотская - неоднозначная, невнятная, да и недописанная до конца (последняя фраза в скобках) ... но я сейчас её уточню ниже и растолкую.
P.S. Написать образец такого кода они предлагают за 1/2 часа - без компиляции и проверки ... Может быть это и возможно если ежедневно писать/править подобный код, но без конкретной подготовки, "набитой руки", я предполагаю что это глупость. Я, столкнувшись с этим в разговоре, просто отказался участвовать в этой глупости, но задача сама по себе интересная, и я сам для себя реализовал её, с компиляцией и тестированием за 3-4 часа.

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ : трансляция страниц

Непрочитанное сообщение Olej » 25 июл 2021, 13:39

Olej писал(а):
25 июл 2021, 13:33
но я сейчас её уточню ниже и растолкую.
Итак:
- есть 32-бит ключ (выбора начала страницы, например, void*)...
- он разбивается на N частей, при N=4 это части по 8 бит
- каждая из последовательных частей последовательно (одна за другой) используется для трансляции через страницу индексов-адресов на следующий уровень...
- последний уровень (при N=4 это 4-й) содержит уже адрес интересующий нас области (void*).

N - может быть разнообразным: 2, 4, 8, 16 ...
P.S. как показало более позднее разбирательство, N, вообще то говоря, может быть любым: 3, 5, 7, 11 ...

Вот, собственно, и всё ... только в исходной формулировке безобразно описано. :twisted:

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ : трансляция страниц

Непрочитанное сообщение Olej » 25 июл 2021, 14:01

P.S. Параметр N (или производное - число бимт на уровень) может здесь иметь самые разнообразные значения, определяющиеся при компиляции через Makefile ... (как это описано здесь: C/C++ передача параметра через Makefile (позже мы это рассмотрим).

То что понадобилось подготовить для сборки:

Код: Выделить всё

olej@nvme:~/2021/OWN_TEST.codes/tree$ cat Makefile
TASK = tree tree++
NM = $(shell ./size)

CC += -Wall -pedantic -std=c99
CXX += -Wall -pedantic -std=c++14

all: $(TASK)

%:      %.c
	$(CC) $< -D NUM=$(NM) -o $@

%:      %.cc
	$(CXX) $< -D NUM=$(NM) -o $@

clean:
	rm -f $(TASK)

Код: Выделить всё

olej@nvme:~/2021/OWN_TEST.codes/tree$ cat size
#!/usr/bin/bash

isnumber()        # функция тестирования на числовое значение
{
    /bin/test $1 -eq $1 2>/dev/null
}

if [ -z ${NUM} ]; # значение не определялась
    then 
	NUM=4; 
	echo $NUM;
        exit
fi

if isnumber $NUM;
    then          # число но не нулевое
	if !(($NUM)); 
	    then NUM=4; 
	fi;
    else          # не число
	NUM=4; 
fi

echo $NUM
Т.е. значение N передаётся в C/C++ код как переменная окружения NUM + она же как параметр -D NUM в переменную препроцессора:

Код: Выделить всё

...
#ifdef NUM                 // число уровней (2, 4, 8, 16)
#define N NUM
#else
#define N 4
#endif
...
...

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ : трансляция страниц

Непрочитанное сообщение Olej » 25 июл 2021, 14:25

Olej писал(а):
25 июл 2021, 13:33
// уровня или значение (если узел является листом). На i-м уровне указатель на
// узел (i + 1)'го уровня определяется в массиве i'го узла как (при адресации, в
// которой менее значимые биты ключа определяют индексы в верхних уровнях дерева).
Только сейчас заметил, что означает эта невнятная "горбатая" фраза в скобках:
- что старшим уровням таблиц страниц соответствует младший индекс к 32-битном ключе.
И так сделать, вообще то говоря, проще.

И вторая фича, оттуда же, из формулировки:
Olej писал(а):
25 июл 2021, 13:33
RtNode rt_root;
Поскольку таблицы трансляции (массивы) void* node[*][L] содержат указатели (а не индексы), то они все (указатели) должны в начале инициализироваться в NULL ... а это, в таком написании как есть, будет только если а). массив (структура его содержащая) объявляется на верхнем глобальном уровне, или б). явно описан как static. И такая "нулевая инициализация по дефаулту" очень скользкое место ... и её лучше бы делать явно, runtime ... даже если это избыточное действие.

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ : трансляция страниц

Непрочитанное сообщение Olej » 25 июл 2021, 18:39

Olej писал(а):
25 июл 2021, 13:54
Чтоб долго не распыляться ... - вот 1-я работающая (слегка косметически подчищенная) реализация на C:
Как показало спокойное изучение, всё что написано в коде выше - это херня.... бес попутал. :evil:
Почему и было удалено до более приемлемого решения. :lol:

Здесь, конечно, никак недостаточно 2-мерного массива [N][L], здесь должно быть дерево глубиной N, размерности ... при N=4 каждый уровень адресуется таблицей 256 позиций нижнего уровня, и так 4 уровня, т.е. максимальная ёмкость дерева 256**4, т.е. до 4294967296 объектов, указываемых void* листьями.

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ : трансляция страниц

Непрочитанное сообщение Olej » 15 авг 2021, 11:23

Olej писал(а):
25 июл 2021, 18:39
Почему и было удалено до более приемлемого решения.
Пока эту задачу отложил до лучших времён ... но в уме её держим.

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ - учебная задача : трансляция страниц

Непрочитанное сообщение Olej » 31 авг 2021, 21:30

Olej писал(а):
25 июл 2021, 18:39
Как показало спокойное изучение, всё что написано в коде выше - это херня.... бес попутал.
Почему и было удалено до более приемлемого решения.
Olej писал(а):
15 авг 2021, 11:23
Пока эту задачу отложил до лучших времён ... но в уме её держим.
1-й из работающих вариантов, на C API (с поясняющим отладочным выводом):

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ cat tree.c 
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#ifdef NUM                       // число уровней (2, 4, 8, 16)
#define N NUM
#else
#define N 4
#endif

#define R 32/N                    // бит на уровень
#define L 1<<R                    // число узлов в уровне

typedef struct {
    void* node[L];
} RtNode;

static RtNode rt_root;
int M1;                          // битовая маска уровня 

void rt_insert(uint32_t key, void *val) {
    void** root = (void*)&rt_root;
    for (int i = 0; i < N; i++)
    {
		int pos = key & M1;      // индекс текущего уровня
		void **adr = root + pos; // указатель следующего уровня
		if (i != N - 1)          // не терминальный уровень
		{
			if (NULL == *adr)
			{
				*adr = malloc(sizeof(void*) * L);
				memset(*adr, 0, sizeof(void*) * L);
			}
		}
		else
			*adr = val;
		printf( "[%d] %03d : [%p + 0x%03lx = %p] => %p\n",
		        i, pos, (void*)root, pos * sizeof(void*), (void*)adr, *adr );
		root = *adr;
		key >>= R;
    }
}

void *rt_lookup(uint32_t key) {  // Returns NULL if there is no element with such key. 
	void** root = (void*)&rt_root, **adr;
	for (int i = 0; i < N; i++)
    {
		int pos = key & M1;      // индекс текущего уровня
		adr = root + pos;        // указатель следующего уровня

		if (NULL == *adr)
			return NULL;
		if (i == N - 1)
			break;
		root = *adr;
		key >>= R;
    }
	return *adr;
}

uint32_t rt_size(void** root, int level)
{
	uint32_t num = 0;            // число терминальных страниц
	for (int i = 0; i < L; i++)
	{
		void **nadr = root + i;
		if (NULL != *nadr)
		{
			if (level < N - 1)
				num += rt_size(*nadr, level + 1);
			else
				num++;
		}
	}
	return num;
}

uint32_t rt_nodes(void** root, int level)
{
	uint32_t num = 0;            // число не NULL узлов в дереве
	for (int i = 0; i < L; i++)
	{
		void **adr = root + i;
		if (NULL != *adr)
		{
			if (level < N - 1)
				num += (rt_nodes(*adr, level + 1) + 1);
			else
				num++;
		}
	}
	return num;
}

int main()
{
	M1 = 1; 
	for (int i = 0; i < R - 1; i++ )
		M1 = ( M1 << 1 ) | 1;
	printf( "%d => %d => %d : маска 0x%08x\n", N, R, L, M1 );

	struct {
		uint32_t key;
		void*    val;
	} data[] = { {0x010203FF, (void*)1},
	             {0x010304FF, (void*)2},
	             {0x020203FF, (void*)2},
	             {0x010303FF, (void*)3},
	             {0x0103050F, (void*)4},
	             {0x020304FF, (void*)5},
	             {0x0000FF00, (void*)6},
	           };
	int dnode = sizeof(data) / sizeof(data[0]); 
	uint32_t bad[] = { 0x01020304, 0x010203FE};
	int bnode = sizeof(bad) / sizeof(bad[0]); 

	printf("root: => %p\n", (void*)&rt_root);
	printf("---------------------------\n");
	for (int i = 0; i < dnode; i++)
	{
		printf("добавить: ключ 0x%08x - значение %p:\n", data[i].key, data[i].val);
		rt_insert(data[i].key, data[i].val);
		printf("размер=%d | ", rt_size((void**)&rt_root, 0));
		printf("узлов=%d\n", rt_nodes((void**)&rt_root, 0));
		printf("---------------------------\n");
	}

	for (int i = 0; i < dnode; i++)
		printf("ищем: 0x%08X => %p\n", data[i].key, rt_lookup(data[i].key));
	for (int i = 0; i < bnode; i++)
		printf("ищем: 0x%08X => %p\n", bad[i], rt_lookup(bad[i]));

	return 0;
}

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ make tree
cc -Wall -Wno-pointer-arith -pedantic -std=c99 tree.c -D NUM=4 -o tree
Дополнительную противность создаёт то, что по условиям используются массивы нетипизированных указателей void*

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ ./tree 
4 => 8 => 256 : маска 0x000000ff
root: => 0x562e9359a040
---------------------------
добавить: ключ 0x010203ff - значение 0x1:
[0] 255 : [0x562e9359a040 + 0x7f8 = 0x562e9359a838] => 0x562e94ce66b0
[1] 003 : [0x562e94ce66b0 + 0x018 = 0x562e94ce66c8] => 0x562e94ce6ec0
[2] 002 : [0x562e94ce6ec0 + 0x010 = 0x562e94ce6ed0] => 0x562e94ce76d0
[3] 001 : [0x562e94ce76d0 + 0x008 = 0x562e94ce76d8] => 0x1
размер=1 | узлов=4
---------------------------
добавить: ключ 0x010304ff - значение 0x2:
[0] 255 : [0x562e9359a040 + 0x7f8 = 0x562e9359a838] => 0x562e94ce66b0
[1] 004 : [0x562e94ce66b0 + 0x020 = 0x562e94ce66d0] => 0x562e94ce7ee0
[2] 003 : [0x562e94ce7ee0 + 0x018 = 0x562e94ce7ef8] => 0x562e94ce86f0
[3] 001 : [0x562e94ce86f0 + 0x008 = 0x562e94ce86f8] => 0x2
размер=2 | узлов=7
---------------------------
добавить: ключ 0x020203ff - значение 0x2:
[0] 255 : [0x562e9359a040 + 0x7f8 = 0x562e9359a838] => 0x562e94ce66b0
[1] 003 : [0x562e94ce66b0 + 0x018 = 0x562e94ce66c8] => 0x562e94ce6ec0
[2] 002 : [0x562e94ce6ec0 + 0x010 = 0x562e94ce6ed0] => 0x562e94ce76d0
[3] 002 : [0x562e94ce76d0 + 0x010 = 0x562e94ce76e0] => 0x2
размер=3 | узлов=8
---------------------------
добавить: ключ 0x010303ff - значение 0x3:
[0] 255 : [0x562e9359a040 + 0x7f8 = 0x562e9359a838] => 0x562e94ce66b0
[1] 003 : [0x562e94ce66b0 + 0x018 = 0x562e94ce66c8] => 0x562e94ce6ec0
[2] 003 : [0x562e94ce6ec0 + 0x018 = 0x562e94ce6ed8] => 0x562e94ce8f00
[3] 001 : [0x562e94ce8f00 + 0x008 = 0x562e94ce8f08] => 0x3
размер=4 | узлов=10
---------------------------
добавить: ключ 0x0103050f - значение 0x4:
[0] 015 : [0x562e9359a040 + 0x078 = 0x562e9359a0b8] => 0x562e94ce9710
[1] 005 : [0x562e94ce9710 + 0x028 = 0x562e94ce9738] => 0x562e94ce9f20
[2] 003 : [0x562e94ce9f20 + 0x018 = 0x562e94ce9f38] => 0x562e94cea730
[3] 001 : [0x562e94cea730 + 0x008 = 0x562e94cea738] => 0x4
размер=5 | узлов=14
---------------------------
добавить: ключ 0x020304ff - значение 0x5:
[0] 255 : [0x562e9359a040 + 0x7f8 = 0x562e9359a838] => 0x562e94ce66b0
[1] 004 : [0x562e94ce66b0 + 0x020 = 0x562e94ce66d0] => 0x562e94ce7ee0
[2] 003 : [0x562e94ce7ee0 + 0x018 = 0x562e94ce7ef8] => 0x562e94ce86f0
[3] 002 : [0x562e94ce86f0 + 0x010 = 0x562e94ce8700] => 0x5
размер=6 | узлов=15
---------------------------
добавить: ключ 0x0000ff00 - значение 0x6:
[0] 000 : [0x562e9359a040 + 0x000 = 0x562e9359a040] => 0x562e94ceaf40
[1] 255 : [0x562e94ceaf40 + 0x7f8 = 0x562e94ceb738] => 0x562e94ceb750
[2] 000 : [0x562e94ceb750 + 0x000 = 0x562e94ceb750] => 0x562e94cebf60
[3] 000 : [0x562e94cebf60 + 0x000 = 0x562e94cebf60] => 0x6
размер=7 | узлов=19
---------------------------
ищем: 0x010203FF => 0x1
ищем: 0x010304FF => 0x2
ищем: 0x020203FF => 0x2
ищем: 0x010303FF => 0x3
ищем: 0x0103050F => 0x4
ищем: 0x020304FF => 0x5
ищем: 0x0000FF00 => 0x6
ищем: 0x01020304 => (nil)
ищем: 0x010203FE => (nil)
Вложения
tree.c
(3.38 КБ) 4 скачивания

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ - учебная задача : трансляция страниц

Непрочитанное сообщение Olej » 01 сен 2021, 14:31

Olej писал(а):
31 авг 2021, 21:30
1-й из работающих вариантов, на C API (с поясняющим отладочным выводом):
Теперь такой же вариант на C++ (сохранена идентичность с реализацией C в выводе, для чего был оставлен вывод printf() вместо вывода в поток cout):

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ cat tree++.cc 
#include <cstdio>
#include <iostream>
#include <cstdint>
#include <vector>
using namespace std;

#ifdef NUM                                // число уровней (2, 4, 8, 16)
#define num NUM
#else
#define num 4
#endif

struct  RtNode{
public:
	RtNode(uint8_t levels)
	      : N(levels), R(32 / levels), L(1 << R)
	{
		M = 1;
		for (int i = 0; i < R - 1; i++ )
			M = ( M << 1 ) | 1;
		root = new vector<void*>(L, NULL);
		printf( "%d => %d => %d : маска 0x%08x\n", N, R, L, M );
	}
	void rt_insert(uint32_t key, void *val) {
		vector<void*> *prv = root;
		for (int i = 0; i < N; i++)
		{
			int pos = key & M;            // индекс текущего уровня
			if (i != N - 1)               // не терминальный уровень
			{
				if (NULL == (*prv)[pos])
					(*prv)[pos] = new vector<void*>(L, NULL);
			}
			else
				(*prv)[pos] = static_cast<vector<void*>*>(val);
			printf("[%d] %03d : [%p + 0x%03lx = %p] => %p\n",
		           i, pos, (void*)prv, pos * sizeof(void*), (void*)(prv + pos), (*prv)[pos]);
			prv = static_cast<vector<void*>*>((*prv)[pos]);
			key >>= R; 
		}
	}
	void* rt_lookup(uint32_t key) const { // Returns NULL if there is no element with such key. 
		vector<void*> *prv = root;
		int pos;
		for (int i = 0; i < N; i++)
		{
			pos = key & M;                // индекс текущего уровня
			if (NULL == (*prv)[pos])      // указатель следующего уровня
				return NULL;
			if (i == N - 1)
				break;
			prv = static_cast<vector<void*>*>((*prv)[pos]);
			key >>= R; 
		}
		return (*prv)[pos];
	}
	uint32_t rt_size(void)
	{
		return tsize(root, true);
	}
	uint32_t rt_nodes(void)
	{
		return tsize(root, false);
	}
private:
	uint8_t  N,                           // число слоёв
	         R;                           // число бит ключа на слой    
	uint32_t L,                           // число узлов в слое
	         M;                           // маска слоя
	vector<void*> *root;
	uint32_t tsize(vector<void*>* root, bool term, int level = 0)
	{
		uint32_t n = 0;                   // число терминальных страниц
		for (uint32_t i = 0; i < L; i++)
		{
			if (NULL != (*root)[i])
			{
				if (level < N - 1)
				{
					vector<void*>* pv = static_cast<vector<void*>*>((*root)[i]); 
					n += tsize(pv, term, level + 1);
					if (!term) n++;
				}
				else
					n++;
			}
		}
		return n;
	}
};

int main()
{
	struct {
		uint32_t key;
		void*    val;
	} data[] = { {0x010203FF, (void*)1},
//	             {0x010304FF, (void*)2},
	             {0x020203FF, (void*)2},
	             {0x010303FF, (void*)3},
//	             {0x0103050F, (void*)4},	             
//	             {0x020304FF, (void*)5},	             
//	             {0x0000FF00, (void*)6},
	           };
	uint32_t bad[] = {0x01020304, 0x010203FE};

	RtNode rt_root(num);
	printf("root: => %p\n", (void*)&rt_root);

    for (auto& p : data)   // заполнили
    {
		printf("добавить: ключ 0x%08x - значение %p:\n", p.key, p.val);
		rt_root.rt_insert(p.key, p.val);
		printf("размер=%d | ", rt_root.rt_size());
		printf("узлов=%d\n", rt_root.rt_nodes());
		printf("---------------------------\n");
	}

	for (auto& p : data)   // сосчитали
		printf("ищем: 0x%08X => %p\n", p.key, rt_root.rt_lookup(p.key) );
	for (auto& p : bad)
		printf("ищем: 0x%08X => %p\n", p, rt_root.rt_lookup(p));

	return 0;
}
Сборка:

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ make tree++
g++ -Wall -pedantic -std=c++14 tree++.cc -D NUM=4 -o tree++
Вложения
tree++.cc
(3.41 КБ) 4 скачивания

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ - учебная задача : трансляция страниц

Непрочитанное сообщение Olej » 01 сен 2021, 14:35

Olej писал(а):
01 сен 2021, 14:31
Теперь такой же вариант на C++ (сохранена идентичность с реализацией C в выводе, для чего был оставлен вывод printf() вместо вывода в поток cout):
Выполнение:

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ ./tree++
4 => 8 => 256 : маска 0x000000ff
root: => 0x7ffce7612a20
добавить: ключ 0x010203ff - значение 0x1:
[0] 255 : [0x558fb9ec2eb0 + 0x7f8 = 0x558fb9ec4698] => 0x558fb9ec3af0
[1] 003 : [0x558fb9ec3af0 + 0x018 = 0x558fb9ec3b38] => 0x558fb9ec4320
[2] 002 : [0x558fb9ec4320 + 0x010 = 0x558fb9ec4350] => 0x558fb9ec4b50
[3] 001 : [0x558fb9ec4b50 + 0x008 = 0x558fb9ec4b68] => 0x1
размер=1 | узлов=4
---------------------------
добавить: ключ 0x020203ff - значение 0x2:
[0] 255 : [0x558fb9ec2eb0 + 0x7f8 = 0x558fb9ec4698] => 0x558fb9ec3af0
[1] 003 : [0x558fb9ec3af0 + 0x018 = 0x558fb9ec3b38] => 0x558fb9ec4320
[2] 002 : [0x558fb9ec4320 + 0x010 = 0x558fb9ec4350] => 0x558fb9ec4b50
[3] 002 : [0x558fb9ec4b50 + 0x010 = 0x558fb9ec4b80] => 0x2
размер=2 | узлов=5
---------------------------
добавить: ключ 0x010303ff - значение 0x3:
[0] 255 : [0x558fb9ec2eb0 + 0x7f8 = 0x558fb9ec4698] => 0x558fb9ec3af0
[1] 003 : [0x558fb9ec3af0 + 0x018 = 0x558fb9ec3b38] => 0x558fb9ec4320
[2] 003 : [0x558fb9ec4320 + 0x018 = 0x558fb9ec4368] => 0x558fb9ec5380
[3] 001 : [0x558fb9ec5380 + 0x008 = 0x558fb9ec5398] => 0x3
размер=3 | узлов=7
---------------------------
ищем: 0x010203FF => 0x1
ищем: 0x020203FF => 0x2
ищем: 0x010303FF => 0x3
ищем: 0x01020304 => (nil)
ищем: 0x010203FE => (nil)
И вот сравнительное выполнение реализации C:

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ ./tree
4 => 8 => 256 : маска 0x000000ff
root: => 0x55af87bcf040
---------------------------
добавить: ключ 0x010203ff - значение 0x1:
[0] 255 : [0x55af87bcf040 + 0x7f8 = 0x55af87bcf838] => 0x55af88e976b0
[1] 003 : [0x55af88e976b0 + 0x018 = 0x55af88e976c8] => 0x55af88e97ec0
[2] 002 : [0x55af88e97ec0 + 0x010 = 0x55af88e97ed0] => 0x55af88e986d0
[3] 001 : [0x55af88e986d0 + 0x008 = 0x55af88e986d8] => 0x1
размер=1 | узлов=4
---------------------------
добавить: ключ 0x020203ff - значение 0x2:
[0] 255 : [0x55af87bcf040 + 0x7f8 = 0x55af87bcf838] => 0x55af88e976b0
[1] 003 : [0x55af88e976b0 + 0x018 = 0x55af88e976c8] => 0x55af88e97ec0
[2] 002 : [0x55af88e97ec0 + 0x010 = 0x55af88e97ed0] => 0x55af88e986d0
[3] 002 : [0x55af88e986d0 + 0x010 = 0x55af88e986e0] => 0x2
размер=2 | узлов=5
---------------------------
добавить: ключ 0x010303ff - значение 0x3:
[0] 255 : [0x55af87bcf040 + 0x7f8 = 0x55af87bcf838] => 0x55af88e976b0
[1] 003 : [0x55af88e976b0 + 0x018 = 0x55af88e976c8] => 0x55af88e97ec0
[2] 003 : [0x55af88e97ec0 + 0x018 = 0x55af88e97ed8] => 0x55af88e98ee0
[3] 001 : [0x55af88e98ee0 + 0x008 = 0x55af88e98ee8] => 0x3
размер=3 | узлов=7
---------------------------
ищем: 0x010203FF => 0x1
ищем: 0x020203FF => 0x2
ищем: 0x010303FF => 0x3
ищем: 0x01020304 => (nil)
ищем: 0x010203FE => (nil)
Характерны значения адресов указателей на корень дерева - статически размещённых в области данных для C, и динамически размещаемых в хипе для случая C++ (вся оставшаяся часть дерева, ветви и терминальные вершины - размещаются динамически и там и там).

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ ldd tree
	linux-vdso.so.1 (0x00007ffcea0f0000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f30f7281000)
	/lib64/ld-linux-x86-64.so.2 (0x00007f30f7495000)

Код: Выделить всё

olej@R420:~/2021/OWN_TEST.codes/tree$ ldd tree++
	linux-vdso.so.1 (0x00007ffdb0d45000)
	libstdc++.so.6 => /lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f0ff8043000)
	libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f0ff8028000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f0ff7e36000)
	libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f0ff7ce7000)
	/lib64/ld-linux-x86-64.so.2 (0x00007f0ff8248000)

Аватара пользователя
Olej
Писатель
Сообщения: 14939
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: C & C++ - учебная задача : трансляция страниц

Непрочитанное сообщение Olej » 01 сен 2021, 16:43

Olej писал(а):
01 сен 2021, 14:35
И вот сравнительное выполнение реализации C:
И если теперь на C++ мы можем объекты (деревья) RtNode создавать произвольно (локальными или динамически), то классу нужно бы добавить и деструктор:

Код: Выделить всё

struct RtNode{
public:
	RtNode(uint8_t levels) : N(levels), R(32 / levels), L(1 << R)
	{
		M = 1;
		for (int i = 0; i < R - 1; i++ )
			M = ( M << 1 ) | 1;
		printf("%d => %d => %d : маска 0x%08x\n", N, R, L, M);
		root = new vector<void*>(L, NULL);
		printf("root: => %p\n", (void*)root);
	}
	~RtNode(void)
	{
		printf("ликвидация дерева, удаляется: ");
		destroy(root);
		printf("\n");
	}
...
private:
...
	void destroy(vector<void*>* root, int level = 0)
	{
		for (uint32_t i = 0; i < L; i++)
		{
			if (NULL != (*root)[i])
			{
				if (level < N - 1)
				{
					vector<void*>* pv = static_cast<vector<void*>*>((*root)[i]);
					destroy(pv, level + 1);
				}
				else
					;                     // удаление терминальной страницы
			}
		}
		printf("%p ", (void*)root);
		delete root;                      // удаление всего слоя
	}
};	
+ некоторые незначительные исправления неточностей (см. в конструкторе):
Вложения
tree++.cc
(4.02 КБ) 4 скачивания

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя