Three Star Programmer Examples

I once saw a guy write this line of code in the C program he was working on. a->nextPtr(a)->move(newCoords)->x; a is a temp pointer in a linked list. Nextptr is a functional reference (there was something weird about the list, forget what, so he used a function rather than a regular next pointer), then move the next object in the list and looked at the new x coordinate. There we have three layers of indirection, and two function references, but never really more than 1 star per layer. That guy would have done that if he had had half a chance on the project.

[Using -> to navigate a structure/class hierarchy isn't quite the same as multiple pointer dereferences. I do foo->bar->baz->bletch all the time and feel no shame in doing so. If I ever have occasion to type ***foo, I start looking for ways to ReFactor.]

I came across this in a Yacc parser. Perhaps it's a complex enough example of structure navigation to qualify as ThreeStarProgramming?

  $$.start = $4.start;
  $$.end = ic_inst(nop_t, NULL);
  $4.end->next = ic_inst(set_t, $2);
  $4.end->next->next = $6.start;
  $6.end->next = ic_inst(var_t, $2);
  $6.end->next->next = ic_inst(eq_t, NULL);
  $6.end->next->next->next = ic_inst(if_t, $$.end);
  $6.end->next->next->next->next = $10.start;
  $10.end->next = ic_inst(var_t, $2);
  $10.end->next->next = $8.start;
  $8.end->next = ic_inst(plus_t, NULL);
  $8.end->next->next = ic_inst(set_t, $2);
  $8.end->next->next->next = $6.start;

I'm a four-star programmer at least. I used them in routines for simple integer-keyed hash tables. (See libihash in the Hurd source code.) The library uses closed hashing. Each element of the hash table is a generic pointer: void *. So the table itself is a void ** array. Now, to delete an element from such a hashtable requires a complete rehash of the key. So it's convenient to tell a library user where their element is in the table so that they can null it out themselves for deletion. (Well, really the library gives them a routine to do that.) So the library user has a pointer to the void ** key. This gets filled in by the hash library automatically: the user passes a void *** telling the library where their void ** pointer is and the add-item functions fills it in. But this is closed hashing, so when the hash table needs to grow, all the elements have to be rehashed, and so the location of a void * pointer might change. So the user's void ** pointer will go invalid. So the hash table keeps track of that void *** pointer that was passed in so that when a rehash occurs, the user's void ** pointer can be automagically adjusted. And--badda bing, badda boom--the library keeps track of the void *** pointers for each table element in a void **** array.

The comment for that struct member is:

  /* An array storing pointers to the `location pointers' for each element.
These are used as cookies for quick 'n' easy removal.  */
  void ****locps;  /* four, count them, four stars */

I wrote a hashtable in my third programming class that was less complicated. I did more, so my client had to do less (e.g. nulled out the deleted key myself). Separation of Concerns also helped. Max stars was two. --EvaO

"unsigned char ***patterns[2] = {" Please tell me that isn't 4-star code?

It's now "unsigned char **patterns[2] = {" Excuse me while I go celebrate for a while. Then on to fixing some other problems with this code (like removing some massive code duplication...). :-)

Actually, that's nothing compared to the structured exception handling library. We sort of needed a time machine in order to keep this server running for more than 5 minutes at a time, so I built one. I don't think I'll do that again anytime soon (although embedding asm code in a C struct is good job security, it's not exactly good form). We ended up scrapping the code and starting from scratch...

I was almost a 4-star programmer. I was working on a newsreader, and wanted to store header data in a cache. There are many newsgroups with many articles each. Each article has multiple header strings (of several characters each). So I typed "char ****headers". Fortunately, I couldn't quite keep track of all the mallocs required, so I finally settled on conventional arrays of structures.

In the spirit of three-star programming, the following line:

 return(sf_files[fnum].lines[sf_files[fnum].line_on++]);

...is still in strn today. (An earlier (much scarier) version of this line confused an early version of the GDB debugger. Printing the expression gave a different output than assigning the expression to a variable, then printing it.)--CliffordAdams (waiting for his powered PropellerBeanie)

 Private fields()()()() As String 'I'm a 5 star programmer in VB.NET

This isn't three stars, only two, but obscures the number so it gets extra points:

Foo fDealWithDeletedRecs(FileType? ft, void* delrecs)
/* delete all recs from "delrecs" */
{
/* ... lots of stuff not touching delrecs ... */
for (; delrecs!=NULL; delrecs = *(void **)delrecs) {
rec = *(RecType? *)((char *)delrecs+sizeof(void *));
//...

I used to maintain code like this; note the especially useful comment at the top of the function. --RandyBrown?

Reversing an array in C or C++ can be done like this:

 int ar[N];
 int i, j;
 /* fill ar */
 for (i = 0, j = N - 1; i < j; i++, j--)
 {
int tmp = ar[i];
ar[i] = ar[j];
ar[j] = tmp;
 }

No pointer arithmetic is needed. Whoever claims it is "less efficient" than some clumsy pointer version should be clued in with respect to modern compiler technology. -- StephanHouben

No pointer arithmetic is needed, because there are actually no pointers involved. "int ar[]" has the type array-of-type-int and not the type pointer-to-array-of-type-int (as in "int *ar", which is completely different). However, ar[i] and *(ar+i) are syntactically synonymous because arrays are implicitly casted to their corresponding pointer-of-array types and integer increments i are implicitly transformed to i*sizeof(pointer-type), yet ar[] and *ar are semantically quite different. -- PhilipBusch

i++ - don't you know the difference between i++ and ++i? Obviously not. Much better to use ++i.

Indeed it can. And most candidates I interview(ed) couldn't write that, and nearly all of them couldn't produce the pointer equivalent (even when given the array version). I don't intend it as an efficiency question, just an exploration of whether they can substantiate their claim to know C++ -- PaulHudson''

Wow, that's bloated. What are you, a Java programmer? First, you shouldn't be using N except to set the size of the array. You should be using sizeof, ala: sizeof(ar) / sizeof *(ar). I prefer this macroized version:

 #define NUMELEM(x) (sizeof (x) / sizeof *(x))

which fails if x was an argument to the current function...

Well, obviously. The macro is only good for arrays defined in lexical scope. Fortunately, this is frequently the case, including in the example above. Consider that if you pass the array in to a function, the signature would be similar to int *reverse( int *ar, int size ); Since arrays are normally declared on the stack, one would typically call this with reverse( ar, NUMELEM(ar) );, so the macro is still useful. The idea is essentially to tie related information together or else you will end up with desynchronicity from the multiplicity. In other words, declare the size of the array OnceAndOnlyOnce! --ss

Second, this loop is 74 bytes in optimized 68k instructions (under CodeWarrior 7)! What?! Try this version:

 int ar[N];
 int *start = ar, *end = ar + NUMELEM(ar) - 1;
 while( start < end ) {
  int swap = *start;
  *start++ = *end;
  *end-- = swap;
 }

which is merely 30 bytes, and the slightly more obtuse

 int ar[N];
 int *start = ar, *end = ar + NUMELEM(ar);
 while( start < end ) {
  int swap = *start;
  *start++ = *--end;
  *end = swap;
 }

which is a nimble 26 bytes. I think you just got schooled in modern compiler technology, eh. ;) -- SunirShah

It's important to know both ways of reversing an array, so you can try the more readable version first and later use the more complicated one if you need to increase performance. There's an obscure but helpful little idiom about that, can't put my finger on it right now, something about premature optimization...

OK, Sunir, I checked it with GCC, and you're right: the pointer version is still smaller. The number I get are 54 bytes for my version and 36 bytes for your version. Options used are

 gcc -Os -fomit-frame-pointer -fstrength-reduce

with gcc 2.95.2. The main difference appears to be the scaling of the array index to a pointer. I had hoped GCC's strength reduce would take care of that, but apparently it doesn't. I can also force GCC to strength-reduce everywhere it can with

 gcc -Os -fomit-frame-pointer -freduce-all-givs

This shaves my code down to 52 bytes but unfortunately blows yours up to 49 bytes. This is because now everything is strength-reduced, which is not in general a good thing as far as code size is concerned.

-- StephanHouben

Haven't used C for a while, but one of my favorite idioms was handling linked lists with doubly indirect pointers. It means that you don't need special cases for handling empty lists or inserting at the head of a list.

Something like:

  Node **i; 

  for(i = &listHeader; *i; i = &((*i)->next)) {
    if(insertBeforeThisSpot(nodeToInsert, *i)) break;
  }

  nodeToInsert->next = *i;
  *i = nodeToInsert;

The central loop of a possible Forth interpreter implementation written in C might use three star programming, and is probably the purest example of it. Note that this only applies to an example written in C. Forth implementations written in assembly language typically use DirectThreadedCode representation, which is only one-star. IndirectThreadedCode representation, which is what the following code approximates, actually is only two-star.

  typedef void (*pvf)();    // Pointer to void C function
  typedef pvf *instruction; // The first word of a compiled routine holds 
                            // a pvf to a function which handles that routine type.
  typedef instruction *PC;  // And the program counter points to a list of instructions, 
                            // being pointers to routines, at which are found pointers to functions.

Now in the fetch-execute loop:

  while(pc) {
    pc++;
    (***pc)();
  }

There are a few small C functions that do things like update the pc to jump into or out of a compiled function, and there are others which perform intrinsic operations like adding integers or interfacing with the operating system. (You can see that this machine will stop if the program counter goes to zero.) For each of these intrinsics, there is a one-word compiled routine that contains only a pointer to the function which does the work, and doesn't touch the program counter.

What? Not? -JM

  while (pc)
    (***++pc)();