Sentinel value
Encyclopedia
In computer programming
, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) 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 be taken to signal the end of the data, prematurely.
Below are some examples of common sentinel values and their uses:
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.
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 of importance.
In safe languages, most uses of sentinel values could be replaced with option type
s, which enforce explicit handling of the exceptional case.
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) is a special value
Value (computer science)
In computer science, a value is an expression which cannot be evaluated any further . The members of a type are the values of that type. For example, the expression "1 + 2" is not a value as it can be reduced to the expression "3"...
whose presence guarantees termination of a loop
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
that processes structured
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
(especially sequential
Sequential access
In computer science, sequential access means that a group of elements is accessed in a predetermined, ordered sequence. Sequential access is sometimes the only way of accessing the data, for example if it is on a tape...
) data
Data (computing)
In computer science, data is information in a form suitable for use with a computer. Data is often distinguished from programs. A program is a sequence of instructions that detail a task for the computer to perform...
. 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 be taken to signal the end of the data, prematurely.
Below are some examples of common sentinel values and their uses:
- Null characterNull characterThe null character , abbreviated NUL, is a control character with the value zero.It is present in many character sets, including ISO/IEC 646 , the C0 control code, the Universal Character Set , and EBCDIC...
for indicating the end of a null-terminated stringNull-terminated stringIn computer programming, a null-terminated string is a character string stored as an array containing the characters and terminated with a null character... - Null pointer for indicating the end of a linked listLinked listIn computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
- A negative integer for indicating the end of a sequence of non-negative integers
- End-of-fileEnd-of-fileIn computing, end of file is a condition in a computer operating system where no more data can be read from a data source...
, 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
Inner loop
In computer programs, an important form of control flow is the loop. For example, this small pseudo-code program uses two nested loops to iterate over all the entries of an n×n matrix, changing their values so that the matrix becomes an identity matrix: for a in 1..n for b in 1..n ...
; 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.
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 of importance.
In safe languages, most uses of sentinel values could be replaced with option type
Option type
In programming languages and type theory, an option type or maybe type is a polymorphic type that represents encapsulation of an optional value; e.g. it is used as the return type of functions which may or may not return a meaningful value when they're applied...
s, which enforce explicit handling of the exceptional case.