Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
1

Пародия на стековый аллокатор

09.01.2017, 11:00. Просмотров 940. Ответов 29
Метки нет (Все метки)

здравствуйте, решил тут чуток поиграться... сделать аллокатор чтобы данные в статическом буфере размещал. в итоге долго поиграться не удалось - вылетает при первой же аллокации... честно, дебаггер не особо помогает в нахождении ошибки... что тут не так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <type_traits>
 
template<typename T, size_t size = 32>
struct stack_allocator {
    
    static_assert(size != 0, "oops");
 
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;
 
    template< class U >
    struct rebind { 
        typedef stack_allocator<U> other; 
    };
 
    stack_allocator() noexcept = default;
 
    stack_allocator(const stack_allocator& other) noexcept = default;
 
    template< class U >
    stack_allocator(const stack_allocator<U>& other) noexcept
    {
    }
 
    ~stack_allocator() noexcept = default;
 
    pointer address(reference x) const {
        return std::addressof(x);
    }
 
    const_pointer address(const_reference x) const {
        return std::addressof(x);
    }
 
    size_type max_size() const {
        return (size_t)(-1)/sizeof(value_type);
    }
 
    T* allocate(std::size_t n) {
        return (value_type*)(ptr + n);
    }
 
    void deallocate(T* p, std::size_t n) 
        {
    }
 
    void construct(pointer p, const_reference val) {
        ::new((void *)p) T(val);
    }
 
    template< class U, class... Args >
    void construct(U* p, Args&&... args) {
        ::new((void *)p) U(std::forward<Args>(args)...);
    }
    
    void destroy(pointer p) {
        p->~value_type();
    }
 
    template< class U >
    void destroy(U* p) {
        p->~U();
    }
private: 
    typename std::aligned_storage<sizeof(T), alignof(T)>::type ptr[size] = {};
};
 
template<size_t size>
struct stack_allocator<void, size>;
 
int main() {
    std::vector<int, stack_allocator<int>> vec;
    vec.emplace_back(1);
    return 0;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2017, 11:00
Ответы с готовыми решениями:

Аллокатор памяти общего назначения
Добрый день! В ВУЗе задали написать аллокатор памяти общего назначения на С++,...

Аллокатор malloc, как избавиться от CRT
Вот рабочий код HANDLE hFile = CreateFile(&quot;temp.txt&quot;, GENERIC_READ,...

Аллокатор в chrome
Всем привет, начал изучать исходники хрома, в аллокаторе, метод realloc должен...

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

Быстрый аллокатор
Собственно, необходим аллокатор для быстрого выделения памяти под мелкие...

29
DrOffset
8158 / 4734 / 1159
Регистрация: 30.01.2014
Сообщений: 7,714
09.01.2017, 11:24 2
tapochka, Ну... тут allocate на самом деле ничего не выделяет. Вместо этого возвращает n-нный указатель, причем он будет всегда одинаковый для одного и того же n. Т.е. тут и n используется не по назначению (как индекс, тогда как это размер в байтах) и положение текущей, уже занятой памяти, никак не сохраняется.
1
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
09.01.2017, 11:40  [ТС] 3
Цитата Сообщение от DrOffset Посмотреть сообщение
Ну... тут allocate на самом деле ничего не выделяет
так по идее так и должно быть, память то уже выделена инициализацией статического буфера...

Цитата Сообщение от DrOffset Посмотреть сообщение
Т.е. тут и n используется не по назначению (как индекс, тогда как это размер в байтах)
n - the number of objects to allocate storage for... с этим все правильно) но возвращаемый указатель из allocate не правильное у меня, благодарвствую
0
DrOffset
8158 / 4734 / 1159
Регистрация: 30.01.2014
Сообщений: 7,714
09.01.2017, 11:44 4
Цитата Сообщение от tapochka Посмотреть сообщение
так по идее так и должно быть, память то уже выделена инициализацией статического буфера...
Нет не должно.
В функции аллокации ты должен зафиксировать состояние отданной памяти как "занятое". У тебя этого не происходит, значит и выделения как такового нет. Возврат пойнтера - это только полдела.

Цитата Сообщение от tapochka Посмотреть сообщение
n - the number of objects to allocate storage for
Здесь согласен.
0
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
09.01.2017, 13:08  [ТС] 5
DrOffset, добавил в поля unsigned int pos = 0; теперь выдает совершенно бесовскую ошибку компиляции внутри uninitialized_fill:
C++
1
2
3
4
5
T* allocate(std::size_t n) {
        std::uninitialized_fill((value_type*)(ptr + pos), (value_type*)(ptr + pos + n), 0);
        pos += n;
        return (value_type*)(ptr + pos);
    }
note: см. ссылку на создание экземпляров функции шаблон при компиляции "std::_Container_proxy *stack_allocator<U,32>::allocate(std::size_t)"
1> with
1> [
1> U=std::_Container_proxy
1> ]
Добавлено через 8 минут
кстати все начинает работать если заменить
C++
1
2
3
4
template< class U >
    struct rebind { 
        typedef std::allocator<U>/*stack_allocator<U>*/ other; 
    };
но это явно не решение
0
DrOffset
8158 / 4734 / 1159
Регистрация: 30.01.2014
Сообщений: 7,714
09.01.2017, 13:11 6
Цитата Сообщение от tapochka Посмотреть сообщение
note:
Это же не ошибка, а подсказка к ошибке. Ошибку ты не показал.

Да и зачем тут этот uninitialized_fill?

Добавлено через 2 минуты
Цитата Сообщение от tapochka Посмотреть сообщение
pos += n;
Ну и это, по идее, должно быть после получения указателя. Иначе мы "дыру" вначале оставляем при первой аллокации.
0
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
09.01.2017, 13:20  [ТС] 7
если вернуть старый rebind, то вот так не дает написать даже
C++
1
const T& val = 0;
пишет
Ошибка C2440 инициализация: невозможно преобразовать "int" в "const std::_Container_proxy &"
т.е. с какого-то перепуга T определяется как std::_Container_proxy )) с чего бы это
0
DrOffset
8158 / 4734 / 1159
Регистрация: 30.01.2014
Сообщений: 7,714
09.01.2017, 13:29 8
Цитата Сообщение от tapochka Посмотреть сообщение
если вернуть старый rebind, то вот так не дает написать даже
ну вот тут: http://rextester.com/EWK96528
все нормально.
0
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
09.01.2017, 13:56  [ТС] 9
ну у меня короче на vs2015 вылетает в файле xutility в строке:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        // MEMBER FUNCTIONS FOR _Container_base12
inline void _Container_base12::_Orphan_all()
    {   // orphan all iterators
 #if _ITERATOR_DEBUG_LEVEL == 2
    if (_Myproxy != 0)
        {   // proxy allocated, drain it
        _Lockit _Lock(_LOCK_DEBUG);
 
        for (_Iterator_base12 **_Pnext = &_Myproxy->_Myfirstiter;
            *_Pnext != 0; *_Pnext = (*_Pnext)->_Mynextiter)
            (*_Pnext)->_Myproxy = 0;                                        //<--- вот здесь
        _Myproxy->_Myfirstiter = 0;
        }
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
    }
