removing an item from linked list...

Go To Last Post
24 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have this function that processes through items of my linked list.

function1(void)
{
   listItem = MyList->HeadPtr;
   while(listItem != NULL)
   {
       switch(listItem->state)
       {
           case 1:
               //do something
           case 2:
               //call another function which may or may
               //not have removed the listItem from my list
               //not just remove but also frees the listItem
           default:
               break;
       }
       listItem = listItem->Next;
   }
}

you can see pretty soon I can run into problem. How do I deal with freeing and removing and at the same time coming out of the switch cases and still continue with my while loop of next item?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Make the list doubly linked - then it's easy to access "before" and "after" and join them together.

Read this:

https://www.avrfreaks.net/index.p...

where I gave an example of double links. (my last post with "content")

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What does "removed the listItem from my list" mean? Did that function already correct the next pointer of the parent element? Then the only thing you need to do is to save the next pointer of the current element prior:

function1(void)
{
   listItem = MyList->HeadPtr;
   while(listItem != NULL)
   {
       savedNext = listItem->Next;
       switch(listItem->state)
       {
           case 1:
               //do something
           case 2:
               //call another function which may or may
               //not have removed the listItem from my list
               //not just remove but also frees the listItem
           default:
               break;
       }
       listItem = savedNext;
   }
} 

Stefan Ernst

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson mine was a doubly linked list already :)
sternst man genius! I was already doing something very similar to that like saving the next pointer as my child functions were freeing the listItems. so I was saving the next point and returning it from the child function to the mother function1 (shown above). lol ... I am getting old!

Oh I have one more question while I am at it... after I free the item in my child function...is it a good idea to set the listItem = NULL to be safe? I read somewhere its always good to do free(item) and then item = NULL so we dont do double freeing by mistake.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

after I free the item in my child function...is it a good idea to set the listItem = NULL to be safe?

Yes - it doesn't help much on AVRs (unless you employ assert() but on chips with memory protection a write through 0 will almost always cause an exception that is trapped.
Quote:

I read somewhere its always good to do free(item) and then item = NULL so we dont do double freeing by mistake.

Could have been me here - I've advised it several times.

Really when using malloc()/free() all pointers should be tested before use either "if (ptr)" or "assert(ptr != 0)", not only to catch use of an un-malloc'd pointer but also to catch the occasion when memory runs out and malloc() returns 0 anyway (more likely on a 1K SRAM AVR than a 4GB Pentium ;-))

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I thought assert() does not work in runtime but is rather a preprocessing macro? How does it work? I would have thought the micro will go crazy if there is a write through 0?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I thought assert() does not work in runtime but is rather a preprocessing macro?

Then you are wrong. It's a run time check. basically:

if (!condition) {
  assert_always();
}

assert_always() is often implemented to output __FILE__ and __LINE__ to UART (possibly LCD).

For avr-gcc see assert.h which uses:

