CODEWITHSUNDEEP
cpointersdictionarystruct
Alex
Alex

Reputation: 101

Inserting in an array struct(Dictionary) in C

So created a Dictionary that had a key and an element. It is ordered by the Key field and the space allocated to the Dictionary must always be equal to the number of elements that it contains. So this is what i did:

//Creating a Dictionary structure
    typedef struct dict{
        int elem;
        int key;
    }Dictionary;

int main(){
    Dictionary * d = NULL;
    int dim = 0;

    insert(&d, 5, 3, &dim);
    insert(&d, 10, 2, &dim);
    insert(&d, 6, 1, &dim);
    //insert(&d, 9, 6, &dim);
    //insert(&d, 55, 2, &dim);
    //insert(&d, 11, 5, &dim);
    return 0;
}


void insert(Dictionary **d, int elem, int key, int *dim){
    (*d) =(Dictionary *)realloc((*d),(*dim)++);//adding space for another element
    int i = 0, j = 0;
    while(i < (*dim) && (*d)[i].key < key)//searching for the corect position to insert 
        i++;

    //sliding all the lements to the right
    for(j = (*dim); j > i; j--){
        (*d)[j] = (*d)[j - 1];
    }

    //iserting the element in the correct position 
    (*d)[i].elem = elem;
    (*d)[i].key = key;
}

So the code works as it should for the first three elements that insert the problem is that whenerver i try to insert the forth i get a stall like an infinte loop and five or more inserts crashes the program. So could someone explain to me what i am missing or what i am doing wrong ?

Upvotes: 1

Views: 48

Answers (1)

Jean-Fran&#231;ois Fabre
Jean-Fran&#231;ois Fabre

Reputation: 140168

with (*d) =(Dictionary *)realloc((*d),(*dim)++); you don't allocate enough memory for the next elements.

After a while you end up corrupt some unallocated/unowned memory and it crashes.

You have to take into account the size of your struct (which must be incremented before calling realloc BTW, another fatal mistake). Since I got tricked by that, I don't propose pre-incrementation, but 2 lines:

(*dim)++;
(*d) = realloc((*d),sizeof(Dictionary)*(*dim));

notes:

  • you never have to cast the output of realloc, malloc, calloc
  • reallocating at eah step is easy but not optimal. You should forward allocate more than 1 slot, and reallocate only when your reserve is exhausted. That would avoid calling realloc too often and/or moving the memory around when the block is too small too often.

Upvotes: 2

Related Questions