Sentinel value

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer programming, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data)[1] is a special value whose presence guarantees termination of a loop that processes structured (especially sequential) data. The sentinel value makes it possible to detect the end of the data when no other means to do so (such as an explicit size indication) is provided. The value should be selected in such a way that it is guaranteed to be distinct from all legal data values, since otherwise the presence of such values would prematurely signal the end of the data.

Below are some examples of common sentinel values and their uses:

  • Null character for indicating the end of a null-terminated string
  • Null pointer for indicating the end of a linked list
  • A negative integer for indicating the end of a sequence of non-negative integers
  • End-of-file, a non-character value returned by certain input routines to signal that no further characters are available from a file
  • High Values, a key value of hexadecimal 0xFF used in business programming

A related practice, used in slightly different circumstances, is to place some specific value at the end of the data, in order to avoid the need for an explicit test for termination in some processing loop, because the value will trigger termination by the tests already present for other reasons. For instance, when searching for a particular value in an unsorted array, every element will be compared against this value, with the loop terminating when equality is found; however to deal with the case that the value should be absent, one must also test after each step for having completed the search unsuccessfully. By placing a copy of the value searched for in an additional slot after the end of the array, an unsuccessful search is no longer possible, and no explicit termination test is required in the inner loop; afterwards one must still decide whether a true match was found, but this test needs to be performed only once rather than at each iteration.[2] Knuth calls the value so placed at the end of the data a dummy value rather than a sentinel.

Sentinel values are often used when searching for something[clarification needed][why?] of importance.[3]

In safe languages, most uses of sentinel values could be replaced with option types, which enforce explicit handling of the exceptional case.

See also[edit]

Notes[edit]

  1. ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms (second edition). Addison-Wesley. pp. 213–214, also p. 631. ISBN 0-201-03809-9. 
  2. ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and searching. Addison-Wesley. p. 395. ISBN 0-201-03803-X. 
  3. ^ McConnell, Steve. "Code Complete" Edition 2 Pg. 621 ISBN 0-7356-1967-0