L·.:~;.
`
`·· - -
`
`·:; - ·.:.
`
`;::,.: ... ·- ··-· :-
`
`· SECOND EDITION
`
`•.• .:.·. -=:-: .• ·::: .. :-;=. -· -;·;:·.:-:·.: ... : .-:· . .. - ···-· ..
`
`. ' • .. """;.""::
`
`• THE
`
`PRENTICE HALL SOFTWARE SERIES
`
`ServiceNow's Exhibit No. 1004
`
`001
`
`

`
`Ubnry of Conpeta CataloJinl-in-PubUcation Data
`
`Kernighan, Brian W.
`The C programming language.
`Includes index.
`1. C (Computer program language)
`Dennis M.
`II. Title.
`QA76.73.C15K47 1988
`005.13'3
`ISBN 0-13-110370-9
`ISBN 0-13-110362-8 (pbk.)
`
`I. Ritchie,
`
`88-5934
`
`Copyriaht o 1988, 1978 by BeU Telephone Laboratories, Incorporated.
`
`C Publiahed by Prentice Hall P T R
`Prenti~·Hall. Inc.
`Upper Saddle River, NJ 07458
`
`All riahts reserved. No part of this publication may be reproduced, stored in a retrieval
`system, or transmitted, in any form or by any means, electronic, mechanical, photocopy·
`ina, record ina, or otherwise, without the prior written permission of the publisher.
`Printed in the United States of America. Published simultaaeously in Canada.
`
`UNIX is a rqistercd trademark of ATclT.
`
`This book was typeset (pic I tbll eqn I troff -aa) in Times Roman and Courier by
`the authors, using an Autolosic APS·S phototypesetter and a DEC VAX 8SSO runnina
`the 9th Edition of the UNIX• operatins system.
`
`Prentice Hall Software Series
`Brian Kernighan, Advisor
`
`ISBN 0-13-110362-8
`Text printed in the United States on recycled paper at Courier in Westford,
`Massachusetts.
`Fifty-Second Printing, February 2014
`
`ISBN
`ISBN
`
`O-l.3-l.l.D3b2-&
`0-1.3-110370-,
`
`{PBK}
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall of Canada, Inc., Toronto
`Prentice-Hall Hispanoamericana, S. A., Mexico
`Prentice-Hall oflndia Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Prentice-Hall Asia Pte. Ltd., Singapore
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`ServiceNow's Exhibit No. 1004
`
`002
`
`

`
`Preface
`
`Preface to tbe First Editioa
`
`Introduction
`
`Chapter 1. A Tutorial Introduction
`1.1 Getting Started
`1.2 Variables and Arithmetic Expressions
`1.3 The For Statement
`1.4 Symbolic Constants
`1.5 Character Input and Output
`1.6 Arrays
`1.7 Functions
`1.8 Arguments-Call by Value
`1.9 Character Arrays
`1.10 External Variables and Scope
`
`Chapter l. Types, Operators, and Expressions
`2.1 Variable Names
`2.2 Data Types and Sizes
`2.3 Constants
`2.4 Declarations
`2.5 Arithmetic Operators
`2.6 Relational and Logical Operators
`2.7 Type Conversions
`2.8
`Increment and Decrement Operators
`2.9 Bitwise Operators
`2.10 Assignment Operators and Expressions
`2.11 Conditional Expressions
`2.12 Precedence and Order of Evaluation
`
`Chapter 3. Control Flow
`3.1 Statements and Blocks
`3.2
`If-Else
`
`Contents
`
`ix
`
`xi
`
`1
`
`5
`5
`8
`13
`14
`15
`22
`24
`27
`28
`31
`
`3S
`35
`36
`37
`40
`41
`41
`42
`46
`48
`50
`51
`52
`
`55
`55
`55
`
`ServiceNow's Exhibit No. 1004
`
`003
`
`

`
`Yi
`
`THE C PROGRAMMING LANGUAGE
`
`CONTENTS
`
`3.3 Else-If
`3.4 Switch
`3.5 Loops-While and For
`3.6 Loops-Do-while
`3.7 Break and Continue
`3.8 Goto and Labels
`
`Chapter 4. Fuactions and Program Structure
`4.1 Basics of Functions
`4.2 Functions Returning Non-integers
`4.3 External Variabl~
`4.4 Scope Rules
`4.5 Header Files
`4.6 Static Variables
`4.7 Register Variables
`4.8 Block Structure
`4.9
`Initialization
`4.10 Recursion
`4.11 The C Preprocessor
`
`Chapter 5. Pointers and Arrays
`5.1 Pointers and Addresses
`5.2 Pointers and Function Arguments
`5.3 Pointers and Arrays
`5.4 Address Arithmetic
`5.5 Character Pointers and Functions
`5.6 Pointer Arrays; Pointers to Pointers
`5.7 Multi-dimensional Arrays
`5.8
`Initialization of Pointer Arrays
`5.9 Pointers vs. Multi-dimensional Arrays
`5.10 Command-line Arguments
`5.ll Pointers to Functions
`5.12 Complicated Declarations
`
`Cllapter 6. Stnactures
`6.1 Basics of Structures
`6.2 Structures and Functions
`6.3 Arrays of Structures
`6.4 Pointers to Structures
`6.5 Self -referential Structures
`6.6 Table Lookup
`6.7 Typedef
`6.8 Unions
`6.9 Bit-fields
`
`Cllapter 7. lnptlt aad Output
`7.1 Standard Input and Output
`7.2 Formatted Output-Printf
`
`57
`58
`60
`63
`64
`65
`
`67
`67
`71
`73
`80
`81
`83
`83
`84
`85
`86
`88
`
`93
`93
`95
`97
`100
`104
`107
`llO
`113
`113
`114
`118
`122
`
`127
`127
`129
`132
`136
`139
`143
`146
`147
`149
`
`151
`151
`153
`
`ServiceNow's Exhibit No. 1004
`
`004
`
`

`
`THE C PROGRAMMING LANGUAGE
`
`CONTENTS
`
`vii
`
`7.3
`7.4
`7.5
`7.6
`7.7
`7.8
`
`Variable-length Argument Lists
`Formatted Input-Scanf
`File Access
`Error Handling-Stderr and Exit
`Line Input and Output
`Miscellaneous Functions
`
`Cbapter 8.
`8.1
`8.2
`8.3
`8.4
`8.5
`8.6
`8.7
`
`T be UNIX System Interface
`File Descriptors
`Low Level I/O-Read and Write
`Open, Creat, Close, Unlink
`Random Access-Lseek
`Example-An Implementation of Fopen and Getc
`Example- Listing Directories
`Example-A Storage Allocator
`
`Appendix A. Reference Manual
`A1
`Introduction
`A2 Lexical Conventions
`A3 Syntax Notation
`A4 Meaning of Identifiers
`A S Objects and Lvalues
`A6 Conversions
`A 7 Expressions
`A8 Declarations
`A9 Statements
`AI 0 External Declarations
`A 11 Scope and Linkage
`A 12 Preprocessing
`Al3 Grammar
`
`Appendix B. Standard Library
`Bl
`Input and Output: <stdio.h>
`B2 Character Class Tests: <ctype.h>
`B3
`String Functions: <string.h>
`B4 Mathematical Functions: <math.h >
`B5 Utility Functions: <stdlib.h>
`B6 Diagnostics: <assert.h>
`B7 Variable Argument Lists: <stdarg.h >
`B8 Non-local Jumps: <setjmp.h>
`B9
`Signals: <signal.h>
`B 10 Date and Time Functions: < time.h >
`Bt l
`Implementation-defined Limits: <limits.h> and <float.h>
`
`Appendix C. Summary of Changes
`
`Index
`
`155
`157
`160
`163
`164
`166
`
`169
`169
`170
`172
`174
`175
`179
`185
`
`191
`191
`191
`194
`195
`197
`197
`200
`210
`222
`225
`227
`228
`234
`
`241
`241
`248
`249
`250
`251
`253
`254
`254
`255
`255
`257
`
`259
`
`263
`
`ServiceNow's Exhibit No. 1004
`
`005
`
`

