:o., .. Lioli
`I,
`'I
`'JA
`SECOND EDIDON
`7G. 71 ,l
`i,;::: ===========
`l
`c1r,
`I 19B8 - ~
`I /'47
`
`THE
`
`1
`
`. •
`• •
`
`•
`•
`
`•
`
`• •
`• .
`. . . •
`• • •
`• • . .
`
`BRIAN W KERNIGHAN
`DENNIS M. RITCHIE
`
`PRENTICE HALL SORWAAE SERIES
`
`
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 1 of 15
`
`

`

`THE
`C
`
`PROGRAMMING
`LANGUAGE
`
`Second Edition
`
`Brian W. Kernighan • Dennis M. Rilcbie
`
`AT & T Bell Laboratorie.,
`Murray Hill, Ntw Jersey
`
`PRENTICE IIALL. Englewood Cliffs. New Jersey 07632
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 2 of 15
`
`

`

`Lt"brary of Coll8ff!l8 C-atalogblg-ln.fublication Data
`
`Kernighan, Brian W.
`The C progralll!lli ng language.
`!Tid ude.s index •
`1. C ( Compute.r progre.ro language ) 1. Ritchie.•
`Dennis M,
`11, Title,
`191!8
`Q.A76.73.Cl5K47
`005.13°3
`tSBN 0-13-110370-9
`I SBN 0-13-110362-8 (pbk.)
`
`83-5934
`
`Copyright• 1988, 1978 by Bell Telephone uboratorie, lnoorporated.
`All right\ rcs.er,•ed. No part of thi!I publication may be reproduced, $lorcd in a retrieval
`~ystem, or lraru.miucd, in uny rorm ur by any mc:1&Ds, ;lectronic. mechanic-a), phocooopy(cid:173)
`i-ng, rec:otding, or otherwise, without tht' prior written pttmission. 6f the publisher.
`Prit1ted in the U,,ited States of Amecica. Published simultaneously in Canada.
`
`UNIX is o registered tradernar~ or "T&T.
`
`this book: wa.s type.\.Ct (pie:tbl:e(in!troff -ma) in Times Roman ahd Courier by
`che authors, using •• Autologio APS·S phototy()<s<ttcr and a DEC VAX 8SSO running
`the 9th Edition of the UNIX• o)l<ratins sy,tom.
`
`Prentice Hall Software Series
`llrian Kernighan, Advisor
`
`Printed in the Llnited $~are5 of Amerlca
`
`10 9 8 7 6
`
`ISBN
`ISBN
`
`0-13- UD 3b2-8
`0 - 13-110370-9
`
`{PBK}
`
`Prentice-Hall International (UK) Limited, Lotuion
`Prentice-Hall of .Austrltlia Pty, Limired, S_ydney
`Prentice-Hall Canada Inc .. Toronto
`Prentice-Hall Hispanoamericana. S.A., Mexico
`Prenlice-H:ill of India Private limited, New Delhi
`Prenticcd·fall of J3p,o.n, Inc., Tnkyn
`.Simon & Schuster Asia Pte. Ltd .. Singapore
`Editora Prentice-Hall do Brasil. Lt<!a .. Rio de Janeiro
`
`I
`
`(
`
`C
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 3 of 15
`
`

`

`EMS
`l18
`C/A
`1 t,
`·_;
`CI.,,
`k- l/
`I 'lf.
`
`Contents
`
`ix
`
`xi
`
`5
`5
`8
`13
`)'4
`IS
`22
`24
`27
`28
`31
`
`35
`35
`36
`37
`40
`41
`41
`42
`46
`48
`$0
`51
`52
`
`55
`55
`55
`
`Ptdace
`
`Prd1u .. ~ to Che Fin:t Eclldon
`
`lntro4uction
`
`Ch1;p~ J.
`1. I
`1.2
`1.3
`1.4
`J.S
`1.6
`1.1
`
`'·* J.9
`
`1.10
`
`,\ T■lorul hllrodu<doa
`Getting Staned
`Va riables attd Arilbmelic Ex.pressiQni
`The For Stateme1u
`Symbolic Consi.nl6
`Character Input ;1nd Output
`Arrays
`Pu net ions
`Argu,nerH&- Co.11 by Vl\luc
`Character Arrays
`Ex.term,I Variables :mcl $-Oopc
`
`Chapler 2.
`2 .1
`2.2
`2 .3
`2.4
`2.5
`2.6
`2.1
`2.8
`2.9
`2.10
`2.11
`2.12
`
`Types, O,.ralors, and E•p,,.<i<>ns
`Variable Names
`Dold T )"J)e' and Sizc!I
`Constants
`Dedaralions
`.A.rilhmctic Opera.tors
`Relational and Logical O~rato!"i
`Type Conversions
`Im:remem and Oecremenl Operawrs
`1:litwise Operators
`:\ssignment Opera.tun. and F.xprcssions
`Cot1diti-0nal Expressions
`Precedence and Order of £valualion
`
`Chapcer 3.
`3.1
`.l.2
`
`Conlrol Flow
`Statemcnts and Blocks
`lf-Fhc
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 4 of 15
`
`

