В C, как улучшить итерацию через список?

Question

У меня есть своя собственная структура данных, которая имитирует блок кучи.

typedef struct heap_block 
{ 
    struct heap_block* next; 
    size_t size; 
    bool isfree; 
} header; 

У меня есть метод, который перебирает мою структуру данных (это как список):

void craw(header* crawler, bool isfree, int* counter) 
{ 
    while(crawler->next != NULL) 
    { 
    if(crawler->isfree == isfree) 
    { 
     ++(*counter); 
    } 

    crawler = crawler->next; 
    } 

    if(crawler->isfree == isfree) 
    { 
     ++(*counter); 
    } 
} 

Мне нужно использовать дополнительную проверку, потому что последний элемент имеет crawler->next == NULL

Как улучшить эта итерация?

Answer 1

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

void craw(header* crawler, bool isfree, int* counter) 
{ 
    int local_counter = *counter; // assuming counter != 0 

    ... iterate ... 
    local_counter++; 

    *counter = local_counter;  
} 

Answer 2

Вы можете изменить тест петли на while (crawler != NULL) { ... }, например, так:

void craw(header* crawler, bool isfree, int* counter) 
{ 
    while(crawler != NULL) 
    { 
    if(crawler->isfree == isfree) 
    { 
     ++(*counter); 
    } 

    crawler = crawler->next; 
    } 
} 

Это изменение также предотвратит ваш код от сбоев, когда craw() вызываются с NULL гусеничным шасси.

Answer 3

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

void craw(header* crawler, bool isfree, int* counter) 
{ 
    for (; crawler; crawler = crawler->next) 
    { 
     if (crawler->isFree == isFree) 
      ++(*counter); 
    } 
} 

Answer 4

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

unsigned crawl2(header *crawler, bool isfree) 
{ 
unsigned count; 

    for (count =0; crawler; crawler=crawler->next) 
    { 
     if (crawler->isFree != isFree) continue; 
     count++; 
    } 
return count; 
} 

Примечания: вещи могут отличаться, если вы действуете в встраиваемом. Ссылка на * счетчик может быть разрешена на прямой в этом случае (и даже может быть сохранена в регистре во время цикла)