2008-02-29

More Vectors and Linked Lists

What’s better than having a vector or a linked list? Having a vector and a linked list, natch. I coded these up today and added them into the SVN repo.

The template classes have a virtually identical set of functions, so they should be entirely interchangeable. The functionality they present is more or less the same as the subset of the vector class that Woopsi uses (push_back(), clear(), insert(), etc) so it should be fairly easy to drop them in as vector replacements.

The only difference between the two, as far as the external API is concerned, is that the linked list has a “getIterator()’ factory method that will produce a class that can iterate through the linked list. It provides functions like “moveToFirst()” and “moveToNext()”, thus allowing the developer to take advantage of the sequential nature of the linked list without the problems I ran into in the first version (embedding the iterator into the list itself is a really bad idea).

Obviously, the classes don’t use the STL iterator functions. The whole point of writing these two classes is to remove the STL from Woopsi.

Internally, the two are very different. The linked list is great at working with sequential data (think loops) and adding/removing items quickly. The dynamic array is useful for data that needs to be accessed randomly and that has a fairly stable number of items. It’s not so great at performing inserts, but it’s much faster than the linked list at retrieving the nth item.

Neither container class is integrated into Woopsi’s code yet.

I came across a couple of oddities when trying to put this together. First of all, trying to split a template class into .h and .cpp files results in some very strange errors. “NULL is not defined” was one. The solution is to make sure that all of a template class’ code is contained within the .h file - the .cpp file is not required.

A second problem I ran into was trying to work with a struct within a template class from another class. I had this situation:


template <class T>
class LinkedList {
public:
    struct LinkedListItem {
        T data;
    }
};

There just doesn’t seem to be any way to declare an instance of this struct outside of the LinkedList class. The compiler goes bonkers when it encounters an attempt at doing so. Switching to this works:


template <class T>
struct LinkedListItem {
    T data;
}

template <class T>
class LinkedList {
};

It may be that I’m missing something obvious, but none of the usual syntax would allow me to instantiate a LinkedListItem struct anywhere but within the LinkedList class when I used the first version. Template structs let me get around the problem - a handy feature, that.

This is the first time that I’ve tried writing template classes and the first time I’ve made a private constructor/friend class/factory method pattern in C++. I was rather surprised to find that it was easy to set up and works well.

One more thing I should mention. The sc.nds and nds.gba versions of Woopsi no longer seem to work; they don’t work in No$GBA, anyway (although the .nds version does, despite No$GBA’s error message when it initially tries to boot the ROM). I think this must be related to the DMA changes made the other day. If the ROMs still work on slot-2 flash carts (I’ve got an M3 and Supercard I can test it on) I’ll just assume that it’s a strange emulator problem.

Comments

Jeff on 2008-02-29 at 03:03 said:

Its not a surprise that the .sc.nds doesn’t work if the .ds.gba doesn’t, since they are bit-for-bit identical.

To make the .sc.nds file, the standard Makefile just copies the .ds.gba

154 %.ds.gba: %.nds 155 @dsbuild $< 156 @echo Built: $(notdir $(OUTPUT)).nds 157 @echo Built: $(notdir $@) 158 @cp $(CURDIR)/../$(RELEASE)/$(notdir $@) ../$(RELEASE)/$(notdir $(OUTPUT)).sc.nds 159 @echo Built: $(notdir $(OUTPUT)).sc.nds

Personally, I’ve never understood why people bother building both, or including them both in releases. But there ya go, I have an R4 which doesn’t like either of them.

Jeff on 2008-02-29 at 03:08 said:

The problem with NULL is a simple one. You don’t include any header that defines it.

NULL is one of the oddities of c/c++ - everyone thinks its a feature of the language but its actually just a #define that comes from somewhere like <stdio.h> or some such.

See http://safari.oreilly.com/0201379260/ch04lev1sec6 which actually says:

“Due to the mess with the type of NULL, several people and style guides recommend not using NULL in C++. Instead, 0 or a special user-defined constant such as NIL might work better.”

Jeff on 2008-02-29 at 03:09 said:

Might want to be careful about using global edits to change data types

“linkedlist.h” 178 // Update the foot pou32ers

Jeff on 2008-02-29 at 03:16 said:

It looks to me like your erase() method short-cuts out on erasing the first item, and forgets to fix up _foot if it was the only item in the list.

pop_back() blindly dereferences _foot even its its NULL.

push_back() blindly dereferences _foot even if its NULL, if _head is non-NULL.

Personally, I’d pass arguments into the constructor rather than having the two distinct sets of assignments in push_back()

ant on 2008-02-29 at 09:56 said:

