deleting array elements

[asilter]

let's say we have a unsigned char pointer with allocated memory of 1 million bytes. Could you give a little code sample which shows how to eliminate first 1000 bytes? the little similar situation is like below:

unsigned char array:
12,34,67,99,215,250,123,67

i want to make it:
215,250,123,67

I want to see the most efficient way to do this with no redundant memory and no memory leak or corruptions. do i have to use memcpy, if so i think it is not so efficient.

thank you.

[Hamrick]

The fastest way is to shift the pointer. If your array is a pointer made by malloc it's really easy.

p += 1000;

Be sure to shift it back before you free the memory though, or you'll get an exception. ;)

If your array is a real array then it's still easy but you have to make a new pointer into the array and use that from then on.

unsigned char *p = &array[1000];

Or you can combine the two so you don't have to remember to shift the main pointer back before freeing the memory.

unsigned char *p2 = p + 1000;

If you want to physically trim bytes from the front of the array, it's going to be a _lot_ slower because you have to shift all of the cells from the end of the trim to the left so you fill in the hole and then realloc the memory to remove the excess bytes.

[TkTkorrovi]

So you want a somewhat dynamic array. For really dynamic array you should implement a linked list, which is not very difficult either, but you must be careful because mistakes in implementing it can easily cause a memory leak. But it depends, how are you going to use your array. If you want to use it for example for fifo buffer, it's much easier to implement it with a normal static array, but of course don't forget to always check the array boundary. If you only need to delete elements from the beginning, you may consider writing array in reverse, which is not difficult, but is somewhat easier and more logical to handle. But if you may need to delete anywhere in the array, then again it's important how are you going to use it. Is the order of the elements important or not, how much your array is expected to grow, how much it would be changed. Based on that, in some cases, especially when the order of the elements is not important, you may just leave some empty places where you delete, and add new values there when necessary, this is also not difficult to implement, and has been used for example even in the indexes of certain databases. But of course when everything is expected to change too much, and has to be fast at that, you may consider using a linked list, though there would rarely be a need for that, especially considering that a lot of memory is available today, and we don't so much have to care about efficient use of it.

Say that we go through the array element by element. Then the trick is to use two arrays, one forward and one reverse, and these arrays can be static. Every time we go forward, we write one element from the end of the reverse array, to the end of the forward array, vice versa if we move back. Then, every step we can delete or add as much information as we want, to the location where we are at the moment.

[asilter]

unsigned char *p2 = p + 1000;

in this way, freeing p will cause freeing p2. i must free the memory of 1000 bytes after assigning to p2. i do not want any memory leaks.

[Hamrick]

i must free the memory of 1000 bytes after assigning to p2.

Then you can't do it efficiently. You _have_ to shift everything in the array to overwrite the 1000 bytes and then realloc the array so that it's 1000 bytes smaller. If you require the 1000 bytes to be freed, you can't make it any faster. Sorry. :(

i do not want any memory leaks.

You keep saying that, but there aren't any. :) And there won't be unless you forget to free something. Just because you don't free the 1000 bytes _right now_ doesn't mean it doesn't get freed later when you free the rest of the array. It does. There's no memory leak when you free p. p2 is just a reference into the allocated memory, it's not the controlling reference for the memory it points to...

[asilter]

So you want a somewhat dynamic array. For really dynamic array you should implement a linked list, which is not very difficult either, but you must be careful because mistakes in implementing it can easily cause a memory leak. But it depends, how are you going to use your array. If you want to use it for example for fifo buffer, it's much easier to implement it with a normal static array, but of course don't forget to always check the array boundary. If you only need to delete elements from the beginning, you may consider writing array in reverse, which is not difficult, but is somewhat easier and more logical to handle. But if you may need to delete anywhere in the array, then again it's important how are you going to use it. Is the order of the elements important or not, how much your array is expected to grow, how much it would be changed. Based on that, in some cases, especially when the order of the elements is not important, you may just leave some empty places where you delete, and add new values there when necessary, this is also not difficult to implement, and has been used for example even in the indexes of certain databases. But of course when everything is expected to change too much, and has to be fast at that, you may consider using a linked list, though there would rarely be a need for that, especially considering that a lot of memory is available today, and we don't so much have to care about efficient use of it.

Say that we go through the array element by element. Then the trick is to use two arrays, one forward and one reverse, and these arrays can be static. Every time we go forward, we write one element from the end of the reverse array, to the end of the forward array, vice versa if we move back. Then, every step we can delete or add as much information as we want, to the location where we are at the moment.

