односвязные списки

А в чем проблема?

как создавали так и удаляйте.

cur = first;
while(cur->next)
  cur = cur->next;
delete cur;

как-то так.

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

Тогда последний указатель в списке будет указывать не на NULL, а на удаленный элемент, неправильно же.

t * delete_tail(t *first)
{
  t *cur = first;
  if(cur == NULL){
    return NULL;
  }
  if(cur->next == NULL){
    delete cur;
    return NULL;
  }
  while(cur->next->next)
    cur = cur->next;
  delete *(cur->next);
  cur->next = NULL;
  return;
}

как-то так, но мог и накосячить...

Это называется init, обычно рекурсивная функция, вроде

init (x:[]) = []
init (x:xs) = x : (init xs)

(defun init (list)
  (unless (endp (rest list))
    (cons (first list) (init (rest list)))))

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int         id;
  struct node *next;
} List;

List*
make_list(int id, List *next) {
  List* list = (List*)malloc(sizeof(List));
  list->id   = id;
  list->next = next;
  return list;
}

List*
init (List *list) {
  if (list->next == NULL)
    return NULL;
  else
    // No TCO...
    return make_list(list->id, init(list->next));
}


void
print_list(List *list) {
  if (list->next == NULL)
    printf("%i.\n", list->id);
  else {
    printf("%i, ", list->id);
    // TCO
    print_list(list->next);
  }
}

main () {
  List *list = make_list(1, make_list(2, NULL));
  print_list(init(list));
}

И какое ограничение на длину списка для Си варианта?

И какое ограничение на длину списка для Си варианта?

Аллокация в куче, так что сколько ОС отдаст оперативной памяти - столько и будет.

Тогда последний указатель в списке будет указывать не на NULL, а на удаленный элемент, неправильно же.

это потому, что надо хранить не указатель на эл-т, а указатель на указатель на следующий.

/* поиск */
p = &first;
while(*p && (*p)->next)
 p = &((*p)->next);
/* удаление */
tmp = *p;
*p = (*p)->next;

что-то подобное (не проверил).

Однако, если ТС намеревается сделать FIFO, то ему лучше применить закольцованные списки. В них удаление самого старого эл-та реализуется проще (искать не надо).

А вообще всё это подробно Кнут расписал.

>И какое ограничение на длину списка для Си варианта?

нет никаких ограничений. Только память, и (главное!) время.

нет никаких ограничений. Только память, и (главное!) время.

Ну, тогда вы можете рассказать почему я получаю segfault в программе ниже?

main () {
  int i;
  int n = 1000000;
  List *list = make_list(n, NULL);
  for (i = 0; i < n; ++i) {
    list = make_list(n - i, list);
    if (list == NULL) {
      return 1;
    }
  }
  print_list(list);
}

$ gcc main.c && ./a.out
...
... 261823, 261824, 2Segmentation fault

Сессия близится. Набежали ><

Откуда у школьников сессия?

как-то так, но мог и накосячить...

ну почти :)

List*
init_mut(List *list) {
  List *current = list;
  if (current == NULL)
    return NULL;
  if (current->next == NULL) {
    free(current);
    current = NULL;
    return NULL;
  }
  while (current->next->next != NULL)
    current = current->next;
  free(current->next);
  current->next = NULL;
  return list;
}

Связные списки в школе не изучают. Там только кнопки на формочки учат таскать.

Зависит от школы.

так же как и любой другой элемент.
Удалить текущий можно 2 способами:
либо дойти до элемента, после которого следует текущий,
либо переписать все поля из следующего после текущего, если он есть и удалить этот следующий, а если нет, то «заземлить» список сделав ссылку на следующий NULL.(это плохой вариант)

«Используй двусвязный, Люк»:)

List*
init (List *list) {
  if (list->next == NULL)
    return NULL;
  else
    // No TCO...
    return make_list(list->id, init(list->next));
}

Кстати, в чем смысл этого «инита»?

У нас в 10-м классе были :) Кнопки на формочке рисовать стали учить гда через 2 как я закончил школу.

Кстати, в чем смысл этого «инита»?

