Author Archive

Catch All

1 Comment »

I was using my google-fu on longjmp when I came across a page from Francesco Nidito describing how to implement a Java like try/catch exception handling in C using the CPP. Very entertaining. However, I did see the dangling ETRY; as a challenge. Can I implement a more serious try/catch without it? On top of that, can I create a syntax more elegant than the syntax of Java, Ruby and Python? I could not resist. So here is the BSD-licensed source for my version of try/catch in CPP [download .tgz]. There is one small gem, I’d like to share with those that lack the time or courage to read the source. The code below would be valid after including the try/catch header file.

try             { /* Do something. */ }
catch(DIV_ZERO) { /* Handle this. */ }
catch(*)        { printf("Can't handle %d\n", excepno); }
ensure          { if (0 == d) d = 1; }

Note the catch(*). It catches all the (hitherto) uncaught exceptions. The preprocessor expands both catch(*) and catch(22) to a correct C integer expression. Since * can mean a pointer dereference and & can mean both pointer-of and bitwise-and, the expression (arg & allones) expands to either (* & allones) or to (22 & allones). Both are a valid C expression, the first evaluating to -1 the later to 22. To distinguish between a star and a number argument, (#arg[0] == '*') is used to check the first character of the argument. I happen to think the catch all catch(*) syntax is already plenty elegant but I am very open to any improvements, so don’t hold back.

Finding a Loop in a Linked List

No Comments »
Ladies, your mission is simple yet dangerous. The enemy is upon us … maybe. We have been handed a linked list. It is claimed it does not loop. But if we are to send in our troops, we better darn well make sure. Assumption is the mother of all, remember!?! It is your job to find a simple algorithm to check this linked list on loops. Ladies, O(n²) will not suffice. (Seriously, try it before reading on. Hint, the photo on the left shows Bob Floyd rendered using Floyd-Steinberg dithering.)

int has_loop(node_t slow)
{ node_t fast1, fast2 = slow; if (!slow) return 0; /* No list, no loop. */ while (fast1 = fast2->next && fast2 = fast1->next) { if (slow == fast1 || slow == fast2) break; slow = slow->next; } return slow == fast1 || slow == fast2; }

This solution is Floyd’s Cycle-Finding Algorithm as published in Non-deterministic Algorithms by Robert W. Floyd in 1967. It is also called The Tortoise and the Hare Algorithm. (Stephen Ostermiller) [Finding a Loop in a Singly Linked List]

Trivia: Actually this solution is not published in the above mentioned article [pdf], apparently Donald Knuth credits Floyd for the algorithm, but without citation. Since nobody influenced Knuth more than Bob Floyd [pdf], they might have simply discussed it and Knuth put it in The Art of Computer Programming II.

Hashed Locking

No Comments »

We have all been there. Multiple threads, many objects, and than you realize you need per-object locking. Maybe you should add a mutex to each and every object, but there are many objects and collisions are rare. So, you should use a linked list with a 4-tuple node: {mutex, count, &object, &next}. Before you use an object, lock the list, see if the object is in any node: if yes, increment the count, if no, create a node with a count of 1. In either case get a pointer to the mutex and unlock the list. Now lock the node, using the pointer to the mutex and do it to the object. After which you lock the list again and either decrement the count or delete the node. Implementing that won’t be hard, just follow the doodle you just made while inserting imaginary objects A, B, A, and C (on the right). But you feel you can do better: collisions of the same object are rare but collisions of unrelated objects run rampant. You realize locking and searching the list might become a bottleneck. How about chopping the linked list into chunks with a hash array? You doodle some more (on the left). A little more complex, but doable. Given a large enough hash array, the list chunks will be seldom longer than one. Than you realize that you can give each list chunk its own mutex. And than you get that special feeling. You know the one I mean. Utter happiness hits you: Why not just fill the hash array with mutexes only? You can’t help but drawing it out (to the right), just to prolong that nice feeling. What a world, what a life, you are in love. Well, maybe not “in love” but your ventral tegmental floods your caudate with dopamine like there is no tomorrow. If you read this far, you know I am not joking.

The Design of Design

No Comments »

tmmmBefore, I loved being in a bookstore. Now, I turn to the WWW to buy books. I, always, prefer choice and cheap over instant gratification. Recently, I had to actually pickup a book for my wife–she likes instant, tell me about it. As I hurry to checkout, out of the corner of an eye, tdod I spot a book that looks like TMMM (the 1995 edition). So I hit the flaps, bank hard left, dive down and swoop up a bluish 400 page book entitled The Design of Design by Frederick P. Brooks, jr. Distrustful, I wonder: “Real or lookalike?,” “Piggybacking on earlier success?” So I browse a few random pages. Wow, brilliant stuff. I have got to have this book, like now! I hurry through checkout, to the car and start reading. Here is what I think. First, re-read TMMM. Go ahead, I’ll wait… Ok, re-read at least chapters 2 and 16. Second, read TDOD, but skip the non computer essays. I say this because the first part of TDOD is brilliant but dense. Refreshing the context will make it more digestible. Also, I highly disagree with the much iterated notion that TDOD is applicable outside the CS realm. Building analogy considered harmful.

If It Quacks Hard, It Must Be

1 Comment »

Alan was complimented for completing his project on schedule. His supervisor looked over the program. With a few minutes of thumbing through he saw that the company standards about structured programming were being observed. He quickly gave up attempting to read the program however; it seemed quite incomprehensible. He realized by now that the project was really much more complex than he had originally assumed, and he congratulated Alan again on his achievement. (N.W. Rickert) [The Parable of the two Programmers]
If you can spot the logic error you are at the forefront of evolution, count yourself lucky. If your boss can spot the logic error count your self luckier and if they can’t, quit.

Uber Flexible

No Comments »

Newer languages like Java lack a preprocessor like C has. The #ifdef AAP is replaced by if(aap) with aap declared final. However, cpp has more to offer than conditional code. A preprocessor is a domain specific language for symbol manipulation that can also offer meta programming and language alterations. The __LINE__ directive is an example of the former. Below an example of the latter:
To fully use a preprocessor, a coder needs to be uber-flexible. Only a few are. Hence the frustration with languages like M4 or the expansion delay effect of && in the SAS macro language. Some preprocessors were added out of necessity. Just imagine writing 10 KLOC of assembler without using a preprocessor. To quote Al Bundy, I’d rather bait a crocodile with my manhood.

Only Your Opinion

No Comments »

WTFBWA friend of mine once worked on some code with a number of other people. At some point he found a large chunk of code that was unreachable, yet someone was working on it. After some inquires about the nature of the code, the person working on it got quite hostile, claiming the code was crucial and was in fact reachable. At some point a manager intervened. This manager listened to both parties and sumed up the problem. “So you claim the code will never be executed and you claim the code is crucial.” Both, my friend the coder and the other person agreed. Without much further thought, the manager decided that the other person should keep working on their code, claiming: “This is really a no-brainer. Since you both did not list any negative performance consequences, we don’t change anything.” When my friend emphasized again that the code was unreachable he was met with “But that is only your opinion.”

Can Someone Please Help Me

No Comments »

solidcodeIf I had a dime for every time I had to read a request like the one below, I’d still be reading comp.lang.c instead of the .moderated version.

> Dear everyone,
>  Can someone please help me on my HW.
>  I'm trying to write a program that will
>  display the following:
>      *
>     ***
>    *****
>   *******
>   *******
>    *****
>     ***
>      * 

As you can see on the left, Richard J. Heathfield has a different, much funnier, approach. It almost makes me go back to the unmoderated group, almost. (Thanks, John)

Post Assignment

No Comments »

A while back, I designed a domain specific language. It combines the good of APL, C, Pascal and SQL. For example, the token ‘=‘ is not used, ‘:=‘ is the assign-token and ‘==‘ is the equal-token. Like C, it uses only ASCII characters and, like APL, it has a minimalistic, mathematical notation. There is no muli- or list-assign, like in Python and Perl, eventhough code like this: ‘(a,b,c) := (b,c,3);‘ just looks so cool and intuitive. But, it did not fit the syntax, it would make it hard to parse (both for humans and for the LR parser) and most of all it went against the minimalisticity. Than I came up with ‘=:‘, the post-assignment operator. It took me but five minutes to implement. It is a regular assignment but returns the old lvalue. For example ‘a =: 3;‘ would assign ‘3‘ to ‘a‘ and return what ever value was in ‘a‘ before. Post-assignment; analogous to the post-increment from C. IMHO, It makes the above shift even more elegant to read: ‘a =: b =: c =: 3;‘. It was love at first sight! However, the smartest person I know (and first programmer in this language) did not see the need for this opperator and neither did anyone else. So I swallowed my pride and removed the ten odd LOCs. I cried myself to sleep that night.

I’m Aware My Code Is a Sad Affair

No Comments »

I was recently asked to hunt a bug in some of my old code. It was a shell script generating Postscript, generating .PNG files for a website. It had “organically” grown over some years and started generating bad Postscript starting May 1st. Since Postscript is well designed and has good error handling, it did not take long to find the problem. The word May had not been replaced by a 120 (the year day number of May 1st). Here is a sniped:


Note the ‘r’ that should be a ‘y’ in the center LOC. My bad. However, I realized that, in theory, this error could have been caught (by sed) because the second /[Mm]ar[^ ]*/ would not ever be satisfied. Sadly, I can’t make sed find my bad code, but I can dream, can’t I?