`
`Introduction
`
`C is a general-purpose programming language. It has been closely associ(cid:173)
`ated with the UNIX system where it was developed, since both the system and
`most of the programs that run on it are written in C. The language, however, is
`not tied to any one operating system or machine; and although it has been
`called a "system programming language" because it is useful for writing com(cid:173)
`pilers and operating systems, it has been used equally well to write major pro(cid:173)
`grams in many different domains.
`Many of the important ideas of C stem from the language BCPL, developed
`by Martin Richards. The influence of BCPL on C proceeded indirectly through
`the language B, which was written by Ken Thompson in 1970 for the first
`UNIX system on the DEC PDP-7.
`BCPL and B are "typeless" languages. By contrast, C provides a variety of
`data types. The fundamental types are characters, and integers and floating(cid:173)
`point numbers of several sizes. In addition, there is a hierarchy of derived data
`types created with pointers, arrays, structures, and unions. Expressions are
`formed from operators and operands; any expression, including an assignment or
`a function call, can be a statement. Pointers provide for machine-independent
`address arithmetic.
`C provides the fundamental control-flow constructions required for well(cid:173)
`structured programs: statement grouping, decision making (if-else), selecting
`one of a set of possible cases (switch), looping with the termination test at the
`top (while, for) or at the bottom (do) , and early loop exit (break).
`Functions may return values of basic types, structures, unions, or pointers.
`Any function may be called recursively. Local variables are typically
`"automatic," or created anew with each invocation. Function definitions may
`not be nested but variables may be declared in a block-structured fashion. The
`functions of a C program may exist in separate source files that are compiled
`separately. Variables may be internal to a function, external but known only
`within a single source file, or visible to the entire program.
`A preprocessing step performs macro substitution on program text, inclusion
`of other source files, and conditional compilation.
`
`C is a relatively "low level" language. This characterization is not
`
`ServiceNow's Exhibit No. 1004
`
`006
`
`

