05 May, 2009, Rojan QDel wrote in the 1st comment:
Votes: 0
I am trying to create a method to pop an object to the front of its list and leave the rest of the list intact.
Here is my method:
//Links an object to the FRONT of the list
#define LINK_FRONT(link, first, last, next, prev) \
do \
{ \
if ((link) == (last)) \
(last) = (link)->prev; \
(link)->prev = (last); \
(link)->prev->next = (link)->next; \
if ((link)->next) \
(link)->next->prev = (link)->prev; \
(link)->next = (first); \
(first) = (link); \
} while(0)


I call this LINK_FRONT(target, ship->starsystem->first_ship, ship->starsystem->last_ship, next_in_starsystem, prev_in_starsystem);
and then the mud freezes up, but GDB acts like it is fine. Anyone know what might be wrong with my method?
05 May, 2009, David Haley wrote in the 2nd comment:
Votes: 0
I would just use existing routines and unlink it normally and then relink it at the beginning.

Line 7 above looks a little fishy, unless the linked list is circular.

Also, using proper indenting would help read the code snippet to see what exactly is happening.
06 May, 2009, Remcon wrote in the 3rd comment:
Votes: 0
try this one out
#define LINK_FRONT(link, first, last, next, prev) \
do \
{ \
(link)->prev = NULL; \
(link)->next = NULL; \
if( (first) ) \
{ \
(link)->next = (first); \
(first)->prev = (link); \
(first) = (link); \
} \
else \
{ \
(first) = (link); \
(last) = (link); \
} \
} while(0)

Haven't tested it, but it should work for what your wanting.
06 May, 2009, ghasatta wrote in the 4th comment:
Votes: 0
Quote
and then the mud freezes up, but GDB acts like it is fine. Anyone know what might be wrong with my method?
That's the classic symptom of an infinite loop. And lo, it turns out you have a loop with absolutely no break/return criteria. I don't think this should be a loop at all.

Quote
I am trying to create a method to pop an object to the front of its list and leave the rest of the list intact.
Do you want to talk a little bit more about why you are trying to create this method? What problem are you trying to solve?

In addition to David Haley's suggestions I think you should also make this method an actual function. Then you will be able to step through it in gdb. I don't think that inlining it really is necessary for any performance reasons, unless you have some sort of super special mud that has gazillions of elements in its linked lists and is running on 1970s hardware.

HTH.
06 May, 2009, David Haley wrote in the 5th comment:
Votes: 0
ghasatta said:
That's the classic symptom of an infinite loop. And lo, it turns out you have a loop with absolutely no break/return criteria. I don't think this should be a loop at all.

Well, it's a do { … } while(0) loop, meaning that it will run exactly once, and then halt upon testing that 0 is indeed false.
06 May, 2009, ghasatta wrote in the 6th comment:
Votes: 0
Indeed. I read that too fast. I still think the loop needs to go away.
06 May, 2009, David Haley wrote in the 7th comment:
Votes: 0
It's a very common idiom to have a do { … } while(0) loop in a macro, because it not only creates a new scope inside the macro (which is useful for functional reasons), but also it is a statement that can be terminated by a semi-colon (which is aesthetically pleasing). So, the macro itself can be terminated by a semi-colon, meaning that it looks like any other statement. This is particularly important when you have a compiler that complains about empty statements or incorrect semi-colons.
06 May, 2009, Rojan QDel wrote in the 8th comment:
Votes: 0
Remcon, your fix doesn't preserve the order of the list (making link->prev point to link->next and vice versa)
06 May, 2009, Sharmair wrote in the 9th comment:
Votes: 0
That is definitely not right (I did a couple test cases and came up with real messed up lists - one just
lost a link, but the other test, a much more common case, created some nasty loops in the list that
would probably make lock you in an endless loop if you tried to walk the list). I am assuming by your
wording that you are removing the link, and moving it to the head of the forward list. This should
work for you:
#define LINK_FRONT(link, first, last, next, prev)\
do{ \
if(!(link)->prev) \
(first) = (link)->next; \
else \
(link)->prev->next = (link)->next; \
if(!(link)->next) \
(last) = (link)->prev; \
else \
(link)->next->prev = (link)->prev; \
if(!(last)) \
(last) = (link); \
else \
(first)->prev = (link); \
(link)->prev = NULL; \
(link)->next = (first); \
(first) = (link); \
}while(0)

You could also use this if your code has a LINK and UNLINK macro:
#define LINK_FRONT(link, first, last, next, prev) \
do{ \
UNLINK((link), (first), (last), (next), (prev)); \
LINK((link), (last), (first), (prev), (next)); \
}while(0)

In fact, the code I gave to start is basically just this expanded from the SMAUG codebase.
Notice in this case the LINK is called with last/first and prev/next reversed. Being we are
using double linked lists, the stock LINK puts the new link at the tail of the forward list
and the head of the reverse list, so just flipping the data you give the macro will put the
link at the head of the forward list and tail of the reverse list.

After giving it a bit more thought, I was able to optimize it a bit:
#define LINK_FRONT(link, first, last, next, prev)\
do{ \
if((first) != (link)){ \
(link)->prev->next = (link)->next; \
if(!(link)->next) \
(last) = (link)->prev; \
else \
(link)->next->prev = (link)->prev; \
(first)->prev = (link); \
(link)->prev = NULL; \
(link)->next = (first); \
(first) = (link); \
}\
}while(0)
06 May, 2009, Rojan QDel wrote in the 10th comment:
Votes: 0
I'll try your optimized version and see if it works. Thanks.
07 May, 2009, Rojan QDel wrote in the 11th comment:
Votes: 0
Strange, it still lags out like its in an infinite loop…
07 May, 2009, Rojan QDel wrote in the 12th comment:
Votes: 0
Weird, I turned it into a normal function and it seems to work fine…
//Links an object to the FRONT of the list
void link_front(SHIP_DATA *link, SHIP_DATA *first, SHIP_DATA *last)
{

if(first != link){
link->prev_in_starsystem->next_in_starsystem = link->next_in_starsystem;
if(!link->next_in_starsystem)
last = link->prev_in_starsystem;
else
link->next_in_starsystem->prev_in_starsystem = link->prev_in_starsystem;
first->prev_in_starsystem = link;
link->prev_in_starsystem = NULL;
link->next_in_starsystem = first;
first = link;
}
return;
}
07 May, 2009, David Haley wrote in the 13th comment:
Votes: 0
Turning it into a function completely changes the semantics. In particular, you are no longer editing the variables passed in: you're just changing the pointers local to link_front.

It doesn't really make a lot of sense for it to go into an infinite loop without gdb, but to work just fine under gdb…
07 May, 2009, Rojan QDel wrote in the 14th comment:
Votes: 0
I know, I was just testing to make sure there were no errors with the algorithm. I think I figured out why its going in an infinite loop, and the reason wasn't in his code. Got it working now.
0.0/14