а в rextester ошибка времени выполнения то детектируется?

Добавлено через 12 минут
и в релизе вроде все нормально, только в дебаге трындец, вот бы кто проверил код на работоспособность еще:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
template<typename T, size_t size = 32>
struct stack_allocator {
    
    static_assert(size != 0, "oops");
 
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;
 
    template< class U >
    struct rebind { 
        typedef stack_allocator<U> other; 
    };
 
    stack_allocator() noexcept = default;
 
    stack_allocator(const stack_allocator& other) noexcept = default;
 
    template< class U >
    stack_allocator(const stack_allocator<U>& other) noexcept
    {
    }
 
    ~stack_allocator() noexcept = default;
 
    pointer address(reference x) const {
        return std::addressof(x);
    }
 
    const_pointer address(const_reference x) const {
        return std::addressof(x);
    }
 
    size_type max_size() const noexcept {
        return (size_t)(-1)/sizeof(value_type);
    }
 
    T* allocate(std::size_t n) {
        auto temp = pos;
        pos += n;
        return (value_type*)(begin + temp);
    } 
 
    void deallocate(T* p, std::size_t n) {
        for (auto i = 0; i < n; ++n)
            reinterpret_cast<value_type*>(p)->~T();
        pos -= n;
    }
 
 
    void construct(pointer p, const_reference val) {
        ::new((void *)p) T(val);
    }
 
    template< class U, class... Args >
    void construct(U* p, Args&&... args) {
        ::new((void *)p) U(std::forward<Args>(args)...);
    }
    
    void destroy(pointer p) {
        p->~value_type();
    }
 
    template< class U >
    void destroy(U* p) {
        p->~U();
    }
private: 
    typename std::aligned_storage<sizeof(T), alignof(T)>::type begin[size] = {};
    unsigned int pos = 0;
};
 
template<size_t size>
struct stack_allocator<void, size> {
 
    using _Not_user_specialized = void;
    using value_type = void;
    using pointer = void*;
    using const_pointer = const void*;
 
    template<class U>
    struct rebind
    {   
        typedef stack_allocator<U> other;
    };
 
    stack_allocator() noexcept = default;
 
    stack_allocator(const stack_allocator<void>&) noexcept
    {
    }
 
    template<class U>
    stack_allocator(const stack_allocator<U>&) noexcept
    {   
    }
 