#  if defined(NDEBUG)
#    define assert(e)	((void)0)
#  else /* !NDEBUG */
#    if defined(__ASSERT_USE_STDERR)
#      define assert(e)	((e) ? (void)0 : \
                         __assert(__func__, __FILE__, __LINE__, #e))
#    else /* !__ASSERT_USE_STDERR */
#      define assert(e)	((e) ? (void)0 : abort())
#    endif /* __ASSERT_USE_STDERR */
#  endif /* NDEBUG */


extern void __assert(const char *__func, const char *__file,
		     int __lineno, const char *__sexp);


So it outputs to stderr which could be connected using FDEV_SETUP_STREAM()

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Oh I have one more question while I am at it... after I free the item in my child function...is it a good idea to set the listItem = NULL to be safe? I read somewhere its always good to do free(item) and then item = NULL so we dont do double freeing by mistake.
But in your case the freeing is being done in the function being called, so setting the value to NULL there will do nothing for the calling program. I would have the called function return the value of the pointer back so you could do this:

case 2:
        listItem = functionThatCouldDeleteTheItem(listItem);

Of course anything after the switch statement that needs to access listItem will need to check for NULL.

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
Quote:

I thought assert() does not work in runtime but is rather a preprocessing macro?

Then you are wrong. It's a run time check. basically:

if (!condition) {
  assert_always();
}

assert_always() is often implemented to output __FILE__ and __LINE__ to UART (possibly LCD).

For avr-gcc see assert.h which uses:

#  if defined(NDEBUG)
#    define assert(e)	((void)0)
#  else /* !NDEBUG */
#    if defined(__ASSERT_USE_STDERR)
#      define assert(e)	((e) ? (void)0 : \
                         __assert(__func__, __FILE__, __LINE__, #e))
#    else /* !__ASSERT_USE_STDERR */
#      define assert(e)	((e) ? (void)0 : abort())
#    endif /* __ASSERT_USE_STDERR */
#  endif /* NDEBUG */


extern void __assert(const char *__func, const char *__file,
		     int __lineno, const char *__sexp);


So it outputs to stderr which could be connected using FDEV_SETUP_STREAM()

thanks for that...so in a small micro environment how is this handy? if the variable wasnt what it should be,. the micro will stall anyway? the assert too will stall the micro? will it not? and what is this FDEV_SETUP_STREAM() and how do I set it?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Koshchi wrote:
But in your case the freeing is being done in the function being called, so setting the value to NULL there will do nothing for the calling program. I would have the called function return the value of the pointer back so you could do this:

case 2:
        listItem = functionThatCouldDeleteTheItem(listItem);

Of course anything after the switch statement that needs to access listItem will need to check for NULL.

I tried that option earlier. But since the child function updates the linked list chain before freeing the middle item, there is no need return the next item if I just save the next item before calling the child function (as recommended in previous posts).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That wasn't the point of returning a value. The value returned would be the address of the list item sent in if the item wasn't deleted, or NULL if the item was. In your current code, if you put something between the switch and the "listItem = savedNext;" that accesses listItem, you will be accessing something that has been deleted. With the return value, you can now check for NULL to see if the item was really deleted.

You could also change your code to be:

   while(listItem != NULL)
   {
       currentItem = listItem;
       listItem = listItem->Next;
       // Use currentItem from here on out
       switch(currentItem->state)
       {

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Koshchi wrote:
That wasn't the point of returning a value. The value returned would be the address of the list item sent in if the item wasn't deleted, or NULL if the item was. In your current code, if you put something between the switch and the "listItem = savedNext;" that accesses listItem, you will be accessing something that has been deleted. With the return value, you can now check for NULL to see if the item was really deleted.

You could also change your code to be:

   while(listItem != NULL)
   {
       currentItem = listItem;
       listItem = listItem->Next;
       // Use currentItem from here on out
       switch(currentItem->state)
       {

yes which becomes then the same as sternst's post above :)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

thanks for that...so in a small micro environment how is this handy? if the variable wasnt what it should be,. the micro will stall anyway? the assert too will stall the micro? will it not? and what is this FDEV_SETUP_STREAM() and how do I set it?

See the source of assert() here:

http://svn.savannah.nongnu.org/v...

it ends with abort():

http://svn.savannah.nongnu.org/v...

IOW it outputs the message to stderr about which file and which line and the test that failed then it stops in that for(;;) loop.

As for FDEV_SETUP_STREAM() - that's the standard way to link printf() to a UART or LCD output routine. The example in the manual shows you how it's done:

http://www.nongnu.org/avr-libc/u...

(in that they show stdout directed to the UART and stderr directed to the LCD - as assert() outputs to stderr that means it will come out on the LCD)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have another issue...
I have malloced some data struct and then do a free on it. immediately after that I set it to null. But to start with I had another pointer pointing to this just freed pointer.

anotherSkt = skt;
free(skt);
skt = NULL;

I have this function on top level which needs to know if skt has been freed and NULLed. It does this by checking if anotherSkt == NULL. But it seems even though I null the skt pointer, my anotherSkt pointer never becomes NULL?? :(

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I null the skt pointer, my anotherSkt pointer never becomes NULL??

Why on earth do you think it would? Forget pointers for a minute:

int a,b;
a = 7;
b = a;
a = 0;

Do you really expect 'b' to magically be set to 0 by the above?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hhm.. this is a problem then.
i have on application level a data structure variable that points to a socket in the list of sockets. this list of socket is periodically treated by the socket level which is bellow the application level.

my application needs to know if the socket was closed, freed and nulled. how can it know if the socket pointer in the application level pointing to the socket in the socket level was freed? As I said so far, my socket level frees and nulls the socket from its list....but looks like the application level pointer still has no clue of that happening.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Surely you just do:

anotherSkt = skt;
free(skt);
skt = NULL; 
anotherSkt = NULL;

And equally set any other "synonyms" for this pointer to NULL at the same time. Either that or make 'another' a pointer to pointer that holds a pointer to 'skt'. That is something like

struct_type *skt, **another;
another = &skt
free(skt);
skt = NULL;

At the end of this *another=NULL too.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think thats what I was looking for! the thing is from socket implementation level it doesnt have access to the application level pointer. so my socket API cant free anotherSkt after freeing the skt variable as it doesnt have access to it.
Ok let me try this pointer to pointer thing now!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hhm.. this does not seem to be working... :(
is the following correct?

Socket *skt, **applSkt;
skt->CallbackFunc(&skt);  //function calling from socket level to application level.

void CallbackFunc(Socket **skt)
{
   applSocket = skt;
}

having trouble with this assignment of pointers..

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This compiles without errors (though I haven't actually checked operation):

#include 

typedef struct skt {
	int n;
	char c;
	void (*CallbackFunc) (struct skt **);
} Socket;

Socket *skt, **applSocket;

void MyCallbackFunc(Socket **p_skt)
{
   applSocket = p_skt;
} 

int main (void)
{
	Socket mysock;
	mysock.CallbackFunc = MyCallbackFunc;

	skt = &mysock;

	skt->CallbackFunc(&skt);  //function calling from socket level to application level.
	while(1);
} 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yup, that appeared to work (slightly modified to set the other fields in "mysock" to make it more recognizable)...

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

thanks for that clawson.... i changed my code to have pointer to pointers now.... however it doesnt work :(
where I used to have before

send(skt, buf, len, 0);

I now have send(*(ftp->CmdSocket), buf, len, 0);

where ftp->CmdSocket is defined as struct Socket ** inside ftp struct. And the call back function calls and assigns ftp->CmdSocket = &skt once the socket is connected from the socket layer (bellow application layer).

It seems the code runs up to the username entry in ftp session...then it gets stuck? bad pointer? Before conversion of this pointer to pointer everything was working :(

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Can't really help with something so involved - all I can suggest is that you follow the call in your debugger and make sure the pointers are pointing at the right things and that pointers to pointers are pointing to pointers that are pointing at the right thing. (phew!).

Just wait until you get to "type ***foo;" ;-) (could easily happen if you have an array of these structs in fact).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think I know why it isnt working...
At the socket level I have a function which goes through the socket list each items and calls a sub function which then does things to the item and then this sub function does the application level callback assignment.

subFunction(Socket *skt)
{
   skt->Callback(&skt);
}

and then in the applicatoin level:

appFunctionCallback(Socket **skt)
{
   appSocket = skt;
}

Problem is that now the appSocket is pointing to the locally defined skt variables address which was locally defined in the subFunction and not the original socket pointer from the socket list item.

in order for this to work I need to redefine the subfunction such that it actually transfers the original socket pointer like this:

subFunction(Socket **skt)
{
   skt->Callback(skt);
}

But this gets messy with all these sub functions trying to pass on the pointer to the original main pointer item from the socket list....

I wonder if I should scrap the idea all together. But then how can the socket level let the application level know that the socket on the other end was closed by the remote machine. :(