Это сабж - «как удалить элемент, который указывает на NULL?»

А где тогда освобождение памяти?

Ну, тогда вы можете рассказать почему я получаю segfault в программе ниже?

Потому что там написано нечто очень странное) make_list в данном случае это cons.

А где тогда освобождение памяти?

Освобождение в мутабельной версии. В pure версии, когда мы создаем из одних объектов новые без изменения старых аллокация производится в конструкторах (make_list), освобождение делается параллельно (с помощью регионов, примитивными методами GC вроде ref. counting и т.п.).

Я в курсе, что такое cons, и даже про кар и кудр слышал.
А что там такого странного написано? В цикле создается список, падает на попытке напечатать его. Причем памяти в куче хватает (в цикле есть проверка на NULL).

> В pure версии, когда мы создаем из одних объектов новые без изменения старых аллокация производится в конструкторах (make_list), освобождение делается параллельно (с помощью регионов, примитивными методами GC вроде ref. counting и т.п.).

Мы всё еще про Си и про тот кусок кода? Где там ref. counting?

>Ну, тогда вы можете рассказать почему я получаю segfault в программе ниже?

что такое make_list() ? откуда вы его выкопали? закопайте обратно.

У меня ПРОЛОГ в школе читали. И двусвязные списки были, и не только ;)

> что такое make_list() ? откуда вы его выкопали? закопайте обратно.
Ты читал тред полностью? Изначально я спрашивал про ограничение для программы из этого поста:
http://www.linux.org.ru/forum/development/5649590?lastmod=1291667769771#comme...

Оттуда же и make_list().

Бяка-код. Какая нафиг TCO?

Студентота рассуждает о школоте. Картина маслом.

Я в курсе, что такое cons, и даже про кар и кудр слышал.

Но там не cons на самом деле :)

А что там такого странного написано?

Там не валидный код. Указателю присваивается адрес списка, потом ему же присваивается адрес другого списка. И не нужная проверка на NULL.

Имелось в виду наверное

main () {

  int i, n = 1000000;
  List *list = make_list(n, NULL);
  List *current = list;

  for (i = 1; i < n; i++) {
    current->next = make_list(n - i, NULL);
    current = current->next;
  }

  print_list(list);

}

Запускайте c `ulimit -s unlimited' или от суперпользователя - не будет seg. fault-a, но OOM killer всё равно прекратит выполнение.

Мы всё еще про Си и про тот кусок кода? Где там ref. counting?

Он сбоку, нужно просто представить :) Изначально была попытка указать на то, что если знать что такое РТД, рекурсивные функции, вроде init, то вопроса топика не возникает - берётся эта схема и ложится на любой ЯП. Но тут есть момент с чистотой - будет у нас мутабельное решение или с созданием копий. В первом случае всё просто (те самые императивные портянки), во-втором случае есть вопрос о сборке мусора - который, в принципе, всякий раз решается когда кто-то хочет писать на си в таком стиле - для обеспечения прозрачности в параллельных алгоритмах или как в GObject (там, кстати, есть этот самый подсчёт ссылок).

Бяка-код. Какая нафиг TCO?

Ты по крайней мере правильно её склоняешь :) Так в чём вопрос?

ты лучше man 3 malloc почитай... Именно там ограничение и расписано. Но к спискам оно не имеет никакого отношения. Скорее к glibc.

Изначально я спрашивал про ограничение для программы

Кстати, вопрос в ограничении на размер списков? Или в том как её отдать без GC? Ответы такие:

1) OOM killer как было сказано и особенности работы виртуальной памяти (последую флэшмобу и скажу «бе»). Это решается тем, что VM которые работают с такого рода большими объектами запрашивают у ОС big chank of memory и уже в её рамках проводят аллокацию / деаллокацию (сборку) чтобы не зависеть от механизмов ОС которые могут быть не очень подходящими для целей VM. Как пример - Erlang со своими потоками, или JVM где heap size настраивается по-своему. Или SBCL где тоже есть параметры на этот счёт. А malloc - у malloc есть секция BUGS в man 3 malloc :)

2) Как отдать - элементарно, рекурсивно (даже итеративно, т.к. TCO) отдать и всё.

т.е. вы принципиально не хотите вставить проверку на NULL в вашем коде?

Насколько я знаю, malloc() возвращает NULL в случае нехватки памяти, и вы этот нуль радостно разименовываете. вот оно и падает.

Там не валидный код. Указателю присваивается адрес списка, потом ему же присваивается адрес другого списка.

А конструкция вида «i = i + 1» для тебя тоже невалидная?

Имелось в виду наверное

Нет, имелось ввиду то, что было написано. Делалось по аналогии с твоим же примером:

List *list = make_list(1, make_list(2, NULL));

Запускайте c `ulimit -s unlimited' или от суперпользователя - не будет seg. fault-a, но OOM killer всё равно прекратит выполнение.

