commit --amend

I've been working on a hashtable implementation in C because, well, everyone should do it once, right? And in principle, it should be easy, right? I've spent more than a few hours getting this far, and more than a few to go.

Some features:

• The getHashCode function returns a char not an int. This keeps memory use low, and in my experience hash tables commonly have dozens, not thousands, of records.
• Simple chaining is used to resolve collisions.
• Since traversing the keys is a common thing to do in a hash table, I have an array to hold the keys.
• For collision resolution, each value in the table is preceded by a pointer to the key in the key array.

The library includes some array helper functions for using re-sizable, null-terminated arrays. I was inspired by the dietlibc [pdf] philosophy of favoring arrays over linked lists and other more complicated data structures, and using realloc() for re-sizing the arrays. A side-effect of realloc, however, is that it may move your array to make enough room, which made life somewhat difficult for me.

I won't print the whole thing here, because:

• I haven't implemented remove(), clear(), or free() yet.
• I have a good, general-purpose getHashCode() function in mind, not yet implemented.
• I don't care to be someone's homework helper. (Please e-mail me, address in the margin, and I'll be happy to send you the latest version).

Here's the hashPut function, though, just for the purpose of showing the amount of work involved.

 
void hashPut(hash * h, void * key, void * value) {

assert(key);
assert(value);
assert(h);

size_t szPtr = sizeof(void *);

if(h->keys) {
        // Couldn't find an existing equivalent key, so we add
        if(!arrSeek(h->keys, key, h->szKey, h->keyComparator)) {
                void * oldKeysArray = h->keys;
                h->keys = arrAdd(h->keys, key, h->szKey);

                // Since realloc (in arrAdd) may have moved the array,
                // we will have to correct all the pointers to the keys.
                off_t keyArrayMoved = h->keys - oldKeysArray;
                if(keyArrayMoved) {
                        size_t szPtrPlusValue = szPtr + h->szValue;
                        char *** oneValue = h->values;
                        int i = 0;
                        for(; i < 256; oneValue++, i++) {
                                if(*oneValue) {
                                        **oneValue += keyArrayMoved;
                                }
                        }
                }
        }
// No existing key array, create it
} else {
        h->keys = arrNew(key, h->szKey);
        
        h->values = calloc(256 , szPtr);
}

void * keyInArray = arrSeek(h->keys, key, h->szKey, h->keyComparator);

char hashCode = h->hashFunc(key);
void ** table = h->values;
void * chain = table[(unsigned char)hashCode];

/* Chain data is stored as an array of an implied
 * struct type:
 *      {
 *              void * ptrToKeyInKeyArray;
 *              char[szValue] value;
 *      }
 *
 * Since values have variable size, the struct can't
 * be explicitly declared.  Just know that's what's going
 * on here.
 */

if(chain) {
        void * arr = chain;
        void * existing = arrSeek(arr, value, h->szValue, 
                h->valueComparator);

        // Replace an existing value in the chain
        if(existing) {
                memcpy(existing,  key, szPtr);
                memcpy(existing + szPtr, value, h->szValue);

        // A new item in the chain
        } else {

                char ptrPlusValue[szPtr + h->szValue];
                *ptrPlusValue = (int)keyInArray;
                memcpy(ptrPlusValue+szPtr, value, h->szValue);
                table[(unsigned char)hashCode] = 
                        arrAdd(arr, &ptrPlusValue, szPtr + h->szValue);

        }
// No chain exists at this location in the values array
} else {

        char ptrPlusValue[szPtr + h->szValue];
        *ptrPlusValue = (int)keyInArray;
        void * copyValueHere = ptrPlusValue + szPtr;
        memcpy(copyValueHere, value, h->szValue);

        void * newChain = arrNew(&ptrPlusValue, szPtr + h->szValue);
        table[(unsigned char)hashCode] = newChain;
}

}

"A hash table? Simple!" I thought. "I could probably do it with macros," I thought.

I've been a fan of DVD rental kiosks for quite a while. They allow for the spontaneity that is lost with Netflix, my practice of returning the movie the next day is rewarded with cheap prices, and the retrieval/vending hardware is called the "Robot". What's not to like?

My neighborhood grocery store changed kiosk vendors from TheDVDConnection to MovieCube (a giant in the market). I walked away empty-handed from the kiosk last night following a horrible user experience!

Every single rule of interface design is broken. I'll start with the landing screen. I don't have screenshots, but the layout is like this:

,___________________________________________________
| *Category* *Buttons* *Up* *Here*                 |
|--------------------------------------------------|
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|--------------------------------------------------|
| |-------. |-------.                              |
| |__Eng__| |__Esp__|                              |
`---------------------------------------------------

With very small buttons, yet the center of the screen is completely blank!

Clicking a category, say "New Releases", results in a progress bar that lasts no less than 10 seconds!

,___________________________________________________
| *Category* *Buttons* *Up* *Here*                 |
|--------------------------------------------------|
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                  +----------+                    |
|                  |Processing|                    |
|                  | xxx----- |                    |
|                  +----------+                    |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|--------------------------------------------------|
| |-------. |-------.                              |
| |__Eng__| |__Esp__|                              |
`---------------------------------------------------

Come on. YOU"RE FILLING AN ARRAY. This is repeated for every category selection, including the case where you click the button for the category you're already on. There's no possible rationale for performance this bad. If you're connecting to the network for some reason, shame on you. And not caching whatever hardcore algorithms are needed to assemble a paged list of movies, double shame.

Now the movies appear in a paged list, a nice two-column layout with thumbnails.

 ,___________________________________________________
 | *Category* *Buttons* *Up* *Here*                 |
 |--------------------------------------------------|
 |                  New Releases                    |
 |          ____               ____                 |
 |         |    |             |    |                |
 |         |    | Borat       |    | La Mujer       |
 |         |    |             |    |                |
 |         '----'             '----'                |
 |          ____               ____                 |
 |  <<<    |    |             |    |           >>>  |
 |         |    | Saw XXI     |    | Pirates!       |
 |         |    |             |    |                |
 |         '----'             '----'                |
 |          ____               ____                 |
 |         |    |             |    |                |
 |         |    | El Oso      |    | Fuego Fuego    |
 |         |    |             |    |                |
 |         '----'             '----'                |
 |                                                  |
 |--------------------------------------------------|
 | |-------. |-------.                              |
 | |__Eng__| |__Esp__|                              |
 `---------------------------------------------------

At this point, so many things are wrong:

• Borat isn't a new release.
• Half the movies shown are Spanish-language titles, even though I pressed the "English" button. I can appreciate that the language of the interface and the language of the movie are two different things, but Joe User doesn't understand that. Offer the user a way to filter based on movie language, and make it clear that the existing "English" and "Spanish" buttons don't do this.
• There's no one-line description of the movie. Come on, just a sentence, it really does help.
• The paging function ... well ...
  • There's no "Page 1 of 7" indicator. You must scroll every page to know how many "New Releases" there are.
  • The paging buttons (left and right arrows) neither disable for impossible actions, nor cycle to the other end of the list. In other words, if I'm on Page One, then either the "Page Back" button should disable, or it should cycle me to the last page of results. Nope. It just reloads page one again (incredibly I'm spared the 10-second progress bar in this case).

After all this fighting with the interface, it turns out that the selection is tiny and poor. I walk away. After years of resisting, I'm joining Netflix today.

MovieCube, don't hire the CEO's nephew to do your interface design. "Trevor, he's good with computers!"

Here's our last grocery list:

Look like a mess? Look again. Instead of the typical list style, we've started writing the items in the geographical location in the grocery store. So, produce being the front right of the store when you walk in, lettuce is drawn in the lower left hand corner.

How does it work? Awesome. Until now, every grocery shopping trip has one moment where I realize I missed something and I have to walk across the store again to get it. Never again.

To stay organized, I find two tools indispensable: ToDo.txt for a to-do list and Remind for being reminded of upcoming dates. These two gems leave one problem to the user - how am I notified about to-dos or events? The Remind output is brief enough that I can display it from my .bashrc and see it every time I open a shell.

The ToDo list, however, would clutter this, and I'm left remembering to type 'todo ls' when I'm ready to tackle an item. I have to remember to look at it and want to look at, which I've stopped doing recently.

Luckily, the Awesome window manager made it trivial to write a rotator plug-in which will randomly show me an item from my to-do list or my Remind calendar, consolidating and presenting data from two tools in a way that is harder to ignore. A full screenshot with the rotator in the upper right:

(Yes, it's Sarah Silverman on a toilet. I never said I was a good man.)

And a close-up of the rotator near the clock:

Two scripts are used. fetchItem.sh assembles the inputs and selects a line at random for display. runRotator.sh is the simple daemon that kicks off from the .xinitrc and sends the item into Awesome every 20 seconds.

fetchItem.sh - pick a random line from any text input

#!/bin/bash

TMP_FILE=/home/erik/rotator/data.tmp

#first input source
cat /home/erik/todo/todo.txt \
        | grep -v "^x " | sed 's/^/TODO: /' > $TMP_FILE

#second input source
remind -g /home/erik/.remind | tail -n +2 \
        | sed "/^$/d" | sed 's/^/REMIND: /' >> $TMP_FILE

#choose a line at random

LINE_COUNT=`wc -l "$TMP_FILE" | sed 's/ .*$//'`
SHOW_LINE=$(($RANDOM % $LINE_COUNT))
SHOW_LINE=$(($SHOW_LINE + 1))

cat $TMP_FILE | tail -n $SHOW_LINE | head -n 1

rm $TMP_FILE

You can see that adding new inputs to the rotator is trivial. I just have to append the lines to the temp file. I may patch GnuCash to spit out my net worth, and include that figure in the rotator. Would that be materialistic?

runRotator.sh - the daemon run from .xinitrc

#!/bin/sh

sendItem() {
        echo "0 widget_tell rotator `/home/erik/rotator/fetchItem.sh`" \
                | awesome-client
}

while true; do
        sendItem
        sleep 20
done

Finally, it's necessary to start the daemon when X starts, by launching it as a background process in the .xinitrc when I'm firing up awesome.

/home/erik/rotator/runRotator.sh &
exec awesome

A final note, I'm running Awesome 2.4. Awesome 3.0, I understand, changes the plug-in architecture, but as easy as this was to set up I'm not worried about making the upgrade.

Awesome users: Are there any productivity widgets you've used?