home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12673 < prev    next >
Encoding:
Internet Message Format  |  1992-08-22  |  6.0 KB
  1. From: richw@inmet.camb.inmet.com
  2. Date: 21 Aug 1992 17:25 EDT
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Allocate memory to typed in string,
  5. Message-ID: <20900033@inmet>
  6. Path: sparky!uunet!noc.near.net!inmet!inmet!richw
  7. Nf-ID: #R:<bibhas:712893811:inmet:20900033:000:5742
  8. Nf-From: inmet.camb.inmet.com!richw    Aug 21 17:25:00 1992
  9. References: <712893811@<bibhas>
  10. Lines: 139
  11.  
  12.  
  13. An algorithm to read an arbitrarily long input line that I've used might be
  14. encoded in a routine with the following kind of "spec":
  15.  
  16.     char *
  17.     read_line (f, buffer, buffer_size)
  18.     FILE *f;
  19.     char *buffer;
  20.     int buffer_size;
  21.     /*
  22.     Reads characters from "f" until either a newline has been read
  23.     or an EOF.  The characters read are either placed in the memory
  24.     pointed to by "buffer" or in memory allocated by "malloc";
  25.     "buffer" is used if fewer than "buffer_size" characters are
  26.     read.  A pointer to the memory used (i.e. the value of "buffer" 
  27.     or of the "malloc"-ed string) is returned, with the input line
  28.     terminated by a '\0'.
  29.  
  30.     To always have this function use "malloc"-ed memory, pass in a
  31.     value of "0" for buffer_size.
  32.     */
  33.  
  34. Note that this function lets one allocate a "usually big enough" buffer and
  35. pass it in as "buffer", but it *also* handles the "rare" case where the input
  36. line is longer than that.  (Personally, I think that any answer to the
  37. original question that refuses to deal with the exceptional case is not
  38. really answering the question.)
  39.  
  40. I'll describe the algorithm for "read_line":
  41.  
  42. "read_line" uses a secondary, recursive function with the following spec:
  43.  
  44.  
  45.     char *
  46.     finish_line (f, reserve_count)
  47.     FILE *f;
  48.     int reserve_count;
  49.     /*
  50.     Like "read_line", this reads N characters from "f" until either a
  51.     newline has been read or an EOF.  The characters are placed in
  52.     a "malloc"-ed piece of memory whose length is X, where X equals
  53.     (reserve_count + N + 1), where the additional 1 is for the term-
  54.     inating '\0'.  The pointer, P, to the "malloc"-ed space is returned.
  55.     The input N characters and the terminating '\0' are written to
  56.     (P + reserve_count), thus leaving space for "reserve_count" characters
  57.     read earlier.
  58.     */
  59.  
  60.  
  61. The body of "finish_line" includes a local buffer:
  62.  
  63.     char buffer [BUFFER_SIZE];
  64.  
  65. where "BUFFER_SIZE" is some "#define"-ed constant.  The second to last element
  66. of "buffer" is initialized to '\0'.  Then, "buffer" is given to "fgets",
  67. which may or may not read a complete line (i.e. it won't if "BUFFER_SIZE"
  68. isn't big enough.  To determine whether or not "fgets" did read a whole line:
  69.  
  70.     (1) if the second-to-last "buffer" character is still '\0',
  71.         then "fgets" must have read a whole line;
  72.  
  73.     (2) Otherwise, if the second-to-last "buffer" character is '\n',
  74.         then, again, "fgets" must have read a whole line;
  75.  
  76.     (3) Otherwise, we don't know if EOF was encountered after *exactly* 
  77.         "BUFFER_SIZE - 1" characters were read, or if characters remain
  78.         in "f" in this line.  In either case, we recursively call
  79.         "finish_line", with "reserve_count + BUFFER_SIZE - 1" as the
  80.         "reserve_count" parameter to the recursive call.
  81.  
  82. In case (1), we "malloc" a string size:  (reserve_count + strlen (buffer) + 1);
  83. in case (2), we "malloc" a string size:  (reserve_count + BUFFER_SIZE);
  84. in case (3), the "malloc"-ed space is returned by the recursive call.
  85.  
  86. In cases (1) and (2), use "strcpy (result + reserve_count, buffer)" to transfer
  87. this final invocation's chunk of the line into the result string; in case (3),
  88. use "memcpy" instead since the '\0' in "buffer" should not be transferred.
  89.  
  90.  
  91. The implementation of "read_line" is entirely analogous, except that the
  92. buffer and its size are the passed-in arguments, and not the "buffer" local
  93. and the BUFFER_SIZE constant.  Also, in cases (1) and (2), no "malloc" or
  94. "strcpy" is needed.
  95.  
  96.  
  97. Performance:
  98.  
  99. In those cases where the "buffer_size" argument to "read_line" is larger than
  100. the size of the input string, the cost equals the cost of a "fgets" plus the
  101. minimal overhead of checking that "fgets" got the whole line.  Thus, if your
  102. "buffer_size" is "usually big enough", then this "usually" is just a little
  103. slower than "fgets" (but a lot safer).
  104.  
  105. In those cases where "buffer_size" is not big enough, then the cost is:
  106.  
  107.     1 malloc + N strcpy calls + (N + 1) fgets calls
  108.     + (read_line overhead) + N * (finish_line overhead)
  109.  
  110. where N is the number of times "finish_line" is called, or about:
  111.  
  112.     (((input line length) - buffer_size) / BUFFER_SIZE) rounded-up
  113.  
  114. In terms of memory usage:
  115.  
  116. When "buffer_size" is big enough, there's just the memory needed for the
  117. "read_line" stack frame (which intentionally does *not* include a "buffer"
  118. like "finish_line").  When it's not big enough, there are N additional
  119. "finish_line" stack frames, each of which includes a BUFFER_SIZE "buffer".
  120.  
  121.  
  122.  
  123. Note that this *intentionally* avoids using "strcat" with each recursize call,
  124. since the cost of each such call gets "BUFFER_SIZE" more expensive than the
  125. last.
  126.  
  127. Note this also effectively allocates temporary storage in the run-time stack
  128. for each extra "chunk" of input that remains; this should be faster than
  129. using a linked-list of "malloc"-ed chunks, as someone suggested, presumably
  130. since stack allocation and freeing is faster than "malloc" and "free" calls.
  131.  
  132. Rich Wagner
  133.     Intermetrics, Inc.
  134.     (richw@inmet.camb.inmet.com)
  135.  
  136.  
  137. P.S.  I should also point out that an alternative solution involves being
  138.       optimistic in "finish_line" and -- instead of using a "buffer" local --
  139.       using "malloc" to allocate a pointer, P, to (reserve_count + BUFFER_SIZE)
  140.       bytes.  The "fgets" then reads directly into (P + "reserve_count").
  141.       This loses if "fgets" then doesn't get the whole string; in that case,
  142.       you paid the price of one extra "malloc" and one extra "free", whereas
  143.       using a "buffer" local would've been faster.
  144.  
  145.       Also, even if the "fgets" in "finish_line" does fit the rest of the
  146.       line into the the space at P, there'll probably unused bytes at the
  147.       end of that "malloc"-ed space, whereas the original method allocates
  148.       exactly the number of needed bytes from the heap.
  149.  
  150.  
  151.