How to delete structure entries in C

Question

From a list of structures how can we delete a few of them. After deleting the structure there should not be any empty space left behind.

The following code was tried to achieve the task, but it didn't work.

   struct symtab *sp;
   for(sp = symtab; sp < &symtab[NSYMS]; sp++)
       if(sp->scope == scope) // delete
       {
           sp = sp+1;

       }

Answer 1

The best solution for this is to use linked list containing the structures. As mentioned above this is very in-efficient doing with arrays, as you have to move the data if it is not deleted at the end.

Answer 2

You cannot do that with C-style arrays(*). Best is to implement it as a linked list, can be any of the single- or double-linked.

(*) If you must use arrays, you can do a memmove from the next element to the element you wish to delete. However, you must also update the value of NSYMS in that case, which, it would seem from it being a #define, impossible.

Answer 3

You could go backwards through the array. Forwards or backwards, though, you will incur an increasing penalty for deleting an element at the beginning of the list in terms of amount of memory that must be moved. For this reason deleting entries at the end of the array first could slightly optimise performance.

struct symtab *sp;
struct symtab *endp; // end of array pointer

endp = symtab + NSYMS; 
for ( sp = symtab + NSYMS - 1; sp >= symtab; sp-- ) {
    if ( sp->scope = scope ) {
        int numelems = endp - (sp + 1);
        if ( numelems > 0 ) {
            memmove( sp, sp + 1, numelems );
            endp--; // adjust end of array pointer
        }
    }
}

Answer 4

You could use memmove():

//pseudocode, not tested
struct symtab* end = &symtab[NSYMS];
for(sp = symtab; sp < end; sp++) {
    if(sp->scope == scope) {
        memmove( sp, sp + 1, (end - sp) * sizeof(struct symtab);
        sp++;
        end--;
    }
}            

note that end can be changed since the array could become "shorter". Other code that works with that array must access the shortened region only.

Answer 5

There's a few options:

• Continue to use a fixed size array, but use a sentinel value (eg. -1) for the key field, so you know which entries are unused. When you need to add an entry, search for the next unused slot. This still suffers from the limitation of having a fixed size array.

• Use memmove as mentioned in other answers. This is not very efficient.

• Use a linked list instead of a fixed array, then you can easily (and cheaply) delete entries, as well as add.

Basically, unless you are writing code for some embedded system that has severe memory constraints, there is probably no good reason to put an arbitrary upper limit on the array. Other structures (such as a linked list) can be easily added to or deleted from, and there's loads of libraries around that provide such containers.

And after all that, are you sure you don't want a hash table (or dictionary) if you're managing a symbol table?