`

`,i THl;C PR()GRAMMlr,.C LANGUAG'F.
`
`C:O'IU:.KTS
`
`3.:l Elsc• ff
`3.4 Switch
`luupt>-Whi1c and for
`3.5
`~.6 Lu,)p,:-
`l)o..whilc
`3.i Br~ k and Cootinue
`3.& Gow •nd Labels
`
`(:haiplc, 4. Functions and Program StHctun:
`4 . l Basiu. uf f'ullCtiOl'lS
`4.2 Functions Rernrniog Non-iitcgcrs
`l!xternaJ Variables
`4 .. l
`4 .4 Scope Rule&
`4.5 Header Files
`4.6 Su.tic Variable~
`4.1 Regis1cr Variables
`4.8 Block Structure
`~-9
`lnitialiulion
`4.10 Recursion
`4.11 T he C Pr~processor
`
`Chapter 5. Pointm and An'8}'S
`5.1 Pointers and AJdr~t:i.
`5.2 Poiatcr5 and Function Argmnents
`5.3 Poinlers and Arrays
`5 .4 Address Arithmetic
`55 Character Pointers and Fulctions
`5.6 Pointer Arrays; Poimcrs to Pointers
`5.7 Multi-dimensional Atrays
`Initialization ur Pointer A rrays
`5.8
`5.9 Pojnters vs. Muhi-dimerL'ii.:,l\a) .Ar,ays
`5.10 Cl)lUnlaRd-Jinc Argumcnti
`,. 11 Poinlers to Functions
`S. 12 Complicated Declaratioris
`
`<.uplet 6. Structures
`6.1 Basi<.:8 of Slru..:tu res
`6.2 Stl'\lcturcs and Fur,c.tions
`6.3 Arrays of Struclun:s
`6.4 Pojnte-rs to Scn~tures
`6.5 Self-,efecential Structures
`6.6 T•bl• Lookup
`6.'J Typcder
`6.~ UniOn.'i
`6.9 Bit~fidJs
`
`Cbapttr 7. laput and Out,ut
`7.1 Standard fopm and Output
`f'onna.Lted Output-Print:
`7.2
`
`5J
`5~
`60
`63
`64
`6S
`
`67
`67
`7 1
`73
`80
`81
`SJ
`83
`84
`85
`86
`88
`
`93
`l)3
`95
`97
`100
`104
`107
`110
`JJJ
`11 '.l
`114
`118
`122
`
`127
`127
`129
`132
`ll6
`IJ9
`143
`146
`147
`149
`
`151
`151
`153
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 5 of 15
`
`

