Добавление одного элемента в связанный список создает два элемента?

Question

Я пытаюсь разработать устройство для копирования файлов с одного USB-накопителя на другой, используя оба FAT-Filesystem. Поэтому я использую микроконтроллер Vinculum II FTDI. Код написан на C.

Чтобы иметь возможность копировать все файлы, мне нужно знать имена (под) каталогов на диске, потому что каждый из них должен обрабатываться отдельно. Существует функция on-chip для сканирования текущего каталога для файлов и подкаталогов («fat_dirTableFindFirst()» и «fat_dirTableFindNext()»).

Мне нужно сохранить имена всех каталогов (тип данных char *), которые я получил от сканирования динамически. Я решил использовать связанный список. Я использую его как стек (LIFO).

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

После завершения сканирования в первом каталоге я захватываю верхний подкаталог со стека (pop()). Затем я нажимаю маркер места «пробел» в стек, чтобы позже узнать, что я входил в более глубокий уровень/слой этого «дерева каталогов». Если во время сканирования я не найду дальнейшие каталоги, я вернусь на последний уровень и так далее. Следовательно, процедура сканирования должна быть похожа на предпросмотр дерева.

Он отлично работает, если есть макс. один подкаталог в каждом каталоге. Но если их несколько, я получаю запутанную ошибку: первый каталог задан правильно, но все следующие записи отображаются дважды в стеке! Из-за этого контроллер копирует те же файлы снова и снова.

Одиночный переход по программе не позволяет понять, почему это происходит. Код также записывает содержимое стека до и после каждого нажатия или pop в файл .txt с теми же запутанными результатами. Он немного похож на операцию push() - создает два элемента, но только если он вызывается во время этого цикла ... while.

Вот интересная часть кода. vos_free() унд vos_malloc() эквивалентна обычной свободной() таНос() вызовы (Ordner это немецкое слово для каталога или папки):

struct ordner { 
      char* data; 
      struct ordner* next; 
      }; 

    void push(struct ordner** headRef, char* dirName) 
    { 
     struct ordner* newOrdner; 
     if (newOrdner = vos_malloc(sizeof(struct ordner)) != NULL) 
     { 
      newOrdner->data = dirName; 
      newOrdner->next = *headRef; 
      *headRef = newOrdner;  
     } 
    } 

    char* pop(struct ordner** headRef) 
    { 
     struct ordner* temp; 
     char* value = "   "; 

     temp = *headRef; 
     value = *headRef->data; // "save" last element to return it 

     *headRef = temp->next; 
     vos_free(temp); 
     return (value); 
    } 

    while(1) 
    {    
     file_context_t fileToCopy; // File-Handle 
     struct ordner dummy; 
     struct ordner* head = &dummy; 
     dummy.next = NULL; 
     dummy.data = begin; 

     newScan: fat_dirTableFindFirst(fatContext1, &fileToCopy);     if(firstRun == 0) // First filename in first scan is the name of the disk, and has to be ignored 
      { 
       fat_dirTableFindNext(fatContext1, &fileToCopy); 
         firstRun = 1; 
      } 

      do 
      { 
      // if the entry is a Directory, add it to the stack 
       if (fat_dirEntryIsDirectory(&fileToCopy) == 1) 
       { 
        strncpy(nextDir, (char*) &fileToCopy, 11); 
        push(&head, nextDir);           

    // The next if-statement usually cannot be true, because there can't be 
    // two files with the same name in one directory and the different levels/layers 
    // of sub-directories are separated by a place marker, but actually it becomes 
    // true (LEDs are flashing because of blink(3)) 
        if (head->data == head->next->data) blink(3); 
       } 
       else 
       { 
        strncpy(nextFile, (char*) &fileToCopy, 11); 
        copyFile(fatContext1,fatContext2, nextFile);      } 
      } while (fat_dirTableFindNext(fatContext1, &fileToCopy) == FAT_OK); // perform scan, until all items of the directory were scanned    

    // then the next (sub-)directory has to be opened to scan it 
    // there are two possibilities to proceed: 
    // (1) no directory found ("space" on stack) --> go back to last layer and open & scan the next directory there (if there is another one) 
    // (2) a new sub-directory was found --> open & scan it 

change_layer: if (head != NULL)     
     {   
      nextDir = pop(&head); // get next Directory from stack 

      // Possibility (1) 
      if (nextDir == space) 
      { 
        // move back to last Directory 
        goto change_layer; 
      }      
      // Possibility (2): neue Unterordner gefunden 
      else 
       { 
       push(&head, space); // sign for entering next layer 
        //... 
        // open next directory 
        //... 
       goto newScan; 
      }      

      } 
     }    
    } // End while(1) 

Можете ли вы сказать мне, почему это происходит, что появляется один пункт дважды в стеке? Является ли мой алгоритм неправильным?

После нескольких часов и часов повторного поиска и кодирования я не мог решить эту проблему.

Пожалуйста, простите мне мой плохой стиль программирования с теми ассемблере петель, и мой плохой английский (я из Германии :))

Заранее спасибо

Chris

Answer 1

Вот декларация узла для связанного списка:

struct ordner { 
     char* data; 
     struct ordner* next; 
     }; 

Таким образом, data не имеет памяти, связанный с ним. Это просто указатель.

Тогда в вашей петле я не вижу, чтобы вы вызывали strdup(), чтобы выделить память для копии имени файла. Кажется, вы передаете некоторый буферный адрес непосредственно на push(), который сохраняет копию. Это ошибка.

Я рекомендую вам изменить push(), чтобы позвонить strdup() и сохранить имя файла. Затем, когда вы освободите экземпляр ordner, вы должны освободить data, дублируемую строку, прежде чем освободить экземпляр ordner.

Поскольку в вашем дизайне pop() также освобождает память, вы должны изменить pop() так, что вызывающий абонент обеспечивает буфер и pop() копирует имя файла в буфер перед освобождением памяти о хлопнутых ordner экземпляре.

Answer 2

Вы не делаете показать, где nextDir заявлено, но на первый взгляд это кажется вероятным:

Вы strncpy имя каталога в nextDir. Затем вы нажимаете это на стек. Теперь у вас есть запись с данными «dir1» в стеке.

Если есть другой каталог в том же каталоге, вы strncpy следующее имя каталога в буфер жеnextDir, эффективно перезаписью. Вы вставляете его в стек. Его указатель данных становится такой жеnextDir буфер.

Теперь обе записи имеют один и тот же указатель данных, а значение представляет собой значение второй записи, поэтому стек выглядит как «dir2», «dir2».

Если вы хотите иметь строку в каждой записи в стеке, вам нужно выделить память для каждого из них (убедитесь, что вы освободите его в конце концов, хотя!)

Answer 3

Я не думаю, что вы можете объявить переменную как в цикле while. Компилятор может дать вам один и тот же указатель снова и снова.

while(1) 
    {    
     file_context_t fileToCopy; // File-Handle 
     struct ordner dummy; 
     struct ordner* head = &dummy;