Archive for October, 2007

Fritz asks about C structure types

2007-10-24

Fritz asks:

Hello,

I have a question regarding structures in C.

What’s the correct way to use it since I saw different styles using typedef struct, and naming struct before ‘{’ and after ‘}’.

Is this correct?

struct _foo {
  int a, b;};
struct _foo *foo;

Thanks!

(short answer yes, but don’t use “_foo”)

Thanks for the question Fritz, which normally I would expect to have seen on the Coming Soon page.

It’s good every once in a while to review even the basic parts of a language with which one is intimately familiar, so I will.

I will be discussing C not C++ (pretty much all I know about C++ is that it’s a bit different in this regard).The code Fritz presents is almost fine. The error is that it uses the struct tag «_foo» which renders it undefined (a point I discuss below). The same code using «struct foo» would be just fine. In the discussion below I’ll use «struct foo».

struct is a keyword in C and it has two related uses:

  • To declare a new structure type and possibly a tag (name) for that type; and,
  • To refer to a previously declared type by its tag.
  • Fritz’s short example shows both of these. The first use of struct:

    struct foo {
      int a, b;
    };

    declares a new structure type and gives that type the name «struct foo». The «foo» in «struct foo» is called a tag and it is used to specify which structure type you mean when you want to refer to the stucture type later (or, as we see below, earlier).The second use:

    struct foo *foo;

    declares a new variable whose type is «struct foo *» (pointer to struct foo), referring to the type we declared earlier by its name. It so happens that the tag used to identify the struct, the «foo» in «struct foo», and the name of the variable are the same. That’s okay, it works because structure tags and variable names live in separate name spaces so they can never conflict (see [ISOC] section 6.2.3).These declarations can be combined; we can simultaneously declare a new structure type and a variable that uses that type:

    struct foo {
      int a,b;
    } *foo;

    This isn’t particular good style, but it is possible. It is downright dangerous in argument lists. Avoid it unless you know better.

    Incomplete types

    More usefully the declaration of the existence of a structure type can be separated from the definition of a structure type. The key idea is that you don’t need to know about the internal details of a structure type in order to have a pointer to it. So the declaration of a pointer type doesn’t have to have a full definition of the structure type.

    This is what makes linked list types possible in C:

    struct node {
      struct node *next;
      int v;
    };

    Or structure types that refer to each other:

    struct bar {
      struct zon *z;
    };
    
    struct zon {
      struct bar *b;
    };

    Note that the definition of «struct bar» doesn’t have to see the definition of «struct zon» before being allowed to use «struct zon *» to declare a pointer type.The same technique allows us to have abstract datatypes in C. Simply define an interface that only uses a pointer type, «struct foo *» say, and never put the definition of «struct foo» in the header, reserve that for the implementation file. Clients of the interface are restricted from inspecting the contents of the structure and the compiler gives a lot of help in enforcing that.

    typedef

    It’s common to use a typedef in conjunction with structure types. A typedef allows you create an alias, or another name, for a type. When used with structure type there are two common patterns of use. The first is to create a typedef for the structure type itself; the second is to create a typedef for a pointer to the structure type:

    typedef struct foo {
      int x;
    } foo_s;
    
    typedef struct foo *foo_p;

    The latter approach, making a typedef of the pointer type, is useful when you want the structure to be opaque so that clients can’t access it. This is the approach taken by the PAM client interface from Linux where all the functions take a pamc_handle_t which is defined as the opaque type «typedef struct pamc_handle_s *pamc_handle_t;». The client never gets to see the definition of the “inside” of the structure type so it can never (legally) access it except via the published interface. This is a good thing.

    The perils of _foo

    You can’t use a structure tag name that begins with an underscore at the top level of a file. At least, that’s my reading of this extract from [ISOC] section 7.1.3, Reserved Identifiers:

    All identifiers that begin with an underscore are always reserved for use as identifierswith file scope in both the ordinary and tag name spaces.

    Using a reserved identifier in your program leads to undefined behaviour (paragraph 2 of the same section, 7.1.3). So don’t do that then.

    What I did on my holiday (Metroid II)

    2007-10-22

    On the dull wet days of my holiday I spent some time playing the ancient Game Boy title Metroid II:

    metroid2-800.png

    The figure is the map I created sitting in the Formule 1. Metroid II is a hard game. I usually consider the fact that I have to make a map as some sort of failing, I’m just never sure whether it’s a failing of me or the game. In any case there are two sorts of games: those for which I have to make a map; and those that I don’t.

    Even some games that have an in-game map I’ve ended up having to draw a map for. Super Metroid has an in-game map but it is too abstract, making it difficult to remember which one was the room with the mysterious X feature, and doesn’t accurately draw in all connexions (such as secret passages) making navigation haphazard. Add to that the need to mark rooms that have been visited but which may warrant a subsequent investigation when Samus gains new powers: a paper map becomes almost essential. Wind Waker not only has an in-game map but the acquisition of sea charts, by which sections of the map are revealed, is an integrated and very satisfying part of the gameplay. I still had to draw map (Wind Waker whips me into a box ticking frenzy in a way that other Zelda games don’t quite manage).

    I don’t think that a game in which you have to draw a map is necessarily a bad game. But I think you need to think very carefully before deliberately designing such a game. Many people will not draw a map, they will find your game too hard, and they will not play it.

    There is a certain satisfaction from drawing a map (even if you have no drawing skills, like me), but there’s also a certain frustration that comes from it. The Metroid II map documents some typical frustrations: not knowing where to start on the page so having to go off the edge of the page and onto a new sheet (except I was on holiday so I was restricted to mapping using a single sheet, the back of the flight confirmation sheet); drawing at inconsistent scales so the map doesn’t join up when it should; inconsistent mapping conventions (I have mapped parts of Metroid II using a schematic system and parts using a topographical system); having to invent a set of symbols to denote various important features, then realising you need to elaborate that in a confusing way (for example, m could be Metroid, Missile Power-up, or Missile Refill); having to go back and document a whole load of features that you previously thought unimportant.

    There is a large and important dark side to maps. The player can spend more of the game looking at the map than the game. And that means that in the eyes of the player the map has become more important than the game itself. Which do you think a game designer would rather the player look at? Doom, the seminal first person shooter, had a pretty traditional 2D plan map. It introduced the more novel feature that game continued even when viewing the map, monsters moved and could still attack the player. The player could move and navigate on the map screen too. With a little bit of practise the player could do entire missions on the 2D map screen alone, and in many ways it was more convenient. So why bother drawing all that 3D nonsense?

    Follow

    Get every new post delivered to your Inbox.