Pointer (computing)
From Wikipedia, the free encyclopedia
In computer science, a pointer is a programming language data type whose value refers directly to (or “points to”) another value stored elsewhere in the computer memory using its address. Obtaining the value to which a pointer refers is called dereferencing the pointer. A pointer is a simple implementation of the general reference data type (although it is quite different from the facility referred to as a reference in C++).
Pointers are so commonly used as references that sometimes people use the word “pointer” to refer to references in general; however, more properly it only applies to data structures whose interface explicitly allows it to be manipulated as a memory address. If you are seeking general information on a small piece of data used to find an object, see reference (computer science).
Contents |
[edit] Architectural roots
Pointers are a very thin abstraction on top of the addressing capabilities provided by most modern architectures. In the simplest scheme, an address, or a numeric index, is assigned to each unit of memory in the system, where the unit is typically either a byte or a word, effectively transforming all of memory into a very large array. Then, if we have an address, the system provides an operation to retrieve the value stored in the memory unit at that address.
In the usual case, a pointer is large enough to hold more different addresses than there are units of memory in the system. This introduces the possibility that a program may attempt to access an address which corresponds to no unit of memory, called a segmentation fault. On the other hand, some systems have more units of memory than there are addresses. In this case, a more complex scheme such as memory segmentation or paging is employed to use different parts of the memory at different times.
In order to provide a consistent interface, some architectures provide memory-mapped I/O, which allows some addresses to refer to units of memory while others refer to device registers of other devices in the computer. There are analogous concepts such as file offsets, array indices, and remote object references that serve some of the same purposes as addresses for other types of objects.
[edit] Uses
Pointers are directly supported without restrictions in C, C++, Pascal and most assembly languages. They are primarily used for constructing references, which in turn are fundamental to constructing nearly all data structures, as well as in passing data between different parts of a program.
In functional programming languages that rely heavily on lists, pointers and references are managed abstractly by the language using internal constructs like cons.
When dealing with arrays, the critical lookup operation typically involves a stage called address calculation which involves constructing a pointer to the desired data element in the array. In other data structures, such as linked lists, pointers are used as references to explicitly tie one piece of the structure to another.
Pointers are used to pass parameters by reference. This is useful if we want a function's modifications to a parameter to be visible to the function's caller. This is also useful for returning multiple values from a function.
Below is an example of the definition of a linked list in C; this is not possible in C without pointers.
/* the empty linked list is
* represented by NULL or some
* other signal value */
#define EMPTY_LIST NULL
struct link {
/* the data of this link */
void *data;
/* the next link; EMPTY_LIST if this is the last link */
struct link *next;
};
Note that this pointer-recursive definition is essentially the same as the reference-recursive definition from the Haskell programming language:
data Link a = Nil
| Cons a (Link a)
Nil is the empty list, and Cons a (Link a) is a cons cell of type a with another link also of type a.
The definition with references, however, is type-checked and doesn't use potentially confusing signal values. For this reason, data structures in C are usually dealt with via wrapper functions, which are carefully checked for correctness.
Arrays in C are just pointers to consecutive areas of memory. Thus:
#include <stdio.h>
int main() {
int array[5] = { 2, 4, 3, 1, 5 };
/* print the address of the array */
printf("%p\n", (void *)array);
/* print the first item of the array, 2 */
printf("%d\n", array[0]);
/* print the first integer at the address
* pointed to by array; this is the first
* item, 2 */
printf("%d\n", *array);
/* print the fourth item of the array, 1 */
printf("%d\n", array[3]);
/* print the third address past array
* which may be six, twelve or twenty four
* bytes past the start of the array,
* depending on the memory model */
printf("%p\n", (void *)(array + 3));
/* print the value at the address just
* printed this is the fourth item, 1 */
printf("%d\n", *(array+3));
/* Due to C's syntax, this is equivalent
* to array[3] and will print 1 */
printf("%d\n", 3[array] );
return 0;
}
This activity is called pointer arithmetic: direct arithmetic operations on pointers are used to index arrays. See below for more detail.
Pointers can be used to pass variables by reference, allowing their value to be changed. For example:
#include <stdio.h>
void alter(int *n) {
*n = 120;
}
int main() {
int x = 24;
/* the '&' operator (read "reference") retrieves
* the address of a variable */
int *address = &x;
/* show x */
printf("%d\n", x);
/* show x's address */
printf("%p\n", (void *)address);
/* pass x's address to alter, x is passed "by reference" */
alter(&x);
/* show x's new value */
printf("%d\n", x);
/* notice that x's address is not altered */
printf("%p %p\n", (void *)address, (void *)&x);
return 0;
}
Lastly, on some computing architectures, pointers can be used to directly manipulate memory or memory mapped devices. In the mid 80's, using the BIOS to access the video capabilities of PCs was slow. Applications that were display-intensive typically used to access CGA video memory directly by casting the hexadecimal constant 0xB8000000 to a pointer to an array of 80 unsigned 16-bit int values. Each value consisted of an ASCII code in the low byte, and a colour in the high byte. Thus, to put the letter 'A' at row 5, column 2 in bright white on blue, one would write code like the following:
#define VID ((unsigned (*)[80])0xB8000000)
void foo() {
VID[4][1] = 0x1F00 | 'A';
}
[edit] Typed pointers and casting
In many languages, pointers have the additional restriction that the object they point to has a specific type. For example, a pointer may be declared to point to an integer; the language will then attempt to prevent the programmer from pointing it to objects which are not integers, such as floating-point numbers, eliminating some errors.
In languages that allow pointer arithmetic, arithmetic on pointers take into account the size of the type. For example, adding an integer to a pointer produces another pointer that points to an address that is higher by that number times the size of the type. This allows us to easily compute the address of elements of an array of a given type.
However, few languages strictly enforce pointer types, because programmers often run into situations where they want to treat an object of one type as though it were of another type. For these cases, it is possible to typecast, or cast, the pointer. Some casts are always safe, while other casts are dangerous, possibly resulting in incorrect behavior. Although it's impossible in general to determine at compile-time which of these casts are safe, some languages store run-time type information which can be used to confirm that these dangerous casts are valid at runtime. Other languages merely accept a conservative approximation of safe casts, or none at all.
[edit] Making pointers safer
Because pointers allow a program to access objects that are not explicitly declared beforehand, they enable a variety of programming errors. However, the power they provide is so great that it can be difficult to do some programming tasks without them. To help deal with their problems, many languages have created objects that have some of the useful features of pointers, while avoiding some of their pitfalls.
One major problem with pointers is that, as long as they can be directly manipulated as a number, they can be made to point to unused addresses or to data which is being used for other purposes. Many languages, including most functional programming languages and recent imperative languages like Java, replace pointers with a more opaque type of reference, typically referred to as simply a reference, which can only be used to refer to objects and not manipulated as numbers, preventing this type of error. Array indexing is handled as a special case.
A pointer which does not have any address assigned to it is called a wild pointer. Any attempt to use such uninitialized pointers can cause unexpected behaviour, either because the initial value is not a valid address, or because using it may damage the runtime system and other unrelated parts of the program.
In systems with explicit memory allocation, it's possible to create a dangling pointer by deallocating the memory region it points into. This type of pointer is dangerous and subtle, because a deallocated memory region may contain the same data as it did before it was deallocated, but may be then reallocated and overwritten by unrelated code, unbeknownst to the earlier code. Languages with garbage collection prevent this type of error.
Some languages, like C++, support smart pointers, which use a simple form of reference counting to help track allocation of dynamic memory in addition to acting as a reference. In the absence of reference cycles, where an object refers to itself indirectly through a sequence of smart pointers, these eliminate the possibility of dangling pointers and memory leaks.
[edit] The null pointer
A null pointer has a reserved value, often but not necessarily the value zero, indicating that it refers to no object. Null pointers are used routinely, particularly in C and C++ where the compile time constant NULL is used, to represent exceptional conditions such as the lack of a successor to the last element of a linked list, while maintaining a consistent structure for the list nodes. This use of null pointers can be compared to the use of null values in relational databases and to the “Nothing” value in the “Maybe” monad. In C, each pointer type has its own null value, and sometimes they have different representations.
Because it refers to nothing, an attempt to dereference a null pointer can cause a run-time error that usually terminates the program immediately (in the case of C, often with a segmentation fault, since the address literally corresponding to the null pointer will likely not be allocated to the running program). In Java, access to a null reference triggers a Java.lang.NullPointerException, which can be caught (but a common practice is to attempt to ensure such exceptions never occur). In safe languages a possibly null pointer can be replaced with a tagged union which enforces explicit handling of the exceptional case; in fact, a possibly-null pointer can be seen as a tagged union with a computed tag.
A null pointer should not be confused with an uninitialized pointer: a null pointer is guaranteed to compare unequal to a pointer to any object or function, whereas an uninitialized pointer might have any value. Two separate null pointers are guaranteed to compare equal and ANSI C guarantees that any NULL pointer will be equal to 0 in a comparison.
malloc returns a NULL pointer if it is unable to allocate the memory region requested as a way of signalling to the caller that there is insufficient memory available. Some implementations of malloc allow malloc(0) to return a NULL pointer as a successful allocation and will both return NULL and set errno if the malloc failed.
[edit] Wild pointers
Wild pointers are pointers that have not been initialized (that is, set to point to a valid address) and may make a program crash or behave oddly. In the Pascal or C programming languages, pointers that are not specifically initialized may point to unpredictable addresses in memory.
The following example code shows a wild pointer:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
/* (undefined) value of some place on the heap */
char *p1 = malloc();
/* wild (uninitialized) pointer */
char *p2;
/* undefined value, may not be a valid address */
printf("Address of p2: %p\n", (void *)p2);
/* random value at random address.
* if you are LUCKY, this will cause an addressing exception */
printf("Value of *p2: %c\n", *p2);
return 0;
}
The problems with invalid pointers include more than simply uninitialized values.
For instance, pointers can be used after the object or variable they point to no longer exists, or has gone out of scope, as in the example below. If such an invalid pointer is used, the program will probably not immediately crash, but the result will still probably be incorrect, and the failure will probably be hard to track down.
#include <stdio.h>
#include <stdlib.h>
/* p is a pointer to a pointer to an int */
int badIdea(int **p)
{
/* allocate an int on the stack */
int x = 1;
/* assign value of x to int that pointer p points to */
**p = x;
/* make the pointer that p points to point to x */
*p = &x;
/* after return x is out of scope and undefined */
return x;
}
int main(void)
{
int y = 0;
/* initialize pointer to y */
int *p1 = &y;
/* a good habit to form */
int *p2 = NULL;
/* prints address of y */
printf("Address of p1: %p\n", p1);
/* prints value of y */
printf("Value of *p1: %d\n", *p1);
/* changes y and changes p1 */
y = badIdea(&p1);
/* p1 now points to where x was
* The place where x was will get clobbered,
* for instance, on the next interrupt, or on
* the next subroutine call, as below.... */
/* some other code that also uses the stack */
p2 = malloc(5 * sizeof *p2);
/* this probably will NOT crash,
* but value printed is unpredictable */
/* prints value of where x was */
printf("Value of *p1: %p\n", *p1);
return 0;
}
A very common problem is using a pointer to the heap after that memory has been deallocated, as in this example. The invalid copies of the pointer are usually much harder to find than here.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
/* initialize pointer to heap */
int *p1 = malloc(sizeof *p1);
/* make a copy */
int *p2 = p1;
/* initialize the heap */
*p1 = 0;
/* points into the heap */
printf("Address of p2: %p\n", (void *)p2);
/* should print zero */
printf("Value of *p2: %d\n", *p2);
/* deallocate the memory */
free(p1);
/* other code, possibly using the heap */
....
/* p2 still points to the original allocation,
* but who knows what is there */
printf("Value of *p2: %d\n", *p2);
/* invalid use of p2 */
return 0;
}
A third way that pointers can be misused is to access outside the data structure they point to. Here is a simple example.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
/* create a variable */
int y = 5;
/* initialize pointer to y */
int *p1 = &y;
/* address of y */
printf("Address of p1: %p\n", (void *)p1);
/* value of y */
printf("Value of *p1: %d\n", *p1);
/* allowed pointer arithmetic */
p1 = p1 + y;
/* p1 no longer points to y */
printf("Value of *p1: %d\n", *p1);
return 0;
}
If a pointer is used to write beyond the end of a local buffer, the stack can be destroyed. In the case below, the problem will probably manifest when the main program returns because the x86 architecture stores a procedure's caller return address in the stack.
#include <stdio.h>
#include <stdlib.h>
/* copy source to destination, no check on sizes */
void strcopy(char *d, char *s)
{
/* copy until '\0' encountered */
while (*d++ = *s++)
;
}
int main(void)
{
/* create a local buffer */
char y[3];
/* another buffer on heap */
char *p1 = malloc(10 * sizeof *p1);
/* terminate the larger buffer */
p1[9] = '\0';
/* overflow the local buffer */
strcopy(y, p1);
free(p1);
return 0;
/* now bad stuff happens */
}
[edit] Double indirection
In C, it is possible to have a pointer point at another pointer. This can make manipulating certain data structures particularly neat and elegant. For instance: consider this code to insert an item into a simple linked list
struct element {
struct element *next;
int value;
};
struct element *head = null;
void insert(struct element *item) {
for(struct element **p = &head; *p!=null; p = &(*p)->next) {
if(item.value <= (*p)->value) {
break;
}
}
item.next = *p;
*p->next = item;
}
[edit] Support in various programming languages
A number of languages support some type of pointer, although some are more restricted than others. If a pointer is significantly abstracted, such that it can no longer be manipulated as an address, the resulting data structure is no longer a pointer; see the more general reference article for more discussion of these.
[edit] Ada
Ada is a strongly typed language where all pointers are typed and only safe type conversions are permitted. All pointers are by default initialized to null, and any attempt to access data through a null pointer causes an exception to be raised. Pointers in Ada are called access types. Ada 83 did not permit arithmetic on access types (although many compiler vendors provided for it as a non-standard feature), but Ada 95 supports “safe” arithmetic on access types via the package System.Storage_Elements.
[edit] C and C++
In C and C++ pointers are variables that store addresses and can be null. Each pointer has a type it points to, but one can freely cast between pointer types. A special pointer type called the “void pointer” points to an object of unknown type and cannot be dereferenced. The address can be directly manipulated by casting a pointer to and from an integer.
C++ fully supports C pointers and C typecasting. It also supports a new group of typecasting operators to help catch some unintended dangerous casts at compile-time. The C++ standard library also provides auto ptr, a sort of smart pointer which can be used in some situations as a safe alternative to primitive C pointers. C++ also supports another form of reference, quite different from a pointer, called simply a reference or reference type.
Pointer arithmetic, that is, the ability to modify a pointer's target address with arithmetic operations, is unrestricted: adding or subtracting from a pointer moves it by a multiple of the size of the datatype it points to. For example, adding 1 to a pointer to 4-byte integer values will increment the pointer by 4. This has the effect of incrementing the pointer to point at the next element in a contiguous array of integers -- which is often the intended result. Pointer arithmetic cannot be performed on void pointers because the void type has no size, and thus the pointed address can not be added to.
Pointer arithmetic provides the programmer with a single way of dealing with different types: adding and subtracting the number of elements required instead of the actual offset in bytes. In particular, the C definition explicitly declares that the syntax a[n], which is the n-th element of the array a, is equivalent to *(a+n), which is the content of the element pointed by a+n.
While powerful, pointer arithmetic can be a source of computer bugs. It tends to confuse novice programmers, forcing them into different contexts: an expression can be an ordinary arithmetic one or a pointer arithmetic one, and sometimes it is easy to mistake one for the other. In response to this, many modern high level computer languages (for example Java) do not permit direct access to memory using addresses. Also, the safe C dialect Cyclone addresses many of the issues with pointers. See C programming language for more criticism.
The void pointer, or void*, is supported in ANSI C and C++ as a generic pointer type . A pointer to void can store an address to any data type, and, in C, is automatically casted to any other pointer type on assignment, but it must be explicitly casted if dereferenced inline. K&R C used char* for the “type-agnostic pointer” purpose.
int x = 4; void* q = &x; int* p = q; /* void* automatically casted to int*: valid C, but not C++ */ int i = *p; int j = *((int*)c); /* when dereferencing inline, there is no automatic casting */
C++ does not allow the automatic casting of void* to other pointer types, not even in assignments. This was a design decision to avoid careless and even unintended casts, though most compilers only output warnings, not errors, when encountering other ill casts.
int x = 4; void* q = &x; // int* p = q; // This fails in C++: there is no autocast from void* int* a = (int*)q; // C-style cast int* b = static_cast<int*>(q); // C++ cast
In C++, there is no void& (reference to void) to complement void* (pointer to void), because references behave like aliases to the variables they point to, and there can never be a variable whose type is void.
[edit] C#
In the C# programming language, pointers are supported only under certain conditions: any block of code including pointers must be marked with the unsafe keyword. Such blocks usually require higher security permissions than pointerless code to be allowed to run. The syntax is essentially the same as in C++, and the address pointed can be either managed or unmanaged memory. However, pointers to managed memory (any pointer to a managed object) must be declared using the fixed keyword, which prevents the garbage collector from moving the pointed object as part of memory management while the pointer is in scope, thus keeping the pointer address valid.
The .NET framework includes many classes and methods in the System and System.Runtime.InteropServices namespaces (such as the Marshal class) which convert .NET types (for example, System.String) to and from many unmanaged types and pointers (for example, LPWSTR or void*) to allow communication with unmanaged code.
[edit] D
The D programming language is a derivative of C and C++ which fully supports C pointers and C typecasting. However D also offers numerous constructs such as foreach loops, out function parameters, reference types, and advanced array handling which replace pointers for most routine programming tasks.
[edit] Fortran
Fortran-90 introduced a strongly-typed pointer capability. Fortran pointers contain more than just a simple memory address. They also encapsulate the lower and upper bounds of array dimensions, strides (for example, to support arbitrary array sections), and other metadata. An association operator, => is used to associate a POINTER to a variable which has a TARGET attribute. The Fortran-90 ALLOCATE statement may also be used to associate a pointer to a block of memory. For example, the following code might be used to define and create a linked list structure:
type real_list_t
real :: sample_data(100)
type (real_list_t), pointer :: next => null ()
end type
type (real_list_t), target :: my_real_list
type (real_list_t), pointer :: real_list_temp
real_list_temp => my_real_list
do
read (1,iostat=ioerr) real_list_temp%sample_data
if (ioerr /= 0) exit
allocate (real_list_temp%next)
real_list_temp => real_list_temp%next
end do
Fortran-2003 adds support for procedure pointers. Also, as part of the C Interoperability feature, Fortran-2003 also supports a intrinsic functions for converting C-style pointers into Fortran pointers and back.
[edit] Modula-2
Pointers are implemented very much as in Pascal, as are VAR parameters in procedure calls. Modula 2 is even more strongly typed than Pascal, with fewer ways to escape the type system. Some of the variants of Modula 2 (such as Modula-3) include garbage collection.
[edit] Oberon
Much as with Modula-2, pointers are available. There are still fewer ways to evade the type system and so Oberon and its variants are still safer with respect to pointers than Modula-2 or its variants. As with Modula-3, garbage collection is a part of the language specification.
[edit] Pascal
Pascal implements pointers in a straightforward, limited, and relatively safe way. It helps catch mistakes made by people who are new to programming, like dereferencing a pointer into the wrong datatype; however, a pointer can be cast from one pointer type to another. Pointer arithmetic is unrestricted; adding or subtracting from a pointer moves it by that number of bytes in either direction, but using the Inc or Dec standard procedures on it moves it by the size of the datatype it is declared to point to. Trying to dereference a null pointer, named nil in Pascal, or a pointer referencing unallocated memory, raises an exception in protected mode. Parameters may be passed using pointers (as VAR parameters) but are automatically handled by the runtime system.
[edit] See also
- Buffer overflow
- Hazard pointer
- Opaque pointer
- Pointer swizzling
- Reference (computer science)
- Static code analysis
- Bounded pointer
[edit] External links
- Pointer Fun With Binky Introduction to pointers in a 3 minute educational video - Stanford Computer Science Education Library (this link has crashed some browsers – use with caution)
- 0pointer.de A terse list of minimum length source codes that dereference a null pointer in several different programming languages
- A tutorial in C Pointers and Arrays by Ted Jensen