`

`TH!i (: PROGRAMMING LA:'IIOUACE
`
`CONTENTS
`
`,ii
`
`7.3
`7.4
`7.5
`7.6
`1.i
`7.8
`
`Variable-length Argument Usu
`Form.ttted lnpul-St:anf
`File Aooen
`Error Handling-Stdcrr and Bxit
`L ine lnpul und Output
`Misce!laneous Functiocis
`
`Ci>llptn 8.
`8. 1
`8.2
`8.3
`8.4
`8.S
`8.6
`8.7
`
`Th<i UKIX Symm lnterfa,c
`File Ocscripton
`low Le\•el J/0- Rcad and \\'rite
`Open, Creal, Close, Unlink
`Ranrloru Access-Lsei:k
`EJtamplc-An lmplementati,:,11 of Fopen and Getc
`EJtample-listing Directories
`Exam.pie-A Swrago Allocator
`
`Apl)ffldlx A. Ref•-•• Man1111I
`AJ
`Inlruduction
`A2 Lexical Corwentious
`A3 Syntax Notalion
`A4 Meaning of identifiers
`AS Objects and L\'ah.:~
`A6 Conversions
`A 7 Expressions
`A8 Declarations
`A9
`St<1Lemc:n1.~
`A IO F l.tcmal Occ!ar2.tions
`A 11 Scope ana Lln..kage
`A 12 Preprocessing
`AlJ G,:ammar
`
`Apptndix. 8. Standud .Library
`DI
`Input and Output: <~tdio.h>
`82 Charactet Clas. .. Tc.~t": <ctypc.h>
`83 Strin& Function1>: <string.b >
`04 MathcmaUai.l Functions: <math.h>
`t:IS Utility functions: < ~tdlib.b>
`86 Diagno~ties: <asscrt.h.>
`87 Variable Ar~l.lmcnt L is1s: <stdatg.h>
`.BS Nun-local Jum))6: <setjn1p.h>
`89 Sign~I$: <sig.nal.h>
`B 10 Date and Time Function~: <timc.h>
`Implementation-defined Limits: <limits.h> ilnd < Ooat.h>
`Bl '
`
`Appendix C. Summ&I')' o! Chang,,;
`
`lade.:
`
`155
`IS7
`160
`163
`164
`166
`
`169
`169
`170
`172
`IH
`l7S
`179
`18S
`
`191
`19 1
`191
`194
`195
`197
`197
`200
`210
`222
`225
`227
`226
`234
`
`141
`24 1
`248
`249
`251)
`251
`253
`254
`254
`255
`25S
`257
`
`259
`
`263
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 6 of 15
`
`