If you have a Supercard, the sc.nds file is invaluable. Before I got a CycloDS I hated developers that didn’t bother including it, because it was such a pain to get homebrew into a usable format.

The NULL thing makes sense. There’s a chain of includes in the other files that ultimately leads to the NULL define.

Thought I’d spotted all of the “pou32er” mistakes. Must try harder!

Fixed the LinkedList::erase() _foot problem.

LinkedList::pop_back() can dereference _foot because the function checks the list size before it starts. If there’s at least one item in the list then _foot is guaranteed not to be NULL (bugs ignored, obviously). There was a bug, though - I wasn’t checking that _foot was NULL before assigning its next pointer. If I’ve popped the last item in the list this would crash.

Same thing in LinkedList::push_back(). If _head is not NULL, _foot is guaranteed not to be NULL. If there’s only one item in the list then _head and _foot will point to the same item. The only time _foot is NULL is if _head is also NULL, which means the list is empty.

I could change it so that you have to pass a head item into the constructor, but I’ve intentionally made the DynamicList and LinkedList as similar as possible. What happens if you create a LinkedList and pass in a head item, then pop_back() and insert another item?

ant on 2008-02-29 at 14:03 said:

OK, I’ve now got a version of the Woopsi code that doesn’t use the vector class and has no dependencies on the STL.

The resultant binary is almost exactly the same size as it was before; in fact, it’s actually ~1K larger.

EDIT: The new version is in the “branches” directory.

Jeff on 2008-02-29 at 22:23 said:

slidervertical.o is still hauling in ios

/Developer/NDS/devkitARM/bin/../lib/gcc/arm-eabi/4.1.1/../../../../arm-eabi/lib/libstdc++.a(ios_init.o) slidervertical.o (_ZNSt8ios_base4InitD1Ev)

which hauls in locale

/Developer/NDS/devkitARM/bin/../lib/gcc/arm-eabi/4.1.1/../../../../arm-eabi/lib/libstdc++.a(locale.o) /Developer/NDS/devkitARM/bin/../lib/gcc/arm-eabi/4.1.1/../../../../arm-eabi/lib/libstdc++.a(ios_init.o) (_ZNSt6localeD1Ev)

etc…

And of course, you are still using PALib by default

Jeff on 2008-02-29 at 22:28 said:

Why does slidervertical.cpp include <iostring> ?

Jeff on 2008-02-29 at 22:28 said:

I mean <iostream> ?

God I hate typing &lt

Jeff on 2008-02-29 at 22:32 said:

Answer: abs()

Seems like stdlib.h would be a better answer to that one

Removing that took Woopsi.nds from

-rw-r--r-- 1 jeff admin 714816 1 Mar 09:24 Woopsi.nds

to

-rw-r--r-- 1 jeff admin 561216 1 Mar 09:30 Woopsi.nds

Thats a sizable improvement.

Jeff on 2008-02-29 at 22:38 said:

Hmmm, if you try to make with the Makefile.nopalib, you get:

/projects/woopsi/woopsi/branches/woopsi_0.30_0.1/Woopsi/woopsi/graphicsport.cpp: In member function ‘void GraphicsPort::drawText(s16, s16, FontBase*, char)’: /projects/woopsi/woopsi/branches/woopsi_0.30_0.1/Woopsi/woopsi/graphicsport.cpp:141: error: ‘sprintf’ was not declared in this scope

/projects/woopsi/woopsi/branches/woopsi_0.30_0.1/Woopsi/woopsi/textbox.cpp: In constructor ‘Textbox::Textbox(s16, s16, u16, u16, char, FontBase*)’: /projects/woopsi/woopsi/branches/woopsi_0.30_0.1/Woopsi/woopsi/textbox.cpp:26: error: ‘sprintf’ was not declared in this scope

including stdio.h fixes both of those, but its another place where floating point support is beig hauled in, probably unnecessarily.

Makeing with .nopalib gives:

-rw-r--r-- 1 jeff admin 505408 1 Mar 09:37 Woopsi.nds

so palib adds about 60K

Jeff on 2008-02-29 at 22:39 said:

Ugghhh. textbox.cpp:

    char text[2];
    sprintf(text, "%c", letter);

This is an atomic bomb to open an egg. Use

text[0]= letter;
text[1] = 0;

Jeff on 2008-02-29 at 22:41 said:

Removing those spurious sprintf() gives

-rw-r--r-- 1 jeff admin 504896 1 Mar 09:40 Woopsi.nds

500 bytes? Doesn’t seem like much, but thats because you aren’t downloading it wifi ;-)

Jeff on 2008-03-01 at 06:42 said:

I’m working at reducing Woopsi’s minimum footprint (I’ve got a makefile that builds a .a file for you - I’ll upload that somewhere when its clean) and one thing stands out quite badly. Here is an adjusted ‘load tree’ - each module insists on the one underneath it.

