computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...

, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) is a special

value Value or values may refer to: Ethics and social * Value (ethics) wherein said concept may be construed as treating actions themselves as abstract objects, associating value to them ** Values (Western philosophy) expands the notion of value beyo ...

in the context of an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

which uses its presence as a condition of termination, typically in a

loop Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...

or recursive algorithm. The sentinel value is a form of

in-band In telecommunications, in-band signaling is the sending of control information within the same band or channel used for data such as voice or video. This is in contrast to out-of-band signaling which is sent over a different channel, or even ...

data that makes it possible to detect the end of the data when no

out-of-band data In computer networking, out-of-band data is the data transferred through a stream that is independent from the main ''in-band'' data stream. An out-of-band data mechanism provides a conceptually independent channel, which allows any data sent via t ...

(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 (the semipredicate problem). A sentinel value is sometimes known as an " Elephant in Cairo," due to a joke where this is used as a physical sentinel. In safe languages, most sentinel values could be replaced with option types, which enforce explicit handling of the exceptional case.

Examples

Some examples of common sentinel values and their uses: *

Null character The null character (also null terminator) is a control character with the value zero. It is present in many character sets, including those defined by the Baudot and ITA2 codes, ISO/IEC 646 (or ASCII), the C0 control code, the Universal Coded Ch ...

for indicating the end of a

null-terminated string In computer programming, a null-terminated string is a character string stored as an array containing the characters and terminated with a null character (a character with a value of zero, called NUL in this article). Alternative names are C str ...

Null pointer In computing, a null pointer or null reference is a value saved for indicating that the pointer or reference does not refer to a valid object. Programs routinely use null pointers to represent conditions such as the end of a list of unknown leng ...

for indicating the end of a

linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which ...

or a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

. * A set

most significant bit In computing, bit numbering is the convention used to identify the bit positions in a binary number. Bit significance and indexing In computing, the least significant bit (LSB) is the bit position in a binary integer representing the binar ...

in a stream of equally spaced data values, for example, a set 8th bit in a stream of 7-bit

ASCII ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because ...

characters stored in 8-bit

byte The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable uni ...

s indicating a special property (like

inverse video Reverse video (or invert video or inverse video or reverse screen) is a computer display technique whereby the background and text color values are inverted. On older computers, displays were usually designed to display text on a black backgroun ...

boldface In typography, emphasis is the strengthening of words in a text with a font in a different style from the rest of the text, to highlight them. It is the equivalent of prosody stress in speech. Methods and use The most common methods in W ...

italics In typography, italic type is a cursive font based on a stylised form of calligraphic handwriting. Owing to the influence from calligraphy, italics normally slant slightly to the right. Italics are a way to emphasise key points in a printed t ...

) or the end of the stream * A negative integer for indicating the end of a sequence of non-negative integers

Variants

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. Unlike the above uses, this is not how the data is naturally stored or processed, but is instead an optimization, compared to the straightforward algorithm that checks for termination. This is typically used in searching. For instance, when searching for a particular value in an unsorted

list A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby unio ...

, 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 appending the value searched for to the end of the list, an unsuccessful search is no longer possible, and no explicit termination test is required in the inner loop; afterward, 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.

Examples

Array

For example, if searching for a value in an array in C, a straightforward implementation is as follows; note the use of a negative number (invalid index) to solve the semipredicate problem of returning "no result": int find(int arr[], size_t len, int val) However, this does two tests at each iteration of the loop: whether the value has been found and whether the end of the array has been reached. This latter test is what is avoided by using a sentinel value. Assuming the array can be extended by one element (without memory allocation or cleanup; this is more realistic for a linked list, as below), this can be rewritten as: int find(int arr[], size_t len, int val) The test for i < len is still present, but it has been moved outside the loop, which now contains only a single test (for the value), and is guaranteed to terminate due to the sentinel value. There is a single check on termination if the sentinel value has been hit, which replaces a test for each iteration. It is also possible to temporarily ''replace'' the last element of the array by a sentinel and handle it, especially if it is reached: int find(int arr[], size_t len, int val)

References

{{reflist Linked lists Trees (data structures)

Examples

Variants

Examples

Array

See also

References