`

`SBCTJON18
`
`MISCt!.LLA~l::OliS flJNCTIO~S
`
`167
`
`7.8.4 Commend Exe<;Ulion
`
`'t'he function 1$yst:em( char "s) executes lhe command contained in the
`chatactC;f string s, then resumes execution of the current progr~m. The con(cid:173)
`tents of s depend strongly on the local opcraling i;ystcm. As a trivia] example.
`on UNIX systems► the st-atcmer'll
`
`syste111{ "date") i
`
`cause. the program date ,o be run; it prinl< the date and time of day on the
`standard output. system reltirns a :::)•.~tem-dependent integer. stattL~ from the
`ooounand executed. Jn the UNlX system, the stauis return is the \'alue returned
`by exit.
`
`7 .8.5 Storage Management
`
`The functions rnalloc and callee Obtai,1 blocks of mem<;>ry dynam[cally.
`
`v9i4 *malloc (size~t n)
`
`returns a pointer to n by1es of -uninHi~Ji1:ed !::orage., or NOLL if the request can(cid:173)
`not be satisfied.
`void ¼calloc(size_t n. sizo_t size}
`
`returns ~ poi~te.r tn enough space for an arr•)' of n objects of the specified si,,e,
`or NULL if the. request cannot be sad~fied . The .!itnragc is initialized to zero.
`'Hte pointer returned by malloc or calloc ba~ 1he prQper a lignment for
`the object in quc::stioo~ \>u~ it n:lust t>c cast tnto. t.bc appropriate 1ype, as l_n
`int 1ip;
`
`ip a (int • ) e&lloc(n, size.of(int));
`
`free( p > frees the ,pace pointed t.o by J;\ where p wa, originaHy obtained
`by a call to rnolloc or calloc. There arc no re>1rictions on ~be order in
`which space is freed, bu1 it i~ a ghastly error co free something not obtained by
`calling calloc or malloc.
`It is also an error to use something arce.r 11 ha~ been freed. A typical but
`incocte:ct piece of c.odc is this loop that frees ile.ms frnm;,. liia:
`for lp = head; p ~• NOLL; p • p- >noxt)
`free("p);
`
`The right way is to $ave \\'hate11er is needed '::efore freeing:
`I= NULL: p : ~) l
`
`tor (p • heAd; p
`q
`:i p->nex.t ♦
`f r E'e(pl:
`
`Section 8.7 shows the -implementation of a storage a 11ocator like malloc► in
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 7 of 15
`
`

`

`168
`
`lNPl,IT ANI> Ou,-PUT
`
`CHAPIT:.R 1
`
`which allocated blocks may be freed in any order.
`
`7 .8.6 Mathematical Functions
`There are more thnn twenty mathcma ~ical functions declared in ,c:math. h>;
`here ;ire some of the more frequently used. Each t~kcs one- or two doubl~
`arguments and return$ a double.
`sine of :r, x ir, radians
`c~int! of x. ): in radians
`arc.tangtnl of ylx. in radi1t.ns
`exponential function e~
`natura1 (base e) lo~.:.triLhm of x (x>O)
`oc)mmon (base 10) l()Earithm or x (x > 0)
`x.''
`squ~re roOl ot x Ct ~O)
`absolute vl'llue nf :<
`
`•in(x)
`cos(x)
`ata.n2(J:,X)
`exp(x)
`loglxl
`log10 (x)
`pow(.x.J•)
`sqrt(x ~
`f abs(x i
`
`7 .8. 7 Random Humber Generation
`
`The fum.:tion rand() computes a s~uencc of pseudo-random integers in the
`range zero to RAND_MAX. which is defined in <stdlib .h>. One way to pr<r
`duce ranJom 0oating-point numberi gre.atcr than or equal to zero but less ,ban
`one is
`
`#define £rand() ((douhleJ rond() /
`
`(RAND_MAX•1,0))
`
`(Jr your library already provides a fu nction for floating-point random numbers,
`it il> likely to have beUer statistical properties than this one.)
`The func1ion srand ( unsigned l sets the seed for rand. The portable
`implcmcnl.aLio,, of rand a nd srand suggested by the standard appears in Sec-(cid:173)
`t ion 2.7.
`
`Exercise 7-9. Functions Jike i supper can be implemented to save space or to
`,ave time. Explore both possibilities. D
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 8 of 15
`
`

`

`•
`
`--
`. ----
`---------
`
`--.
`
`--
`
`-
`
`SECTfON OS
`
`LTILll'''i f\JWCTIONS: <STOLID.M>
`
`'251
`
`sin (x }
`cot(x }
`tan(x.}
`a,sin(x>
`.::1.eo~C,d
`a.tan(x )
`a.tan2(y,x.)
`sinb(x)
`cosh(x.)
`tanh(,t)
`exp{xl
`log(x}
`log10fx )
`pow(x ,y )
`
`sine of x
`cosine of x.
`tangent of x
`sin-•(x) in rauge (-1C'l2.1r/2J.x E 1-1. 1).
`~<'ls-1 (.v) 1n ri:..n,e.e ro, \Tl. :e E (-1. 11.
`tan-•(.,-) in range (-,,./2, ,r/2].
`ta.n-l (J'IX) in rnnge 1-11', .,rJ.
`hyperbolic ~ine ot x
`hyperbolic cosine of-''
`hyperbolic tangent of x
`i;~ponentio.l functioJ) ex
`na~ur1:1.I logarithm ln.(x), x>O.
`base 10 logarithm IOJhob). x>O.
`x>'. A domain error occurs if x-0 and y<O. ur ir
`x<O and y is nor. an integc=,.
`Fx, ., ~O.
`sqrt{ x)
`smallest inLegtr oot Jess than x, as o doub1~.
`c;:eil (x)
`largest integer not g~ter that x.. as a double,
`floorCx)
`absohne value l.t I
`faOe [x)
`x·l"
`ldexptx.n)
`Crexp(xt int •exp)
`in lhe int~rval
`spJiu. x inlo a normali7.cd rnu.:.ti..:;u
`[tl2, 1)., which is l'e1urncd, and a power of 2. whii;h is
`stored ·in •exp. If xis z-:.ro, both pitrlll o( the result
`arc zero,
`modf(x, double •ip)
`•plit<: "It i11lr'I it1tt-,er:tl ~nd frac1t)n11I parts.. each with the
`~m~ sign as x, It stor~ the intcgr:I part in idp, and
`retu.rns the fra1;:tlon~l ~rt.
`tloating~pohit remainder of x/y, wirh the a.amt &ign JS
`x.. lf y i!I um), the result is .in:p1erneotat'°n•defined.
`
`£ mod(x.y)
`
`es. Utility Functions: <stdllb,h>
`T he hel!der <stdlib.h> dcelarci. fu,nctlon:s for number con.vel'$ioO, s10ragt; ~llnca(cid:173)
`fon~ and similar tas.ks.
`double atofCcon•t char •sl
`a,:.of oonveru: e io double; ii iii C1,1.u.i11it.ltol co &t'rtod(.e, <char .. , )NULL).
`int atol(conat char •al
`conve.rts e to int. it is cqui,•:'iltnt to (int) strtol (,. C char•• )NULL, 10 ).
`
`long atol(const char •sl
`oonvcrJ-5 -• to long; -it is eq_ui\•ale:.nt to atrtol (s, ( char** )l~OLL. 10 ).
`d~ubl• strtod(~onst cbar •S , cb ~~ ♦•endpJ
`s.trtod converts the prtfix. of s to double. ianori11g leading whrtc• 5p11,',:e~ ft Storti a
`point~r to any uncoc,vtned suffix in •endp unle~ endp is NULL. If th: answer
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 9 of 15
`
`

`

`2S1
`
`STANDAk O t ll:IJ<.AKY
`
`l\fPENOIX B-
`
`would uvc:rOow.., HQCg_ VAt. js returned "•ith the proper sigo; if the ar'l.$wi;r would
`11ncl¢rflow. zero l5 rcwrncd.
`lo either case ll"r~no j,s set lo !:llA.NGE.
`
`long strtol (const ehar • s, Char ••endp, int baRe}
`::Jt-t'tol oonvercs the prefix of a to lon g. ig.e1orillg tt:adint whito space~ it stores a
`lf base is
`poin,cr to ;my UD(.'()m•~ned suffix in ai endp UC\1es.s endp. i$ NVt.L.
`befween 2 ~od 36. convcr,;iQo i$ c::tonc amuuin•g that the i(ipu( is wrilleo in that b11sc:.
`lf .Dase is zero. the ba!c j.$ 8, I 0. or J 6" !cadirl.& 0 implicll ocia:J and lea,ding Ox or ox:
`hexadecimal. Letters io eilhct ca,c te:ue!lenL dlSil$ from IO to ba,se -1 : a leading
`Ox ur OX ill l)(:mniued fo base 16~ r:· the e,n.swcr would O\'crflow. LONG_HAX or
`LOt;G..,MtN i.s- rctum,c<l, depc.ndlng on tJ,c slgn of the rcsuh. aod @rrno is seL 10
`EMNG!:.
`
`unE>igned long a1=rtoql,(com:t ch-a:::- ~.!.. ohar +tendp , int baee J
`strtoul i~ lhc: same AS strto.l excc:pl lhat the. re.,--ult is qns1gnad. long and the
`rm)'I' ""alue i, ULONG,..MAX.
`
`'int --rAnd(void l
`rand returns a pseudo-random Jntege., irl Lhe ronsc O lo RAND_MAX, which i11 1n
`least 12761.
`
`void srand( unsigned int Eeed )
`o ra.nd usu seed -as. the !!ced £or a new scttucnce-of ps.cudo•random numbers. The
`foitiai seed is 1.
`
`v oid •calloc(size_t nob j , s i ze_~ size >
`oall o o retur.ni; a pointer to sp:icc for 1n ar-ray ot .no.bj objects:. e..icb o( size size,
`or .NULL if tb.e request cannot be satisfltd. The space is il'tiliitl,iud to z~.ro b.ytd.
`
`void •malloc ( -si-ze_t size }
`•alloc fetufru 11 pointer LU -i1pace for 311 <>bje-'.-1. of ~.i~.e -si. ze, or NOLL if th.c rc.que-,.t
`caD.Dol be sa,isfied, The space is uliliti.lialiied.
`
`void *r,alloc(void ◄-P~ ~iz+_t si%~)
`.realloc d 1ah.ges the-size o( the objec1 poitu.c:d to by p tu siz.e.. The OODl~li will
`ff th~ new- , i1:e il hngcr,
`be unc hanged up to the n,inim,um of Lhe i)ld And T1Cw-!ii7.ci..
`th'e new space it unlnitia,li?.Cli. rea l.:oo returns a pointer to the new sp.acc, or
`NULL if ll'u: n::quo;t t.1:1.nnoL be salb;f'icd, in whkh caic• •:P is Ucnchangcd.
`void Cree (void •p)
`free dealJOl.:tltc!I the :.'lp.a~c pointed t9 by· p; i~ docs qotbiri.g lf p is NULL. p inust be
`a pointer to space-. preYfously allocated by calloc, ma,lloc, 01 realloo.
`
`void abort(void)
`aboJ't causes the program ta te:rminace abuo,niall)~ as if by raise ( SlGABRT) ,
`
`void ~xi~(i nt s tatus)
`~xi t causet- nocm.n1 protr.llm. tennlm1..,m1. ate lC it functions .ue: caHed in te'\'ers:e
`order of registrruior., open files ar-c n,uhcd, opco streams arc.- closed, and oontrol is
`rtt.urntd to the t:Jl\'ironmt:nl. How statue i1; rc\urnc.d to the environment is
`impicmontation-dcpcndeDL bul zero is. taken n succc.~:.ful tcrminatjon. The values
`EXIT_SUCCESS and EllT _PAILCRE may • l!IO be ur,cd.
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 10 of 15
`
`

`

`St::C·TJON8.7
`
`EXAMPLE- As·rOllA0 6 AUOCATOR
`
`185
`
`8. 7 EKample-A Storage Allocator
`
`In Chapter 5. we presented a very limited 3~ck.-orien ted stort.ge allocator.
`The. ver $fon, at\flt we wilt now wri le is tmrcstrictc:d . Calls to m&1loc a nd free
`may occur in any order~ malloc calls upon the operating S)'Stern lo --ObLafo more
`memory as. necessary. These routines illu~trate some Of the- oonsiJc:ralions
`fovolvcd in writing machlne:-depende,ll code: i"n a rf:.htliv~ly maohinc~indcpcndcnc
`way. a nd ~lso show a real-life appli.:alion of structures, unions •and t:ypedef,
`Rather than allocating from a compiled-in fixed-sized array,_~ l ~ c- wi! L
`request J pace from t he operating system as ncclcxi.. Since ocber activities in t he
`program m•y aho reguesf spa·c., •withoul"c,rlling this allocator, the space chat
`malloc manages. may nor be contiguous. T hu~ its fr~~SJ.Qrage Jsj.~p_t as ·a list
`or free bl~ !: fo_c~ block ,conmi_n.s a size, a 1>9inJcr lO the ncxt..blc<)k,_onii the.
`srmce riseJf, The block,; are kept in order ofTocre~slng, storage a ddres., aod lhe
`1a·st block (h igh est address) points to the first.
`
`(r~ list ~ .
`
`rree~ owned by in3.lloc
`
`D
`j in use. I in u-se, owned 1;,y ma 11 o c
`J: :::; I not owned by rulloc
`
`\Vhen a 1cqucst is made, the free list is scanned until a big•~nough block ii;
`found, This algorithm is called 4-•firsf n4·•.• by contrast with "best tit," which
`looks for the smaltcst bloclc that will satisfy the request. ff t he block is exaclli'
`the , r,e reques,ed J1 is unl'inked fro1li 11,e list :1nd returned to I.he user, If the
`block i,; loo big,. it is split, and lhe proper amotnl is returned 10 the user while
`the residue remains on the free list. If no big-enough block is found, ~nolhcr
`la rge ch unk is obta ined from the operating system and linked into the free l ist.
`freeing also causes • sea.rob of t he free list, to find the proper place to inien
`the block be-irtg freed. If the block being freoc is odj~cent to a free block on
`either side, it i,s ooalcsced with it lnto a 1i~gle tigger block. so storage d~s not
`become too fragmented. Determining adjacenc~ is easy because I.he free list is
`maintained in order of increasing addrcos,
`On~ problem, v,,nich we alluded to in C hapte; 5, is to, ensure t hat the storage
`returned by ,.,.noc •• a ligned properly for the objects that will be stored [n i\.
`Although machines· vary, for each machine there ts a most restrktive type : U" th e
`most restricti ve-type can be stored -al a particu a:r -address, a.11 o•h~r ty-pcs may
`be also. On ~ome machines, Lhe m'(),\it restrict i\,: type .is a double; oo others,
`i nt or long suffices,
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 11 of 15
`
`

`

`]81)
`
`THE UNlX SYSTF..M TNTRRFAC~
`
`CHAPTF.R II
`
`A free blo,;ILcont.ains n llQinter to tt.e next block in the chain, a rccprd of ihe
`sj1.c _9.f ~~e block.> and t)lcn the fr~c ~J?.£!: it~clf; t ~ ~ntro~ i nformation at _!he
`begin"ing i< c-1lled the "head~." To ,implify alignme~t. all block~ nre multi•
`pies pf life iie,;de, slie, •nd the header is aligned properly. This is aehie--•ed by
`ij lfnion thitt OOntAins the desired 1bead:.r structure- and an instante 6f the m~t
`resuie-tive a lignment type; which we ha\Je arbitrarily made a long:
`
`~ypedef long Align; /• for alignment to long bo;.m~acy •I
`
`I• :Olock header~ /fr/
`
`union header t
`struct: {
`union header •ptq I• next block if or, free list • /
`un•igned size;
`/• -size. of this. block • I
`f s;
`Align z;
`
`/ • corce aligrurien't- or .blocks •I
`
`f ;
`
`typede£ union "header Header;
`
`Th¢ J\l ign field is ne,,e.r used; it Just forces each .header to be alig1:1td on a
`w<m;~•ca:,;e boondriry.
`ln .mal1oc. the requested =-ilre ;n characteN- i~ rounded ,_1p to the proper
`number o( he8der-sized un'its; ,he .blocl', that will be· ai'll()C;;l•ed contains ,ine more
`unit, for the header itself, and this is tt.c value recorded in. the size field of the
`header. The poin1er returned by mdloc points at the free space, not ai the
`header it,;elf. The user can do anything with the space requested, but if any(cid:173)
`iliiug j,:s w1itL~u vul~id~ vf thic; i41loi;.atcd 6P.\Ce du~ ll~t .i$ Uk~ly to b,;: 6~1'ambled,
`
`H points ro next free block
`
`/
`
`size
`
`]
`
`L
`
`addreso-returned to user
`
`A block returned by mal loc
`
`The size field i; necc:s.ary be<.--ausc 1he blocks .:onttolled by malloc- need 1iOI be
`r.:untiguuus-il is not pos~iblt: to t:ompute si~s by poinl.cr arlLhtnelic.
`The- variable base ~ used to gel started. lf free.p is NULL, as it is. at the
`tTrst ,;:;II Qf .,.,_lloc, then a degenerate free 1ist is created: it contains one block
`of size zero. and points to itself. In any ease, the ftee list. is then searched. The
`,eareh for a free block of adequnte slie begins at the point (freep) where the
`last block was found: Ibis strategy helj:6 keep 1be list homogeneou~. If a too-big
`block is- found, the tail end is returned to the-u.scr; in this way the-header of the
`original need, onl'>• to have iu si1.e adji.r;tcd. ln all cases:, the pointer returned to
`tbe lL~r poin_ts 10 the free space-witbir the bloCk, which. begins one u"it beyond
`fhe hea4er.
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 12 of 15
`
`

`

`~11Cfl0~ !1.7
`
`E>AMPLE-A STOR.Ac:rS.At.l.OCA tOk
`
`IR7
`
`atat:i c He.adtr- base ;
`/ ,. eftpt:y list to 9et starte<2 .-/
`sca~lc S.*du • freep • NULL;
`I • start. of free list•/
`
`/ • malloc J 9eneral-pu.rpose •torage &lloea tor •I
`void • malloalt.mccigned. nt,y1=••>
`{
`
`Heade~ •p, ~vrevp;
`H•ad•r ~I\Orecore (unsig;ned):
`uns1gn9d ouni t:s;
`
`nunit1 • (r.bytes+sizeof(Re&der ) - 1) /ais■ot ( Keader } • 1;
`if ((prevp s freep ) •• NULL) {
`/ • no £ree list yet • I
`ba•e.1. ptr ~ f~etp • p~e vp • &.baa• ;
`ba&& ,8. ■ize = O;
`
`for ( p
`u
`
`p. p • P->4 .ptr) l
`/ • bi9 enough a /
`I • exactly + /
`
`• prievp->s . pu: : pTevp =(cid:173)
`(p•>a.ai~e >=- nunita) (
`it (p- >a .sixe ~• nWlits)
`prevp•>s ,ptc • ?•>s . ptr;
`♦l ee {
`/ • al locate ,:a:11 e nd • /
`p- >~ . size - • nu~it$;
`p •= p->a . eh:e:
`p->s. s.iz e • r\uni t.s;
`
`freep • pnvp;
`return (void ♦ ) ( p♦1 1;
`
`if ( J) • • freepl
`/ • wrappP.d Arnnnl'I Ir:•• l i~t A/
`iC ( (p ~ morec0<ro( n11nit o)) •• NULL)
`1'~ turn NULL;
`l • none l •ft • I
`
`The function moncora obtains slOrage from the operating system. The
`detaib of' how it due~ thi1 vary from sy.stem 10 system. Since aslcing the sy;(cm
`for memory is a comp1mllively expensive operation. we don't want to do that on
`every c:a.ll to ulloc. so t00recore rcque.,u .a1 least NALLOC unib.; chis larGer
`block will be chopped up a, needed. Aft er «tting the slu field, n,ore core
`i11>cr1> 1bc adclitional memory into 11K: arena by calling f ree.
`The t:NIX system a.II ebrk{n) return, a pointer LO n more bytes of
`nurage. sbrl< returns - 1 if t here was no spa::e, even though NULL would hove
`been a better desilln, T he - 1 must be ca.it to c h ar • so Ii can be compared
`with the return value. ,\gain, calls malt• the function relotively immllJlc to the
`details of pointer representation on differer,t machines. There i., still one
`aiSumption, how.,..,, that point"1ll to dlfferen1 blocks returned by sbrk can be
`mtllllingfully compared. This is not guan1nte1d by the standard, which permits
`pointer comparisons onl)1 within a.o array. Thus thi, ,·enion or rcalloc is port(cid:173)
`oblo only among macMne. for which gonol'lll pointer comparison i• meaningful.
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 13 of 15
`
`

`

`l8~ nn: UNIX SVSl'l!M l.'.~l'l'l:RfA<.0
`
`:.-:
`
`CHAi"fER 8
`
`~defi ne NAL~OC:
`
`1021
`
`;,,, rninimwn. #units to reque.e.t: */
`
`I• morecore: ask aystern for a,o-re memory .. ;
`sl..~ 1..i¢ H1;1adet' «-moreco:re(·.msigned nu)
`
`char •cp, •sbrk{int);
`nea-der -.up~
`
`if { nu< ~ALLOC)
`nu -= NALLOC;
`cp = abr k(n\;l ~ aizeo((Hea.ded >;
`if (cp == (char ~) -1)
`I• no cpace a~ all •/
`return NULL;
`up-= ( !lead.er tl <=Pi
`-= nu;
`up->.ti . ~h:.1!"
`free{ t void • )( up• 1 :• j :
`retuxn freep~
`
`f.ree llSc:lf is. ihe last tbing. 1t sc.ms the free list, starting at freep> look(cid:173)
`ing for the pl-ate to insert the free biook. This is eitbe-r betwe¢o tWQ existing
`block.s or at one end of the list. In any case. if (h~ block be.Ing freed is adjacent
`to either neighbor, the adjacent bloc~s ,uo combined. The only <roubles are
`keeping t be pointers pointin; to the right. things and the sizes correcl.
`/• free: put block ap in f~te list •I
`voi d fxee(void .,ap:
`\
`
`Heaaer •DP. ~p-:
`
`/* point to block header */
`bp • {He~der , )ap - 1~
`f or (p = freep ;
`t (bp > p 6.S.. bp < p - >s.:pt r); p = p->s . ptr )
`if ~P >= p->s.ptr && tbp > p
`: : bp < p->s.ptr))
`/~ freed block at start or and of arena ~1
`break;
`
`/ +. join to upper nbr •/
`
`i f {bp + bp->s.size == ~ - >s.ptr) (
`bp-_i•R , aiz.e +• p .. .,.s .pi:r•,.s. size ;
`bp->s . ptr
`p-> S-.'Ptr->s. pt r ;
`_) else
`bp->s.ptr • p - >s.ptr:
`i f :p • p->s.s~ze 2~ bp) {
`p-► $,Size += Dp- .>s.size;
`p - >s.ptr ~ bp->s.pt r;
`else
`p->e:.ptr o bp;
`fr~e-p C p;
`
`Although -storage allocation is intrin~JCally mac.:hine-dependem. 1he code
`above illustrates how the machine dc~ndcncics can -be cont rollod .ttnd COr\fine(I
`\0 a sery small part of the program. The use of typedef and union handles
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 14 of 15
`
`

`

`SECTIO~U
`
`6'XA'ff'l.[-A ST'ORA(jEALLOCATOR.
`
`189-
`
`alignment (ih",n that sbrl< suppUes an appropriate pointer). Casts arrange
`that pointer conversion• arc made CJ<plich. and ~vcn cope with a badly-designed
`system interfaoo. F.ven though the details here arc related to storage allncntion,
`the general approach i• applicable to other situa:ions as well.
`Exorcise 8-6. The standard
`library function ealloc(n,size) returns n
`poi.11ler lo n objects ti size eiz e, with the storage injtia.lized lo zero. Write
`ca lloc, by calling malloc or by modifying it. D
`Excrdsc 8-7. malloc accepts a si,c r"'lu .. t v.ithout checking its plausibilit);
`free believes that the block ii iJ asked to f·ee oontains a valid size fleld.
`Improve these routine.• so they t.'!kc more pains with error checking. 0
`Excrcix 8-8. Write a routine bfroe(p,n) th•t will free an arbitrary block p
`of n characters into the fr~ list maintained by .mal loc and free. By uiing:
`bLree, a u1Cr can add a static or external •rr•y to the free list at any time. a
`
`-
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1010
`Page 15 of 15
`
`