woopsi.o woopsifuncs.o sysfont.o font.o fontbase.o debug.o multilinetextbox.o scrollingpanel.o text.o tinyfont.o amigascreen.o screentitle.o amigawindow.o screendepthbutton.o button.o textbutton.o screenflipbutton.o window.o windowborderbottom.o windowborderside.o windowclosebutton.o windowdepthbutton.o

woopsi.o pulls in an amazing load of baggage, because it insists on using Debug::setWoopsi(this) - it would be way more efficient to have a singleton in there (that we’ve discussed earlier) that the Debug module can access when it needs it.

Oh, and Woopsi::eraseRect() uses Debug::printf() as well - I think thats literally debugging and doesn’t need to be there. After all, no-one that sees it can do anything about it…

Jeff on 2008-03-01 at 06:44 said:

Oh, crap, you lost the fancy hierarchy.

woopsi.o ---- woopsifuncs.o ----sysfont.o ----font.o ----fontbase.o ----debug.o --------multilinetextbox.o ------------scrollingpanel.o ------------text.o --------tinyfont.o --------amigascreen.o ------------screentitle.o --------amigawindow.o ------------screendepthbutton.o ----------------button.o ----------------textbutton.o ------------screenflipbutton.o ------------window.o ------------windowborderbottom.o ------------windowborderside.o ------------windowclosebutton.o ------------windowdepthbutton.o

Jeff on 2008-03-01 at 07:16 said:

http://rapidshare.com/files/96091777/archive.zip.html

Albatross:Woopsi jeff$ unzip -l archive Archive: archive.zip Length Date Time Name


 8072  03-01-08 17:55   makefile.lib
10860  03-01-08 18:06   woopsi/woopsi.cpp
 5545  03-01-08 18:00   woopsi/woopsi.h
 2479  03-01-08 18:02   woopsi/debug.cpp

26956                   4 files

This has the singleton change to remove the insistence on Debug.

The makefile just sits at the same level as Makefile.palib - you invoke it as:

make -f Makefile.lib

and it builds Release/libwoopsi.a - note that it has too much stuff in it at present because you still have the all_gfx.c file, and you have the sample images (the animation stuff) in the same directory as the mandatory bitmaps (the amiga widgets) but thats something I can’t change from here…

ant on 2008-03-01 at 13:38 said:

Code submissions! My favourite kind of code!

This is really good stuff. I’ve added the library makefile and your changed files into the 0.30 branch and made all of the changes you’ve suggested. Down to 493K now, which is astonishing.

For a test, I stripped out everything from the “data” directory (none of which is needed for a basic build - all of the Amiga widgets are in the font.c file. The GUI bitmaps are all used for the skinned screens) and made a “hello world” program - 302K with PALib, and 243K for a PALib-free version:

Hello World

Just need to write a full post and merge the branch back into the trunk.

Oh, and the sc.nds build works again. Hurrah!

Jeff on 2008-03-01 at 23:56 said:

You put the <stdlib.h> into slidervertical.h instead of slidervertical.cpp

I guess this must be a personal preference, but its not an easy one to justify, in my opinion. Nothing in slidervertical.h requires that header file, and now anyone who includes slidervertical.h has to compile stdlib.h as well.

You really should include header files, in (and only in) the files that actually need them, not some other convenient file that the dependent one includes. This is one of the major reasons that people bitch about ‘compiles being so slow’, because they’ve allowed the interdependencies between all their source files to be come unwieldy. They end up compiling every header into every source, and because make auto-generates .d files, they tend to end up compiling every source file whenever they change any single header.

Personally, I dislike including <nds.h> - instead I pick out the bits (like nds/video.h or nds/arm9/sound.h) that I specifically need.

ant on 2008-03-02 at 12:07 said:

Yeah, that makes sense. Throughout the Woopsi code I’ve tried to keep all of the includes in the h files, not through personal preference, but because I was under the impression it was the “correct” thing to do. I’ll swap it around.

Jeff on 2008-03-02 at 22:20 said:

One of the gotchas with header files is the situation:


class B {
   A *myA;
}

People think that means that you must have the full definition of A available, and thus put #include “a.h” into b.h

You should just put a forward reference to A instead. ie,


class A;
class B {
  A *myA;
}

which is more than enough, from the compilers perspective and has the added advantage of giving you more self-contained documentation. You can tell from looking in “b.h” that A is a class, not a struct or a typedef’d int, etc.

You do need a.h if you are subclassing from it. ie


#include "a.h"
class B : A {
...
}

but then its no big deal that changing a.h means you need to recompile everything that includes b.h.