I'm a consultant and I review code at a variety of customers. This one came from an embedded Linux system. They had an event queue in the system that checked a sorted linked list to see if it was time to fire an event. Events would get put on the queue with their time and a callback to invoke at that time. Each interval, the queue manager would wake up, see if it was time to do the top element(s) of the queue, and then go back to sleep. The joy was in the implementation of the linked list that served as their queue.
In an effort to save space (I suppose), it was a singly linked list. The insert() code did the intuitive thing. It put the event in the right part of the queue, based on its timestamp. Perhaps a little ASCII art would help (it's certainly appropriate to the genre):
+---+ +---+ +---+
| A |+|--->| B |+|--->| C |+|--+
+---+ +---+ +---+ v
The search routine, however, had to take into account the fact that it wasn't a doubly-linked list (i.e. with back pointers from each node). If you wanted to delete the event that you found (the most common reason for searching the linked list), you would need to have the thing that pointed at the thing you wanted to delete. Follow me? If I A links to B, and I want to delete B, I need a pointer to A. Thus, the search routine returned "the thing that points at the thing that matches your search"! search(C) would return B. There are a couple of caveats. If the thing you want isn't found, search() returns NULL. If the thing you want was actually the first element of the list, it returned the first element of the list; search(A) returned A. All the event code was aware of this unusual way of doing things.
The delete() routine, naturally, was aware of the shenanigans going on in search(). If you passed a pointer to an event to delete(), it would actually delete the object pointed to by the object you passed. delete(B) would have the effect of removing C from the list. Likewise, if you passed it A, and it knew that A was the head of the list, it deleted A. Silly, but it matches the search() behavior. Figured it out yet?
What if the thing you wanted to delete was the second thing in the list? You would do search(B), which returned A. Then you pass A to delete(). Delete() sees that you've passed A, which is the head of the list, so it deletes A. This has the glorious effect of:
- Deleting the next event to fire, which you probably DID want
- Leaving the second event on the list, which is the one you DIDN'T want