Sometimes that is much more bigger than 1000 bytes and memcpy slows my program :) It's a very little delay but irritating. I wonder if I find a better solution.

I need the erase first 1000, because i'm calling this function from a loop, i do not want to query the same 1000 bytes message from the front of the array in the next calling.

function abc(unsigned char ** ucBinary, unsigned char ** ucB1000, int nSizeOfArray)
{
             int i=0;
             *ucB1000 = malloc(1000);
             unsigned char * ucDummy = *ucBinary;
             unsigned char * ucNew = NULL;
             for(i=0; i<nSizeOfArray; i++)
             {
                  if(ucDummy[i] == 'B' && ucDummy[i+1] == 'U' && ucDummy[i+2] == 'F' && ucDummy[i+3] == 'R')
                  {
                          memcpy(*ucB1000,ucDummy,1000);
                          ucNew = malloc(nSizeOfArray-1000);
                          memcpy(ucNew,ucDummy+1000,nSizeOfArray-1000);
                          free(*ucBinary);
                          *ucBinary = ucNew;
 
                  }
             }
 
}

It has just come to my mind keeping index without memcpy and free in the function. I will try :). Send the starting index to function to look every time. And when the loop finishes, free the ucBinary outside.

Thanx.

[asilter]

p2 is just a reference into the allocated memory, it's not the controlling reference for the memory it points to...

if I;

free(p2);

what happens? don't I get segmentation fault when ;

printf("%d\n",p[1001]);

[Hamrick]

if I free(p2); what happens?

You get an exception because p2 shouldn't be freed, period. p2 doesn't point to the memory that was returned by malloc; p does. When you want to free, you free p, not p2 or p3, or any other p's that you create that point to a different address from p.

What you're doing with this is ignoring the first 1000 bytes by using p2 to point to the 1001st byte and then using p2 _exclusively_ as if it were p. Then when you're done and want to get rid of the entire array, you free p because it points to the address that malloc returned. When you use p2 as if it were p, the example looks like this and you don't _have_ to free the 1000 bytes until you want to free everything.

unsigned char p2 = p + 1000;

/* Use p2. It points to the array without the first 1000 bytes */
printf("%d\n",p2[0]);

/* All done, free the entire array including the first 1000 bytes */
free( p );

This is a trick. You pretend to remove the 1000 bytes by using a slice of the array instead of the entire array. p2 represents the start of the slice; think of it as a virtual array. What this does is save you the cost of physically removing bytes from the array. You don't have to copy anything or reallocate memory. All you have to do is pretend that p2 is the whole array, and then when you want to free the memory for the array, free p instead.

[shikeb]

What about the data, if we free p ??

Regards,
Shikeb Ali

[TkTkorrovi]

I would say you either use static arrays, which you of course also can allocate and free in the end, as you have plenty of memory, 1000 bytes and even 10 000 bytes is just nothing, or you use a linked list. But something in between, like reallocating the array, is not a good and clear solution, and may cause additional problems. But concerning speed, linked list is not even so much better than using the forward and reverse array, as i said, because you must still go through the linked list for finding an element. To make it faster, you can of course use a binary tree, but you should decide whether you need so much speed that it's worth to make things that complicated. Both singly linked and doubly linked lists and also hash tables are btw also implemented in glib, which is a part of GTK. It may be worth to use them if there is a need, because they eliminate the risk of any mistake in implementing such things just in c.

[shikeb]

one more question apart from the previous :)
we have lots of hashing techniques, which one is better for searching purpose ??

[TkTkorrovi]

Maybe binary search, it's the most simple, when the time is not so much important, and when the arrays are static... Just keep things in order...

[IcantC]

If you have a C structure i.e like this:

typedef struct                    
{
    int i;
    char* string;
} myStructure;

and you have an array of that structure's elements:

myStructure myArray [100];

you can delete the element you want (by index) with this simple loop

while (index <= nmbOfElements-1)
{
    myArray[index] = myArray[index+1];
    index++;
}
nmbOfElements--;

where index is the index of element that you want to delete ( be carefull with +-1 )
and nmbOfElements is the number of the elements in myArray ( not sizeof(myArray) )

[Narue]

Thanks for the post, IcantC, but take note that this thread is four years old. Perhaps your expertise would be better spent on current threads? :)

[IcantC]

Thanks for the post, IcantC, but take note that this thread is four years old. Perhaps your expertise would be better spent on current threads? :)

Yes, i figured it out :) I have just read the "Read before post" thing after my 1st post.
I am new here.
It's just that I spent some time solving this problem by myself and the topic describes my problem perfectly. Since this thread gives no answer to my question, I thought it would be helpful for others.