Aar  0 U `@0  000HH $ @d HHHHff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?bs/ bTOCHeading1Heading2   /EquationVariables@66 9":B$:[&:v(:*;,;o.;0;2<$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>AAlA5y5|55559<)???999*99999999, Exercise 1. 99*9999.999999999999999999999::::::4:4::6:: : : 1: .: ::::::::::::::::::: :!:":#:$:%:&6:':(1:):*1:+:,1:-:.:/1:01:1<:2<:3<:4:5<:6<:7<:8<:9<:::;1:<:=1:>:?6:@:A1:E, Exercise 2. :F.???????@@@@:U1:V1:W1:X:Y1:Z:^, Exercise 3. :_:`:a.:b:c:d:e:f:g:h:i:j:k=:l:m:n:o:p:q1:r1:s:t1:u:y, Exercise 4. :z6:{:|.:}:~:::::::::::*::.:::::::6::6::::::1::1::::::::::::::::::::::::::::::::::::::::::::::, Exercise 5. :, Exercise 6. :.::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;; 1; ; 1; ; ;;1;;;, Exercise 7. ;, Exercise 8. ;, Exercise 9. ;;;;;;;;; ;!;";#;$;%;&;';(;);*;+;,;-;.;/;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;X1;Y;Z;[;\1;];^#1.;_ 2.;`!3.;a;b;c;d;e;f;g1;h;i<;j<;k<;l;m6;n;r, Exercise 10. ;s, Exercise 11. ;t. ;u;v;w;x;y;z;{;|;};~;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;6;;1;;1;;;;1;;;1;;1;;1;, Exercise 12. $;. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;1;;1;, Exercise 13. ;,Exercise 14. ;;.;;;;;;;;;;;;;;;;;;;;;;;;;;;;<<<<<<<<<< < < < < <<<<<<1<.<<<<<<<<<<<< count =  newvalue ; :$where  qptr  is a pointer to the relevant queue and  newvalue  the expression for the new value to be assigned to the Dqueues counter. ;$|The use of the macro  MAXELT  also limits the reusability of the library. If the size of the queues is changed, the wlibrary must be recompiled. However, as the include file macro has changed, the callers of the queue library must also UPpbe recompiled; otherwise, the pointers may be invalid (depending on the architecture) and if a routine directly UPDcaccesses any field in the queue structure, not recompiling that file will cause incorrect results.  㝗dThe Queue Management Function ?܁dAThe first function controls the creation and deletion of stacks: @d/* Ad * create or delete a queue Bd * C UFd@ * PARAMETERS:QUEUE **qptrspace for, or pointer to, queue Dd. * int flag1 1 for create, 0 for delete Ed& *int sizemax elements in queue Fd */ Gd/void qmanage(QUEUE **qptr, int flag, int size) Hd{ Id if (flag){ Jd/* allocate a new queue */ Kd!*qptr = malloc(sizeof(QUEUE)); Ld&(*qptr)->head = (*qptr)->count = 0; Md-(*qptr)->que = malloc(size * sizeof(int)); Nd(*qptr)->size = size; Od} Pdelse{ Qd!/* delete the current queue */ Rd(void) free((*qptr)->que); Sd(void) free(*qptr); Td} Ud} V$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 D;such poor cohesion does not speak well for its robustness. WЁ$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 intewDHgers to be allowed in the queue. Suppose a caller interchanged the two: Xdqmanage(&qptr, 85, 1); Y$The  qmanage  routine would not detect this as an error, and will allocate a queue with room for 1 element rather than Dn85. This ease of confusion in the parameters is the first problem, and one that cannot be checked for easily. Z-dC+ The order of elements in the parameter list is not checked. [Έ$}Next, consider the  flag  argument. When does it mean to create a queue and when does it mean to delete a queue? For Hwthis function, the intention is that 1 means create and 0 means delete, but the coding style has changed this to allow /7 tany non-zero value to mean create. But there is little connection between 1 and create, and 0 and delete. So psychop=rlogically, 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 D~is simply loaded,  enum s do not help as the elements are translated into integers (so no type checking can be done). HH>靕ld 0  and  b > 0 , then overp"oflow 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 E problems. HH<|@HH?EAA 靕ld<EE HH<CHHɝ11&&Eu dAdding 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 DXqueue size), and places the new element at that location; it then increments the count:  d/*  d' * add an element to an existing queue vd * wd9 * PARAMETERS:QUEUE *qptrpointer for queue involved xd# *int nelement to be appended yd */ zd&void put_on_queue(QUEUE *qptr, int n) {d{ |d(/* add new element to tail of queue */ }d9qptr->que[(qptr->head + qptr->count) % qptr->size] = n; ~dqptr->count++; d} $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 0eUL~is lucky, the problem will arise in this routine; if the caller is unlucky, the symptom will not appear until later on in the D/program, with no indication of what caused it. d+ Check all parameters. dd|As an offshoot of this, suppose  qptr  is valid but  que  is not. Then the routine will not work correctly: d?+ Check for incorrect values in structures and variables. $Second, suppose the queue is full (that is,  qptr->count  equals  qptr->size ). If this function is called, it will overwrite 1qthe head of the queue. There is no check for an overflowing queue, doubtless because the author assumed it would Dnever happen. Ld6+ Check for array overflow when inserting items.  U$vA more sophisticated problem is the placing of trust in the values of the queue structure. The integrity of the queue gstructure depends on the consistency of the  count ,  size , and  head  fields. If  size  increases between calls, the routine 0pwill think that the queue has been allocated more space than it actually has, leading to a segmentation fault. If  size  D6decreases between calls, some elements might be lost.  ",n ]Write 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 Drarise if the values of  head  and/or  count  are changed across calls to  put_on_queue .  d  ֭$sGiven the accessibility of the queue structure elements to the callers, these elements may change (accidentally or Ddeliberately).  ȝd!Removing Elements from the Queue ܁$Taking elements off the queue begins by getting the element at index  head . Then count is decremented, and  head  is D%incremented (modulo  size ): d/*  d6 * take an element off the front of an existing queue NELd * d9 * PARAMETERS:QUEUE *qptrpointer for queue involved d, *int *nstorage for the return element d */ d)void take_off_queue(QUEUE *qptr, int *n) d{ d3/* return the element at the head of the queue */ Ad*n = qptr->que[qptr->head++]; HH<CHHBHDD 靕ld<HH HH<FHHɝ..((H܁܁dqptr->count--; 큩dqptr->head %= MAXELT; d} $The parameter problems described in the previous section exist here too;  qptr  may be invalid,  NULL , or point to an DQinvalid queue. Moreover,  n  may also be an invalid integer pointer. So: Hd+ Check all parameters. [d?+ 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  rDJwill be garbage, and  count  will be set to a bogus value. Hence: !Łd8+ Check for array underflow when extracting items. "݁dOThe problem of variable consistency across calls occurs in this routine, also. #"le ^What problems might an invalid pointer for  n  cause? Specifically, suppose in the call $d 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 Emanner? & dSummary '܁ځdThe library  fqlib.c , the contents of which are presented in this section, is very fragile code. Among its flaws are: (dIThe callers have access to the internal elements of the queue structure. ) d9The order of elements in parameter lists is not checked. *dbThe value of command parameters (which tell the function what operation to perform) is arbitrary. +d> 16) & 0xffff) - 0x1221 =\dand >WHdOnonce  = ( f ( index ,  nonce ) & 0xffff) - 0x0502 ?d*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 D\systems have a datatype supporting integers of this length. So, in the header file, we put: AdJ/* queue identifier; contains internal index and nonce mashed together */ Bdtypedef long int QTICKET; CÁd[With this token defined, calling routines need know nothing about the internal structures. D݁dP+ Dont hand out pointers to internal data structures; use tokens instead. EX$sThe second issue is errors; how to handle them? We can print error messages (and take action, possibly even termi{nating), we can return error results and allow the caller to handle the error, or we can set up special error handlers (if vthe language supports these; they are typically written as trap or exception handlers). Unfortunately, C does not pro02bvvide 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 Dcodes. FA$x+ Handle errors in a consistent manner: either print error messages from a centralized printing routine, or return MD?error codes to the caller and let the caller report the error. G\$uWe make some decisions about the library functions for this purpose. The return value will indicate whether an error h}has occurred; if so, the function returns an error code and an expositor message in a buffer. If not, it returns a flag indi:;D?cating no error. So, we define all error codes to be negative: HɁd/* Id * error return values J$d6 * all the queue manipulation functions return these; K|Spd7 * you can interpret them yourself, or print the error Ld5 * message in qe_errbuf, which describes these codes Md */ NdI#define QE_ISERROR(x)((x) < 0)/* true if x is a qlib error code */ Od'#define QE_NONE 0/* no errors */ Pd/* QdB * the error buffer; contains a message describing the last queue RdF * error (but is NUL if no error encountered); not cleared on success Sd */ Tdextern char qe_errbuf[256]; U"$ Like the UNIX system variable  errno (3),  qe_errbuf  is set on an error but not cleared on success. The buffer will con.utain additional information (such as in which routine the error occurred and relevant numbers). The following macros \Daid this process: VI~d"/* macros to fill qe_errbuf */ WU}dI#define ERRBUF(str)(void) strncpy(qe_errbuf, str, sizeof(qe_errbuf)) X0d<#define ERRBUF2(str,n)(void) sprintf(qe_errbuf, str, n) YAdA#define ERRBUF3(str,n,m)(void) sprintf(qe_errbuf, str, n, m) SZ|z$ These are defined in  qlib.c  because they format messages placed in  qe_errbuf ; the functions that call the library have HH<IHHHNJJ靕ld<NN HH<LHHѝ11**NZ܁܁Dno use for them. [dhWe also redefine the function interface to eliminate the low cohesion of the  qmanage  routine: \d7int create_queue(QTICKET *);/* create a queue */ ]d5int delete_queue(QTICKET);/* delete a queue */ ^dFint put_on_queue(QTICKET, int);/* put number on end of queue */ _dNint take_off_queue(QTICKET, int *);/* pull number off front of queue */ `WdKThis eliminates the use of a flag variable to manage creation or deletion. a_dgIn the  qlib.c  file we place the definition of the queue structure and the related variables: bd./* macros for the queue structure (limits) */ cŁd1#define MAXQ1024/* max number of queues */ dd?#define MAXELT1024/* max number of elements per queue */ ed fd/* the queue structure */ gd:typedef int QELT;/* type of element being queued */ hdtypedef struct queue { id4QTICKET ticket;/* contains unique queue ID */ jd.QELT que[MAXELT];/* the actual queue */ kd4int head;/* head index in que of the queue */ ld3int count;/* number of elements in queue */ md } QUEUE; nd+/* variables shared by library routines */ od;static QUEUE *queues[MAXQ];/* the array of queues */ pd%/* nonce generator -- this */ qdLstatic unsigned int noncectr = NOFFSET;/* MUST be non-zero always */ r8$vWe made one change to the queue definition: all queues are to be of fixed size. This was for simplicity (see the exerDDcise below). Also, all globals are declared  static  so they are not accessible to any functions outside the library file. sS$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 CDexist). tz",u _The macros  ERRBUF2  and  ERRBUF3  use  sprintf  to format the error message. What prob܁DYlem does this function not guard against? Why can we ignore this problem in our library? u$[What problems does static allocation of space for each queues contents and for all queues Dintroduce? What advantages? v dToken Creation and Analysis w܁$yOne function internal to the library creates a token from an index, and another takes a token, validates it, and returns Dthe appropriate index. x$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 0VUwinvolved. In either case, this increases cohesion and decreases coupling, laudable goals from the software engineering D!(and maintenance!) perspectives. y$In what follows,  IOFFSET  is the offset added to the index of the element and  NOFFSET  is the initial nonce. Both are $Ddefined in  qlib.c : z3dD#define IOFFSET0x1221/* used to hide index number in ticket */ {?d.#define NOFFSET0x0502/* initial nonce */ |Nd*Here is the function to generate a token: }Md/* ~i}dF * generate a token; this is an integer: index number + OFFSET,,nonce d0 * WARNING: each quantity must fit into 16 bits Ad * HH<LHHKQMM靕ld<QQ HH<OHH֝55Q ܁܁d) * PARAMETERS:int indexindex number 큩d6 * RETURNED:QTICKETticket of corresponding queue d6 * ERRORS:QE_INTINCON* index + OFFSET is too big d ** nonce is too big d ** index is out of range d- *(qe_errbuf has disambiguating string) d * EXCEPTIONS:none d */  d+static QTICKET qtktref(unsigned int index)  d{  d<unsigned int high;/* high 16 bits of ticket (index) */  d:unsigned int low;/* low 16 bits of ticket (nonce) */  d d4/* sanity check argument; called internally ... */ dif (index > MAXQ){ d8ERRBUF3("qtktref: index %u exceeds %d", index, MAXQ); dreturn(QE_INTINCON); d} d d/* d> * get the high part of the ticket (index into queues array, d' * offset by some arbitrary amount) dG * SANITY CHECK: be sure index + OFFSET fits into 16 bits as positive d */ d"high = (index + IOFFSET)&0x7fff; dif (high != index + IOFFSET){ d5ERRBUF3("qtktref: index %u larger than %u", index, d0x7fff - IOFFSET); dreturn(QE_INTINCON); d} d  d/* !d+ * get the low part of the ticket (nonce) "d2 * SANITY CHECK: be sure nonce fits into 16 bits #d */ $dlow = noncectr & 0xffff; %d'if ((low != noncectr++) || low == 0){ &d8ERRBUF3("qtktref: generation number %u exceeds %u\n", 'd(noncectr - 1, 0xffff - NOFFSET); (dreturn(QE_INTINCON); )d} *d +d'/* construct and return the ticket */ ,d)return((QTICKET) ((high << 16) | low)); -d} .%}d_The function is declared  static  so that only functions in the library may access it. /M$vRather than return a value through the parameter list, we compute the token and return it as the function value. This @{xallows us to return error codes as well (since tokens are always positive, and error codes always negative). The single  D=parameter is an index for which the token is to be computed. 0[ydV+ Make interfaces simple, even if they are for routines internal to the library. 1[$The next  if  statement checks the value of the parameter; in this case, it must be a valid array index (between 0 and  vwsMAXQ  inclusive). As the parameter is unsigned, only the upper bound need be checked. This may seem excessive; Rwafter all, this function is only called within our library, so cant we ensure the parameter is always in the expected HH<OHHNTPP靕ld<TT HH<RHH֝33,,T 1܁܁vrange? 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 Dbest to program defensively. 2dA+ Always check parameters to make sure they are reasonable. 3$xIf an error occurs, it should be identified precisely. Two techniques are combined here. The first is an error message, Hgiving the name of the routine and an exact description of the problem. It is in  qe_errbuf , and available to the caller. BD\The second is a return value indicating an error (specifically, an internal inconsistency): 4cd7#define QE_INTINCON-8/* internal inconsistency */ 5❞d@The calling routine must detect this error and act accordingly. 6$t+ Give useful and informative error messages. Include the name of the routine in which the error occurs. Allow DQnumbers in the error message. Use error codes that precisely describe the error. 7$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 \DRwould not know why the error occurred, or (depending on the error message) where. 8$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 D is given. 9́"l- `Explain how the check works, in detail. :Sy$xThe code uses  0x7fff  to mask  index  for the comparison instead of using  0xffff . Why is the Dmask 15 bits instead of 16? ;$hThe check for  noncectr  is similar, but uses 0xffff as a mask. Explain why it does not need to  D use 0x7fff. Jd3 * check a ticket number and turn it into an index ?d * @d: * PARAMETERS:QTICKET qnoqueue ticket from the user Ad+ * RETURNED:intindex from the ticket Bd= * ERRORS:QE_BADTICKETqueue ticket is invalid because: Cd) ** index out of range [0 .. MAXQ) Dd# ** index is for unused slot Ed ** nonce is of old queue Fd. *(qe_errbuf has disambiguating string) Gd= *QE_INTINCONqueue is internally inconsistent because: Hd. ** one of head, count is uninitialized Id ** nonce is 0 Jd. *(qe_errbuf has disambiguating string) Kd * EXCEPTIONS:none Ld */ Md static int readref(QTICKET qno) Nd{ Od;register unsigned index;/* index of current queue */ Pd9register QUEUE *q;/* pointer to queue structure */ Qd Rd6/* get the index number and check it for validity */ Sd+index = ((qno >> 16) & 0xffff) - IOFFSET; Tdif (index >= MAXQ){ Ud8ERRBUF3("readref: index %u exceeds %d", index, MAXQ); Vdreturn(QE_BADTICKET); Wd} AXdif (queues[index] == NULL){ HH<RHHQWSS 靕ld<WW HH<UHH֝44W Y܁܁d=ERRBUF2("readref: ticket refers to unused queue index %u", Z큩dindex); [dreturn(QE_BADTICKET); \d} ]d ^d/* _d< * you have a valid index; now validate the nonce; note we `d< * store the ticket in the queue, so just check that (same ad  * thing) bd */ cd$if (queues[index]->ticket != qno){ ddCERRBUF3("readref: ticket refers to old queue (new=%u, old=%u)", ed0((queues[index]->ticket)&0xffff) - IOFFSET, fd(qno&0xffff) - NOFFSET); gdreturn(QE_BADTICKET); hd} id jd/* kd% * check for internal consistencies ld */ md;if ((q = queues[index])->head < 0 || q->head >= MAXELT || nd)q->count < 0 || q->count > MAXELT){ od?ERRBUF3("readref: internal inconsistency: head=%u,count=%u", pdq->head, q->count); qdreturn(QE_INTINCON); rd} sd!if (((q->ticket)&0xffff) == 0){ td6ERRBUF("readref: internal inconsistency: nonce=0"); udreturn(QE_INTINCON); vd} wd xd"/* all's well -- return index */ ydreturn(index); zd} {$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 0U<serror message is given. Notice that the error code simply indicates a problem with the parameter, although the mesD;sage in  qe_errbuf  distinguishes between the two. |dT+ Make parameters quantities that can be checked for validity, and check them. }_+$zAs the caller of the library has supplied the token, a bogus token is not an internal error. So we use another error code Dto indicate the problem: ~ d:#define QE_BADTICKET-3/* bad ticket for the queue */ $wNext, we check that the queue with the same index as the token is the queue the token refers to. This is the dangling %~preference problem mentioned earlier. The current queues token is stored in each queue structure, so we simply \DZensure the current token is the queues token. If not, we handle the error appropriately. @|d9+ Check for references to outdated data structures. ߬$xThe last section of code checks for internal consistency. The goal is to detect problems internal to the queue library. [zDThe consistency checks are: jydRThe position of the queue  head  must lie between 0 and  MAXELT . vxdgThe  count  of elements in the queue must be nonnegative and no greater than  MAXELT . Q4d^The nonce can never be 0. This prevents a random integer 0 from being taken as a valid token. HH<UHHTZVV靕ld<ZZ HH<XHH~11..Z ܁܁d>When any of these are detected, the routine reports an error. $uAn alternate approach, favored by some experts, is to make this code conditionally compilable, and omit it on producD=tion versions. They either use #ifdefs to surround the code: d #ifdef DEBUG d/* the code goes here */  UPd#endif  W$~or use the  assert()  macro. This saves space when the library is provided for production, but can make tracking down csany problems more difficult when they occur in production software, because less information is provided than in a UDdevelopment environment.  ~dp+ Assume debugged code isnt. When its moved to other environments, previously unknown bugs may appear.  $ The  assert()  macro is described in the manual as  assert (3) Its argument is an expression, and that expression is evaluyated. If the expression is false, the macro writes a message to the standard error, aborts the program and forces a core GDidump for debugging purposes. For example, the internal consistency checking code could be replaced with:  dhead < 0 || q->head >= MAXELT); d+assert(q->count < 0 || q->count > MAXELT); UId"assert((q->ticket)&0xffff) != 0); dRIf the middle  assert  expression were false, the error message would be: [U>dMassertion q->count < 0 || q->count > MAXELT failed file qlib.c, line 178 $ If the compile-time constant  NDEBUG  is defined, all  assert()  macros are empty, so they are in effect deleted from the D program. ",n aThe  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 D5caller to attempt to recover. Which is better? When? ;$_Assume  IOFFSET  were not added to indices. What error message would be printed if the GD(QTICKET were 0? Why is this misleading?  `dQueue Creation ܁pd3The routine  create_queue  creates queues: d/* d * create a new queue d * d * PARAMETERS:none d? * RETURNED:QTICKETtoken (if > 0); error number (if < 0) d- * ERRORS:QE_BADPARAMparameter is NULL d6 *QE_TOOMANYQStoo many queues allocated already d1 *QE_NOROOMno memory to allocate new queue d+ *(qe_errbuf has descriptive string)  d * EXCEPTIONS:none !d */ "dQTICKET create_queue(void) #d{ $d3register int cur;/* index of current queue */ %d=register QTICKET tkt;/* new ticket for current queue */ &d 'd/* check for array full */ (d!for(cur = 0; cur < MAXQ; cur++) )dif (queues[cur] == NULL) *d break; +dif (cur == MAXQ){ A,d;ERRBUF2("create_queue: too many queues (max %d)", MAXQ); HH<XHHW]YY 靕ld<]] HH<[HH22] -܁܁dreturn(QE_TOOMANYQS); .큩d} /d 0d/* allocate a new queue */ 1d5if ((queues[cur] = malloc(sizeof(QUEUE))) == NULL){ 2d2ERRBUF("create_queue: malloc: no more memory"); 3dreturn(QE_NOROOM); 4d} 5d 6d/* generate ticket */ 7d&if (QE_ISERROR(tkt = qtktref(cur))){ 8d:/* error in ticket generation -- clean up and return */ 9d(void) free(queues[cur]); :dqueues[cur] = NULL; ;dreturn(tkt); <d} =d >d"/* now initialize queue entry */ ?d-queues[cur]->head = queues[cur]->count = 0; @dqueues[cur]->ticket = tkt; Ad Bdreturn(tkt); Cd} D$uThe parameter list for this routine is empty; all information is returned as a function value. An alternate approach )DRwould be to pass the QTICKET back through the parameter list with the declaration E8dint 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 Sqarguments; others do not. Programmers may become confused, or suffer memory lapses, about which routines require UUDVpointers and which do not. The routine should guard against these potential problems. Gnd(+ Keep parameter lists consistent. HT$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 Uxthe process address space or that the address is not properly aligned for the quantity to be stored there (on some sys0Ustems, notably RISC systems, this can cause an alignment fault and terminate the program)? Using a style of programDEming akin to functional programming languages avoids these problems. Ide+ Avoid changing variables through a parameter list; whenever possible, avoid passing pointers. J${This routine checks if there is room for another queue; if so, it determines the index of the queue; if not, it reports an ׁDxerror and returns an error code. The error code is returned to the calling routine, which is not a part of the library: KʁdB#define QE_TOOMANYQS-7/* too many queues in use (max 100) */ L%Q$nIn the error message we supply helpful information, namely the maximum number of queues allowed. This enables DRthe programmers to know why the routine failed and tailor their code accordingly. Mdk+ Check for array overflow and report an error when it would occur (or take other corrective action). NI$The next part allocates space for the queue. Again, the routine checks for a failure in  malloc , and reports it should it +happen. Again, a special error code is used. This is of special importance since a  malloc  failure is usually due to a sysrl tem call failure, and  perror (3) will print a more informative message that the caller may desire. The queue librarys C&dDerror indicator is: OR|d=#define QE_NOROOM-6/* can't allocate space (sys err) */ PqdB+ Check for failure in C library functions and system calls. Qr$uThe routine then obtains a token for the new queue, checking again for failure. If the token cannot be obtained, the P|yDnew queue is deleted and an error is returned. No error message is provided; the token generator  qtktref  provides that. HH<[HHZ`\\靕ld<`` HH<^HHZ//00`R܁܁dE+ Check for failure in other library functions in your library. S$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 URDif initialization is needed. Td+ Initialize on creation. UPUP",t bIf a token cant be generated, then the error message in  qe_errbuf  comes from  qtktref , but Wvthere is no indication of what routine called  qtktref . Write a macro that will append this to the error mesKUNfsage in  qe_errbuf . Remember to check for bounds problems when you append to the contents of  Dqe_errbuf . W dQueue Deletion X܁dThis routine deletes queues. Y߁d/* Zd * delete an existing queue [id * \dB * PARAMETERS:QTICKET qnoticket for the queue to be deleted ]d * RETURNED:interror code ^dE * ERRORS:QE_BADPARAMparameter refers to deleted, unallocated, _d+ *or invalid queue (from readref()). `d: *QE_INTINCONqueue is internally inconsistent (from ad *readref()). bd * EXCEPTIONS:none cd */ ddint delete_queue(QTICKET qno) ed{ fd3register int cur;/* index of current queue */ gd hd/* id0 * check that qno refers to an existing queue; jd * readref sets error code kd */ ld%if (QE_ISERROR(cur = readref(qno))) mdreturn(cur); nd od/* pd/ * free the queue and reset the array element qd */ rd(void) free(queues[cur]); sdqueues[cur] = NULL; td udreturn(QE_NONE); vd} w$xThis routine takes as a parameter the token of the queue to be deleted. It determines if the token is valid, and if not Dxreturns the error code. Thus, a queue which is not created, or one that has already been deleted, will report an error. x-dB+ Check that the parameter refers to a valid data structure. y$The queue is then freed. The entry in the  queues  array is reset to indicate that an element of the array is available for H~Dreassignment. SzW}dJ+ Always clean up deleted information it prevents errors later on. HH<^HH]c__靕ld<cc HH<aHH~3322c{܁܁ ( cDo we need to check that  queues [ cur ] is not  NULL  before we call  free ? Why or why not? 큩@aIf we do, what error will occur in the above code? If we do not, should we? Justify your answer. |`;What prevents a caller from deleting the same queue twice? }` ~ I`Adding an Element to a Queue ܁Y`EAdding an element to a queue requires that it be placed at the tail: h`/* t`' * add an element to an existing queue ` * `= * PARAMETERS:QTICKET qnoticket for the queue involved `$ *int nelement to be appended ` * RETURNED:interror code `E * ERRORS:QE_BADPARAMparameter refers to deleted, unallocated, `+ *or invalid queue (from readref()). `; * QE_INTINCONqueue is internally inconsistent (from  ` *readref()).  `: *QE_TOOFULLqueue has MAXELT elements and a new one  ` *cant be added  ` * EXCEPTIONS:none  ` */ `%int put_on_queue(QTICKET qno, int n) `{ `3register int cur;/* index of current queue */ `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++; '`} (` )`return(QE_NONE); *`} +oz }The variables in the parameter list are not pointers; all are passed by value. As before, the validity of the token is first P{y@~checked, and as  readref  builds the error message and code, if the token is not valid, the error is simply returned. HH<aHH`fbb靕ld<ff HH<dHH44f,܁܁ Adding an element to the queue requires checking that the queue is not full. The first part of the  if   else  state0큩sment does this. The error message again gives the maximum number of elements that the queue can hold. If the queue @1is full, an appropriate error code is generated: -`9#define QE_TOOFULL-5/* append it to a full queue */ .`G+ Allow error messages to contain numbers or other variable data. / U`#Removing an Element from the Queue 0܁e`/We remove elements from the head of the queue: 1t`/* 2ā`6 * take an element off the front of an existing queue 3` * 4`= * PARAMETERS:QTICKET qnoticket for the queue involved 5`) * RETURNED:interror code or value 6`4 * ERRORS:QE_BADPARAMbogus parameter because: 7`0 ** parameter refers to deleted, invalid, 8`0 * or unallocated queue (from readref()) 9`- ** 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 @` */ A` int take_off_queue(QTICKET qno) B`{ C`4register int cur;/* index of current queue */ D`9register QUEUE *q;/* pointer to queue structure */ E`;register int n;/* index of element to be returned */ F` G`/* H`0 * check that qno refers to an existing queue; I` * readref sets error code J` */ K`%if (QE_ISERROR(cur = readref(qno))) L`return(cur); M` N`/* O`1 * now pop the element at the head of the queue P` */ Q`%if ((q = queues[cur])->count == 0){ R`/* it's empty */ S`)ERRBUF("take_off_queue: queue empty"); T`return(QE_EMPTY); U`} V`else{ W`/* get the last element */ X`q->count--; Y`n = q->head; Z`$q->head = (q->head + 1) % MAXELT; [`return(q->que[n]); \`} A]` HH<dHHciee靕ld<ii HH<gHHT,,46i^܁܁d*/* should never reach here (sure ...) */ _큩dIERRBUF("take_off_queue: reached end of routine despite no path there"); `dreturn(QE_INTINCON); ad} b$tHere we must distinguish between a return value that is an error code and a return value that comes from the queue. EThe solution is to check the error buffer  qe_errbuf . Before this function is called, the first byte of that array is set to 0wthe NUL byte \0. If, on return, the error buffer contains a string of length 1 or greater, an error occurred and the D[returned value is an error code; otherwise, no error occurred. So the calling sequence is: cldqe_errbuf[0] = \0; dxdrv = take_off_queue(qno); ed,if (QE_ISERROR(rv) && qe_errbuf[0] != \0) fdD  rv contains error code, qe_errbuf the error message  gdelse hdA  no error; rv is the value removed from the queue  i$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. dD~The standard I/O library function  fseek  uses a similar technique to distinguish failure from success in some cases. jށde+ Avoid changing variables through a parameter list; whenever possible, avoid passing pointers. k]",q dRewrite  take_off_queue   to use a second parameter,  int *n , and return the value removed kfrom the queue through that parameter. (Use the error code  BADPARAM , defined as 1, to report an 0b hinvalid pointer.) The function value is the error code. Compare and contrast this approach with the one D4used in the above version. When would you use each? l dVHow does  fseek (3S) use  errno  to distinguish failure from success? m /$|The rest of this routine is similar to  add_to_queue . We check the parameter, and then validate the queue. We next ;DEcheck for an empty queue, and report an error if the queue is empty: nJd8#define QE_EMPTY-4/* take it off an empty queue */ o#߻$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 eDJelement in the queue, which becomes the element at the head of the queue. p ~dSummary q܁$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 mod0E-Oqule, and have informational cohesion and stamp coupling (the latter because they share data in common variables; specifically,  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 D routines. r",\ eRewrite 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 S DFallowed in the queue. Allocate space for the queue array dynamically. s$\Rewrite this library to use a linked list structure for each queue. What are the advantages  Dand disadvantages to this? tUT&U-d Conclusion u܁9$rMany security problems arise from fragile coding. The UNIX operating system, and the C standard libraries, encourEage this. They provide library calls that can cause severe problems; for example,  gets (3S) does not check for buffer P_D overflow. Avoid these routines! HH<gHHflhh 靕ld<ll HH<jHHɝ  88lv܁܁",x fWhy should the following functions be avoided when writing robust code:  gets ,  strcpy ,  str 큩DPcat ,  sprintf ? How would you modify them to make them acceptable? w$_When should members of the  scanf  family of functions be avoided while writing robust D#code? What should you use instead? x@dAcknowledgements y܁@V Chip Elliott (then of Dartmouth College, later of BBN Communications Corp.) provided Mothe inspiration for this. His handout Writing Bomb-Proof Code for Dartmouths class COSC 23, Introduction to YDiSoftware Engineering,, succinctly described many of the principles and techniques which I have extended. zh$nThanks to Kim Knowles for her constructive suggestions on this document. Also, the students of ECS 40 and ECS tv153 at UC Davis helped me refine this exposition by asking questions and indicating what was difficult to understand. P_DNI hope this document is clear; it is certainly clearer than earlier versions! HH<jHHikk靕ldLeftdRightd Referencedd:d=d@d Cd Fd Id Ld Od Rd Ud Xd [d ^dadddgdjf@D 0BodyBody. f@E 0 BulletedBulleted. f@N 0 Numbered N:.\t. f@E 0 BulletedBulleted. f@ 0 Footnote.  f@P0 TitleBody. f@T 0Heading2Body. f@T 0 HeadingRunInBody. f@D 0BodyBody. $f@AE 0$. LetteredA A:.Lettered. f@NE 0 Numbered1 N:.Numbered. f@ 0 TableFootnote. f@T 0 TableTitleT:Table : . Ŀ@@ 0Header Double Line. f@T 0 TableTitleT:Table : . f@T0Heading1Body. $f@A 0$. Lettered A:.\t. f@ 0 CellFooting. f@D 0 BodyCenterBody. @    $H.l..... .D.h....Code. Ŀ@@ 0Footer. f@D 0 BodyCenterBody. f@ 0Rule. @    $H.l..... .D.h....Code. @    $H.l..... .D.h....Code. Ŀ@@ 0 $ H l      D h  ManHeading. f@N 0 NumberedN:.. f@N 0 NumberedN:.. f@NE 0 Numbered1 N:.Numbered. f@ 0 CellHeading. f@T 0 HeadingRunInBody. f@D 0BodyBody. f@T0Heading1Body. f@H 0ExerciseBoldH:Exercise . . f@P 0 Heading InfoBody. f@T 0 Heading2Body. f@H 0ExerciseBoldH:Exercise . . f@ 0 CellHeading. f@ 0 Hand. f@ 0 Hand. $$f@D 0BodyBody. f@ 0CellBody. @    $H.l..... .D.h.... CodeCenter. f@ 0CellBody. @    $H.l..... .D.h.... CodeCenter.  f@P0TitleBody. $$f@D 0BodyListBody. $$f@D 0BodyListBody. $@    $H.l..... .D.h.... CodeIndent. $@    $H.l..... .D.h.... CodeIndent. Ŀ@@ 0 ManHeading2. Ŀ@@ 0 $ H l      D h  ManBody. 0蜜Emphasis0蜜EquationVariables 0蜜 0蜜 0蜜 0 0 3300 330 0 0  0 0       7  0 Superscript   Computer 0 0蜜0 0蜜/Bold 0Bold   Code ۸  CodeThinMediumDoubleThick@ Very Thin H&5H&5H&5H&5H&5Format A H&5H&5H&5H&5H&5Format BComment6d BlackT!WhiteddARedddŝGreendd 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.P Times-Roman FrameRoman M.Times.B Times-Bold 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 FrameRoman9 Courier Helvetica/Times6 Zapf Dingbats!Regular#Roman MediumBoldRegular ObliqueItalic=y~ªǍ"ep~td7Y;8'7MJC"A?il]G׍jSa魃 /ѴB(ju2e>5:Nś!$-z ?ZLJ~>TסH:|ߞ;;k5E-aT~!zdFa(D:h/ ZGat8G+0>B)H eD<ƪX~n%ִ3Q8mF9u.ґ[;X%9K<7?fUl~= [B\(a@C杛Aa)M֡.