И это называется нет ограничений на длину списка, кроме «сколько ОС отдаст оперативной памяти - столько и будет»? Тут рекурсивный вызов print_list, никакой ТСО в Си нет, насколько мне известно, и понятное дело, что рекурсия ограничена стеком в таком случае.

Изначально была попытка указать на то, что если знать что такое РТД, рекурсивные функции, вроде init, то вопроса топика не возникает - берётся эта схема и ложится на любой ЯП.

В том-то и дело, что не ложится она на любой ЯП.

GCC умеет ТСО

т.е. вы принципиально не хотите вставить проверку на NULL в вашем коде?

Там принцип демонстрируется. На такие вещи просто внимания обращать не стоит, т.к. только речь зайдет о тестировании утечек или возвращаемых значений - будут свои обвёртки (скажем, нет никакого кайфа писать сетевое приложение в прямых API со всеми танцами, у Стивенса на эту тему есть даже библиотека обёрток); malloc, очевидно должен много чего ещё делать если мы хотим использовать динамические списки.

> GCC умеет ТСО
Хм, не знал, тогда признаю, что был не прав.

Имелось в виду наверное

Нет, имелось ввиду то, что было написано

Вот

List *list = make_list(n, NULL);
       \
            \
                  \
                       \
                             \
    list = make_list(n - i, list);

теперь понятно, не разглядел сразу.

И это называется нет ограничений на длину списка

Я выше написал про (1) и (2) на этот счёт. Ты как-то через чур придирчив к моему примеру того как вытаскивать кроликов из воздуха.

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

print_list написан в TCO форме - он итеративный.

В том-то и дело, что не ложится она на любой ЯП.

Ок, init не в TCO форме (на данный момент, в случае gcc).

Но мне кажется главное понимать принципы - что такое init, как он выглядит в естественной форме, как в рекурсивной форме, как в хвостово-рекурсивной, как в виде свёртки. После этого реализовать init с помощью цикла не составит проблем. Но будет видение общей перспективы вещей.

Забей, я придирался предполагая, что gcc не умеет TCO (и очевидно, он ее не делает без -O2 опции).

>Там принцип демонстрируется.

Тогда вопросов нет.

А ведь может оказаться, что у TC просто зачёт по предмету :)

Как в воду глядите :)

как удалить элемент, который указывает на NULL?

  delete(void* from, void* what){
     void* cur = from;
     void* prev, next;

     if( NULL == cur          || 
         NULL == cur -> next  ||
         NULL == what            )
       throw exception("Ой!");

     prev = cur;
     cur  = cur -> next;
     next = cur -> next;

     /* what->next может быть NULL-ом (в грамотном списке)*/
     while(NULL != next && what != cur){
        prev = cur;
        cur  = prev -> next;
        next = cur  -> next;
     }
     
     if( what != cur )
       throw exception("Ой!^2");
       
     next = cur->next;
     delete cur;
     prev->next = next;
  }

иными словами, нужно знать не только указатель на сам удаляемый элемент (указывающий на NULL) но так же и указатель на элемент, следующий для которого - удаляемый.

throw, delete - откуда эти няшки?

> void delete(void* from, void* what){ //fixed

Из цпп, кажись, не?

вам ник очень подходит :)

Блаадарю!