Listing 1. Insert and Lock-Free Search

 1 struct el *insert(long key, long data)
 2 {
 3      struct el *p;
 4      p = kmalloc(sizeof(*p), GPF_ATOMIC);
 5      spin_lock(&mutex);
 6      p->next = head.next;
 7      p->key = key;
 8      p->data = data;
 9      smp_wmb();
10      head.next = p;
11      spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {
16      struct el *p;
17      p = head.next;
18      while (p != &head) {
19          /* BUG ON ALPHA!!! */
20          if (p->key == key) {
21               return (p);
22          }
23          p = p->next;
24      };
25      return (NULL);
26 }