Removing elements from an array of linked list

Hello there,

I've got the following structure:

Code:

---

struct s_no {
    char * word;
    struct s_no * next;
};

---

And then I declared an array of pointers:

Code:

---

struct s_no *t_test [100];
    for (oc = 0; oc < 100; oc++) {
        t_test[oc] = NULL;
}

---

It's a hashing table, so after that the program reads a wordlist and creates the table, where the hash value is the index of t_test and the words that gave that value will be on a linked list starting from that pointer index.

The problem is, I need the program to read a word from a file, calculate the hash to find the index it belongs, search the linked list starting in that index (if there's one) to check if the word is there and if it is, remove the word.

Everything is fine until I try to remove the node. I'm not sure about what to pass as reference or as value so all I get is a huge mess. I'd really appreciate if you guys could help me.

Thanks in advance.

Edit: And by the way, I did call malloc when creating the nodes and passing values. The nodes are just fine, the problem is to remove them.

You haven't actually said anything that will help anyone to solve your problem. You have a hashing function that returns the correct list, and is able to find the correct node in that list and now you need to know how to remove a node in a list?

Do you have a list_remove() function? Does your list_search() function return a value or a node reference?

Anyway when you have a reference to the node you want to remove, you need to link it to the next node. (I did this exact example just a few days ago here):

Code:

---

struct node *target = node; // node that should be removed
node = node->next;          // link to the next node
free(target);              // free the temporary pointer

---

If you can post relevant code of the remove part that would probably help.

Sorry, I'll post my remove function.

But basically, the program first receives a list of words. Then a function will give the value of the hash for each word. Another function will take that hash and try to put that word into the node t_test[hash]. If it's NULL, the first node will be created. If it's not NULL, a node will be created contaning that word and be inserted between the node t_test[hash] and t_test[hash]->next.

After that, the program needs to read another list of words and search for them in the table.

Here's my attempt to create the remove function:

Code:

---

void remove(FILE * file_rem, struct s_no * **v) {
    char line[40];
    int hash_p;


    struct s_no * s;
    struct s_no * p;


    FILE * result;
    result = fopen("new_table.txt", "w");


    while (!feof(file_rem)) {
        fgets(line, sizeof (line), file_rem);


        size_t ln = strlen(line) - 1;
        if (line[ln] == '\n') {
            line[strlen(line) - 2] = '\0';
        }


        hash_p = hash_A(line, 100);
   
        if (*v[hash_p] != NULL) {
            if (strcmp((*v[hash_p])->word, line) == 0) {
        p = *v[hash_p];
                *v[hash_p] = (*v[hash_p])->next;
                free(p);
            }
            if ((*v[hash_p])->next != NULL) {
                p = *v[hash_p];
                for (s = (*v[hash_p])->next; s != NULL; s = s->next) {
                    if (strcmp(s->word, line) == 0) {
                        p->next = s->next;
                        free(s);
                    }
                    //p = p->next;
                }
            }
        }
    }
    write_table_to_file(*v, 100, "new_table.txt");
    printf("\n=> New table written to the file new_table.txt.\n");
}

---

As you can see, it's a pretty big mess and I got lost. I know how to remove a node from a single linked list, but in this case with arrays I got really confused.

I appreciate any help.

What happens when you try to run it, can you compile it? You probably don't need the triple star argument in your function, two should be enough as far as I can tell.

No, I can't compile it. It gives me lots of errors after removing that star.

Code:

---

main.c:222: error: invalid operands to binary != (have 'struct s_no' and 'void *')main.c:223: error: invalid type argument of '->'
main.c:224: error: invalid type argument of '->'
main.c:225: error: incompatible types in assignment
main.c:226: error: invalid type argument of '->'
main.c:229: error: invalid type argument of '->'
main.c:230: error: incompatible types in assignment
main.c:231: error: invalid type argument of '->'
main.c:242: warning: passing argument 1 of 'write_table_to_file' from incompatible pointer type
main.c: In function 'main':
main.c:328: warning: passing argument 2 of 'remove' from incompatible pointer type

---

How should I call the remove function in this case?
I'm calling it like this:

Code:

---

remove(open_file(), &t_teste);

---

But I'm not sure about the reference, even though if I remove it this last warning isn't shown, but the other errors continue.

Did your code compile with 3 levels of indirection? If t_teste is an array of pointers to structs you should be able to call it without the ampersand. The indirection is not strictly necessary to fix, but it makes the code unnecessary complex, which you don't need when you are trying to figure out why it's not working.

Edit: Of course, if your code compiled with the 3 stars in place you could perhaps leave it there for now. But, what exactly doesn't work when the code compiles?

Ok, I changed the function to use v[] directly instead of the reference. It compiled ok, but I got a segmentation fault on this line:

Code:

---

(v[hash_p]->next != NULL)

---

I couldn't understand what I could be trying to access that is not allowed. I verified before that v[hash_p] is not NULL, so even if a list has only one element then v[hash_p]->next must be NULL, so what am I doing wrong?


I also tried with tripple stars, and got a segmentation fault on this line:

Code:

---

(strcmp((*v[hash_p])->word, line) == 0)

---

Is your array initialized to 0? Otherwise there may be junk at v[hash_p] which would make a test to !NULL true.

Code:

---

while (!feof(file_rem)) {

---

FAQ > Why it's bad to use feof() to control a loop - Cprogramming.com

Code:

---

size_t ln = strlen(line) - 1;
if (line[ln] == '\n') {
    line[strlen(line) - 2] = '\0';

---

You've already stored the length of the line in "ln", so no need to call strlen() a second time.
But the main problem is that your line length is probably wrong because strlen() returns the length of the string excluding the '\0', thus there's no need to subtract 1. And you want to set line[ln] to '\0' in case there is a newline because in your case you overwrite the last but one character of the string.

Code:

---

if ((*v[hash_p])->next != NULL) {
    p = *v[hash_p];
    for (s = (*v[hash_p])->next; s != NULL; s = s->next) {
        if (strcmp(s->word, line) == 0) {
            p->next = s->next;
            free(s);
        }
        //p = p->next;

---

You need to move forward p, why have you commented this line out?

Quote:

---

As you can see, it's a pretty big mess and I got lost. I know how to remove a node from a single linked list, but in this case with arrays I got really confused.

---

One thing which may help a lot is using descriptive variable names, e.g. instead of "p" use "previous_node" and instead of "s" use "current_node".
Basically, the logic is the same when you use an array of pointer. The only difference is that instead of a variable name like "head" or "list" for the list pointer, you use "v[hash_p]" (btw "v" is another bad name).

Bye, Andreas

Yes, each element of t_test is initialized to NULL, that's why I tested if it was NULL and to also check it had no words.

Code:

---

struct s_no * t_test [100];
    for (oc = 0; oc < 100; oc++) {
        t_test[oc] = NULL;
}

---

And after the first insertion, besides calling malloc for the node, I set t_test->prox to NULL;

I think you need to split up your functions into smaller pieces, so you can test each one separately to verify they work. (Unit testing)

Seeing that you can handle dynamic memory management, why don't you create a hash table and hash table entry types, and then the functions needed to manipulate them?

I like C99 flexible arrays (size determined at run time, must be allocated dynamically), so I would personally go with

Code:

---

struct hashentry {
    struct hashentry *next;
    unsigned long    hash;
    size_t            size;
    unsigned char    data[];
};

struct hashtable {
    unsigned long    entries;
    struct hashentry *entry[];
};

struct hashentry *hash_getline(FILE *const input);
struct hashentry *hash_string(const char *const string);
struct hashentry *hash_data(const void *const data, const size_t length);
struct hashentry *hash_free(struct hashentry *const hash); /* Always returns NULL */

struct hashtable *hashtable_create(const unsigned long entries);
int              hashtable_add(struct hashtable *const table, struct hashentry *const entry);
struct hashentry *hashtable_detach(struct hashtable *const table, const unsigned long hash, const void *const data, const size_t length);
struct hashtable *hashtable_destroy(struct hashtable *const table); /* Always returns NULL */

/* Notes: Bernstein hash, hash = (hash * 33UL) ^ ((unsigned long)(newchar)), is okay.
 *        Entry for hash h in table t is (t->entry[h % t->entries]).
 *        Store hashes unmodified, so you can rehash the table: reallocate it, then relink entries;
 *        no need to recalculate any hashes from data. (h->hash do not change.)
 *        Two hash entries, h1 and h2, are the same if and only if
 *            (h1->size == h2->size &&
 *            h1->hash == h2->hash &&
 *            !memcmp(h1->data, h2->data, h1->size))
 *        The hash entries are suitable for binary data. For ease of use, I recommend always
 *        reserving room and appending a '\0' after the hashed data, i.e. h->data[h->size] = '\0'
*/

---

A test program that does what you stated should take about 300 lines. I wrote a test implementation. The hash_getline() alone took me 100 lines, as it skips leading and trailing whitespace, calculates the Bernstein hash inline (as it reads the input), and accepts any newline convention. The other functions took about 100 lines altogether. The last 100 lines were in main(), reading the word list from one file to a hash table, removing entries based on another file, plus verbose output, command line parameter checking (including help/usage if none), and so on.

But this is just my personal preference; pick any approach (structures) you like; just write and test the hash table and hash entry functions first.

Andreas, just saw your reply, thank you for the tip about feof(), I didn't know that and just corrected it.

Nominal Animal, I never thought about that approach. Thank you, I'll try your suggestion.

In the meantime, I've tried another way to search and remove the elements:

Code:

---

s = v[hash_p];
while (s != NULL) {
    if (strcmp(s->word, line) == 0) {
        p = s;
        s = s->next;
        free(p); p = NULL;
    }
    if (s != NULL) s = s->next;
    else break;
}

---

Is this correct? I got now a segmentation fault when try to print some elements after removing. Do you have any clues?

Thanks a lot!

You should post your current code.

Have you already used a debugger to break before the loop, singlestepping through it and printing all the values? If not I highly recommend it.

Bye, Andreas

Code:

---

s = v[hash_p];
while (s != NULL) {
    if (strcmp(s->word, line) == 0) {
        p = s;
        s = s->next;
        free(p); p = NULL;
    }
    if (s != NULL) s = s->next;
    else break;
}

---

Just noticed that doesn't work.
If the wanted word is not at the beginning of the list, you loose the connection between the node before the word and the node after the word.
If the wanted word is at the beginning you loose the whole list.

Bye, Andreas