Sentinels

Introduction

In this section, we discuss the use of sentinels, which are extra objects used to simplify the implementation of some module. Sentinel objects are not visible to the client of a module, so it is strictly a matter of implementation.

Sorted set with sentinels

It is easier to explain sentinels with an example. Recall the implementation of sorted set. The find function looked like this:
  static list *
  find(list *lp, void *e, int (*less)(void *, void *))
  {
    for(; *lp && less((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }
Notice that in the for-loop, the termination condition requires two tests, one for the end of the list, and another for testing the order between two elements. By using a sent, we will show how it is possible to avoid one of the tests. This makes the code faster, but it also simplifies it, thus making it more maintainable.

In other sections, we show more spectacular simplifications from using sentinels.

In the case of a sorted set, the sentinel we are going to use, is an extra element at the end of the list, which physically is, but conceptually is not part of the list. We thus have to take great care to preserve this difference between the conceptual and physical contents of the list.

Recall the implementation of the set itself and the create function:

  struct slset
  {
    int (*less)(void *, void *);
    list elements;
  };

  slset
  slset_create(int (*less(void *, void *)))
  {
    slset l = malloc(sizeof(struct slset));
    l -> elements = NULL;
    l -> less = less;
    return l;
  }
With a sentinel, we modify it thus:
  struct slset
  {
    int (*less)(void *, void *);
    void **sentinel;
    list elements;
  };

  slset
  slset_create(int (*less(void *, void *)))
  {
    slset l = malloc(sizeof(struct slset));
    l -> elements = cons(NULL, NULL);
    l -> less = less;
    l -> sentinel = &(l -> elements -> element);
    return l;
  }
Notice the additional field in the slset structure. It is a pointer to an object of type void *, so it is of type void **. The value of this field will be the pointer to the element field of the list cell containing the sentinel, as can be seen from the create function.

Now, let us see how we can avoid the first test in find.

  static list *
  find(void **sentinel, list *lp, void *e, int (*less)(void *, void *))
  {
    *sentinel = e;
    for(less((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }
Notice that we now give an additional argument to find, namely the value of the sentinel field of the set structure. The first statement of find stores the element to be searched for in the sentinel at the end of the list. After that statement, there is at least one object on the list that is not less than the one we search for, which in turn means that the expression less((*lp) -> element, e) must be false for at least one element on the list, namely the sentinel. We therefore no longer need to test for the end of the list.

Of course, now we have altered the conditions we have to test for in the routines that use find. The end of the list is no longer indicated by *lp == NULL as is tested in points_to. We have to modify it like this:

  static int
  points_to(void **sentinel, list *lp, void *e, int (*less)(void *, void *))
  {
    return &((*lp) -> element) != sentinel
           && equal((*lp) -> element, element, l -> less);
  }
Here we have to give it the sentinel so that we can check whether *lp is the last cell of the list, i.e., the one containing the sentinel. We check that by comparing the address of the element field of *lp to that of the sentinel. If they are identical, then we are at the end of the list.

Here is the complete code for the implementation:

  #include "slset.h"
  #include "list.h"
  #include < assert.h>
  #include < stdlib.h>

  struct slset
  {
    int (*less)(void *, void *);
    void **sentinel;
    list elements;
  };

  slset
  slset_create(int (*less(void *, void *)))
  {
    slset l = malloc(sizeof(struct slset));
    l -> elements = cons(NULL, NULL);
    l -> less = less;
    l -> sentinel = &(l -> elements -> element);
    return l;
  }

  static list *
  find(void **sentinel, list *lp, void *e, int (*less)(void *, void *))
  {
    *sentinel = e;
    for(less((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }

  static int 
  equal(void *e1, void *e2, int (*less)(void *, void *))
  {
    return !less(e1, e2) && !less(e2, e1);
  }

  static int
  points_to(void **sentinel, list *lp, void *e, int (*less)(void *, void *))
  {
    return &((*lp) -> element) != sentinel
           && equal((*lp) -> element, element, l -> less);
  }

  int
  slset_member(slset l, void *element)
  {
    list *lp = find(l -> sentinel, &(l -> elements), element, l -> less);
    return points_to(l -> sentinel, lp, element, l -> less);
  }

  void
  slset_insert(slset l, void *element)
  {
    list *lp = find(l -> sentinel, &(l -> elements), element, l -> less);
    assert(!points_to(l -> sentinel, lp, element, l -> less));
    *lp = cons(element, *lp);
  }

  void
  slset_delete(slset l, void *element)
  {
    list *lp = find(l -> sentinel, &(l -> elements), element, l -> less);
    assert(points_to(l -> sentinel, lp, element, l -> less));
    *lp = cdr_and_free(*lp);
  }
The only advantage we can claim with the sentinel in this case is faster code. We cannot really claim simplified code, since we had to add new arguments and make some functions more complicated. For that reason, we do not recommend using a sentinel for this simple a routine. But the example above illustrates the basic idea, and other modules can be greatly simplified by the use of sentinels.