Come eseguire in sicurezza una lista per rimuovere in sicurezza un elemento e gli elementi associati

Il bug è causato da un'interazione (piuttosto) complessa tra:

SLIST_FORACH_SAFE e l'invocazione ricorsiva di destroy_element e la rimozione che fanno ciascuno.

SLIST_FOREACH_SAFE si rende "sicuro" per eliminare l'elemento corrente, memorizzando nella cache una copia dell'elemento successivo dopo questo - e lo fa sostanzialmente prima della parte del corpo del ciclo. Pertanto, a differenza di SLIST_FOREACH , non si basa sull'attuale oggetto che è valido quando continua il ciclo per l'iterazione successiva, ma fa affidamento sull'elemento successivo dopo essere ancora valido, dal momento che sta memorizzando nella cache che

Tuttavia, nel tuo caso, la chiamata ricorsiva può distruggere l'elemento memorizzato nella cache, quindi quell'elemento non è più valido.

Non penso che il double traversal risolverà questo problema (potrebbe cambiare il comportamento ma avrà ancora un errore logico) poiché il valore memorizzato nella cache di next sarà ancora usato nel primo loop (come risultato di la rimozione della sorella durante l'invocazione ricorsiva).

Suppongo che potresti risolvere il problema in diversi modi:

(a) scrivi la tua versione del ciclo for. Copia dal modello di SLIST_FOREACH :

for (item = SLIST_FIRST(list);
    item;
    /*item = SLIST_NEXT(item, next)*/) {
    if((item->type == type) && (ID==-1 || item->ID == ID) {
        cleanup_for_element(item);
        if (item->sister_ID != -1) {
            destroy_element(item->sister_list, item->sister_ID);
        }
        item = SLIST_NEXT(item, next);
        SLIST_REMOVE(list, item);
   }
   else {
       item = SLIST_NEXT(item, next);
   }
}

(b) ricarica il valore memorizzato nella cache dopo l'invocazione ricorsiva

destroy_element(list, type, ID) {
   struct elem *item, *tmp_item 
   SLIST_FOREACH_SAFE(item, list, next, tmp_item) {
       if((item->type == type) && (ID==-1 || item->ID == ID) {
           cleanup_for_element(item);
           if (item->sister_ID != -1) {
               destroy_element(item->sister_list, item->sister_ID);
               tmp_item = SLIST_NEXT(item, field);  // update the next item
           }
           SLIST_REMOVE(list, item);
       }
   }
}

I seguenti due approcci catturano ciò che deve essere eliminato senza usare una chiamata ricorsiva, e attendono fino a dopo il ciclo principale per eliminare la sorella:

(c) catturare gli elementi della sorella da cancellare in una lista separata e cancellarli dopo il ciclo principale. Ciò richiederebbe un elenco secondario.

(d) contrassegnare gli elementi come "dovrebbe eliminare" e dopo il ciclo principale eseguire attraverso la lista ancora una volta cancellando qualcosa contrassegnato "dovrebbe eliminare". Ciò richiederebbe un valore booleano per acquisire questo stato.

Ognuno di questi modi potrebbe essere reso più semplice mettendo a parte il -1 valore magico che stai utilizzando che significa "tutto" dal caso più semplice di rimozione di un solo elemento. Vorrei separare delete_element da delete_all . Quindi delete_element può eliminare una sorella dopo il ciclo principale, senza una lista (e senza ricorsione se lo desideri).

Il delete_all , può utilizzare un elenco secondario o, con una solida conoscenza del dominio, ad esempio, scorrere su tutti gli elenchi disponibili in modo che non sia necessario alcun elenco secondario.

Poiché questi tipi di problemi non sono univoci, alcuni linguaggi offrono costrutti iterativi che non consentono la modifica della struttura dati che viene attraversata e si guasteranno immediatamente se vengono apportate modifiche, anche se "sicure".

Dovresti essere consapevole che la tua versione a ciclo singolo attraversa l'elenco molte volte:

(1) il ciclo esterno è un attraversamento

(2) la chiamata ricorsiva è un'altra traversata

(3) SLIST_REMOVE esegue un altro attraversamento

Tra i lati positivi, escono presto così quando trovano l'elemento che interrompono.

Quindi, per rimuovere un elemento con una sorella, ottieni 4 travesali della lista, anche se presto.

Riferimento: link