Content deleted Content added
Line 1:
'''Index mapping''' is a [[computer science]] term (also known as a "'''trivial hash function'''"<ref>http://en.wikipedia.org/wiki/Hash_function#Trivial_hash_function</ref>) that is used to describe the mapping of [[raw data]], used directly as in [[array index]], for an [[array data structure|array]]. The technique can be most effective for mapping data with a small range. If the array encompasses all combinations of input, a range check is not required.
==Applicable arrays==
In practise there are many examples of data exhibiting a small range of valid values all of which are suitable for processing using a trivial hash function including:
* month in the year (1-12) - see C example 1 and 2 below
* day in the month (1-31)
* day of the week (1-7)
* human lifespan (0-130) - eg. lifecover actuary tables, fixed term mortgage
* [[ASCII]] characters (0-256), encompassing:
:* common mathematical operator symbols (+-/*^)
:* common punctuation symbols (,.;:")
:* english uppercase language alphabet (A-Z)
:* english lowercase language alphabet (a-z)
:* numeric digits (0-9)
:* etc
* [[EBCDIC]] characters (0-256)
==Examples==
The following two examples demonstrate how a simple non-iterative table lookup, using a trivial hash function, can eliminate conditional testing & branching completely thereby reducing [[instruction path length]] significantly. Although both examples are shown here as functions, the required code would be better [[Inline expansion|inlining]] to avoid function call overhead in view of their obvious simplicity
===C example 1===▼
▲===C example===
This example<ref>[http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf "A Superoptimizer Analysis of Multiway Branch Code Generation"] by Roger Anthony Sayle</ref> of a C function - returning TRUE if a month (x) contains 30 days (otherwise FALSE), illustrates the concept succinctly
<source lang="c">
Line 10 ⟶ 24:
return T[x]; /* return with boolean 1 = true, 0=false */
</source>
===C example 2===
Example of another C function - incrementing a month number (x) by 1 and automatically resetting if greater than 12
<source lang="c">
static const int M[12] ={2,3,4,5,6,7,8,9,10,11,12,1}; /* 1-based table to increment x */
return M[x]; /* return with new month number */
</source>
==See also==
*[[Multiway branch]]
| |||