Aa!rӀ}  0 U `P`0 p 0`PP`HH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?,ds dsTOCHeading1Heading2   ZEquationVariablesPL::=M:M-%M';;R<<$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear>;<$monthname> <$daynum>, <$year> <$hour>:<$minute00> <$ampm>"<$monthnum>/<$daynum>/<$shortyear><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear> <$fullfilename> <$filename> <$paratext[Title]> <$paratext[Heading1]> <$curpagenum> <$marker1> <$marker2> (Continued)+ (Sheet <$tblsheetnum> of <$tblsheetcount>)Heading & Page <$paratext> on page<$pagenum>Pagepage<$pagenum>See Heading & Page%See <$paratext> on page<$pagenum>. Table All7Table<$paranumonly>, <$paratext>, on page<$pagenum>Table Number & Page'Table<$paranumonly> on page<$pagenum>AHeadings-kHTML##EA||~~A5y::: 55: MMM  ::::: ::::?:A:C:E:G:I:K:M:O:|:~::::::::::::::::::::::::::::;;;;;!;#;%;';);T;V;X;Z;\;^;`;b;d;fA ;jA A ;;;;;;;A?;;;;;;;A-;;;;;;;A;;;;;AA;A/A1<AAAC<<<<>>>> > > >>>>>>>>>>!>#>%>'>)>+>->/>1>3>5>7>9>;JC>?>A>C>E>G>I>K>M>O>Q>S>U>WGJEGJHK=HKQHKI KIAK@@@AA AAA AAA AM! LM M M"1. M#M$M%2. M&M'M(M)M*M+M,M0I Exercise 1. M1M23. M3M4M5M63.1. M7M8M9M:M;M<M=M>M?M@MAMBMCMDMEMFMGMHMIMJMKMLMMMNMOMPMQMRMSMTMUMVMWMX3.2. MYMZM[M\M]M^M_M`MaMbMcMdMeMfMgMhMiMjMkMlMmMnMoMpMqMrMsMtMuMvMwMxMyMzM{M|M}M~MMMMMMMMMMMMMMMMI Exercise 2. M3.3. MMMMMMMMMMMMMMMMMMMMMI Exercise 3. MMO3.4. OMMMMMMMMMMMMMMMMMMMMI Exercise 4. M#MM3.5. MM$M$M$M$M$M$M$M$M$M$MM4. MM4.1. MMMMM"MM#MM#MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNNNNNNNNNN N N N N NNNNNNNNNI Exercise 5. NI Exercise 6. N4.2. NNNNN N!N"N#N$N%N&N'N(N)N*N+N,N-N.N/N0N1N2N3N4N5N6N7N8N9N:N;N<N=N>N?N@NANBNCNDNENFNGNHNINJNKNLNMNNNONPNQNRNSNTNUNVNWNXNYNZN[N\N]NaI Exercise 7. NbI Exercise 8. NcI Exercise 9. NdNeNfNgNhNiNjNkNlNmNnNoNpNqNrNsNtNuNvNwNxNyNzN{N|N}N~NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN(1.N*2.N*3.NNNNNNNNNNNNNNNI Exercise 10. NI Exercise 11. N4.3. NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN#NNNNNNNNNNNNNNNOI Exercise 12. $O4.4. OOOO O O O O OOOOOOOOOOOOOOOOOOO O!O"O#O$O%O&O'O(O,I Exercise 13. O-IExercise 14. O.O/4.5. O0O1O2O3O4O5O6O7O8O9O:O;O<O=O>O?O@OAOBOCODOEOFOGOHOIOJOKOLOMONOOOPOQOROSOTOUOVOWOXOYOZO[O\O]O^O_O`4.6. OaObOcOdOeOfOgOhOiOjOkOlOmOnOoOpOqOrOsOtOuOvOwOxOyOzO{O|O}O~OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOIExercise 15. OIExercise 16. OOOO4.7. OOIExercise 17. OIExercise 18. O5. OOIExercise 19. OIExercise 20. O1OOEdqd:H¸M##dM " HmRM HmRHRHR Footnote Hr@MHr@HzHz Single LineHM Footnote M  HDM HDHH Double LineHM Double LineM M HM  Single LineM HZM " TableFootnoted5p HHˆ5xHHˆGe HHˆ5zHHˆl $$:$$wqGBm V $$:$$l} : GeHeadings Table } :  Ge } :  Ge }l: lG eHeading Level HUV 5HUV Ge HUV 5HUV l H$ 5H$ Ge H$ 5H$ l HHˆ5HHˆƒ -- `Robust Programming   hMatt Bishop Y q Department of Computer Science 0E"University of California at Davis @Davis, CA 95616-8562 uh` Introduction vz yRobust programming, also called  bomb-proof programming , is a style of programming that prevents abnormal termi0xnation or unexpected actions. Basically, it requires code to handle bad (invalid or absurd) inputs in a reasonable way. vIf an internal error occurs, the program or library terminates gracefully, and provides enough information so the pro@*grammer can debug the program or routine. w tThis handout discusses the principles of bomb-proof coding, and gives you a detailed example of how to do it right. 0sOur example is library for managing queues (FIFO lists) of numbers. This allows the example to consider parameters yand global variables. The principles apply to programs, also; specifically, input and parameters are equivalent, and the @&environment is like global variables. x`!Principles of Robust Programming y`}A robust program differs from a non-robust, or  fragile , program by its adherence to the following four principles: z vParanoia . Dont trust anything you dont generate! Whenever someone uses your program or library routine, assume 2vthey will try to break it. When you call another function, check that it succeeds. Most importantly, assume that your @pown code will have problems, and program defensively, so those problems can be detected as quickly as possible. { 0 Stupidity .   Assume that the caller or user is an idiot, and cannot read any manual pages or documentation. Program so 2<sthat the code you write will handle incorrect, bogus, and malformed inputs and parameters in a reasonable fashion, qreasonable being defined by the environment. For example, if you print an error message, the message should be xself-explanatory and not require the user to look up error codes in a manual. If you return an error code to the caller u(for example, from a library routine) make the error codes unambiguous and detailed. Also, as soon as you detect the @Rproblem, take corrective action (or stop). This keeps the error from propagating. |{ xPart of the problem is that in a week, you most likely will have forgotten the details of your program, and may call it @dincorrectly or give it bogus input. This programming style is also a form of defensive programming. } uDangerous Implements.  A dangerous implement is anything that your routines expect to remain consistent across 2wcalls. For example, in the standard I/O library, the contents of the FILE structure for allocated files is expected to sremain fixed across calls to the standard I/O library. That makes it a dangerous implement. Dont let users gain xaccess to these! They might accidentally (or deliberately) modify the data in that data structure, causing your library xfunctions to fail badly. Never return pointers or indices into arrays; always hide the true addresses (or indices) by @"using something called a token. ~᪌ mHiding data structures also makes your program or library more modular . For example, the queue manager uses 0rarrays to represent queues. This gives them a maximum size. You might decide that linked lists would be more suituable and want to rewrite the routines. If you have properly designed the interface and hidden as much infomation and vdata as possible, the calling program need not be changed; however, if you neglected this style of information hiding qand information abstraction, programs that correctly function with the current representation might break if you uchanged that representation (because the caller assumed that the queue elements are in sequential integer locations, @for example).  8 {Cant happen.  As the old saw goes, never say never. Impossible cases are rarely that; most often, they are merely rDqhighly unlikely. Think about how those cases sould be handled, and implement that type of handling. In the worst ycase, check for what you think is impossible, and print an error message if it occurs. After all, if you modify the code xrepeatedly, it is very likely that one modification will affect other parts of the code and cause inconsistent effects, @0which may lead to impossible cases occurring. HHˆ5HHˆl}: G eParagraph Format }:!G e Comments }l: )lGe4 EGxRMEGxREPwEPw TableFootnoteM$$l M#W `! 1998,1999,2000 by Matt Bishop. HH-%M.&& -.M/%-. =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset HH-1Mx(( -.M'-. =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset }:!*GeBody }:)uGe d:8-- $$:9+$$(a-(XSNID?:50+& l^bf~zvrnjUX[IMQ.14FC@=:7GBm ` _ ^ ] Z W $$:;+$$%,,l} :>iT1 jGeCharacter Macros } :@i jGe } :Bi jGe }H:Di.2HjGe Character }:Fi13jGe Replace With }:Hi24jGe Comments }H:Ji35HjGe }:Li46jGe¢ }:Ni5FjGe }H:{i<8HjGe }:}i79jGe... }:i8jGe }H:i?;HjGe }:i:<jGe- }:i;7jG e }H:iB>Hj G!e }:i=?j G"e-- }:i>:j G#e }H:iEAHj G$e }:i@Bj G%e° }:iA=j G&e }H:iHDHj G'e }:iCEj G(e® }:iD@j G)e }H:i6GHj G*e }:iFHj G+e© }:iGCj G,e } :i]M j G-eGeneral Macros } :i j G.e } :i j G/e } :i j G0e }h:iINhjG1e Macro Name }h:iMOhjG2e Replace With }h:iNPhjG3eHead }:iOQjG4e Comments }h:iPRhjG5e }h:iQShjG6e }h:iRThjG7e }:iS.jG8e } ;iX j G9eCross-Reference Macros } ;i j G:e } ;i j G;e };iUYj G<e Macro Name }; iXZj G=e Replace With };"iY[j G>e Comments };$iZ\j G?e See Also };&i[]j G@eSee <$paratext> };(i\Ij GAe } ;S#nb $ GBeSystem Macros } ;U# $ GCe } ;W# $ GDe } ;Y# $ GEe }h;[#^ch$ GFe Macro Name }h;]#bdh$ GGe Replace With }h;_#ceh$ GHeHead }h;a#dfh$ GIe Comments }h:;c#egh:$ GJe StartOfDoc }h:;e#fhh:$ GKe }h:;g#gih::$ Pe L��e <$defaulttitle> N��e AOe }h:;i#hh:$ GMe }h;#qkh$ GQeEndOfLastSubDoc }h;#jlh$ GRe }h;#kmh$ GSe }h;#lh$ GTe }h:;#uoh:$ GUeStartOfLastSubDoc }h:;#nph:$ GVe }h:;#oqh::$ ue W��e <$defaulttitle> s��e Ate }h:;#pjh:$ GXe }h;#ysh$ GYeEndOfFirstSubDoc }h;#rth$ GZe }h;#suh$ G[e }h;#tnh$ G\e }h:;#}wh:$ G]eStartOfFirstSubDoc }h:;#vxh:$ G^e }h:;#wyh::$ re _��e <$defaulttitle> p��e Aqe }h:;#xrh:$ G`e }h;#{h$ Gae EndOfSubDoc }h;#z|h$ Gbe }h;#{}h$ Gce }h;#|vh$ Gde }h:;#h:$ GeeStartOfSubDoc }h:;#~h:$ Gfe }h:;#h::$ oe g��e <$defaulttitle> m��e Ane }h:;#zh:$ Ghe }h;#ih$ Gie EndOfDoc }h;#h$ Gje }h;#h$ Gke }h;#~h$ Gle } <#*  $ GveHTML Options Table } <# $ Gwe } <# $ Gxe }< # $ GyeControl }<"# $ GzeValue }H<$# H$ G{e Comments }<&# $ G|e Image Format }<(# $ G}eIMAGGIF }H<*# lH$ G~e } 6$ 'G#eX:Page }H<#57H$ 'G$e See Also }6<#686$ 'G%eN }6<#796$ 'G&eN }<#80$ 'G'e }<#C;$ (G(eX:Heading & Page }H<#:<H$ (G)e See Also }6<#;=6$ (G*eN }6=#<>6$ (G+eN }=#=5$ (G,e }=#H@$ )G-eC:EquationVariables }H=#?AH$ )G.eEM }6=#@B6$ )G/eN }6= #AC6$ )G0eN }= #B:$ )G1e }=#ME$ *G2e C:Emphasis }H=#DFH$ *G3eEM }6=#EG6$ *G4eN }6=#FH6$ *G5eN }=#G?$ *G6e }=#RJ$ +G7eC:Code }H=#IKH$ +G8eEM }6=#JL6$ +G9eN }6=#KM6$ +G:eN }= #LD$ +G;e }="#WO$ ,G<eC:Bold }H=$#NPH$ ,G=eEM }6=&#OQ6$ ,G>eN }6=(#PR6$ ,G?eN }=*#QI$ ,G@e }=,#\T$ -GAeP:Title }H=.#SUH$ -GBeH* }6=0#TV6$ -GCeN }6=2#UW6$ -GDeN }=4#VN$ -GEe },=6#Y,$ .GFe P:TableTitle }H,=8#XZH,,$ .ceLI Ge Parent = OL Ade Depth = 0 }6,=:#Y[6,$ .GHeN }6,=<#Z\6,$ .GIeN },=>#[S,$ .GJe }=@+f^, /GKeP:TableFootnote }H=B+]_H, /GLeP }6=D+^`6, /GMeN }6=F+_a6, /GNeN }=H+`, /GOe }=J+kc, 0GPeP:Rule }H=L+bdH, 0GQeP }6=N+ce6, 0GReN }6=P+df6, 0GSeN }=R+e], 0GTe },=T+ph,, 1GUe P:Numbered1 }H,=V+giH,,, 1aeLI Ve Parent = OL Abe Depth = 0 }6,=X+hj6,, 1GWeN }6,=Z+ik6,, 1GXeN },=\+jb,, 1GYe },=^+um,, 2GZe P:Numbered }H,=`+lnH,,, 2_eLI [e Parent = OL A`e Depth = 0 }6,=b+mo6,, 2G\eN }6,=d+np6,, 2G]eN },=f+og,, 2G^e }=h+zr, 3G_eP:Mapping Table Title }H=j+qsH, 3G`eP }6=l+rt6, 3GaeN }6=n+su6, 3GbeN }=p+tl, 3Gce }=r+w, 4GdeP:Mapping Table Cell }H=t+vxH, 4GeeP }6=v+wy6, 4GfeN }6=x+xz6, 4GgeN }=z+yq, 4Ghe }=|+|, 5GieP:ManHeading2 }H=~+{}H, 5GjeP }6=+|~6, 5GkeN }6=+}6, 5GleN }=+~v, 5Gme }=+ , 6Gne P:ManHeading }H=+H, 6GoeP }6=+6, 6GpeN }6=+6, 6GqeN }=+{, 6Gre }=+, 7Gse P:ManBody }H=+H, 7GteP }6=+6, 7GueN }6=+ 6, 7GveN }=+, 7Gwe },=+ ,, 8Gxe P:LetteredA }H,=+ H,,, 8]eLI ye Parent = OL A^e Depth = 0 }6,=+ 6,, 8GzeN }6,=+ 6,, 8G{eY },=+ ,, 8G|e },=+,, 9G}e P:Lettered }H,=+H,,, 9[eLI ~e Parent = OL A\e Depth = 0 }6,=+6,, 9GeN }6,=+6,, 9GeY },=+ ,, 9Ge }=+, :Ge P:Indented }H=+H, :GeP }6=+6, :GeN }6=+6, :GeN }=+, :Ge }=+", ;GeP:HeadingRunIn }H=+H, ;GeP }6=+6, ;G eN }6=+6, ;G eN }=+, ;G e }=+', <G e P:Heading2 }H=+ H, <G eH* }6=+!6, <GeN }6=+ "6, <GeN }=+!, <Ge }=+,$, =Ge P:Heading1 }H=+#%H, =GeH* }6=+$&6, =GeN }6=+%'6, =GeN }=+&, =Ge }=+1), >GeP:Heading Info }H=+(*H, >GeP }6=+)+6, >GeN }6=+*,6, >GeN }=++#, >Ge }=+6., ?GeP:Hand }H=+-/H, ?GeP }6=+.06, ?GeN }6=+/16, ?GeN }=+0(, ?Ge }=+;3, @G e P:Footnote }H=+24H, @G!eP }6=+356, @G"eN }6=+466, @G#eN }=+5-, @G$e },=+@8,, AG%e P:Exercise }H,=+79H,,, AYeLI &e Parent = OL AZe Depth = 0 }6,=+8:6,, AG'eN }6,=+9;6,, AG(eN },=+:2,, AG)e }=+E=, BG*e P:Due Date }H>+<>H, BG+eP }6>+=?6, BG,eN }6>+>@6, BG-eN }>+?7, BG.e }>+JB, CG/e P:CodeIndent }H> +ACH, CG0eP }6> +BD6, CG1eN }6>+CE6, CG2eN }>+D<, CG3e }>+OG, DG4e P:CodeCenter }H>+FHH, DG5eP }6>+GI6, DG6eN }6>+HJ6, DG7eN }>+IA, DG8e }>+TL, EG9eP:Code }H>+KMH, EG:eP }6> +LN6, EG;eN }6>"+MO6, EG<eN }>$+NF, EG=e }>&+YQ, FG>eP:CellHeading }H>(+PRH, FG?eP }6>*+QS6, FG@eN }6>,+RT6, FGAeN }>.+SK, FGBe }>0+^V, GGCe P:CellBody }H>2+UWH, GGDeP }6>4+VX6, GGEeN }6>6+WY6, GGFeN }>8+XP, GGGe },>:+c[,, HGHe P:Bulleted }H,><+Z\H,,, HWeLI Ie Parent = UL AXe Depth = 0 }6,>>+[]6,, HGJeN }6,>@+\^6,, HGKeN },>B+]U,, HGLe }>D+h`, IGMe P:BodyList }H>F+_aH, IGNeP }6>H+`b6, IGOeN }6>J+ac6, IGPeN }>L+bZ, IGQe }>N+"e, JGRe P:BodyCenter }H>P+dfH, JGSeP }6>R+eg6, JGTeN }6>T+fh6, JGUeN }>V+g_, JGVe d>kk $$>i$$U9kUX[IMQ.14FC@=:7$$>i$$%jjl}@#m$ KGee!Copy Files Imported by Reference }@#ln$ KGfeN }H@#m^H$ KGge }lAtplLGhe1 }AoqLGi eTitle }ApLGje }lAwslMGke3 }ArtMGle Heading2 }AsoMGme }lA*vlNGne2 }AuwNGoUTe Heading1 }AvrNGpe H-M'yy --Mx-- =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset H(-M dL|H$ L{~H$ }}l H$ L{H$ |Wr h2 URobust Programming aECS 153 Fall 2000 HUV L{|HUV  l HUV L{HUV ~WslbVersion of   bSeptember 26, 2000 11:10 am cPage   d# e of   f18 g HHˆL{~HHˆ l HHˆL{HHˆWte --Mğz-- =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset H -N%& --N-- =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset Hy-N_+, -6N`-6 =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset H-N12 -6N-6 =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset H-O7 8 -6O -6 =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset H-O*: ; -6O+ -6 =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset Hj-O@A -6O -6 =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset HV-O@ A -6O-6 =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset HV-OCD -6O-6 =QuickDraw PICT #%v%' @%(%'%'pppPPPPPPPP0C0@̶001 ch , =EndInset dO HHˆOHHˆƒ11%%"(a [Relate the informal descriptions of the principles of robust programming to the more formal fprinciples of good programming style, such as cohesion and coupling, information abstraction, informa0jtion hiding, and good documentation. The point of this exercise is to show you that robust programs arise @Rfrom writing code in a good style; what you learn in school  is  useful!  pRobust programming is defensive, and the defensive nature protects the program not only from those who use your Eqroutine but also from yourself. Programming is not mathematics; errors occur. Good programming assumes this, and @xtakes steps to detect and report those errors, internal as well as external. Beware of everything even your own code! h`Example of a Fragile Library z sThis library implements queues in a very straightforward way. Its typical of what many C programmers would write. @SIts also very fragile code. Well analyze it in detail to support that statement.  wThe library can handle any number of queues, and when a queue is created, its pointer is returned to the caller. Three entry points are provided:  qmanage , for creating or deleting a queue;  put_on_queue , for adding an element to a 0UGqueue; and  take_off_queue , for deleting an element from a queue. All files calling this routine must include the header @`2As indicated, the queue management functions are: 4ͦ5`$qmanage()create and delete queues;  Y`6put_on_queue()add an element to the end of the queue !V`count =  newvalue ; $ where  qptr  is a pointer to the relevant queue and  newvalue  the expression for the new value to be assigned to the H@queues counter. %W |The use of the macro  MAXELT  also limits the reusability of the library. If the size of the queues is changed, the cwlibrary must be recompiled. However, as the include file macro has changed, the callers of the queue library must also 0Zpbe recompiled; otherwise, the pointers may be invalid (depending on the architecture) and if a routine directly @caccesses any field in the queue structure, not recompiling that file will cause incorrect results. &`JSo, the problem with including this header file in the callers files is: '˪`P+ The callers have access to the internal elements of the queue structure. (`The Queue Management Function )ª`AThe first function controls the creation and deletion of stacks: *Ѫ`/* +ݪ` * create or delete a queue ,C` * -`@ * PARAMETERS:QUEUE **qptrspace for, or pointer to, queue .`. * int flag1 1 for create, 0 for delete /`& *int sizemax elements in queue 0` */ 1`/void qmanage(QUEUE **qptr, int flag, int size) 2`{ 3` if (flag){ 4`/* allocate a new queue */ 5`!*qptr = malloc(sizeof(QUEUE)); 6`&(*qptr)->head = (*qptr)->count = 0; 7`-(*qptr)->que = malloc(size * sizeof(int)); 8`(*qptr)->size = size; 9`} :`else{ ;`!/* delete the current queue */ <`(void) free((*qptr)->que); =`(void) free(*qptr); >`} ?`} @ܪ Glancing over it, we see it uses logical cohesion because the parameter  flag  indicates which of two distinct, logically 誆vseparate operations are to be performed. The operations could be written as separate functions. That this routine has Z@;such poor cohesion does not speak well for its robustness. A Consider the parameter list, and the calling sequence. The  flag  parameter is an integer that indicates whether a queue is to be created (if  flag  is non-zero) or deleted (if  flag  is zero). The  size  parameter gives the maximum number of inte$@Hgers to be allowed in the queue. Suppose a caller interchanged the two: B*`qmanage(&qptr, 85, 1); C䛭= The  qmanage  routine would not detect this as an error, and will allocate a queue with room for 1 element rather than E@n85. This ease of confusion in the parameters is the first problem, and one that cannot be checked for easily. DT~`C+ The order of elements in the parameter list is not checked. E* }Next, consider the  flag  argument. When does it mean to create a queue and when does it mean to delete a queue? For o|wthis function, the intention is that 1 means create and 0 means delete, but the coding style has changed this to allow Pxޟtany non-zero value to mean create. But there is little connection between 1 and create, and 0 and delete. So psychoHHˆOHHˆldO HHˆOHHˆaU..Erlogically, the programmer may not remember which number to use and this can cause a queue to be destroyed when it should have been created. Using  enum s would help here if the library is compiled with the program, but if the library @~is simply loaded,  enum s do not help as the elements are translated into integers (so no type checking can be done). F`5+ The value of the flag parameter is arbitrary. G xThe first parameter is a pointer to a pointer necessary when a value is returned through the parameter list, as all C Htfunction arguments are passed by value. Passing a pointer provides the call by reference mechanism. However, a call 0Buby reference usually uses a singly indirect pointer; if a doubly indirect pointer is used, programmers will make mis|takes (specifically, pass a singly indirect pointer). In general, it is better to avoid call by reference; when it is neces@Msary, do not use multiple levels of indirection unless absolutely necessary. H{`C+ Using pointers to pointers causes errors in function calls. IUE }The third set of problems arises from a failure to check parameters. First look at queue creation. Suppose  qptr  is   NULL  or an invalid pointer. Then the line containing  malloc  will cause a segmentation fault. Also, suppose  size  is UUnon-positive. What happens when the queue is allocated (the second  malloc )? If  size  is 0, most  malloc s will return a  NULL  pointer, but this is not universal. If  size  is negative, the result is implementation dependent and may cause a @Esegmentation violation. In either case, the result is unpredictable. Jɪ Now look at queue deletion. The parameter  size  is irrelevant, but suppose  qptr  or  *qptr  is  NULL . Then the result of  ժfree  is undefined and may result in a segmentation fault. Worse, imagine the parameter is not  NULL  but instead a 2Uuwmeaningless address. This is almost impossible to catch before the call, and causes segmentation violations (if lucky) @*or very odd behavior afterwards (if not). K`4+ The parameter values are not sanity checked. L<`\The calling sequence is not checked either. Suppose one deletes a queue before creating it: M`qmanage(&qptr, 0, 1); N&` /* ... */ OM`qmanage(&qptr, 1, 100); PA tThis would either cause a segmentation violation when called, or the releasing of unallocated memory; in the latter Mcase, the program will probably crash later on, with little indication of why. Again, the problem is that  qmanage  does @pnot check that  qptr  refers to a valid queue. However, heres a more subtle variation of this problem: Qh`qmanage(&qptr, 1, 100); Rt` /* ... */ Su`qmanage(&qptr, 0, 1); T` /* ... */ U`qmanage(&qptr, 0, 1); V Now a queue is deleted twice. Attempting to  free  space that has already been deallocated causes an undefined action, @"usually a segmentation violation. Wª`P+ The user can delete an unallocated queue, or a previously deleted queue. X,  Consider the body of the routine. What happens if either  malloc  fails, and returns  NULL ? The subsequent references ݪ@\to  qptr  to fault, as they are references through a  NULL  pointer. Hence: Y쪅` + Check all return values. ZVtsF`AOne subtle problem arises from overflow. Consider the expression [`size * sizeof(int) \ULUUU$ in the first call to  malloc . Suppose  size  is 2 31 , and an integer is 4 bytes (a common value). Then this expression evalu*ates to 2 33 . On a 32 bit machine, this overflows, and (most likely) produces a value of 0. Such a flaw will most likely 6rnot cause any problems during the call, but will cause the program to produce a segmentation fault in a seemingly 0̥~vunrelated place later on. Overflow (and underflow, in floating point calculations) are very pernicious and nasty prob@lems; watch out for them. S]]`\+ Look out for integer (or floating point) overflow (and underflow, when appropriate). HHˆOHHˆldO HHˆOHHˆƒ00'x^"(x \The obvious way to test for overflow is to multiply the absolute value of  size  and  sizeof(int)   and see if the result is smaller than  size  (because if  a * b < a  when  a > 0  and  b > 0 , then over0oflow has occurred). Does this always work? What problems does it introduce? ( Hint : think about archibtectures allowing arithmetic overflow to cause a trap.) Suggest an alternate method without these @ problems. _O`Adding to a Queue `_ sThis function adds an element to the queue. It adds the index of the head element to the current count (modulo the k@Xqueue size), and places the new element at that location; it then increments the count: az`/* b`' * add an element to an existing queue c` * d`9 * PARAMETERS:QUEUE *qptrpointer for queue involved e`# *int nelement to be appended f` */ g`&void put_on_queue(QUEUE *qptr, int n) h`{ i`(/* add new element to tail of queue */ j`9qptr->que[(qptr->head + qptr->count) % qptr->size] = n; k`qptr->count++; l`} m  Two basic problems arise. First, the  qptr  parameter is not checked to ensure it refers to a valid queue; it may refer to a |queue that has been deleted, or to random memory, or may be  NULL . Any of these will cause problems; if the caller 0 U1~is lucky, the problem will arise in this routine; if the caller is unlucky, the symptom will not appear until later on in the @/program, with no indication of what caused it. n@`+ Check all parameters. o`|As an offshoot of this, suppose  qptr  is valid but  que  is not. Then the routine will not work correctly: p`?+ Check for incorrect values in structures and variables. q Second, suppose the queue is full (that is,  qptr->count  equals  qptr->size ). If this function is called, it will overwrite yqthe head of the queue. There is no check for an overflowing queue, doubtless because the author assumed it would ̂@never happen. r`6+ Check for array overflow when inserting items. s띫 vA more sophisticated problem is the placing of trust in the values of the queue structure. The integrity of the queue structure depends on the consistency of the  count ,  size , and  head  fields. If  size  increases between calls, the routine 0-will think that the queue has been allocated more space than it actually has, leading to a segmentation fault. If  size  @6decreases between calls, some elements might be lost. t֪"(n hWrite a program that demonstrates when decreasing  size  between calls to  add_to_queue  ⪇ecauses elements previously added to the queue to become inaccessible. Describe the problems that can @rarise if the values of  head  and/or  count  are changed across calls to  put_on_queue . u` vS sGiven the accessibility of the queue structure elements to the callers, these elements may change (accidentally or @deliberately). w1`!Removing Elements from the Queue xA Taking elements off the queue begins by getting the element at index  head . Then count is decremented, and  head  is M@%incremented (modulo  size ): y\`/* zh`6 * take an element off the front of an existing queue {v` * A|`9 * PARAMETERS:QUEUE *qptrpointer for queue involved HHˆOHHˆ!ldO!! HHˆOHHˆ|..zz!}`, *int *nstorage for the return element ~` */ `)void take_off_queue(QUEUE *qptr, int *n) `{ `3/* return the element at the head of the queue */ `*n = qptr->que[qptr->head++]; `qptr->count--; `qptr->head %= MAXELT; `} u The parameter problems described in the previous section exist here too;  qptr  may be invalid,  NULL , or point to an @Qinvalid queue. Moreover,  n  may also be an invalid integer pointer. So: `+ Check all parameters. `?+ Check for incorrect values in structures and variables.   Here. the danger is underflow, not overflow. Suppose there are no elements in the queue. The value returned through  n  @Jwill be garbage, and  count  will be set to a bogus value. Hence:  ɪ`8+ Check for array underflow when extracting items.  ``OThe problem of variable consistency across calls occurs in this routine, also.  "he iWhat problems might an invalid pointer for  n  cause? Specifically, suppose in the call  ` take_off_queue(qptr, c)  zthe variable c is declared as a  char *  or a  float * ? How would you solve these problems in a portable @manner? *`Summary :`The library  fqlib.c , the contents of which are presented in this section, is very fragile code. Among its flaws are: I`IThe callers have access to the internal elements of the queue structure. U`9The order of elements in parameter lists is not checked. )`bThe value of command parameters (which tell the function what operation to perform) is arbitrary. `> 16) & 0xffff &)`and '`Dnonce  =  f ( index ,  nonce ) & 0xffff (`*where & and >> are the usual C operators. ) zThis simplifies the interface considerably, but at the cost of assuming a 32-bit quantity (or greater). Fortunately, most @\systems have a datatype supporting integers of this length. So, in the header file, we put: *`J/* queue identifier; contains internal index and nonce mashed together */ +`typedef long int QTICKET; ,`[With this token defined, calling routines need know nothing about the internal structures. -u`P+ Dont hand out pointers to internal data structures; use tokens instead. . sThe second issue is errors; how to handle them? We can print error messages (and take action, possibly even termiA{nating), we can return error results and allow the caller to handle the error, or we can set up special error handlers (if 0Qvthe language supports these; they are typically written as trap or exception handlers). Unfortunately, C does not provvide exception handlers for errors. The method of returning error codes to the caller allows much greater flexibility xthan handling the error in the routine, and is equally simple to perform. The complication is that a set of error codes ymust indicate the errors that could occur. So, as we proceed through our library, we shall track errors and define error @codes. / x+ Handle errors in a consistent manner: either print error messages from a centralized printing routine, or return @?error codes to the caller and let the caller report the error. 0 uWe make some decisions about the library functions for this purpose. The return value will indicate whether an error yhas occurred; if so, the function returns an error code and an expository message in a buffer. If not, it returns a flag ѫ@Cindicating no error. So, we define all error codes to be negative: 1Ϊ`/* 2ڪ` * error return values 3`6 * all the queue manipulation functions return these; 4`7 * you can interpret them yourself, or print the error 5`5 * message in qe_errbuf, which describes these codes 6` */ 7`I#define QE_ISERROR(x)((x) < 0)/* true if x is a qlib error code */ 8`'#define QE_NONE 0/* no errors */ 9`/* :`B * the error buffer; contains a message describing the last queue ;`F * error (but is NUL if no error encountered); not cleared on success <` */ =`extern char qe_errbuf[256]; >m{ Like the UNIX system variable  errno (3),  qe_errbuf  is set on an error but not cleared on success. The buffer will conPyzutain additional information (such as in which routine the error occurred and relevant numbers). The following macros HHˆO"HHˆ!'##ldO'' HHˆO%HHˆ„11'>@aid this process: ?`"/* macros to fill qe_errbuf */ @`I#define ERRBUF(str)(void) strncpy(qe_errbuf, str, sizeof(qe_errbuf)) AUR`<#define ERRBUF2(str,n)(void) sprintf(qe_errbuf, str, n) B`A#define ERRBUF3(str,n,m)(void) sprintf(qe_errbuf, str, n, m) CH These are defined in  qlib.c  because they format messages placed in  qe_errbuf ; the functions that call the library have T@no use for them. Dc`hWe also redefine the function interface to eliminate the low cohesion of the  qmanage  routine: E`7int create_queue(QTICKET *);/* create a queue */ F~`5int delete_queue(QTICKET);/* delete a queue */ G[`Fint put_on_queue(QTICKET, int);/* put number on end of queue */ H`Nint take_off_queue(QTICKET, int *);/* pull number off front of queue */ I`KThis eliminates the use of a flag variable to manage creation or deletion. J5`gIn the  qlib.c  file we place the definition of the queue structure and the related variables: K`./* macros for the queue structure (limits) */ LϪ`1#define MAXQ1024/* max number of queues */ MI`?#define MAXELT1024/* max number of elements per queue */ N` O`/* the queue structure */ P`:typedef int QELT;/* type of element being queued */ Q`typedef struct queue { R`4QTICKET ticket;/* contains unique queue ID */ S`.QELT que[MAXELT];/* the actual queue */ T`4int head;/* head index in que of the queue */ U`3int count;/* number of elements in queue */ V` } QUEUE; W`+/* variables shared by library routines */ X`;static QUEUE *queues[MAXQ];/* the array of queues */ Y`%/* nonce generator -- this */ Z`Lstatic unsigned int noncectr = NOFFSET;/* MUST be non-zero always */ [ vWe made one change to the queue definition: all queues are to be of fixed size. This was for simplicity (see the exer@cise below). Also, all globals are declared  static  so they are not accessible to any functions outside the library file. \ We distinguish between an  empty  queue and a  nonexistent  queue. The former has its  count  field set to 0 (so the queue exists but contains no elements); the latter has the relevant element in  queues  set to  NULL  (so the queue does not %@exist). ]Ȫ"(u jThe macros  ERRBUF2  and  ERRBUF3  use  sprintf  to format the error message. What probԪ@Ylem does this function not guard against? Why can we ignore this problem in our library? ^㪅 [What problems does static allocation of space for each queues contents and for all queues 彩@introduce? What advantages? _`Token Creation and Analysis ` yOne function internal to the library creates a token from an index, and another takes a token, validates it, and returns $@the appropriate index. a3 xThese are separate routines because we need to be able to change the tokens representation if the library is ported to ?pa system without a 32-bit quantity to store the token in. Or, we may prefer to modify the mathematical function 01tTYwinvolved. In either case, this increases cohesion and decreases coupling, laudable goals from the software engineering @!(and maintenance!) perspectives. bf} In what follows,  IOFFSET  is the offset added to the index of the element and  NOFFSET  is the initial nonce. Both are r|@defined in  qlib.c : Sc{`D#define IOFFSET0x1221/* used to hide index number in ticket */ HHˆO%HHˆ$*&&ldO** HHˆO(HHˆ…55* d`.#define NOFFSET0x0502/* initial nonce */ e`*Here is the function to generate a token: f`/* g`F * generate a token; this is an integer: index number + OFFSET,,nonce h`0 * WARNING: each quantity must fit into 16 bits i` * j`) * PARAMETERS:int indexindex number k`6 * RETURNED:QTICKETticket of corresponding queue l`6 * ERRORS:QE_INTINCON* index + OFFSET is too big m` ** nonce is too big n` ** index is out of range o`- *(qe_errbuf has disambiguating string) p` * EXCEPTIONS:none q` */ r`+static QTICKET qtktref(unsigned int index) s`{ t`<unsigned int high;/* high 16 bits of ticket (index) */ u`:unsigned int low;/* low 16 bits of ticket (nonce) */ v` w`4/* sanity check argument; called internally ... */ x`if (index > MAXQ){ y`8ERRBUF3("qtktref: index %u exceeds %d", index, MAXQ); z`return(QE_INTINCON); {`} |` }`/* ~`> * get the high part of the ticket (index into queues array, `' * offset by some arbitrary amount) `G * SANITY CHECK: be sure index + OFFSET fits into 16 bits as positive ` */ `"high = (index + IOFFSET)&0x7fff; `if (high != index + IOFFSET){ `5ERRBUF3("qtktref: index %u larger than %u", index, `0x7fff - IOFFSET); `return(QE_INTINCON); `} `  `/*  `+ * get the low part of the ticket (nonce)  `2 * SANITY CHECK: be sure nonce fits into 16 bits  ` */  `low = noncectr & 0xffff; `'if ((low != noncectr++) || low == 0){ `8ERRBUF3("qtktref: generation number %u exceeds %u\n", `(noncectr - 1, 0xffff - NOFFSET); `return(QE_INTINCON); `} ` `'/* construct and return the ticket */ `)return((QTICKET) ((high << 16) | low)); `} sw`_The function is declared  static  so that only functions in the library may access it. Qƪ vRather than return a value through the parameter list, we compute the token and return it as the function value. This HHˆO(HHˆ'-))ldO-- HHˆO+HHˆ22- xallows us to return error codes as well (since tokens are always positive, and error codes always negative). The single @=parameter is an index for which the token is to be computed. `V+ Make interfaces simple, even if they are for routines internal to the library. UR The next  if  statement checks the value of the parameter; in this case, it must be a valid array index (between 0 and  sMAXQ  inclusive). As the parameter is unsigned, only the upper bound need be checked. This may seem excessive; DUPwafter all, this function is only called within our library, so cant we ensure the parameter is always in the expected 0vrange? The principle of cant happen applies here. We can indeed assure the index always lies within the range, but wsuppose someone else one day modifies our code and makes an error. That error could cause the library to fail. So its @best to program defensively. {`A+ Always check parameters to make sure they are reasonable. UJ xIf an error occurs, it should be identified precisely. Two techniques are combined here. The first is an error message, giving the name of the routine and an exact description of the problem. It is in  qe_errbuf , and available to the caller. UK@\The second is a return value indicating an error (specifically, an internal inconsistency): `7#define QE_INTINCON-8/* internal inconsistency */ UC`@The calling routine must detect this error and act accordingly.  t+ Give useful and informative error messages. Include the name of the routine in which the error occurs. Allow ۪@Qnumbers in the error message. Use error codes that precisely describe the error.  ꪙ x.The error code here indicates an internal inconsistency (because an error indicates another library routine is calling  zqtktref  incorrectly). An error message or code simply indicating an error occurred would be less helpful, because we F@Rwould not know why the error occurred, or (depending on the error message) where. ! z The next statements add the offset to the index. As this is to be the upper half of a 32-bit number, it must fit into 16 ybits as a signed number. The code checks that this requirement is met. Again, if it is not met, a detailed error message @ is given. "8"h- kExplain how the check works, in detail. #1c xThe code uses  0x7fff  to mask  index  for the comparison instead of using  0xffff . Why is the S@mask 15 bits instead of 16? $b hThe check for  noncectr  is similar, but uses 0xffff as a mask. Explain why it does not need to n@ use 0x7fff. %}`]The routine to break down a token into its component parts, and check the queue, is similar: &f/`/* '`3 * check a ticket number and turn it into an index (H` * )`: * PARAMETERS:QTICKET qnoqueue ticket from the user *`+ * RETURNED:intindex from the ticket +`= * ERRORS:QE_BADTICKETqueue ticket is invalid because: ,`) ** index out of range [0 .. MAXQ) -`# ** index is for unused slot .` ** nonce is of old queue /`. *(qe_errbuf has disambiguating string) 0`= *QE_INTINCONqueue is internally inconsistent because: 1`. ** one of head, count is uninitialized 2` ** nonce is 0 3`. *(qe_errbuf has disambiguating string) 4` * EXCEPTIONS:none 5` */ 6` static int readref(QTICKET qno) 7`{ 8`;register unsigned index;/* index of current queue */ 9`9register QUEUE *q;/* pointer to queue structure */ A:` HHˆO+HHˆ*0,,ldO00 HHˆO.HHˆ|440 ;`6/* get the index number and check it for validity */ <`+index = ((qno >> 16) & 0xffff) - IOFFSET; =`if (index >= MAXQ){ >`8ERRBUF3("readref: index %u exceeds %d", index, MAXQ); ?`return(QE_BADTICKET); @`} A`if (queues[index] == NULL){ B`=ERRBUF2("readref: ticket refers to unused queue index %u", C`index); D`return(QE_BADTICKET); E`} F` G`/* H`< * you have a valid index; now validate the nonce; note we I`< * store the ticket in the queue, so just check that (same J`  * thing) K` */ L`$if (queues[index]->ticket != qno){ M`CERRBUF3("readref: ticket refers to old queue (new=%u, old=%u)", N`0((queues[index]->ticket)&0xffff) - IOFFSET, O`(qno&0xffff) - NOFFSET); P`return(QE_BADTICKET); Q`} R` S`/* T`% * check for internal consistencies U` */ V`;if ((q = queues[index])->head < 0 || q->head >= MAXELT || W`)q->count < 0 || q->count > MAXELT){ X`?ERRBUF3("readref: internal inconsistency: head=%u,count=%u", Y`q->head, q->count); Z`return(QE_INTINCON); [`} \`!if (((q->ticket)&0xffff) == 0){ ]`6ERRBUF("readref: internal inconsistency: nonce=0"); ^`return(QE_INTINCON); _`} `` a`"/* all's well -- return index */ b`return(index); c`} d vThe argument for this function is a token representing a queue; the purpose of this function is to validate the token and return the corresponding index. The first section of  readref  does this; it derives the index number from the token, ~and checks first that the index is a legal index, then that there is a queue with that index. If either fails, an appropriate 0serror message is given. Notice that the error code simply indicates a problem with the parameter, although the mes@;sage in  qe_errbuf  distinguishes between the two. e4|`T+ Make parameters quantities that can be checked for validity, and check them. fnT zAs the caller of the library has supplied the token, a bogus token is not an internal error. So we use another error code Oz@to indicate the problem: g^y`:#define QE_BADTICKET-3/* bad ticket for the queue */ h wNext, we check that the queue with the same index as the token is the queue the token refers to. This is the dangling Pywpreference problem mentioned earlier. The current queues token is stored in each queue structure, so we simply HHˆO.HHˆ-3//ldO33 HHˆO1HHˆ~003 h@Zensure the current token is the queues token. If not, we handle the error appropriately. i`9+ Check for references to outdated data structures. j xThe last section of code checks for internal consistency. The goal is to detect problems internal to the queue library. @The consistency checks are: k`RThe position of the queue  head  must lie between 0 and  MAXELT . lK`gThe  count  of elements in the queue must be nonnegative and no greater than  MAXELT . mR`^The nonce can never be 0. This prevents a random integer 0 from being taken as a valid token. nf`>When any of these are detected, the routine reports an error. or uAn alternate approach, favored by some experts, is to make this code conditionally compilable, and omit it on produc@=tion versions. They either use #ifdefs to surround the code: p` #ifdef DEBUG q`/* the code goes here */ r`#endif s ~or use the  assert () macro. This saves space when the library is provided for production, but can make tracking down êsany problems more difficult when they occur in production software, because less information is provided than in a UA@development environment. tު`p+ Assume debugged code isnt. When its moved to other environments, previously unknown bugs may appear. uUN The  assert () macro is (described in the manual as  assert (3) Its argument is an expression, and that expression is evalzuated. If the expression is false, the macro writes a message to the standard error, aborts the program and forces a core U.@idump for debugging purposes. For example, the internal consistency checking code could be replaced with: v`=assert((q = queues[index])->head < 0 || q->head >= MAXELT); w `,assert(q->count < 0 || q->count > MAXELT); xX`#assert((q->ticket)&0xffff) != 0); y;`RIf the middle  assert  expression were false, the error message would be: z7`Massertion q->count < 0 || q->count > MAXELT failed file qlib.c, line 178 {aU If the compile-time constant  NDEBUG  is defined, all  assert () macros are empty, so they are in effect deleted from the e@ program. |t"(n lThe  assert  macro aborts the program if the condition fails. It applies the theory that if the mlibrary is internally inconsistent, the entire set of queues cannot be trusted. The other methods allow the @5caller to attempt to recover. Which is better? When? } _Assume  IOFFSET  were not added to indices. What error message would be printed if the @(QTICKET were 0? Why is this misleading? ~`Queue Creation Ъ`3The routine  create_queue  creates queues: ߪ`/* 몈` * create a new queue ` * w` * PARAMETERS:none `? * RETURNED:QTICKETtoken (if > 0); error number (if < 0) `- * ERRORS:QE_BADPARAMparameter is NULL `6 *QE_TOOMANYQStoo many queues allocated already `1 *QE_NOROOMno memory to allocate new queue `+ *(qe_errbuf has descriptive string)  ` * EXCEPTIONS:none  ` */  `QTICKET create_queue(void)  `{ A `3register int cur;/* index of current queue */ HHˆO1HHˆ0622ldO66 HHˆO4HHˆ‚336 `=register QTICKET tkt;/* new ticket for current queue */ ` `/* check for array full */ `!for(cur = 0; cur < MAXQ; cur++) `if (queues[cur] == NULL) ` break; `if (cur == MAXQ){ `;ERRBUF2("create_queue: too many queues (max %d)", MAXQ); `return(QE_TOOMANYQS); `} ` `/* allocate a new queue */ `5if ((queues[cur] = malloc(sizeof(QUEUE))) == NULL){ `2ERRBUF("create_queue: malloc: no more memory"); `return(QE_NOROOM); `} ` `/* generate ticket */  `&if (QE_ISERROR(tkt = qtktref(cur))){ !`:/* error in ticket generation -- clean up and return */ "`(void) free(queues[cur]); #`queues[cur] = NULL; $`return(tkt); %`} &` '`"/* now initialize queue entry */ (`-queues[cur]->head = queues[cur]->count = 0; )`queues[cur]->ticket = tkt; *` +`return(tkt); ,`} -} uThe parameter list for this routine is empty; all information is returned as a function value. An alternate approach @Rwould be to pass the QTICKET back through the parameter list with the declaration .`int create_queue(QTICKET *tkt) /fu wand have the return value be the error code. But this can lead to confusion. Some library routines require pointers as qarguments; others do not. Programmers may become confused, or suffer memory lapses, about which routines require @Vpointers and which do not. The routine should guard against these potential problems. 0Ϊ`(+ Keep parameter lists consistent. 17 uMaking all parameters be pointers is not suitable. First, pointers are difficult to check for validity; one can (and 骃should) check for  NULL  pointers, but how can one portably determine if a non- NULL  pointer contains an address in ʫxthe process address space or that the address is not properly aligned for the quantity to be stored there (on some sys0stems, notably RISC systems, this can cause an alignment fault and terminate the program)? Using a style of program@Eming akin to functional programming languages avoids these problems. 2`e+ Avoid changing variables through a parameter list; whenever possible, avoid passing pointers. 3˨ {This routine checks if there is room for another queue; if so, it determines the index of the queue; if not, it reports an 7} @xerror and returns an error code. The error code is returned to the calling routine, which is not a part of the library: 4F|`B#define QE_TOOMANYQS-7/* too many queues in use (max 100) */ 53 nIn the error message we supply helpful information, namely the maximum number of queues allowed. This enables az@Rthe programmers to know why the routine failed and tailor their code accordingly. 6py`k+ Check for array overflow and report an error when it would occur (or take other corrective action). S7e The next part allocates space for the queue. Again, the routine checks for a failure in  malloc , and reports it should it HHˆO4HHˆ3955ldO99 HHˆO7HHˆ22 97happen. Again, a special error code is used. This is of special importance since a  malloc  failure is usually due to a system call failure, and  perror (3) will print a more informative message that the caller may desire. The queue librarys @error indicator is: 8`=#define QE_NOROOM-6/* can't allocate space (sys err) */ 9`B+ Check for failure in C library functions and system calls. : uThe routine then obtains a token for the new queue, checking again for failure. If the token cannot be obtained, the W@new queue is deleted and an error is returned. No error message is provided; the token generator  qtktref  provides that. ;f`E+ Check for failure in other library functions in your library. <| zFinally, all quantities in the queue structure are set to default values (here, indicating an empty queue), and the token yis returned. This way, we need not worry about initialization later in the library, when it might be harder to determine p@if initialization is needed. =`+ Initialize on creation. >٪"(t mIf a token cant be generated, then the error message in  qe_errbuf  comes from  qtktref , but vthere is no indication of what routine called  qtktref . Write a macro that will append this to the error mesXfsage in  qe_errbuf . Remember to check for bounds problems when you append to the contents of  A@qe_errbuf . @`Queue Deletion A`This routine deletes queues. B`/* C` * delete an existing queue D ` * EAUq`B * PARAMETERS:QTICKET qnoticket for the queue to be deleted F` * RETURNED:interror code G`E * ERRORS:QE_BADPARAMparameter refers to deleted, unallocated, H`+ *or invalid queue (from readref()). I`: *QE_INTINCONqueue is internally inconsistent (from J` *readref()). K` * EXCEPTIONS:none L` */ M`int delete_queue(QTICKET qno) N`{ O`3register int cur;/* index of current queue */ P` Q`/* R`0 * check that qno refers to an existing queue; S` * readref sets error code T` */ U`%if (QE_ISERROR(cur = readref(qno))) V`return(cur); W` X`/* Y`/ * free the queue and reset the array element Z` */ [`(void) free(queues[cur]); \`queues[cur] = NULL; ]` ^`return(QE_NONE); _`} `r{ xThis routine takes as a parameter the token of the queue to be deleted. It determines if the token is valid, and if not P~z@xreturns the error code. Thus, a queue which is not created, or one that has already been deleted, will report an error. HHˆO7HHˆ6<88ldO<< HHˆO:HHˆ„33 <a`B+ Check that the parameter refers to a valid data structure. b The queue is then freed. The entry in the  queues  array is reset to indicate that an element of the array is available for @reassignment. c`J+ Always clean up deleted information it prevents errors later on. d"( nDo we need to check that  queues [ cur ] is not  NULL  before we call  free ? Why or why not? K@aIf we do, what error will occur in the above code? If we do not, should we? Justify your answer. eZ`;What prevents a caller from deleting the same queue twice? feUO` g`Adding an Element to a Queue h`EAdding an element to a queue requires that it be placed at the tail: i`/* j`' * add an element to an existing queue kUL` * l`= * PARAMETERS:QTICKET qnoticket for the queue involved m`$ *int nelement to be appended n` * RETURNED:interror code o`E * ERRORS:QE_BADPARAMparameter refers to deleted, unallocated, p`+ *or invalid queue (from readref()). q`; * QE_INTINCONqueue is internally inconsistent (from r` *readref()). s`: *QE_TOOFULLqueue has MAXELT elements and a new one t` *cant be added u` * EXCEPTIONS:none v` */ w`%int put_on_queue(QTICKET qno, int n) x`{ y`3register int cur;/* index of current queue */ z`8register QUEUE *q;/* pointer to queue structure */ {` |`/* }`0 * check that qno refers to an existing queue; ~` * readref sets error code ` */ `%if (QE_ISERROR(cur = readref(qno))) `return(cur); ` `/* `% * add new element to tail of queue ` */ `)if ((q = queue[cur])->count == MAXELT){ `"/* queue is full; give error */ `=ERRBUF2("put_on_queue: queue full (max %d elts)", MAXELT);  `return(QE_TOOFULL);  `}  `else{  `/* append element to end */  `)q->que[(q->head+q->count)%MAXELT] = n; `/* one more in the queue */ `q->count++; `} A` HHˆO:HHˆ9?;;ldO?? HHˆO=HHˆ33?`return(QE_NONE); `}  }The variables in the parameter list are not pointers; all are passed by value. As before, the validity of the token is first @~checked, and as  readref  builds the error message and code, if the token is not valid, the error is simply returned.  Adding an element to the queue requires checking that the queue is not full. The first part of the  if   else  stateHsment does this. The error message again gives the maximum number of elements that the queue can hold. If the queue G@1is full, an appropriate error code is generated: c`6#define QE_FULL-5/* append it to a full queue */ `G+ Allow error messages to contain numbers or other variable data. `#Removing an Element from the Queue `/We remove elements from the head of the queue: `/* `6 * take an element off the front of an existing queue Ӫ` * UF`= * PARAMETERS:QTICKET qnoticket for the queue involved `) * RETURNED:interror code or value `4 * ERRORS:QE_BADPARAMbogus parameter because:  `0 ** parameter refers to deleted, invalid, !`0 * or unallocated queue (from readref()) "`- ** pointer points to NULL address for #` * returned element $`+ *(qe_errbuf has descriptive string) %`: *QE_INTINCONqueue is internally inconsistent (from &` *readref()). '`5 *QE_EMPTYno elements so none can be retrieved (` * EXCEPTIONS:none )` */ *` int take_off_queue(QTICKET qno) +`{ ,`4register int cur;/* index of current queue */ -`9register QUEUE *q;/* pointer to queue structure */ .`;register int n;/* index of element to be returned */ /` 0`/* 1`0 * check that qno refers to an existing queue; 2` * readref sets error code 3` */ 4`%if (QE_ISERROR(cur = readref(qno))) 5`return(cur); 6` 7`/* 8`1 * now pop the element at the head of the queue 9` */ :`%if ((q = queues[cur])->count == 0){ ;`/* it's empty */ <`)ERRBUF("take_off_queue: queue empty"); =`return(QE_EMPTY); >`} ?`else{ @`/* get the last element */ AA`q->count--; HHˆO=HHˆ>ldOBB HHˆO@HHˆ€00 BB`n = q->head; C`$q->head = (q->head + 1) % MAXELT; D`return(q->que[n]); E`} F` G`*/* should never reach here (sure ...) */ H`IERRBUF("take_off_queue: reached end of routine despite no path there"); I`return(QE_INTINCON); J`} Ku tHere we must distinguish between a return value that is an error code and a return value that comes from the queue. The solution is to check the error buffer  qe_errbuf . Before this function is called, the first byte of that array is set to UUOwthe NUL byte \0. If, on return, the error buffer contains a string of length 1 or greater, an error occurred and the z@[returned value is an error code; otherwise, no error occurred. So the calling sequence is: L`qe_errbuf[0] = \0; M`rv = take_off_queue(qno); N`,if (QE_ISERROR(rv) && qe_errbuf[0] != \0) OqUc`D  rv contains error code, qe_errbuf the error message  P`else Q`A  no error; rv is the value removed from the queue  R vThis way, we need not pass a pointer through the parameter list. The disadvantage of this method is the complexity of zcalling the function; however, that seems a small price to pay to avoid a possible segmentation fault within the library. @~The standard I/O library function  fseek  uses a similar technique to distinguish failure from success in some cases. S`e+ Avoid changing variables through a parameter list; whenever possible, avoid passing pointers. T۩"(q oRewrite  take_off_queue   to use a second parameter,  int *n , and return the value removed 5kfrom the queue through that parameter. (Use the error code  BADPARAM , defined as 1, to report an Ϋhinvalid pointer.) The function value is the error code. Compare and contrast this approach with the one n}@4used in the above version. When would you use each? U\`VHow does  fseek (3S) use  errno  to distinguish failure from success? V) |The rest of this routine is similar to  add_to_queue . We check the parameter, and then validate the queue. We next w@Echeck for an empty queue, and report an error if the queue is empty: W`8#define QE_EMPTY-4/* take it off an empty queue */ XR2 If it is not empty, it returns the element at the head of the queue. The  head  index is incremented to move to the next @Jelement in the queue, which becomes the element at the head of the queue. Y`Summary Zʪ rThe above routines give several examples of the differences between robust and fragile coding. The above routines ֪ware robust, because they cannot be crashed by poor or incorrect calls, or inconsistency in the caller. They form a mod)FBqule, and have informational cohesion and stamp coupling (the latter because they share data in common variables; 0߅dspecifically,  queues ,  noncectr , and  qe_errbuf . While the coding of these versions of the routines takes more time than vthe fragile routines, they take much less to debug, and will require less debugging time for applications using these @ routines. ["(\ pRewrite this library to allocte space for each queue dynamically. Specifically, change  !ycreate_queue  to take the parameter  int size , where  size  is to be the maximum number of elements ((@Fallowed in the queue. Allocate space for the queue array dynamically. \< \Rewrite this library to use a linked list structure for each queue. What are the advantages H@and disadvantages to this? ]_` Conclusion ^q~ rMany security problems arise from fragile coding. The UNIX operating system, and the C standard libraries, encourP}}age this. They provide library calls that can cause severe problems; for example,  gets (3S) does not check for buffer HHˆO@HHˆ?EAAldOEE HHˆOCHHˆ  E^@ overflow. Avoid these routines! _"(x qWhy should the following functions be avoided when writing robust code:  gets ,  strcpy ,  str @Pcat ,  sprintf ? How would you modify them to make them acceptable? ` _When should members of the  scanf  family of functions be avoided while writing robust @#code? What should you use instead? aO`Acknowledgements bOV Chip Elliott (then of Dartmouth College, later of BBN Communications Corp.) provided \rthe inspiration for this. His handout Writing Bomb-Proof Code for Dartmouths COSC 23, Introduction to Software h@eEngineering class, succinctly described many of the principles and techniques which I have extended. cw nThanks to Kim Knowles for her constructive suggestions on this document. Also, the students of ECS 40 and ECS u153 here at UC Davis helped me refine this exposition by asking questions and indicating what was difficult to underPmUL@Ustand. I hope this document is clear; it is certainly clearer than earlier versions! HHˆOCHHˆBDDldLeftd{Rightd Referenced dHeadingsd+HTMLd#HTMLdiHTMLd d d d d d "d%d(d +d .d 1d 4d 7d:d=d@dC f@P[TitleBody. @@ [Body. f@D [.Due DateBody. @@ [Mapping Table Title. @@ [Mapping Table Cell. f@ [Body. @@ [Mapping Table Title. @@ [Mapping Table Cell. f@ [Body. @@ [Mapping Table Cell. @@ [Mapping Table Cell. @@ [Mapping Table Cell. @@ [Mapping Table Cell. @@ [Header Double Line. f@T [ TableTitleT:Table : . f@ [ Footnote. f@  [ CellFooting.  f@HU [Heading1 H:< =0>. Body. @@ [Footer.  f@HU [Heading2H:.. < >Body. @   $H.l..... .D.h....Code. f@ [. Indented. $f@AE [$. LetteredA A:.Lettered. f@E [AnswerEmphasisAnswer: Body. f@ [. Indented. f@ [Body. f@ [ Hand. $f@A [$. Lettered A:.\t. f@D [ BodyCenterBody. f@D [ BodyCenterBody. @   $H.l..... .D.h.... CodeCenter. f@ [ Bulleted\t. f@  [ CellHeading. f@E  [ Numbered1.\tNumbered. f@ [ Hand. f@  [ Numbered.\t. @   $H.l..... .D.h.... CodeCenter. f@T [ HeadingRunInBody. $$f@D [BodyListBody. $@   $H.l..... .D.h.... CodeIndent. f@T [ HeadingRunInBody. $$f@E [AnswerAEmphasisAnswer: Body. f@ [ TableFootnote. f@ [CellBody. f@T [ TableTitleT:Table : . $$f@D [AnswerA+EmphasisBody. f@ [Rule. @@ [ $ H l      D h  ManHeading. f@D [Answer+EmphasisBody. f@P [ Heading InfoBody. f@ [ Numbered+. $f@ [$. Lettered+. f@ [ CellHeading. f@E  [ Numbered1.\tNumbered. f@  [ Numbered.\t. f@ [ Bulleted\t. f@ [CellBody.  f@P[TitleBody. @@ [ ManHeading2. @@ [ $ H l      D h  ManBody. f@HU [Heading1 H:< =0>. Body. f@E [ExerciseBoldE:Exercise . . f@E [ExerciseBoldE:Exercise . . f@HU [Heading2H:.. < >Body. @   $H.l..... .D.h....Code.  [ [[ [ [ [ [[ [ 33[ [/Bold 2  Code [[[Emphasis[EquationVariables [Bold [   [   [ j  [ Superscript  Computer [ZThinMediumDoubleThick@ Very Thin H&5H&5H&5H&5H&5Format AH Mapping Table H&5H&5H&5H&5H&5Format BH Mapping Table GLlh pH  hhh   ( hhhh  KH>D $H66N  N!)*h j./0hj123h j456hj789h j:;<h j= > ? h j@ A B h jC D E h jF G H  jI J K L  jMNOPjQRST jUVWjXYZj[\] $^_`a$bcde:$fghi$jklm:$nopq$rstu:$vwxy$z{|}:$~$ $$   K$   !,      ",!!!!!!#,""""""J,## #!#"#%$&$'$($)$*$&$$+%,%-%.%/%'%$0&1&2&3&4&(&$5'6'7'8'9')'$:(;(<(=(>(*($?)@)A)B)C)+)$D*E*F*G*H*,*$I+J+K+L+M+-+$N,O,P,Q,R,.,$S-T-U-V-W-,/-$X.Y.Z.[.\.0.,]/^/_/`/a/1/,b0c0d0e0f0,20,g1h1i1j1k1,31,l2m2n2o2p242,q3r3s3t3u353,v4w4x4y4z464,{5|5}5~5575,6666686,7777 7,97, 8 8 8 88,:8,99999;9,:::::<:,;;;;;=;,<< <!<"<><,#=$=%=&='=?=,(>)>*>+>,>@>,-?.?/?0?1?A?,2@3@4@5@6@,B@,7A8A9A:A;ACA,B?B@BDB,ACBCCCDCECEC,FDGDHDIDJDFD,KELEMENEOEGE,PFQFRFSFTFHF,UGVGWGXGYG,IG,ZH[H\H]H^HJH,_I`IaIbIcI#I,dJeJfJgJhJ$lKmKnKMoLpLqLNLrMsMtMMuNvNwNComment LMMMd BlackT!WhiteddARedddGreendd BluedCyandMagentad YellowHeader/Footer $1Header/Footer $1Header/Footer $2Header/Footer $2IndexIndexCommentCommentSubjectSubjectAuthorAuthorGlossaryGlossaryEquationEquation Hypertext Hypertext  Cross-Ref Cross-Ref Conditional TextConditional TextPositionFMPrivatePositionFMPrivateRangeEndFMPrivateRangeEndFMPrivate HTML Macro HTML Macro M.Times.B Times-Bold FrameRoman M.Times.P Times-Roman FrameRoman M.Courier.PCourier FrameRoman M.Times.BITimes-BoldItalic FrameRoman M.Times.I Times-Italic FrameRoman M.Helvetica.BHelvetica-Bold FrameRoman M.Courier.ICourier-Oblique FrameRomanM.Zapf Dingbats.P ZapfDingbats FrameRomanlCourier1 HelveticaZTimesi Zapf Dingbats#Regular$Roman MediumBoldRegular ObliqueItalicn (do!= RU(6F8NM޻k^ODʝN$p(9 r|ÌҶUCs/gXln.ۡ,Ko3tH:E:%GV+}-}PWc$N~e*~0gXWpQ|'j~)(/Vq͝Wz_x S5R-57L_kH .2#J sʿgK͹9X>Yww,d8'/`9EOWz:뮽0%ya4 G6TrUS>m$eY8ґ;'ZPc 諀?0]FpWsݨA\o_tj0:{4 |JGpW+2H |2DR1:aKYÔ<