source/texk/web2c/mplibdir/mpstrings.w

   1 % This file is part of MetaPost;
   2 % the MetaPost program is in the public domain.
   3 % See the <Show version...> code in mpost.w for more info.
   4
   5 @* String handling.
   6
   7
   8 @ First, we will need some stuff from other files
   9 @c
  10 #include <w2c/config.h>
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <stdarg.h>
  15 #include <assert.h>
  16 #ifdef HAVE_UNISTD_H
  17 #  include <unistd.h>           /* for access */
  18 #endif
  19 #include <time.h>               /* for struct tm \& co */
  20 #include "mpstrings.h"          /* internal header */
  21
  22 @ Then there is some stuff we need to prepare ourselves
  23
  24 @(mpstrings.h@>=
  25 #ifndef MPSTRINGS_H
  26 #define MPSTRINGS_H 1
  27 #include "mplib.h"
  28 #include "mplibps.h"            /* external header */
  29 #include "mplibsvg.h"           /* external header */
  30 #include "mpmp.h"               /* internal header */
  31 #include "mppsout.h"            /* internal header */
  32 #include "mpsvgout.h"           /* internal header */
  33 #include "mpmath.h"             /* internal header */
  34 @<Definitions@>;
  35 #endif
  36
  37 @ Here are the functions needed for the avl construction.
  38
  39 @<Definitions@>=
  40 void *copy_strings_entry (const void *p);
  41
  42 @ An earlier version of this function used |strncmp|, but that produces
  43 wrong results in some cases.
  44 @c
  45 #define STRCMP_RESULT(a) ((a)<0 ? -1 : ((a)>0 ? 1 : 0))
  46 static int comp_strings_entry (void *p, const void *pa, const void *pb) {
  47   const mp_lstring *a = (const mp_lstring *) pa;
  48   const mp_lstring *b = (const mp_lstring *) pb;
  49   size_t l;
  50   unsigned char *s,*t;
  51   (void) p;
  52   s = a->str;
  53   t = b->str;
  54   l = (a->len<=b->len ? a->len : b->len);
  55   while ( l-->0 ) {
  56     if ( *s!=*t)
  57        return STRCMP_RESULT(*s-*t);
  58     s++; t++;
  59   }
  60   return STRCMP_RESULT((int)(a->len-b->len));
  61 }
  62 void *copy_strings_entry (const void *p) {
  63   mp_string ff;
  64   const mp_lstring *fp;
  65   fp = (const mp_lstring *) p;
  66   ff = malloc (sizeof (mp_lstring));
  67   if (ff == NULL)
  68     return NULL;
  69   ff->str = malloc (fp->len + 1);
  70   if (ff->str == NULL) {
  71     return NULL;
  72   }
  73   memcpy ((char *) ff->str, (char *) fp->str, fp->len + 1);
  74   ff->len = fp->len;
  75   ff->refs = 0;
  76   return ff;
  77 }
  78 static void *delete_strings_entry (void *p) {
  79   mp_string ff = (mp_string) p;
  80   mp_xfree (ff->str);
  81   mp_xfree (ff);
  82   return NULL;
  83 }
  84
  85 @ Actually creating strings is done by |make_string|, but in order to
  86 do so it needs a way to create a new, empty string structure.
  87
  88 @ @c
  89 static mp_string new_strings_entry (MP mp) {
  90   mp_string ff;
  91   ff = mp_xmalloc (mp, 1, sizeof (mp_lstring));
  92   ff->str = NULL;
  93   ff->len = 0;
  94   ff->refs = 0;
  95   return ff;
  96 }
  97
  98
  99 @ Some even more low-level functions are these:
 100
 101 @<Definitions@>=
 102 extern int mp_xstrcmp (const char *a, const char *b);
 103 extern char *mp_xstrdup (MP mp, const char *s);
 104 extern char *mp_xstrldup (MP mp, const char *s, size_t l);
 105 extern char *mp_strdup (const char *p);
 106 extern char *mp_strldup (const char *p, size_t l);
 107
 108 @ @c
 109 char *mp_strldup (const char *p, size_t l) {
 110   char *r, *s;
 111   if (p == NULL)
 112     return NULL;
 113   r = malloc ((size_t) (l * sizeof (char) + 1));
 114   if (r == NULL)
 115     return NULL;
 116   s = memcpy (r, p, (size_t) (l));
 117   *(s + l) = '\0';
 118   return s;
 119 }
 120 char *mp_strdup (const char *p) {
 121   if (p == NULL)
 122     return NULL;
 123   return mp_strldup (p, strlen (p));
 124 }
 125
 126 @ @c
 127 int mp_xstrcmp (const char *a, const char *b) {
 128   if (a == NULL && b == NULL)
 129     return 0;
 130   if (a == NULL)
 131     return -1;
 132   if (b == NULL)
 133     return 1;
 134   return strcmp (a, b);
 135 }
 136 char *mp_xstrldup (MP mp, const char *s, size_t l) {
 137   char *w;
 138   if (s == NULL)
 139     return NULL;
 140   w = mp_strldup (s, l);
 141   if (w == NULL) {
 142     mp_fputs ("Out of memory!\n", mp->err_out);
 143     mp->history = mp_system_error_stop;
 144     mp_jump_out (mp);
 145   }
 146   return w;
 147 }
 148 char *mp_xstrdup (MP mp, const char *s) {
 149   if (s == NULL)
 150     return NULL;
 151   return mp_xstrldup (mp, s, strlen (s));
 152 }
 153
 154
 155 @ @c
 156 void mp_initialize_strings (MP mp) {
 157   mp->strings = avl_create (comp_strings_entry,
 158                             copy_strings_entry,
 159                             delete_strings_entry, malloc, free, NULL);
 160   mp->cur_string = NULL;
 161   mp->cur_length = 0;
 162   mp->cur_string_size = 0;
 163 }
 164
 165 @ @c
 166 void mp_dealloc_strings (MP mp) {
 167   if (mp->strings != NULL)
 168     avl_destroy (mp->strings);
 169   mp->strings = NULL;
 170   mp_xfree (mp->cur_string);
 171   mp->cur_string = NULL;
 172   mp->cur_length = 0;
 173   mp->cur_string_size = 0;
 174 }
 175
 176 @ Here are the definitions
 177 @<Definitions@>=
 178 extern void mp_initialize_strings (MP mp);
 179 extern void mp_dealloc_strings (MP mp);
 180
 181 @ Most printing is done from |char *|s, but sometimes not. Here are
 182 functions that convert an internal string into a |char *| for use
 183 by the printing routines, and vice versa.
 184
 185 @<Definitions@>=
 186 char *mp_str (MP mp, mp_string s);
 187 mp_string mp_rtsl (MP mp, const char *s, size_t l);
 188 mp_string mp_rts (MP mp, const char *s);
 189 mp_string mp_make_string (MP mp);
 190
 191 @ @c
 192 char *mp_str (MP mp, mp_string ss) {
 193   (void) mp;
 194   return (char *) ss->str;
 195 }
 196
 197 @ @c
 198 mp_string mp_rtsl (MP mp, const char *s, size_t l) {
 199   mp_string str, nstr;
 200   str = new_strings_entry (mp);
 201   str->str = (unsigned char *)mp_xstrldup (mp, s, l);
 202   str->len = l;
 203   nstr = (mp_string) avl_find (str, mp->strings);
 204   if (nstr == NULL) {            /* not yet known */
 205     assert (avl_ins (str, mp->strings, avl_false) > 0);
 206     nstr = (mp_string) avl_find (str, mp->strings);
 207   }
 208   (void)delete_strings_entry(str);
 209   add_str_ref(nstr);
 210   return nstr;
 211 }
 212
 213 @ @c
 214 mp_string mp_rts (MP mp, const char *s) {
 215   return mp_rtsl (mp, s, strlen (s));
 216 }
 217
 218
 219 @ Strings are created by appending character codes to |cur_string|.
 220 The |append_char| macro, defined here, does not check to see if the
 221 buffer overflows; this test is supposed to be
 222 made before |append_char| is used.
 223
 224 To test if there is room to append |l| more characters to |cur_string|,
 225 we shall write |str_room(l)|, which tries to make sure there is enough room
 226 in the |cur_string|.
 227
 228 @<Definitions@>=
 229 #define EXTRA_STRING 500
 230 #define append_char(A) do { \
 231     str_room(1); \
 232     *(mp->cur_string+mp->cur_length)=(unsigned char)(A); \
 233     mp->cur_length++; \
 234 } while (0)
 235 #define str_room(wsize) do { \
 236     size_t nsize; \
 237     if ((mp->cur_length+(size_t)wsize) > mp->cur_string_size) { \
 238         nsize = mp->cur_string_size + mp->cur_string_size / 5 + EXTRA_STRING; \
 239         if (nsize < (size_t)(wsize)) { \
 240             nsize = (size_t)wsize + EXTRA_STRING; \
 241         } \
 242         mp->cur_string = (unsigned char *) mp_xrealloc(mp, mp->cur_string, (unsigned)nsize, sizeof(unsigned char)); \
 243         memset (mp->cur_string+mp->cur_length,0,(nsize-mp->cur_length)); \
 244         mp->cur_string_size = nsize; \
 245     } \
 246 } while (0)
 247
 248
 249 @ At the very start of the metapost run and each time after
 250 |make_string| has stored a new string in the avl tree, the
 251 |cur_string| variable has to be prepared so that it will be ready to
 252 start creating a new string. The initial size is fairly arbitrary, but
 253 setting it a little higher than expected helps prevent |reallocs|
 254
 255 @<Definitions@>=
 256 void mp_reset_cur_string (MP mp);
 257
 258 @ @c
 259 void mp_reset_cur_string (MP mp) {
 260   mp_xfree (mp->cur_string);
 261   mp->cur_length = 0;
 262   mp->cur_string_size = 63;
 263   mp->cur_string = (unsigned char *) mp_xmalloc (mp, 64, sizeof (unsigned char));
 264   memset (mp->cur_string, 0, 64);
 265 }
 266
 267
 268 @ \MP's string expressions are implemented in a brute-force way: Every
 269 new string or substring that is needed is simply stored into the string pool.
 270 Space is eventually reclaimed using the aid of a simple system system
 271 of reference counts.
 272 @^reference counts@>
 273
 274 The number of references to string number |s| will be |s->refs|. The
 275 special value |s->refs=MAX_STR_REF=127| is used to denote an unknown
 276 positive number of references; such strings will never be recycled. If
 277 a string is ever referred to more than 126 times, simultaneously, we
 278 put it in this category.
 279
 280 @<Definitions@>=
 281 #define MAX_STR_REF 127 /* ``infinite'' number of references */
 282 #define add_str_ref(A) { if ( (A)->refs < MAX_STR_REF ) ((A)->refs)++; }
 283
 284 @ Here's what we do when a string reference disappears:
 285
 286 @<Definitions@>=
 287 #define delete_str_ref(A) do {  \
 288     if ( (A)->refs < MAX_STR_REF ) { \
 289        if ( (A)->refs > 1 ) ((A)->refs)--;  \
 290        else mp_flush_string(mp, (A)); \
 291     } \
 292   } while (0)
 293
 294 @ @<Definitions@>=
 295 void mp_flush_string (MP mp, mp_string s);
 296
 297 @ @c
 298 void mp_flush_string (MP mp, mp_string s) {
 299   if (s->refs == 0) {
 300     mp->strs_in_use--;
 301     mp->pool_in_use = mp->pool_in_use - (integer) s->len;
 302     (void) avl_del (s, mp->strings, NULL);
 303   }
 304 }
 305
 306
 307 @ Some C literals that are used as values cannot be simply added,
 308 their reference count has to be set such that they can not be flushed.
 309
 310 @c
 311 mp_string mp_intern (MP mp, const char *s) {
 312   mp_string r;
 313   r = mp_rts (mp, s);
 314   r->refs = MAX_STR_REF;
 315   return r;
 316 }
 317
 318 @ @<Definitions@>=
 319 mp_string mp_intern (MP mp, const char *s);
 320
 321
 322 @ Once a sequence of characters has been appended to |cur_string|, it
 323 officially becomes a string when the function |make_string| is called.
 324 This function returns a pointer to the new string as its value.
 325
 326 @<Definitions@>=
 327 mp_string mp_make_string (MP mp);
 328
 329 @ @c
 330 mp_string mp_make_string (MP mp) {                               /* current string enters the pool */
 331   mp_string str;
 332   mp_lstring tmp;
 333   tmp.str = mp->cur_string;
 334   tmp.len = mp->cur_length;
 335   str = (mp_string) avl_find (&tmp, mp->strings);
 336   if (str == NULL) {            /* not yet known */
 337     str = mp_xmalloc (mp, 1, sizeof (mp_lstring));
 338     str->str = mp->cur_string;
 339     str->len = tmp.len;
 340     assert (avl_ins (str, mp->strings, avl_false) > 0);
 341     str = (mp_string) avl_find (&tmp, mp->strings);
 342     mp->pool_in_use = mp->pool_in_use + (integer) str->len;
 343     if (mp->pool_in_use > mp->max_pl_used)
 344       mp->max_pl_used = mp->pool_in_use;
 345     mp->strs_in_use++;
 346     if (mp->strs_in_use > mp->max_strs_used)
 347       mp->max_strs_used = mp->strs_in_use;
 348   }
 349   add_str_ref(str);
 350   mp_reset_cur_string (mp);
 351   return str;
 352 }
 353
 354
 355 @ Here is a routine that compares two strings in the string pool,
 356 and it does not assume that they have the same length. If the first string
 357 is lexicographically greater than, less than, or equal to the second,
 358 the result is respectively positive, negative, or zero.
 359
 360 @<Definitions@>=
 361 integer mp_str_vs_str (MP mp, mp_string s, mp_string t);
 362
 363 @ @c
 364 integer mp_str_vs_str (MP mp, mp_string s, mp_string t) {
 365   (void) mp;
 366   return comp_strings_entry (NULL, (const void *) s, (const void *) t);
 367 }
 368
 369
 370
 371 @ @<Definitions@>=
 372 mp_string mp_cat (MP mp, mp_string a, mp_string b);
 373
 374 @ @c
 375 mp_string mp_cat (MP mp, mp_string a, mp_string b) {
 376   mp_string str;
 377   size_t needed;
 378   size_t saved_cur_length = mp->cur_length;
 379   unsigned char *saved_cur_string = mp->cur_string;
 380   size_t saved_cur_string_size = mp->cur_string_size;
 381   needed = a->len + b->len;
 382   mp->cur_length = 0;
 383   /* mp->cur_string = NULL; */ /* needs malloc, spotted by clang */
 384   mp->cur_string = (unsigned char *) mp_xmalloc (mp, needed+1, sizeof (unsigned char));
 385   mp->cur_string_size = 0;
 386   str_room (needed+1);
 387   (void) memcpy (mp->cur_string, a->str, a->len);
 388   (void) memcpy (mp->cur_string + a->len, b->str, b->len);
 389   mp->cur_length = needed;
 390   mp->cur_string[needed] = '\0';
 391   str = mp_make_string (mp);
 392   mp_xfree(mp->cur_string); /* created by |mp_make_string| */
 393   mp->cur_length = saved_cur_length;
 394   mp->cur_string = saved_cur_string;
 395   mp->cur_string_size = saved_cur_string_size;
 396   return str;
 397 }
 398
 399
 400 @ @<Definitions@>=
 401 mp_string mp_chop_string (MP mp, mp_string s, integer a, integer b);
 402
 403 @ @c
 404 mp_string mp_chop_string (MP mp, mp_string s, integer a, integer b) {
 405   integer l;    /* length of the original string */
 406   integer k;    /* runs from |a| to |b| */
 407   boolean reversed;     /* was |a>b|? */
 408   if (a <= b)
 409     reversed = false;
 410   else {
 411     reversed = true;
 412     k = a;
 413     a = b;
 414     b = k;
 415   }
 416   l = (integer) s->len;
 417   if (a < 0) {
 418     a = 0;
 419     if (b < 0)
 420       b = 0;
 421   }
 422   if (b > l) {
 423     b = l;
 424     if (a > l)
 425       a = l;
 426   }
 427   str_room ((size_t) (b - a));
 428   if (reversed) {
 429     for (k = b - 1; k >= a; k--) {
 430       append_char (*(s->str + k));
 431     }
 432   } else {
 433     for (k = a; k < b; k++) {
 434       append_char (*(s->str + k));
 435     }
 436   }
 437   return mp_make_string (mp);
 438 }
 439