Steven Engelhardt

The following algorithms might be useful if you want to implement a spell checker (or Google-style “did you mean” feature):

• Levenshtein distance
• Jaro-Winkler distance
• N-gram

A reader-writer lock is a lock which will allow multiple concurrent readers but only one writer.  A reader-writer lock can be significantly more efficient than a standard mutex if reads on your shared memory far outnumber writes.

Reader-writer locks naturally fit together with caches, as caches are only effective if reads far outnumber writes.

Here is a general pattern for using a reader-writer lock with a cache:

1. Acquire a reader lock.
2. Check the cache for the value. If it exists, save the value and go to step 8.
3. Upgrade the reader lock to a writer lock.
4. Check the cache for the value. If it exists, save the value and go to step 7.
5. Calculate the value (expensive, otherwise we wouldn’t cache it)
6. Insert the value into the cache.
7. Release the writer lock.
8. Release the reader lock.
9. Return the value.

The reason why we have to check the cache for the value again in step (4) is because of the following possibility (assume step 4 doesn’t exist):

Thread 1                         Thread 2
============================     ===============================
- Acquire reader lock            - Acquire reader lock
- Check cache for value          - Check cache for value
  with key A (not found)           with key A (not found)
- Upgrade to writer lock         - (block)
- Calculate value (expensive)
- Insert value into cache
- Release writer lock
- Release reader lock
                                 - Upgrade to writer lock
                                 - Calculate value (expensive)
                                   (We are paying this cost
                                   twice)
                                 - Insert value into cache
                                   (We are inserting two values
                                   with the same key, which may
                                   be fatal)

With step 4 it becomes:

Thread 1                         Thread 2
============================     ===============================
- Acquire reader lock            - Acquire reader lock
- Check cache for value          - Check cache for value
  with key A (not found)           with key A (not found)
- Upgrade to writer lock         - (block)
- Calculate value (expensive)
- Insert value into cache
- Release writer lock
- Release reader lock
                                 - Upgrade to writer lock
                                 - Check cache for value
                                   with key A (found)
                                 - Release writer lock
                                 - Release reader lock
- Return value                   - Return value

When you are processing an HTTP request in ASP.NET you can retrieve the user-provided query string parameters using the HttpRequest.QueryString property.  This property is an instance of the NameValueCollection class.

If the user has provided multiple parameters with the same key in the query string, HttpRequest.QueryString[key] will return all the values concatenated together with commas.  If you would rather process the values individually, use HttpRequest.QueryString.GetValues(key), which will return an array of all the provided values.

For example:

URL: http://example.com?a=1&a=2
HttpRequest.QueryString["a"] = "1,2"
HttpRequest.QueryString.GetValues("a") = { "1", "2" }

I have released a pseudolocalization tool I wrote for 32-bit Windows resource DLLs here.

In the Windows XP login screen, the password text box will warn you with a balloon tooltip if you accidentally turn Caps Lock on:

The balloon tooltip appears to be a Windows tooltip common control with the TTS_BALLOON style.

To replicate this functionality, I decided to write a function called ShowMsgBalloon() which, given a control and the various balloon tooltip parameters, creates and shows the balloon tooltip below the control.

The key insight to making ShowMsgBallon() work as intended was to use the TTF_TRACK option to create a tracking tooltip. This will immediately show the tooltip without requiring the user to position the mouse over the control. The main downside to using TTF_TRACK is that the tooltip will not move with the control if the window is moved; you need to manually move the tooltip using TTM_TRACKPOSITION as required. One could probably make this automatic by subclassing the tooltip’s parent control and handling WM_WINDOWPOSCHANGED messages.

Here is the source code to ShowMsgBalloon(). When you are done with the balloon, call DestroyWindow() on the returned HWND. Note: you may want your application to use comctl32.dll version 6 as it will lead to a nicer visual style, including a close button.

Update 2008-11-01 3:08PM: If you are targeting comctl32.dll version 6 or later, I recommend using the EM_SHOWBALLOONTIP message.  Comctl32.dll version 6 or later also automatically shows the caps lock warning balloon for edit boxes with the ES_PASSWORD window style.

XPath is a language for selecting nodes from an XML document. XPath is used extensively in XSLT and other XML technologies. I also vastly prefer using XPath (e.g. with XPathNavigator) over the XML DOM when manipulating XML in a non-streaming fashion.

In XPath, strings must be delimited by either single or double quotes. Given a quote character used to delimit a string, one can’t represent that same quote character within the string. This means that if you decide to use single quotes to delimit your XPath string, you couldn’t represent the string O'Reilly; use double quotes, and you can’t represent "Hello".

However, given a quote delimiter, you can represent the other quote character. We can use this observation along with the concat XPath function to devise a general quoting rule for XPath strings. It’s easiest to show this via a series of examples:

Below is a piece of C++ code which implements these quotation rules:

Usage looks like:

If you ever have the need to represent a date/time (or part of a date/time) as a string for programmatic rather than human consumption (e.g. you are defining a save file format or a network protocol), please use ISO 8601 unless you have a very strong reason not to.

For more information, please read what the W3C has to say about ISO 8601 style date and time formats.

I recently received a bug report for my quick-and-dirty TCP debugging tool tcpconndbg where it was creating a large number of zombie processes. The person who filed the bug, Peter Viskup, was even kind enough to send a patch. While this is old news to anyone with extensive Unix programming experience, always remember the following:

If you create a child process using fork(), you must either:

1. Explicitly retrieve the child process’s exit code using one of the wait() functions (e.g. waitpid())
2. Tell the system that you aren’t interested in the child process’s exit code by using either:
   1. sigaction() with the SA_NOCLDWAIT parameter (preferred)
   2. signal(SIGCHILD, SIG_IGN); (for systems which do not support sigaction())

As I fixed this bug, I realized I hadn’t looked at tcpconndbg in 5 years. My how programming style changes…

Here is some quick-and-dirty SQL to calculate an geometric annual return (as a percent) from a column of monthly returns (in percents).

Update 2008-01-30 10:52PM: Here’s the equivalent “one-liner”:

While reading the Mandelbrot set chapter in Dewdney’s The New Turing Omnibus, I realized that this would be a great test application for Microsoft’s new interactive Web application framework Silverlight. Below is the component, its source code, and a few things I learned along the way.

Beware: the Mandelbrot set is computationally expensive and may appear to lock up your web browser. If a “Stop running this script?” dialog pops up, please click no to allow the calculations to finish.
Read the rest of this entry »