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

void delete_node(void* from, void* what){ //fixed

Если уж cpp, то «delete» нельзя использовать, ибо зарезервированное слово.

void* cur;
cur  = cur -> next;

Вы прям открыли новый способ писать на си.

А, да, виноват.

А, ну да, там же должен быть

struct node{
 node* next;
 void* data;
};
..
void delete_node(node* from, node* what){ //fixed
..

я именно это хотел сказать.

А больше ничего не хотите сказать:

NULL == cur -> next

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

Суммируя вышесказанное

typedef struct node{
 struct node* next;
 void* data;
};

void delete_node(node* from, node* what){
     node* cur = from;
     node* 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;
     if(NULL != cur -> data)
        delete cur -> data;
     delete cur;
     prev->next = next;
  }

как-то так.

> А больше ничего не хотите сказать:

Не, не хочу. Семантика сигнатуры процедуры delete_node не предполагает такого поведения. Головы рубят по-другому.

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

Зато (free, perror, exit ∈ POSIX)

И да, головой может оказаться переменная из статической памяти.

все может быть из статической памяти, если захотеть.

А чем голова отличается от любого другого элемента?

delete_node(head, srch_ptr)

delete_node(head->next, srch_ptr)

Пустой список тоже список.

> все может быть из статической памяти, если захотеть.

Странные у вас желания.

А чем голова отличается от любого другого элемента?

У неё нет предка.

Пустой список тоже список.

Возможно, но практика показывает, что голова часто - из статики, а все остальные элементы - из кучи.

>> все может быть из статической памяти, если захотеть.

Странные у вас желания.

Вернее, не так, а вот так: Как вы будете распознавать - из динамической памяти у вас параметр what или из статической?

Допустим первый элемент мы выделили на стеке. Теперь создали еще 10 элементов в динамической памяти. Проверяем первый, который в стеке, он совпал, что делаем? Удалить не можем перезаписывать данные из следующего в него?

А если у нас только указатель и остальные 11 в динамической памяти, удалил первый, а указатель показывает на следующий.

Если я отвечаю за aллокацию блоков( может и пользователь если захочет) мне как-то пофиг, что там в what, просто адрес не совпадет не с одним элементом списка.

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

> Допустим первый элемент мы выделили на стеке. Теперь создали еще 10 элементов в динамической памяти. Проверяем первый, который в стеке, он совпал, что делаем? Удалить не можем перезаписывать данные из следующего в него?

Обычно данные хранятся в динамических элементах, а голова - статическая переменная (и NULL == data), которую не нужно удалять. Это удобно тем, что у нас всегда есть точка входа в список и нам не нужно проверять удалена она или нет. В delete_node, соответственно мы передаём &from и from.next, если мы хотим удалить первый элемент списка (а from - это, стало быть, нулевой).

Но вы правы в том, что это предмет торга - можно сделать так, а можно эдак. Главное чтобы не была нарушена общая концепция системы и ТЗ, как создавали - так и удаляем.

> Как вы будете распознавать - из динамической памяти у вас параметр what или из статической?

Я лучше просто оторву элемент от списка и верну вызывающему. А он уж пусть сам ломает голову, надо ли его free, delete или что ещё.

> Я лучше просто оторву элемент от списка и верну вызывающему. А он уж пусть сам ломает голову, надо ли его free, delete или что ещё.

Давайте тогда вообще ничего не будем делать, пусть вызывающий сам с этим разбирается. Для процедуры с названием delete_node - это наиболее ожидаемое поведение.

> GCC умеет ТСО

Подозреваю, что только в простейшем случае (как в скале или кложуре). Никакой взаимной рекурсии, наверное.

sys/queue.h

>Никакой взаимной рекурсии, наверное.

вы знаете много языков (реализаций), могущих взаимную рекурсию? А между нелокальными функциями?

Никакой взаимной рекурсии, наверное

#include <iostream>

typedef long long int big;

big g(big i, big res );

big f(big i, big res ) { return i==0 ? res : g(i-1, i+res); }
big g(big i, big res ) { return i==0 ? res : f(i-1, i+res); }

int main()
{
    std::cout << f(1000*1000*1000, 0) << '\n';
    return 0;
}

> вы знаете много языков (реализаций), могущих взаимную рекурсию? А между нелокальными функциями?

Небольшой список есть. Дотнетовский F# умеет (компилятор вставляет специальный тег .tail в генерируемый байт-код IL, а CLR о нем знает). Причем работает даже в mono, но на порядок или два медленнее. Среди реализаций CL умеет SBCL, если не ошибаюсь. Должен уметь и хаскелевский GHC, но специально не проверял.

Это критически важно, например, для продолжений. В F# это будут async workflow (три продолжения в каждом асинхронном вычислении). И поэтому, кстати, немного убого смотрятся продолжения в Scala - в JVM просто нет TCO, необходимой для полноценной реализации продолжений. Даже while толком не поиспользуешь из-за этого (while рекурсивно определяется через самого себя и связку bind/flatMap/>>=):

    let rec whileC p m =
        if p () then 
            bindC m (fun () -> whileC p m) 
        else 
            zeroC

Хорошая новость. А если функции f и g будут определены в разных модулях компиляции (в разных объектниках)?

>Дотнетовский F# умеет (компилятор вставляет специальный тег .tail в генерируемый байт-код IL, а CLR о нем знает).

можно сразу простейший пример двух _нелокальных_ (public?) взаимнорекурсивных функций и тест их?

Среди реализаций CL умеет SBCL, если не ошибаюсь.

Очень сомневаюсь именно во взаиморекурсивности

Должен уметь и хаскелевский GHC, но специально не проверял.

Не удивлюсь если это так, но «один в поле не воин» =)

> можно сразу простейший пример двух _нелокальных_ (public?) взаимнорекурсивных функций и тест их?

Объявляешь функции в модуле.

>>Среди реализаций CL умеет SBCL, если не ошибаюсь.

>Очень сомневаюсь именно во взаиморекурсивности

Срабатывает. Как-то натыкался. Был приятно удивлен.

Тут дело не столько в самой взаимной рекурсивности, сколько в том, чтобы хвостовой вызов срабатывал для функции, определенной извне (именно поэтому я попросил сишные функции разнести по разным модулям компиляции). Это очень важно для продолжений. Очевидно, если такой хвостовой вызов работает, то и работает взаимная рекурсия, независимо от того, открыты или локальны функции (.NET налагает жесткое требование - такой вызов должен быть помечен атрибутом .tail в байт-коде).

В случае локальных функций компилятор F# может произвести жесткую оптимизацию и заменить всю рекурсию циклом, даже для нескольких зависимых функций. Но факт в том, что TCО будет работать даже без такой оптимизации (в свойствах проекта выставить свойство «TailCall», а сам проект компилировать в режиме «Debug»).

>Срабатывает. Как-то натыкался. Был приятно удивлен.

Хм, очень странно... Там jamp на funcall (или его «внутренний» аналог)?

Ладно, будет не лень - поковыряю...

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

для нелокальных функций это дублирование кода... Этим хотелось бы как-то управлять...

Но факт в том, что TCО будет работать даже без такой оптимизации (в свойствах проекта выставить свойство «TailCall», а сам проект компилировать в режиме «Debug»).

А без дебага TCO не работает?

> Хм, очень странно... Там jamp на funcall (или его «внутренний» аналог)?

Тоже есть сомнения. Но у меня почему-то сработало. Да и продолжения сработали в СL однажды как надо. Опять же в пользу. В общем, изучать надо отдельно :)

