Fix assertion for proper Huffman merge pattern: 0 == 1 modulo 1.
[pspp] / src / str.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3    Written by Ben Pfaff <blp@gnu.org>.
4
5    This program is free software; you can redistribute it and/or
6    modify it under the terms of the GNU General Public License as
7    published by the Free Software Foundation; either version 2 of the
8    License, or (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful, but
11    WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
18    02111-1307, USA. */
19
20 #include <config.h>
21 #include "str.h"
22 #include "error.h"
23 #include <ctype.h>
24 #include <limits.h>
25 #include <stdlib.h>
26 #include "alloc.h"
27 #include "error.h"
28 #include "pool.h"
29 \f
30 /* sprintf() wrapper functions for convenience. */
31
32 #if !__GNUC__
33 char *
34 spprintf (char *buf, const char *format,...)
35 {
36 #if HAVE_GOOD_SPRINTF
37   int count;
38 #endif
39   va_list args;
40
41   va_start (args, format);
42 #if HAVE_GOOD_SPRINTF
43   count =
44 #endif
45     vsprintf (buf, format, args);
46   va_end (args);
47
48 #if HAVE_GOOD_SPRINTF
49   return &buf[count];
50 #else
51   return strchr (buf, 0);
52 #endif
53 }
54 #endif /* !__GNUC__ */
55
56 #if !__GNUC__ && !HAVE_GOOD_SPRINTF
57 int
58 nsprintf (char *buf, const char *format,...)
59 {
60   va_list args;
61
62   va_start (args, format);
63   vsprintf (buf, format, args);
64   va_end (args);
65
66   return strlen (buf);
67 }
68
69 int
70 nvsprintf (char *buf, const char *format, va_list args)
71 {
72   vsprintf (buf, format, args);
73   return strlen (buf);
74 }
75 #endif /* Not GNU C and not good sprintf(). */
76 \f
77 /* Reverses the order of NBYTES bytes at address P, thus converting
78    between little- and big-endian byte orders.  */
79 void
80 mm_reverse (void *p, size_t nbytes)
81 {
82   unsigned char *h = p, *t = &h[nbytes - 1];
83   unsigned char temp;
84
85   nbytes /= 2;
86   while (nbytes--)
87     {
88       temp = *h;
89       *h++ = *t;
90       *t-- = temp;
91     }
92 }
93
94 /* Finds the last NEEDLE of length NEEDLE_LEN in a HAYSTACK of length
95    HAYSTACK_LEN.  Returns a pointer to the needle found. */
96 char *
97 mm_find_reverse (const char *haystack, size_t haystack_len,
98          const char *needle, size_t needle_len)
99 {
100   int i;
101   for (i = haystack_len - needle_len; i >= 0; i--)
102     if (!memcmp (needle, &haystack[i], needle_len))
103       return (char *) &haystack[i];
104   return 0;
105 }
106
107 /* Compares A of length A_LEN to B of length B_LEN.  The shorter
108    string is considered to be padded with spaces to the length of
109    the longer. */
110 int
111 st_compare_pad (const char *a, size_t a_len, const char *b, size_t b_len)
112 {
113   size_t min_len;
114   int result;
115
116   min_len = a_len < b_len ? a_len : b_len;
117   result = memcmp (a, b, min_len);
118   if (result != 0)
119     return result;
120   else 
121     {
122       size_t idx;
123       
124       if (a_len < b_len) 
125         {
126           for (idx = min_len; idx < b_len; idx++)
127             if (' ' != b[idx])
128               return ' ' > b[idx] ? 1 : -1;
129         }
130       else 
131         {
132           for (idx = min_len; idx < a_len; idx++)
133             if (a[idx] != ' ')
134               return a[idx] > ' ' ? 1 : -1;
135         }
136       return 0;
137     }
138 }
139
140 /* Copies SRC to DEST, truncating to N characters or right-padding
141    with spaces to N characters as necessary.  Does not append a null
142    character.  SRC must be null-terminated. */
143 void
144 st_bare_pad_copy (char *dest, const char *src, size_t n)
145 {
146   size_t len;
147
148   len = strlen (src);
149   if (len >= n)
150     memcpy (dest, src, n);
151   else
152     {
153       memcpy (dest, src, len);
154       memset (&dest[len], ' ', n - len);
155     }
156 }
157
158 /* Copies SRC to DEST, truncating SRC to N characters or right-padding
159    with spaces to N characters if necessary.  Does not append a null
160    character.  SRC must be LEN characters long but does not need to be
161    null-terminated. */
162 void
163 st_bare_pad_len_copy (char *dest, const char *src, size_t n, size_t len)
164 {
165   if (len >= n)
166     memmove (dest, src, n);
167   else
168     {
169       memmove (dest, src, len);
170       memset (&dest[len], ' ', n - len);
171     }
172 }
173
174 /* Copies SRC to DEST, truncating SRC to N-1 characters or
175    right-padding with spaces to N-1 characters if necessary.  Always
176    appends a null character. */
177 void
178 st_pad_copy (char *dest, const char *src, size_t n)
179 {
180   size_t len;
181
182   len = strlen (src);
183   if (len == n - 1)
184     strcpy (dest, src);
185   else if (len < n - 1)
186     {
187       memcpy (dest, src, len);
188       memset (&dest[len], ' ', n - 1 - len);
189       dest[n - 1] = 0;
190     }
191   else
192     {
193       memcpy (dest, src, n - 1);
194       dest[n - 1] = 0;
195     }
196 }
197 \f
198 /* Initializes ST with initial contents S. */
199 void
200 ds_create (struct string *st, const char *s)
201 {
202   st->length = strlen (s);
203   st->capacity = 8 + st->length * 2;
204   st->string = xmalloc (st->capacity + 1);
205   strcpy (st->string, s);
206 }
207
208 /* Initializes ST, making room for at least CAPACITY characters. */
209 void
210 ds_init (struct string *st, size_t capacity)
211 {
212   st->length = 0;
213   if (capacity > 8)
214     st->capacity = capacity;
215   else
216     st->capacity = 8;
217   st->string = xmalloc (st->capacity + 1);
218 }
219
220 /* Replaces the contents of ST with STRING.  STRING may overlap with
221    ST. */
222 void
223 ds_replace (struct string *st, const char *string)
224 {
225   size_t new_length = strlen (string);
226   if (new_length > st->capacity) 
227     {
228       /* The new length is longer than the allocated length, so
229          there can be no overlap. */
230       st->length = 0;
231       ds_concat (st, string, new_length);
232     }
233   else
234     {
235       /* Overlap is possible, but the new string will fit in the
236          allocated space, so we can just copy data. */
237       st->length = new_length;
238       memmove (st->string, string, st->length);
239     }
240 }
241
242 /* Frees ST. */
243 void
244 ds_destroy (struct string *st)
245 {
246   free (st->string);
247 }
248
249 /* Truncates ST to zero length. */
250 void
251 ds_clear (struct string *st)
252 {
253   st->length = 0;
254 }
255
256 /* Pad ST on the right with copies of PAD until ST is at least
257    LENGTH characters in size.  If ST is initially LENGTH
258    characters or longer, this is a no-op. */
259 void
260 ds_rpad (struct string *st, size_t length, char pad) 
261 {
262   assert (st != NULL);
263   if (st->length < length) 
264     {
265       if (st->capacity < length)
266         ds_extend (st, length);
267       memset (&st->string[st->length], pad, length - st->length);
268       st->length = length;
269     }
270 }
271
272 /* Ensures that ST can hold at least MIN_CAPACITY characters plus a null
273    terminator. */
274 void
275 ds_extend (struct string *st, size_t min_capacity)
276 {
277   if (min_capacity > st->capacity)
278     {
279       st->capacity *= 2;
280       if (st->capacity < min_capacity)
281         st->capacity = min_capacity * 2;
282       
283       st->string = xrealloc (st->string, st->capacity + 1);
284     }
285 }
286
287 /* Shrink ST to the minimum capacity need to contain its content. */
288 void
289 ds_shrink (struct string *st)
290 {
291   if (st->capacity != st->length)
292     {
293       st->capacity = st->length;
294       st->string = xrealloc (st->string, st->capacity + 1);
295     }
296 }
297
298 /* Truncates ST to at most LENGTH characters long. */
299 void
300 ds_truncate (struct string *st, size_t length)
301 {
302   if (length >= st->length)
303     return;
304   st->length = length;
305 }
306
307 /* Returns the length of ST. */
308 size_t
309 ds_length (const struct string *st)
310 {
311   return st->length;
312 }
313
314 /* Returns the allocation size of ST. */
315 size_t
316 ds_capacity (const struct string *st)
317 {
318   return st->capacity;
319 }
320
321 /* Returns the value of ST as a null-terminated string. */
322 char *
323 ds_c_str (const struct string *st)
324 {
325   ((char *) st->string)[st->length] = '\0';
326   return st->string;
327 }
328
329 /* Returns the string data inside ST. */
330 char *
331 ds_data (const struct string *st)
332 {
333   return st->string;
334 }
335
336 /* Returns a pointer to the null terminator ST.
337    This might not be an actual null character unless ds_c_str() has
338    been called since the last modification to ST. */
339 char *
340 ds_end (const struct string *st)
341 {
342   return st->string + st->length;
343 }
344
345 /* Concatenates S onto ST. */
346 void
347 ds_puts (struct string *st, const char *s)
348 {
349   size_t s_len;
350
351   if (!s) return;
352
353   s_len = strlen (s);
354   ds_extend (st, st->length + s_len);
355   strcpy (st->string + st->length, s);
356   st->length += s_len;
357 }
358
359 /* Concatenates LEN characters from BUF onto ST. */
360 void
361 ds_concat (struct string *st, const char *buf, size_t len)
362 {
363   ds_extend (st, st->length + len);
364   memcpy (st->string + st->length, buf, len);
365   st->length += len;
366 }
367
368 void ds_vprintf (struct string *st, const char *format, va_list args);
369
370
371 /* Formats FORMAT as a printf string and appends the result to ST. */
372 void
373 ds_printf (struct string *st, const char *format, ...)
374 {
375   va_list args;
376
377   va_start (args, format);
378   ds_vprintf(st,format,args);
379   va_end (args);
380
381 }
382
383 /* Formats FORMAT as a printf string and appends the result to ST. */
384 void
385 ds_vprintf (struct string *st, const char *format, va_list args)
386 {
387   /* Fscking glibc silently changed behavior between 2.0 and 2.1.
388      Fsck fsck fsck.  Before, it returned -1 on buffer overflow.  Now,
389      it returns the number of characters (not bytes) that would have
390      been written. */
391
392   int avail, needed;
393
394   avail = st->capacity - st->length + 1;
395   needed = vsnprintf (st->string + st->length, avail, format, args);
396
397
398   if (needed >= avail)
399     {
400       ds_extend (st, st->length + needed);
401       
402       vsprintf (st->string + st->length, format, args);
403     }
404   else
405     while (needed == -1)
406       {
407         ds_extend (st, (st->capacity + 1) * 2);
408         avail = st->capacity - st->length + 1;
409
410         needed = vsnprintf (st->string + st->length, avail, format, args);
411
412       }
413
414   st->length += needed;
415 }
416
417 /* Appends character CH to ST. */
418 void
419 ds_putc (struct string *st, int ch)
420 {
421   if (st->length == st->capacity)
422     ds_extend (st, st->length + 1);
423   st->string[st->length++] = ch;
424 }
425
426 /* Appends to ST a newline-terminated line read from STREAM.
427    Newline is the last character of ST on return, unless an I/O error
428    or end of file is encountered after reading some characters.
429    Returns 1 if a line is successfully read, or 0 if no characters at
430    all were read before an I/O error or end of file was
431    encountered. */
432 int
433 ds_gets (struct string *st, FILE *stream)
434 {
435   int c;
436
437   c = getc (stream);
438   if (c == EOF)
439     return 0;
440
441   for (;;)
442     {
443       ds_putc (st, c);
444       if (c == '\n')
445         return 1;
446
447       c = getc (stream);
448       if (c == EOF)
449         return 1;
450     }
451 }
452
453 /* Reads a line from STREAM into ST, then preprocesses as follows:
454
455    - Splices lines terminated with `\'.
456
457    - Deletes comments introduced by `#' outside of single or double
458      quotes.
459
460    - Trailing whitespace will be deleted.  
461
462    Increments cust_ln as appropriate.
463
464    Returns nonzero only if a line was successfully read. */
465 int
466 ds_get_config_line (FILE *stream, struct string *st, struct file_locator *where)
467 {
468   /* Read the first line. */
469   ds_clear (st);
470   where->line_number++;
471   if (!ds_gets (st, stream))
472     return 0;
473
474   /* Read additional lines, if any. */
475   for (;;)
476     {
477       /* Remove trailing whitespace. */
478       {
479         char *s = ds_c_str (st);
480         size_t len = ds_length (st);
481       
482         while (len > 0 && isspace ((unsigned char) s[len - 1]))
483           len--;
484         ds_truncate (st, len);
485       }
486
487       /* Check for trailing \.  Remove if found, bail otherwise. */
488       if (ds_length (st) == 0 || ds_c_str (st)[ds_length (st) - 1] != '\\')
489         break;
490       ds_truncate (st, ds_length (st) - 1);
491
492       /* Append another line and go around again. */
493       {
494         int success = ds_gets (st, stream);
495         where->line_number++;
496         if (!success)
497           return 1;
498       }
499     }
500
501   /* Find a comment and remove. */
502   {
503     char *cp;
504     int quote = 0;
505       
506     for (cp = ds_c_str (st); *cp; cp++)
507       if (quote)
508         {
509           if (*cp == quote)
510             quote = 0;
511           else if (*cp == '\\')
512             cp++;
513         }
514       else if (*cp == '\'' || *cp == '"')
515         quote = *cp;
516       else if (*cp == '#')
517         {
518           ds_truncate (st, cp - ds_c_str (st));
519           break;
520         }
521   }
522
523   return 1;
524 }
525 \f
526 /* Lengthed strings. */
527
528 /* Creates a new lengthed string LS with contents as a copy of
529    S. */
530 void
531 ls_create (struct len_string *ls, const char *s)
532 {
533   ls->length = strlen (s);
534   ls->string = xmalloc (ls->length + 1);
535   memcpy (ls->string, s, ls->length + 1);
536 }
537
538 /* Creates a new lengthed string LS with contents as a copy of
539    BUFFER with length LEN. */
540 void
541 ls_create_buffer (struct len_string *ls,
542                   const char *buffer, size_t len)
543 {
544   ls->length = len;
545   ls->string = xmalloc (len + 1);
546   memcpy (ls->string, buffer, len);
547   ls->string[len] = '\0';
548 }
549
550 /* Sets the fields of LS to the specified values. */
551 void
552 ls_init (struct len_string *ls, const char *string, size_t length)
553 {
554   ls->string = (char *) string;
555   ls->length = length;
556 }
557
558 /* Copies the fields of SRC to DST. */
559 void
560 ls_shallow_copy (struct len_string *dst, const struct len_string *src)
561 {
562   *dst = *src;
563 }
564
565 /* Frees the memory backing LS. */
566 void
567 ls_destroy (struct len_string *ls)
568 {
569   free (ls->string);
570 }
571
572 /* Sets LS to a null pointer value. */
573 void
574 ls_null (struct len_string *ls)
575 {
576   ls->string = NULL;
577 }
578
579 /* Returns nonzero only if LS has a null pointer value. */
580 int
581 ls_null_p (const struct len_string *ls)
582 {
583   return ls->string == NULL;
584 }
585
586 /* Returns nonzero only if LS is a null pointer or has length 0. */
587 int
588 ls_empty_p (const struct len_string *ls)
589 {
590   return ls->string == NULL || ls->length == 0;
591 }
592
593 /* Returns the length of LS, which must not be null. */
594 size_t
595 ls_length (const struct len_string *ls)
596 {
597   return ls->length;
598 }
599
600 /* Returns a pointer to the character string in LS. */
601 char *
602 ls_c_str (const struct len_string *ls)
603 {
604   return (char *) ls->string;
605 }
606
607 /* Returns a pointer to the null terminator of the character string in
608    LS. */
609 char *
610 ls_end (const struct len_string *ls)
611 {
612   return (char *) (ls->string + ls->length);
613 }