`
`l
`
`lNTRODUCfiON
`
`pejorative; it simply means that C deals with the same sort of objects that most
`computers do, namely characters, numbers, and addresses. These may be com(cid:173)
`bined and moved about with the arithmetic and logical operators implemented
`by real machines.
`C provides no operations to deal directly with composite objec~ such as
`character strings, sets, lists, or arrays. There are no operations that manipulate
`an entire array or string, although structures may be copied as a u~it. The
`language does not define any storage allocation facility other than static defini(cid:173)
`tion and the stack discipline provided by the local variables of functions; there is
`no heap or garbage collection. Finally, C itself provides no input/output facili(cid:173)
`ties; there are no READ or WRITE statements, and no built-in file access
`methods. All of these higher-level mechanisms must be provided by explicitly(cid:173)
`called functions. Most C implementations have included a reasonably standard
`collection of such functions.
`Similarly, C offers only straightforward, single-thread control flow: tests,
`loops, grouping, and subprograms, but not multiprogramming, parallel opera(cid:173)
`tions, synchronization, or coroutines.
`Although the absence of some of these features may seem like a grave defi(cid:173)
`ciency ("You mean I have to call a function to compare two character
`strings?"), keeping the language down to modest size has real benefits. Sin~ C
`is relatively small, it can be described in a small space, and learned quickly. A
`programmer . can reasonably expect to know and understand and indeed regu(cid:173)
`larly use the entire language.
`
`For many years, the defmition of C was the reference manual in the first
`edition of The C Programming Language. In 1983, the American National
`Standards Institute (ANSI) established a committee to provide a modern,
`comprehensive definition of C. The resulting definition, the ANSI standard, or
`"ANSI C," was completed late in 1988. Most of the features of the standard
`are already supported by modern compilers.
`The standard is based on the original reference manual. The language is
`relatively little changed; one of the goals of the standard was to make sure that
`most existing programs would remain valid, or, failing that, that compilers could
`produce warnings of new behavior.
`For most programmers, the most important change is a new syntax for
`declaring and defining functions. A function declaration can now include a
`description of the arguments of the function; the definition syntax changes to
`match. This extra information makes it much easier for compilers to detect
`errors caused by mismatched arguments; in our experience, it is a very useful
`addition to the language.
`There are other small-scale language changes. Structure assignment and
`enumerations, which had been widely available, are now officially part of the
`language. Floating-point computations may now be done in single precision.
`The properties of arithmetic, especially for unsigned types, are clarified. The
`preprocessor is more elaborate. Most of these changes will have only minor
`
`ServiceNow's Exhibit No. 1004
`
`007
`
`

`
`THE C PROGRAMMING LANGUAGE
`
`3
`
`effects on most programmers.
`A second significant contribution of the standard is the definition of a library
`to accompany C. It specifies functions for accessing the operating system (for
`instance, to read and write files), formatted input and output, memory alloca(cid:173)
`tion, string manipulation, and the like. A collection of standard headers pro(cid:173)
`vides uniform access to declarations of functions and data types. Programs that
`use this library to interact with a host system are assured of compatible
`behavior. Most of the library is closely modeled on the "standard 1/0 library"
`of the UNIX system. This library was described in the first edition, and has
`been widely used on other systems as well. Again, most programmers will not
`see much change.
`Because the data types and control structures provided by C are supported
`directly by most computers, the run-time library required to implement self·
`contained programs is tiny. The standard library functions are only called
`explicitly, so they can be avoided if they are not needed. Most can be written in
`C, and except for the operating system details they conceal, are themselves port(cid:173)
`able.
`Although C matches the capabilities of many computers, it is independent of
`any particular machine architecture. With a little care it is easy to write port(cid:173)
`able programs, that is, programs that can be run without change on a variety of
`hardware. The standard makes portability issues explicit, and prescribes a set
`of constants that characterize the machine on which the program is run.
`C is not a strongly-typed language, but as it has evolved, its type-checking
`has been strengthened. The original definition of C frowned on, but permitted,
`the interchange of pointers and integers; this has long since been eliminated, and
`the standard now requires the proper declarations and explicit conversions that
`had already been enforced by good compilers. The new function declarations
`are another step in this direction. Compilers will warn of most type errors, and
`there is no automatic conversion of incompatible data types. Nevertheless, C
`retains the basic philosophy that programmers know what they are doing; it only
`requires that they state their intentions explicitly.
`C, like any other language, has its blemishes. Some of the operators have
`the wrong precedence; some parts of the syntax could be better. Nonetheless, C
`has proven to be an extremely effective and expressive language for a wide
`variety of programming applications.
`
`The book is organized as follows. Chapter 1 is a tutorial on the central part
`of C. The purpose is to get the reader started as quickly as possible, since we
`believe strongly that the way to learn a new language is to write programs in it.
`The tutorial does assume a working knowledge of the basic elements of pro(cid:173)
`gramming; there is no explanation of computers, of compilation, nor of the
`meaning of an expression like n=n+ 1. Although we have tried where possible to
`show useful programming techniques, the book is not intended to be a reference
`work on data structures and algorithms; when forced to make a choice, we have
`concentrated on the language.
`
`ServiceNow's Exhibit No. 1004
`
`008
`
`

`
`4
`
`INTRODUCTION
`
`Chapters 2 through 6 discuss various aspects of C in more detail, and rather
`more formaUy, than does Chapter 1, although the emphasis is still on examples
`of complete programs, rather than isolated fragments. Chapter 2 deals with the
`basic data types, operators and expressions. Chapter 3 treats control flow:
`if·else, switch, while, for, etc. Chapter 4 covers functions and program
`structure-external variables, scope rules, multiple source files, and so on-and
`also touches on the preprocessor. Chapter S discusses pointers and . address
`arithmetic. Chapter 6 covers structures and unions.
`Chapter 7 describes the standard library, which provides a common interface
`to the operating system. This library is defined by the ANSI standard and is
`meant to be supported on all machines that support C, so programs that use it
`for input, output, and other operating system access can be moved from one sys·
`tern to another without change.
`Chapter 8 describes an interface between C programs and the UNIX operat·
`ing system, concentrating on input/output, the file system, and storage alloca·
`tion. Although some of this chapter is specific to UNIX systems, programmers
`who use other systems should still find useful material here, including some
`insight into how one version of the standard library is implemented, and sugges(cid:173)
`tions on portability.
`Appendix A contains a language reference manual. The official statement of
`the syntax and semantics of C is the ANSI standard itself. That document,
`however, is intended foremost fQr compiler writers. The reference manual here
`conveys the definition of the language more concisely and without the same
`legalistic style. Appendix B is a summary of the standard library, again for
`users rather than implementers. Appendix C is a short summary of changes
`from the original language. In cases of doubt, however, the standard and one's
`own compil~r remain the final authorities on the language.
`
`ServiceNow's Exhibit No. 1004
`
`009
`
`

`
`cHAPTER s: Pointers and Arrays
`
`A pointer is a variable that contains the address of a variable. Pointers are
`much used in C, partly because they are sometimes the only way to express a
`computation, and partly because they usually lead to more compact and effi(cid:173)
`cient code than can be obtained in other ways. Pointers and arrays are closely
`related; this chapter also explores this relationship and shows how to exploit it.
`Pointers have been lumped with the goto statement as a marvelous way to
`create impossible-to-understand programs. This is certainly true when they are
`used carelessly, and it is easy to create pointers that point somewhere unex(cid:173)
`pected. With discipline, however, pointers can also be used to achieve clarity
`and simplicity. This is the aspect that we will try to illustrate.
`The main change in ANSI C is to make explicit the rules about how pointers
`can be manipulated, in effect mandating what good programmers already prac(cid:173)
`tice and good compilers already enforce. In addition, the type void * (pointer
`to void) replaces char *as the proper type for a generic pointer.
`
`5.1 Pointers and Addresses
`
`Let us begin with a simplified picture of how memory is organized. A typi(cid:173)
`cal machine has an array of consecutively numbered or addressed memory cells
`that may be manipulated individually or in contiguous groups. One common
`situation is that any byte can be a char, a pair of one-byte cells can be treated
`as a short integer, and four adjacent bytes form a long. A pointer is a group
`of cells (often two or four) that can hold an address. So if cis a char and pis
`a pointer that points to it, we could represent the situation this way:
`
`The unary operator &. gives the address of an object, so the statement
`
`ServiceNow's Exhibit No. 1004
`
`010
`
`

`
`94
`
`POINTERS AND ARRAYS
`
`CHAPTERS
`
`P = &.c;
`assigns the address of c to the variable p, and p is said to "point to" c. The &
`operator only applies to objects in memory: variables and array elements. It
`cannot be applied to expressions, constants, or register variables.
`The unary operator * is the indirection or dereferencing operator; when
`applied to a pointer, it accesses the object the pointer points to. Suppose that x
`and y are integers and ip is a pointer to int. This artificial sequence shows
`how to declare a pointer and how to use & and *:
`int x = 1' y = 2, z[10];
`I• ip is a pointer to int */
`int *ip;
`ip = &.x;
`y = •ip;
`•ip = 0• '
`ip = &.z[O];
`The declarations of x, y, and z are what we've seen all along. The declaration
`of the pointer ip,
`
`/• ip now points to x •I
`/• y is now 1 •I
`/• x is now 0 •I
`I• ip now points to z[O] •/
`
`is intended-as a mnemonic; it says that the expression *iP is an int. The syn(cid:173)
`tax of the declaration for a variable mimics the syntax of expressions in which
`the variable might appear. This reasoning applies to function declarations as
`well. For example,.
`double •dp, atof(char •);
`
`says that in an expression *dP and atof ( s) have values of type double, and
`that the argument of a to£ is a pointer to char.
`You should also note the implication that a pointer is constrained to point to
`a particular kind of object: every pointer points to a specific data type. (There
`is one exception: a "pointer to void" is used to hold any type of pointer but
`cannot be dereferenced itself. We'll come back to it in Section 5.11.)
`If ip points to the integer x, then *iP can occur in any context where x
`could, so
`•ip = •ip + 10;
`increments *iP by 10.
`The unary operators * and & bind more tightly than arithmetic operators, so
`the assignment
`y = •ip + 1
`takes whatever ip points at, adds 1, and assigns the result to y, while
`•ip += 1
`
`increments what ip points to, as do
`
`ServiceNow's Exhibit No. 1004
`
`011
`
`

`
`SECTION 5.2
`
`POINTERS AND FUNCTION ARGUMENTS
`
`95
`
`and
`
`The parentheses are necessary in this last example; without them, the expression
`would increment ip instead of what it points to, because unary operators like *
`and ++ associate right to left.
`Finally, since pointers are variables, they can be used without dereferencing.
`For example, if iq is another pointer to int,
`iq = ip
`copies the contents of ip into iq, thus making iq point to whatever ip pointed
`to.
`
`5.2 Pointers and Function Arguments
`
`Since C passes arguments to functions by value, there is no direct way for
`the called function to alter a variable in the calling function. For instance, a
`sorting routine might exchange two out-of-order elements with a function called
`swap. It is not enough to write
`
`swap( a, b);
`
`where the swap function is defined as
`
`void swap(int x, int y)
`{
`
`/* WRONG */
`
`int temp;
`temp = x;
`X = y;
`y = temp;
`
`}
`
`Because of call by value, swap can't affect the arguments a and b in the rou(cid:173)
`tine that called it. The function above only swaps copies of a and b.
`The way to obtain the desired effect is for the calling program to pass
`pointers to the values to be changed:
`
`swap(&a, &b);
`
`Since the operator & produces the address of a variable, &a is a pointer to a. In
`swap itself, the parameters are declared to be pointers, and the operands are
`accessed indirectly through them.
`
`ServiceNow's Exhibit No. 1004
`
`012
`
`

`
`96
`
`POINTERS AND ARRAYS
`
`CHAPTERS
`
`void swap(int •px, int •py)
`{
`
`/• interchange •px and *PY •I
`
`int temp;
`temp = •px;
`*PX • •py;
`*PY = temp;
`
`}
`
`Pictorially:
`
`in caller:
`
`a:
`
`in swap:
`
`Pointer arguments enable a function to access and change objects in the
`function that called it. As an ·example, consider a function qetint that per(cid:173)
`forms free-format input conversion by breaking a stream of characters into
`integer values, one integer per call. qetint has to return the value it found
`and also signal end of file when there is no more input. These values have to be
`passed back by separate paths, for no matter what value is used for EOF, that
`could also be the value of an input integer.
`One solution is to have qetint return the end of file status as its function
`value, while us~ng a pointer argument to store the converted integer back in the
`calling function. This is the scheme used by scan£ as well; ·see Section 7 .4.
`The following loop fills an array with integers by calls to getint:
`int n, array[SIZE], qetint(int •);
`
`for (n ~ 0; n < SIZE && qetint(&array[n]) I= EOF; n++)
`
`Each call sets array[n) to the next integer found in the input and increments
`n. Notice that it is essential to pass the address of array[n] to getint.
`Otherwise there is no way for qetint to communicate the converted integer
`back to the caller.
`Our version of qetint returns EOF for end of file, zero if the next input is
`not a number, and a positive value if the input contains a valid number.
`
`ServiceNow's Exhibit No. 1004
`
`013
`
`

`
`SECTION 5.3
`
`POINTERS AND ARRAYS
`
`97
`
`#include <ctype.h>
`
`int getch (void) ;
`void ungetch(int);
`
`I• getint: get next integer from input into •pn •I
`int getint(int •pn)
`{
`
`int c, sign ;
`
`while (isspace(c = getch ()))
`
`I• skip white space • I
`
`'+' && c I= '-') {
`if ( lisdigit(c) && c I= EOF && c 1=
`ungetch(c);
`I* it's not a number *I
`return 0;
`
`}
`sign= (c == '-') ? -1 : 1;
`if ( c •• , +, : : c ==
`, -, )
`c • getch();
`for (*pn = 0; isdigit(c); c = getch())
`*Pn = 10 * *Pn + (c- '0');
`*Pn *= sign;
`if (c I= EOF)
`ungetch(c);
`return c;
`
`}
`
`Throughout getint, *Pn is used as an ordinary int variable. We have also
`used getch and ungetch (described in Section 4.3) so the one extra character
`that must be read can be pushed back onto the input.
`
`Exercise 5-1. As written, getint treats a + or - not followed by a digit as a
`valid representation of zero. Fix it to push such a character back on the input.
`0
`
`Exercise 5-2. Write getfloat, the floating-point analog of getint. What
`type does getfloat return as its function value? 0
`
`5.3 Pointers and Arrays
`
`In C, there is a strong relationship between pointers and arrays, strong
`enough that pointers and arrays should be discussed simultaneously. Any opera(cid:173)
`tion that can be achieved by array subscripting can also be done with pointers.
`The pointer version will in general be faster but, at least to the uninitiated,
`somewhat harder to understand.
`The declaration
`
`ServiceNow's Exhibit No. 1004
`
`014
`
`

`
`98
`
`POINTBRS AND ARRAYS
`
`CHAPTERS
`
`int a[ 10];
`defines an array a of size I 0, that is, a block of 10 consecutive objects named
`a[O], a[ 1 ], ... , a[9].
`a: I
`I
`a[O]a[1]
`
`a[9]
`
`I
`
`The notation a[ i] refers to the i-th element of the array. If pais a pointer to
`an integer, declared as
`
`int •pa;
`then the assignment
`pa • &.a[O];
`sets pa to point to element zero of a; that is, pa contains the address of a [ 0 ] .
`
`Now the assignment
`X • •pa;
`will copy the contents of a [ 0 ] into x.
`If pa points to a particular element of an array, then by definition pa+ 1
`points to the next element, pa+i points i elements after pa, and pa-i points i
`elements before. Thus, if pa points to a [ 0 ] ,
`•(pa+1)
`
`refers to the contents of a[ 1 ], pa+i is the address of a[i], and •(pa+i) is
`the contents of a [ i ] .
`
`These remarks are true regardless of the type or size of the variables in the
`array a. The meaning of "adding 1 to a pointer," and by extension, all pointer
`arithmetic, is that pa+ 1 points to the next object, and pa+i points to the i-th
`
`ServiceNow's Exhibit No. 1004
`
`015
`
`

`
`SECTION 5.3
`
`POINTERS AND ARRAYS
`
`99
`
`object beyond pa.
`The correspondence between indexing and pointer arithmetic is very close.
`By definition, the value of a variable or expression of type array is the address
`of element zero of the array. Thus after the assignment
`pa = &a[O];
`pa and a have identical values. Since the name of an array is a synonym for
`the location of the initial element, the assignment pa=&a [ 0 ] can also be writ(cid:173)
`ten as
`
`pa = a;
`Rather more surprising, at least at first sight, is the fact that a reference to
`a[i] can also be written as *(a+i}. In evaluating a[i], C converts it to
`* ( a+i) immediately; the two forms are equivalent. Applying the operator & to
`both parts of this equivalence, it follows that &a [ i] and a+i are also identical:
`a+i is the address of the i-th element beyond a. As the other side of this coin,
`if pa is a pointer, expressions may use it with a subscript; pa [ i 1 is identical to
`* ( pa + i}. In short, an array-and-index expression is equivalent to one written
`as a pointer and offset.
`There is one difference between an array name and a pointer that must be
`kept in mind. A pointer is a variable, so pa=a and pa++ are legal. But an
`array name is not a variable; constructions like a=pa and a++ are illegal.
`When an array name is passed to a function, what is passed is the location
`of the initial element. Within the called function, this argument is a local vari(cid:173)
`able, and so an array name parameter is a pointer, that is, a variable containing
`an address. We can use this fact to write another version of strlen, which
`computes the length of a string.
`
`return length of string s */
`I* strlen:
`int strlen(char *S)
`{
`
`int n;
`
`for (n = 0; *S I= '\0'; s++)
`n++;
`return n;
`
`}
`
`Since s is a pointer, incrementing it is perfectly legal; s++ has no effect on the
`character string in the function that called strlen, but merely increments
`strlen's private copy of the pointer. That means that calls like
`strlen( "hello, world");
`strlen(array);
`strlen(ptr);
`
`/* string constant */
`I* char array[100]; */
`/* char *Ptr; */
`
`all work.
`As formal parameters in a function definition,
`
`ServiceNow's Exhibit No. 1004
`
`016
`
`

`
`100
`
`POINTERS AND ARRAYS
`
`CHAPTERS
`
`char s[];
`
`and
`
`char •s;
`are equivalent; we prefer . the latter because it says more explicitly that the
`parameter is a pointer. When an array name is passed to a function, the func(cid:173)
`tion can at its convenience believe that it has been handed either an array or a
`pointer, and manipulate it accordingly. It can even use both notations if it
`seems appropriate and clear.
`It is possible to pass part of an array to a function, by passing a pointer to
`the beginning of the subarray. For example, if a is an array,
`f(&.a[2])
`
`and
`
`f(a+2)
`both pass to the function f the address of the subarray that starts at a [ 2 1.
`Within f, the parameter declaration can read
`f ( int arr [ ] ) { ... }
`
`or
`
`f ( int •a.rr) { ... }
`
`So as far as f is co~cemed, the fact that the parameter refers to part of a larger
`array is of no consequence.
`If one is sure that the elements exist, it is also possible to index backwards in
`an array; p[ -1 1. p[ -21. and so on are syntactically legal, and refer to the ele(cid:173)
`ments that immediately precede p[ 01. Of course, it is illegal to refer to objects
`that are not within the array bounds.
`
`5.4 Address Arithmetic
`
`If p is a pointer to some element of an array, then p++ increments p to
`point to the next element, arid p+=d increments it to point i elements beyond
`where it currently does. These and similar constructions are the simplest forms
`·
`of pointer or address arithmetic.
`C is consistent and regular in its approach to address arithmetic; its integra(cid:173)
`tion of pointers, arrays, and address arithmetic is one of the strengths of the
`language. Let us illustrate by writing a rudimentary storage allocator. There
`are two routines. The first, alloc(n), returns a pointer p to n consecutive
`character positions, which can be used by the caller of alloc for storing char(cid:173)
`acters. The second, a free ( p} , releases the storage thus acquired so it can be
`re-used later. The routines are "rudimentary" because the calls to afree must
`be made in the opposite order to the calls made on alloc. That is, the storage
`
`ServiceNow's Exhibit No. 1004
`
`017
`
`

`
`SECTION 5.4
`
`ADDRESS ARITHMETIC
`
`101
`
`managed by alloc and afree is a stack, or last-in, first-out list. The stand(cid:173)
`ard library provides analogous functions called malloc and free that have no
`such restrictions; in Section 8.7 we will show how they can be implemented.
`The easiest implementation is to have alloc hand out pieces of a large
`character array that we will call allocbuf. This array is private to alloc
`and afree. Since they deal in pointers, not array indices, no other routine
`need know the name of the array, which can be declared static in the source
`file containing alloc and afree, and thus be invisible outside it. In practical
`implementations, the array may well not even have a name; it might instead be
`obtained by calling malloc or by asking the operating system for a pointer to
`some unnamed block of storage.
`The other information needed is how much of allocbuf has been used.
`We use a pointer, called allocp, that points to the next free element. When
`alloc is asked for n characters, it checks to see if there is enough room left in
`allocbuf. If so, alloc returns the current value of allocp (i.e., the begin·
`ning of the free block). then increments it by n to point to the next free area. If
`there is no room, alloc returns zero. afree(p) merely sets allocp to p if
`pis inside allocbuf.
`
`allocp: \
`
`I I
`
`I
`
`..---in use - - • .,. ___ _
`
`before call to alloc:
`
`allocbu£:
`
`after call to alloc:
`
`allocbuf:
`
`free
`
`allocp: \
`
`muse ___ _,..,..,. __ free
`
`I I I
`
`I
`
`#define ALLOCSIZE 10000 I* size of available space *I
`
`static char allocbuf[ALLOCSIZE] ;
`static char *allocp = allocbuf;
`
`I * storage for alloc *I
`I* next free position •I
`
`char *alloc(int n)
`{
`
`I • return pointer to n characters • I
`
`if (allocbuf + ALLOCSIZE - allocp >= n ) { I* it fits • I
`allocp += n ;
`return allocp - n; I• old p *I
`} else
`I• not enough room * I
`return 0;
`
`}
`
`ServiceNow's Exhibit No. 1004
`
`018
`
`

`
`101
`
`POINTERS AND ARRAYS
`
`CHAPTERS
`
`void afree(char *P)
`{
`
`/* free storage pointed to by p */
`
`if (p >= all