> для нелокальных функций это дублирование кода... Этим хотелось бы как-то управлять...

Почему дублирование? Должен получиться чистый и незаоптимизированный компилятором хвостовой вызов, который виртуальная машина и распознает.

Кстати, оптимизация TCO должна быть очень нетривиальной вещью. В .NET к ней шли долго (пришли ли ??). В четвертой версии для x64 срабатывает чаще, но медленней в тех случаях, в которых срабатывало раньше. А в mono хвостовой вызов работает ужасно медленно. По моим тестам разница на порядок (я измерял совсем другое, но все в итоге свелось именно к разнице в реализации TCO).

> А без дебага TCO не работает?

Если быть точнее, то нужно отключить оптимизацию кода, но поставить галочку напротив опции хвостовой рекурсии. Код проверял рефлектором. Компилятор F# ничего такого особенного уже не делает, в циклы рекурсию не превращает, но добавляет к хвостовому вызову атрибут .tail. Мне самому тогда было интересно. Да и многого недопонимал тогда в этом вопросе :)

> А без дебага TCO не работает?

В общем, эти вещи независимы в F#. Хотя в релизе компилятор может превратить даже взаимную локальную рекурсию в цикл.

>Почему дублирование? Должен получиться чистый и незаоптимизированный компилятором хвостовой вызов, который виртуальная машина и распознает.

а, я «для локальных» не заметил =)

Хотя в релизе компилятор может превратить даже взаимную локальную рекурсию в цикл.

ну для умного компилятора это то как раз не диво... Диво, что умеющих TCO (а не просто зацикливание хвостовой рекурсии) меньше, чем пальцев на одной руке...

> а, я «для локальных» не заметил =)

Будет и для них, если отключишь оптимизацию кода (один тег в файле проекта). Без оптимизации почти все остается как есть. Но с TCO ;)