    template<typename U>
    stack_allocator<void>& operator=(const stack_allocator<U>&)
    {   
        return (*this);
    }
};
Добавлено через 6 минут
и в rextester не детектируются ошибки времени выполнения, к сожалению
0
nonedark2008
1061 / 793 / 223
Регистрация: 28.07.2012
Сообщений: 2,213
09.01.2017, 15:38 10
tapochka,
1) deallocate у тебя реализован неверно
2) Что-то мне кажется, что аллокатор не может внутри себя содержать память под выделяемые объекты.
Стоит блок памяти вынести вне класса.
1
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
09.01.2017, 15:46  [ТС] 11
nonedark2008, пробовали у себя запускать? мне интересно будет ли вылет
0
nonedark2008
1061 / 793 / 223
Регистрация: 28.07.2012
Сообщений: 2,213
09.01.2017, 16:09 12
tapochka, вылетает.
Чутка поэкспериментировал:
C++
1
2
3
4
template< class U >
struct rebind {
    typedef stack_allocator<U, size> other;
};
C++
1
2
3
template< class U >
stack_allocator(const stack_allocator<U,size>& other) noexcept {
}
Теперь не вылетает.
1
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
09.01.2017, 16:26  [ТС] 13
ах, да, невнимательность... только мне это не помогает напрочь, вылетает в том же месте
0
nonedark2008
1061 / 793 / 223
Регистрация: 28.07.2012
Сообщений: 2,213
09.01.2017, 21:04 14
Цитата Сообщение от tapochka Посмотреть сообщение
только мне это не помогает напрочь, вылетает в том же месте
Вся фишка в том, что выделяемые объекты должны быть живы, даже если ты уничтожишь аллокатор.
Можешь проверить по своему коду: наверняка в какой-то момент вызывается декструктор аллокатора, а потом где-то происходит работа с объектами, выделенными через этот аллокатор. А объектов уже нет, т.к. вместе в аллокаторами умерла и вся твоя память.
1
Fulcrum_013
1588 / 1071 / 124
Регистрация: 14.12.2014
Сообщений: 8,822
Завершенные тесты: 3
09.01.2017, 21:08 15
Не так похоже сама идея аллокации на стеке. После выхода из allocate вызывающий вернет указатель стека в то положение в котором он находился перед вызовам Allocate и следующими же действиями начнет писать как стек вызовов с этого же места. При этом и данные он пишет по возвернутому аллокатором адресу. в результате то ли данные затирают стек вызовов то ли стек вызовов данные но в общем капут гарантирован.
1
nonedark2008
1061 / 793 / 223
Регистрация: 28.07.2012
Сообщений: 2,213
09.01.2017, 21:26 16
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
После выхода из allocate вызывающий вернет указатель стека в то положение в котором он находился
С чего бы это? Во время работы allocate мы ничего странного со стеком не делаем.
Мы просто работает с блоком данных, который был выделен когда-то ранее.
0
Fulcrum_013
1588 / 1071 / 124
Регистрация: 14.12.2014
Сообщений: 8,822
Завершенные тесты: 3
09.01.2017, 22:13 17
Цитата Сообщение от nonedark2008 Посмотреть сообщение
чего бы это? Во время работы allocate мы ничего странного со стеком не делаем.
Так он аллокатор или просто подпихиватель константного по размеру блока?
0
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
10.01.2017, 00:36  [ТС] 18
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Вся фишка в том, что выделяемые объекты должны быть живы, даже если ты уничтожишь аллокатор.
а можно поподробнее? есть, допустим, статический буфер, в котором разместили пару объектов, уничтожили вектор, ну значит и деструктор аллокатора должен их уничтожить в буфере, разве нет?
0
Fulcrum_013
1588 / 1071 / 124
Регистрация: 14.12.2014
Сообщений: 8,822
Завершенные тесты: 3
10.01.2017, 01:14 19
Цитата Сообщение от tapochka Посмотреть сообщение
ну значит и деструктор аллокатора должен их уничтожить в буфере, разве нет?
Это в куче. А на стеке в каком порядке выделял в обратном и высвобождай. Причем если это подпихивалка буфера вектору (а поскольку вызова alloca или манипуляций с SP тут не видно то оно так и есть) то сам буфер выделяется на стеке до этого и удаляет (отсчитывает назад указатель стека) сам компилятор при выходе из функции.
0
tapochka
40 / 40 / 17
Регистрация: 25.04.2014
Сообщений: 499
10.01.2017, 01:20  [ТС] 20
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
А на стеке в каком порядке выделял в обратном и высвобождай.
вы походу не поняли цель мою) это не создание аллокатора в куче по принципу LIFO, стековый в моем случае всего лишь берем статический массив в аппаратном стеке и в нем создаем объекты с помощью placement new... ну или надо сделать shrink_to_fit в контейнере - и вызываем деструкторы просто всех объектов созданных (т.к. реально освободить память мы не можем - она один раз выделяется в конструкторе аллокатора и освобождается только в деструкторе аллокатора)
0
10.01.2017, 01:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2017, 01:20

Задача с собеседования (аллокатор памяти)
Вопрос звучит так: &quot;Напишите быстрый аллокатор памяти&quot; Как я его понимаю:...

Int 13h и пародия на ОС
Здравствуйте! Решил написать ОС с по-настоящему красивыми обоями. Имеется...

Как написать пуловый аллокатор для работы с объектами
Здравствуйте! Подскажите как написать пуловый аллокатор для работы с объектами


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru