C - Step linked list analysis

[pinprick]

http://pastebin.com/BBHxd0iY

I have to use the the following file shuffle.csv to identify which parish from the most populated county has the least people. It is done line by line, for instance:

county A, parish B, Population B

county A, parish C, Population C

county A -> parish B or C -> Population B or C

If ( pop C < pop B ) county A -> parish C -> Population C

county A -> population + = Pop C

The most populated county is placed in the root of the linked list and then fprintf("output.csv"... ), in each interaction ( line by line ) evaluation til that line.

All the counties are added.

The least populated parish from the corresponding county is updated.

It very easy but I cannot spot the bug. It compiles well but when I run it the output, which is placed in a file named output.csv, is wrong. I have spent at least 5 hours revising the code, debugging, testing, breakpoints and I cant find the little *****r xD. I would appreciate it if you could help me out.

Input file structure:

District , county , parish, population

Grande Porto, Vila do Conde, Rio Mau, 1907

Output file structure:

fprintf( stdout, "%s, %s, %d\n", base->root->minusParish->parishName, base->root->countyName, base->root->minusParish->population);

Arcos, Vila do Conde, 869

...

Ferreiro, Vila do Conde, 660

...

Outeiro Maior, Vila do Conde, 378

...

It just prints Vila do Conde parish and it shouldn't.

HEADER

typedef struct {
	int population;
	char *parishName;
} parish;

typedef struct nextCounty {
	char *countyName;
	int population;
	parish *minusParish;
	struct nextCounty *next;
} county;

typedef struct {
	int numberCounties;
	county *root;
} core;

int list_assign( core *l, int pos, char **str, int people);

int list_insert( core *l, int pos, county *curr);

county* lista_removeTOSORT(core *l, int pos);

county * list_search( core *l, char* str, int *pos);

int list_sort( core *l, int posiVerifi, county *foundAddr);
[/CODE]

