When linked lists attack

ID:30141
 
Apr 30 2007, 12:22 pm

There's an old BYOND bug in which sometimes system text (like a crash or pager message) would print in the text output and the font would change. Another issue, possibly related, had to do with margins not resetting properly at times. I don't know if they're the same bug, but I think I may have found the first one, and it's ancient. It all has to do with linked lists. BYOND uses linked lists all over the place, and one of those uses is to keep track of stylesheets it has parsed. To properly apply a stylesheet, it has to clear out all the old style rules first.

void StyleParser::ClipRules(int origin) {
        StyleRule *r = ruleL;
        StyleRule **rp = &ruleL;

        while(r) {
                if(r->origin == origin) {
                        *rp = r->next;
                        r->next = NULL;
                        delete r;
                        if(!*rp) break;
                        r = (*rp)->next;
                }
                else {
                        rp = &r->next;
                        r = r->next;
                }
        }
}

The error occurs on only one line, and I'll give you this hint: When all of the rules needed to be removed, sometimes they would be fully removed, sometimes not. (I found it because in one case it would alternate between working fully and working partially.) So, who wants to guess which line had to be changed, and how?

Apr 30 2007, 12:27 pm
Could it be deleting a pointer and reassigning it?
Apr 30 2007, 12:27 pm
StyleRule **rp = &ruleL;

Is it this?

should it be

StyleRule **rp = ruleL;?

Probably not, but I'm not great with pointers and if I could remember what the ** did in this case I think I might could find the error. Does it make an array of pointers?
Apr 30 2007, 12:28 pm
KirbyAllStar wrote:
StyleRule **rp = &ruleL;

Is it this?

should it be

StyleRule **rp = ruleL;?

Probably not, but I'm not great with pointers and if I could remember what the ** did in this case I think I might could find the error. Does it make an array of pointers?

** is a pointer to a pointer. You need to get the address.
Apr 30 2007, 12:35 pm
Oh ok, well now I'm just guessing...

if(!*rp) break;

should be

if(!(*rp)) break;?


Dark - Could it be deleting a pointer and reassigning it? Pointers are dynamically allocated, and when you "delete" a pointer, it deletes what it points to so maybe deleting the ruleL was the problem...
Apr 30 2007, 12:41 pm (Edited on Apr 30 2007, 12:49 pm)
Not really sure. I've only programmed in C++ for a week. And I rarely use pointers in C# so I'm not sure, also the extra () isn't necessary. I believe when you delete a pointer and try to reassign it you point to the wrong location of memory.
Apr 30 2007, 12:49 pm
Xx Dark Wizard xX wrote:
Not really sure. I've only programmed in C++ for a week. And I rarely use pointers in C# so I'm not sure, also the extra () isn't necessary. I believe when you delete a pointer and try to reassign it, your actually reassigning either assigns the wrong thing or points to the wrong piece of memory.

Well unless ruleL was dynamically allocated then it shouldn't work. Otherwise deleting should be fine, maybe Lummox will reply soon lol.
Apr 30 2007, 1:18 pm
I was going to guess that you were nullifying r->next, but never deleting it, then you'd just move on to (*rp)->next. You'd instead want to nullify r and delete it, then set r to (*rp) if it's non-null and continue. As it is, you're skipping r->next and never deleting it, but you are nullifying that reference.

Either that or you needed to put parenthesis around *rp in if(!*rp), making it if(!(*rp)).

Should've used the std::vector.
Apr 30 2007, 3:14 pm
Audeuro gets the brass ring! r=(*rp)->next should be r=*rp instead. Since *rp was already set to the next pointer in line, it's the next logical choice for r; by using (*rp)->next the code was skipping over a pointer, creating a memory leak and also not fully erasing every style sheet.
Apr 30 2007, 3:16 pm
Audeuro, your analysis is wrong, and I'll explain why:

1. r points to the data structure pointed to by ruleL.
2. rp points to the address of the pointer to that data structure.
3. The deletion method works like this:
-a. Set ruleL to point to the next StyleRule object; rp still points to ruleL and now references the "next" object, while r still points to the original object.
-b. Set the original object's "next" reference (which would be what ruleL is now) to NULL and delete the original object.
4. If there was no next object, break; otherwise continue the loop with it.

Anyways, that's what I came up with.

If I had to guess at a problem off-hand, I would say that r = (*rp)->next; seems suspicious; by the time that line is reached, *rp already points to the "next" object, and I don't see why you would set r to the "next-next" object. I think the line probably is supposed to look something like this:

r = *rp;
Apr 30 2007, 3:17 pm
Ack, Lummox! I had it; Aud was wrong. Nononono. =(

In addition, upon re-reading Aud's comment, I noted that he covered the next-next reference; I merely assumed that the whole comment was that the current object was never deleted. Oops. =(
Apr 30 2007, 6:35 pm
It's hardcore pointer management like this that makes me thankful for D.
May 1 2007, 4:02 am
Jtgibson wrote:
It's hardcore pointer management like this that makes me thankful for D.

Heck, I'm not fussy. I'll take any language with a garbage collector. (Even, dare I say it, Java.)
May 1 2007, 7:02 am
At its core, Java is actually a beautifully simple language, even elegant. But Sun made three core mistakes with it, all of which are software-based and easily fixed:

1) There is no goto keyword even though it's supported in bytecode.
2) You can have only one public class per file, and it must have the same name.
3) Sun has a love affair with ponderous design patterns that make even the simplest tasks incredibly cumbersome when using the standard packages they provide.