Что такое сегментированные списки?

Тема в разделе "WASM.A&O", создана пользователем weiv, 7 мар 2006.

  1. weiv

    weiv New Member

    Публикаций:
    0
    Регистрация:
    2 ноя 2003
    Сообщения:
    25
    Адрес:
    Новосибирск
    Что такое списки вообще и в частности стеки, очереди, деки я понимаю. Но вот что-то не найду определения - что такое сегментированные списки и как с ними работать.



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



    Предположу только что в отличие от так сказать традиционных списков в сегментированных память выделяется/освобождается не для отдельных узлов списка, а сразу под целый "сегмент", в котором будут несколько узлов. А как тогда узлы располагаются внутри сегмента?Также каждый узел хранит указатель на соседний или просто без указателей, как массив? А как тогда добавлять/удалять первый узел в сегменте, если весь сегмент заполнен?
     
  2. AsmGuru62

    AsmGuru62 Member

    Публикаций:
    0
    Регистрация:
    12 сен 2002
    Сообщения:
    689
    Адрес:
    Toronto
    Это смесь массива со связанным списком. Пример: выделяем страницу (4096 байт) под массив указателей - 1024 указателя получится. Используем только 1023 указателя, а последний указатель укажет на следующую такую страницу из 1024 указателей. Конечно, будут нужны некоторые сервисные переменные: сколько указателей занято, чтобы можно было удалять и видеть когда нужен следующий сегмент.



    Недостатки: трудно делать бинарный поиск - он требует линейности массива.
     
  3. weiv

    weiv New Member

    Публикаций:
    0
    Регистрация:
    2 ноя 2003
    Сообщения:
    25
    Адрес:
    Новосибирск
    А как в таком случае добавлять элемент в начало списка, если в первой странице занят первый указатель?
     
  4. AsmGuru62

    AsmGuru62 Member

    Публикаций:
    0
    Регистрация:
    12 сен 2002
    Сообщения:
    689
    Адрес:
    Toronto
    Не получится, наверное... такие списки годятся только для не сортированных элементов.



    Кстати, чтобы избежать дефрагментации и больших затрат памяти, можно использовать простой стандартный связный список. Только для выделения элементов списка использовать сегменты. Например, выделить сразу 1024 узла списка одним куском памяти, и потом брать из этого сегмента узлы и присоединять к списку или отсоединять от него. Не хватает узлов - ещё 1024 выделить.
     
  5. 3ahyga

    3ahyga New Member

    Публикаций:
    0
    Регистрация:
    28 фев 2006
    Сообщения:
    24
    Адрес:
    Стольный град Москов
    Ну и для добавления элемента в начало списка можно найти решение, например, аполнять списко не всесь сразу, но допустим на 75%, и добавлять нужный элемент, сдвигая списко на 1 или несколько позиций!
     
  6. Dr.Golova

    Dr.Golova New Member

    Публикаций:
    0
    Регистрация:
    7 сен 2002
    Сообщения:
    348
    > аполнять списко не всесь сразу, но допустим на 75%



    Нах? Выделяем еще одну ноду, в последний ее элемент сохраняем что хотели, ставим новую ноду как корень, и связываем ее с оригинальным корнем.
     
  7. weiv

    weiv New Member

    Публикаций:
    0
    Регистрация:
    2 ноя 2003
    Сообщения:
    25
    Адрес:
    Новосибирск
    У меня есть два класса Heap и List (их писал другой человек).

    Я пытаюсь разобраться на их основе что собственно представляют

    эти сегментированные списки. Пока что общей картины для чего нужны

    все эти структуры и переменные мне не понятно.



    Heap - отвечает за все выделение памяти сегментами.

    List - сегментированный список должен быть.

    List осуществляет обычные функции - добавление элемента,

    удаление элемента с начала, удаление с конца.

    Память List берет только через функции Heap.

    List будет служить как базовый класс, на его основе

    потом можно создавать разные списки.



    Так вот как я пока понимаю всю работу.

    При инициализации List создается объект класса Heap,

    который по умолчанию создает один сегмент размером 64 кб



    Допустим я буду добавлять элементы следующего вида в список:



    struct article

    {

    char * word;

    char * desc;

    };



    Метод add списка вызывает get_mem из Heap для получения памяти.

    Heap выделяет ее из сегмента. Т.е. из тех 64 кб что выделили для начала.



    Мне непонятна схема как будут размещаться элементы вот в этом Heap.



    Должны ли элементы указывать друг на друга?

    И вообще память под строки word и desc тоже берется из того же сегмента

    что и под сами элементы?



    Далее идут сами файлы.


    Код (Text):
    1.  
    2. //-----------------------------------------------------------
    3. // HEAP.H
    4. //
    5. #define SEGMENTSIZE 65539
    6. #define SEGMENTCOUNT 1024
    7.  
    8. class Heap
    9. {
    10. public:
    11.         Heap(int _segment_size = SEGMENTSIZE);
    12.                {
    13.                     segment_size  = _segment_size;
    14.                     current       = 0;
    15.                }
    16.         ~Heap()    
    17.                {  delete_segments(); }
    18.         void*      get_mem(int size);
    19.         void       free_mem (void *);
    20. private:
    21.         struct Segment_def
    22.         {      
    23.                 bool      used;
    24.                 int       size;
    25.                 void*     offset;
    26.         };
    27.  
    28.         struct Segment
    29.         {
    30.                 void*     data;
    31.                 Segment*  prev;
    32.                 Segment_def[SEGMENTCOUNT]  descriptor;
    33.                 int                        descriptor_count;
    34.         };
    35.  
    36.         int       make_segment();
    37.         void      delete_segments();
    38.  
    39.         int       segment_size;
    40.  
    41.         segment*  current;
    42. };
    43.  
    44. //-----------------------------------------------------------
    45. // LIST.H
    46. //
    47. #include "heap.h"
    48.  
    49. #define LISTSIZE 64
    50.  
    51. class List
    52. {
    53. public:
    54.     List(int _element_size, int _element_count = LISTSIZE);
    55.     ~List();
    56.  
    57.     void*      get(int pos);
    58.     void       add(void* data);
    59.  
    60.     // returns and deletes elements
    61.     void       take_first(void* store);
    62.     void       take_last(void* store);
    63.     void       take(int pos, void* store);
    64.  
    65.     int        count();
    66.     bool       error(); { return error; } // true if error in last operation
    67. private:
    68.     struct Segment
    69.     {
    70.         void*    data;
    71.         Segment* prev;
    72.         Segment* next;
    73.     };
    74.     Segment*         first;
    75.     Segment*         last;
    76.     int              first_index;
    77.     int              last_index;
    78.  
    79.     int              element_size;
    80.     int              element_count;
    81.     bool             error;
    82.    
    83.     void new_segment();
    84.     void delete_segment(Segment* seg);
    85. };
    86.  
    87. //-----------------------------------------------------------
    88.  
     
  8. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    http:/gzip.rsdn.ru/article/cpp/segmented_list.xml