[b][u][color=#b22222]MAIN[/color][/u][/b]

[CODE]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lista.h"

county* createCounty( char *name, int people ) {

county *ptr;

if ( ( ptr = ( county *) malloc( sizeof(county) * 1 ) ) == NULL ) return NULL;

ptr->countyName = name;
ptr->population = people;
ptr->next = NULL;

return ptr;
}

parish* createParish ( char *name, int people ) {

parish *ptr;

if ( ( ptr = ( parish *) malloc( sizeof(parish) * 1 ) ) == NULL ) return NULL;

ptr->parishName = name;
ptr->population = people;

return ptr;
}

FILE* readlnVeriPlace( FILE *input, core *listCore) {

int i;
int people;
county *countyList, *foundAddress;
parish *parishList;
char *countyMalloc;
char *parishMalloc;
char ch;
int position;


if ( input == NULL || listCore == NULL ) return NULL;

parishMalloc = (char *) malloc ( sizeof(char) * 50 );
countyMalloc = (char *) malloc ( sizeof(char) * 50 );

if ( parishMalloc == NULL || countyMalloc == NULL ) return input;

// READLINE

while ( ( ch = fgetc(input) ) != ',' );

i = 0;
while ( ( ch = fgetc(input) ) != ',' ) {
countyMalloc[i] = ch;
i++;
}
countyMalloc[i] = '\0';

i = 0;
while ( ( ch = fgetc(input) ) != ',' ) {
parishMalloc[i] = ch;
i++;
}
parishMalloc[i] = '\0';

fscanf(input, "%d", &people);

while ( fgetc(input) != '\n' && !feof(input)) ;

//ENDREADLINE

foundAddress = list_search( listCore, countyMalloc, &position);

if ( foundAddress != NULL ) {
list_assign( listCore, position, &parishMalloc, people);
free(countyMalloc);
}
else {
parishList = createParish ( parishMalloc, people );
countyList = createCounty ( countyMalloc, people );
countyList->minusParish = parishList;
foundAddress = countyList;
if ( listCore->numberCounties == 0 ) list_insert( listCore, -1, countyList);
}

list_sort( listCore, position, foundAddress);

return input;
}


int main( int argc, const char *argv[] ) {

FILE *input;
FILE *output;
core *base;

if ( argc != 2 ) {
fprintf( stdout, "%s shuffle.csv\n", argv[0] );
exit(1);
}

if ( ( input = fopen( argv[1], "r") ) == NULL ) {
fprintf( stdout, "Not possible to open the file.\n");
exit(2);
}

if ( ( output = fopen ( "output.csv", "w") ) == NULL ) exit(3);

if ( ( base = (core *) malloc( sizeof(core) * 1) ) == NULL ) exit (4);

base->numberCounties = 0;
base->root = NULL;

while ( !feof(input) ) {
input = readlnVeriPlace( input, base );
fprintf( stdout, "%s, %s, %d\n", base->root->minusParish->parishName, base->root->countyName, base->root->minusParish->population);
}

return 0;
}
[/CODE]

[color=#b22222][b][u]Function Library[/u][/b][/color]

[CODE]
#include "lista.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int list_assign( core *l, int pos, char **str, int people)
{
int i = 0;
county *aux;

if (l == NULL || pos < 0)
return -1;

aux = l->root;

for (i = 0; i < pos && aux != NULL; i++)
aux = aux->next;

if (aux == NULL)
return -1;

aux->population += people;

if ( people < aux->minusParish->population ) {
aux->minusParish->population = people;
free(aux->minusParish->parishName);
aux->minusParish->parishName = *str;
} else free(*str);

return pos;
}


int list_insert( core *l, int pos, county *curr)
{
int i = 0;
county *temp;

if (l == NULL || pos < -1 || pos >= l->numberCounties) return -1;

temp = l->root;

if (curr == NULL) return -1;

l->numberCounties++;

if(pos == -1)
{
if (temp == NULL) l->root = curr;
else
{
while (temp->next != NULL) temp = temp->next;
temp->next = curr;
}

return l->numberCounties-1;
}

if (pos == 0)
{
curr->next = temp;
l->root = curr;
return pos;
}

for (i = 0; i < pos-1 && temp != NULL; i++) temp = temp->next;

curr->next = temp->next;
temp->next = curr;

return pos;
}


county* lista_removeToSort(core *l, int pos)
{
int i = 0;
county *prev, *curr;

if (l == NULL || pos < 0 || pos >= l->numberCounties) return NULL;

curr = l->root;

l->numberCounties--;

if(pos == 0)
{
l->root = curr->next;
curr->next = NULL;
return curr;
}

for( i = 0; i < pos && curr->next; i++)
{
prev = curr;
curr = curr->next;
}

prev->next = curr->next;

curr->next = NULL;
return curr;
}

county * list_search( core *l, char* str, int *pos)
{

int i = 0;
county *aux;

if( l == NULL ) return NULL;

for (aux = l->root; aux != NULL; aux = aux->next, i++)
{
if ( strcmp( aux->countyName, str) == 0) {
*pos = i;
return aux;
}
}

*pos = -1;
return NULL;
}

int list_sort( core *l, int posiVerifi, county *foundAddr)
{
county *ptr;
int i = 0;

if ( l == NULL ) return -1;
if ( l->root == NULL || l->numberCounties == 1) return 0;

if ( posiVerifi != -1 ) foundAddr = lista_removeToSort( l, posiVerifi);

for ( ptr = l->root; ptr != NULL; ptr = ptr->next, i++ ) {
if ( ptr->population < foundAddr->population ) {
list_insert( l, i, foundAddr);
}
}
list_insert( l, -1, foundAddr);

return 0;
}[/CODE]

[PatoLouco]

In the function list_sort, inside the 'for' ,if that situation verifies, it will insert your new struct in the 'i' position, after that you should put return 0;

If not it will put the same struct, in duplicate, on other position. Sry for my bad English.

[pinprick]

        for ( ptr = l->root; ptr != NULL; ptr = ptr->next, i++ ) {
                if ( ptr->population < foundAddr->population ) {
                        list_insert( l, i, foundAddr);
                        return 0;
                }
        }
[/CODE]

Well spotted :woot:, however it doesn't produce the correct output so there must be another bug somewhere :|.

Thanks a lot.

[simplezz]

I think there's a problem with your list insertions in function readlnVeriPlace:

if ( listCore->numberCounties == 0 ) list_insert( listCore, -1, countyList);

Unless I'm mistaken, your code will only insert the first county because afterwards listCore->numberCounties will be non-zero, therefore list_insert doesn't get executed again.

And personally, I would read a whole line at a time, then use strtok to parse it using ',' as a delimiter.

list_search is going to get expensive as well towards the end of the file.

[pinprick]

Nice, thanks for your help :rofl: . The sort function does insert. What it does is see if the county is in the list or not with the help of list_search, if it was there (in the list) it removesToSort ( connects the neighbours but does not free )and searches for the correct place and then inserts it there.

The problem was that after the first run, a new item could not be inserted because list_sort had a control statement that was absurd :blush: ,

 if ( l->root == NULL || l->numberCounties == 1) return 0;[/CODE]

So, nothing would ever be added because l->numberCounties would never increment.

:pinch: I removed that instruction

[CODE]if ( listCore->numberCounties == 0 ) list_insert( listCore, -1, countyList);[/CODE]

And replaced,

[CODE] if ( l->root == NULL || l->numberCounties == 1) return 0;[/CODE]

with:

[CODE]if ( l->numberCounties == 0 ) { list_insert( l, -1, foundAddr); return 0; }[/CODE]

[pinprick]

Thanks, I owe you one beer :D .

[simplezz]

Nice, thanks for your help :rofl: . The sort function does insert. What it does is see if the county is in the list or not with the help of list_search, if it was there (in the list) it removesToSort ( connects the neighbours but does not free )and searches for the correct place and then inserts it there.

The problem was that after the first run, a new item could not be inserted because list_sort had a control statement that was absurd :blush: ,

 if ( l->root == NULL || l->numberCounties == 1) return 0;[/CODE]

So, nothing would ever be added because l->numberCounties would never increment.

:pinch: I removed that instruction

[CODE]if ( listCore->numberCounties == 0 ) list_insert( listCore, -1, countyList);[/CODE]

And replaced,

[CODE] if ( l->root == NULL || l->numberCounties == 1) return 0;[/CODE]

with:

[CODE]if ( l->numberCounties == 0 ) { list_insert( l, -1, foundAddr); return 0; }[/CODE]

I see. I knew there was a problem with the insertion somewhere, because numberCounties was always 1 after the first insert in readlnVeriPlace.