diff options
author | Peter Breitenlohner <peb@mppmu.mpg.de> | 2013-03-21 09:16:59 +0000 |
---|---|---|
committer | Peter Breitenlohner <peb@mppmu.mpg.de> | 2013-03-21 09:16:59 +0000 |
commit | 388463b9fa865c3b2311508c41647b0f3c532031 (patch) | |
tree | 1cdfbf5552d0783ecbcc52017e49567e5042af33 /Build/source/texk/web2c/mplibdir/mpstrings.w | |
parent | abd0b00a4e8c1ac6f5b20c7474d70ef579129991 (diff) |
Import MetaPost 1.800 and LuaTeX beta-0.75.0 from LuaTeX repository r4604
git-svn-id: svn://tug.org/texlive/trunk@29453 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/web2c/mplibdir/mpstrings.w')
-rw-r--r-- | Build/source/texk/web2c/mplibdir/mpstrings.w | 441 |
1 files changed, 441 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/mplibdir/mpstrings.w b/Build/source/texk/web2c/mplibdir/mpstrings.w new file mode 100644 index 00000000000..0ecc4e6ff7e --- /dev/null +++ b/Build/source/texk/web2c/mplibdir/mpstrings.w @@ -0,0 +1,441 @@ +% $Id: mpstrings.w 1702 2012-09-27 10:31:30Z taco $ +% +% This file is part of MetaPost; +% the MetaPost program is in the public domain. +% See the <Show version...> code in mpost.w for more info. + +@* String handling. + + +@ First, we will need some stuff from other files +@c +#include <w2c/config.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <stdarg.h> +#include <assert.h> +#ifdef HAVE_UNISTD_H +# include <unistd.h> /* for access */ +#endif +#include <time.h> /* for struct tm \& co */ +#include "mpstrings.h" /* internal header */ + +@ Then there is some stuff we need to prepare ourselves + +@(mpstrings.h@>= +#ifndef MPSTRINGS_H +#define MPSTRINGS_H 1 +#include "mplib.h" +#include "mplibps.h" /* external header */ +#include "mplibsvg.h" /* external header */ +#include "mpmp.h" /* internal header */ +#include "mppsout.h" /* internal header */ +#include "mpsvgout.h" /* internal header */ +#include "mpmath.h" /* internal header */ +@<Definitions@>; +#endif + +@ Here are the functions needed for the avl construction. + +@<Definitions@>= +void *copy_strings_entry (const void *p); + +@ An earlier version of this function used |strncmp|, but that produces +wrong results in some cases. +@c +#define STRCMP_RESULT(a) ((a)<0 ? -1 : ((a)>0 ? 1 : 0)) +static int comp_strings_entry (void *p, const void *pa, const void *pb) { + const mp_lstring *a = (const mp_lstring *) pa; + const mp_lstring *b = (const mp_lstring *) pb; + size_t l; + unsigned char *s,*t; + (void) p; + s = a->str; + t = b->str; + l = (a->len<=b->len ? a->len : b->len); + while ( l-->0 ) { + if ( *s!=*t) + return STRCMP_RESULT(*s-*t); + s++; t++; + } + return STRCMP_RESULT((int)(a->len-b->len)); +} +void *copy_strings_entry (const void *p) { + mp_string ff; + const mp_lstring *fp; + fp = (const mp_lstring *) p; + ff = malloc (sizeof (mp_lstring)); + if (ff == NULL) + return NULL; + ff->str = malloc (fp->len + 1); + if (ff->str == NULL) { + return NULL; + } + memcpy ((char *) ff->str, (char *) fp->str, fp->len + 1); + ff->len = fp->len; + ff->refs = 0; + return ff; +} +static void *delete_strings_entry (void *p) { + mp_string ff = (mp_string) p; + mp_xfree (ff->str); + mp_xfree (ff); + return NULL; +} + +@ Actually creating strings is done by |make_string|, but in order to +do so it needs a way to create a new, empty string structure. + +@ @c +static mp_string new_strings_entry (MP mp) { + mp_string ff; + ff = mp_xmalloc (mp, 1, sizeof (mp_lstring)); + ff->str = NULL; + ff->len = 0; + ff->refs = 0; + return ff; +} + + +@ Some even more low-level functions are these: + +@<Definitions@>= +extern int mp_xstrcmp (const char *a, const char *b); +extern char *mp_xstrdup (MP mp, const char *s); +extern char *mp_xstrldup (MP mp, const char *s, size_t l); +extern char *mp_strdup (const char *p); +extern char *mp_strldup (const char *p, size_t l); + +@ @c +char *mp_strldup (const char *p, size_t l) { + char *r, *s; + if (p == NULL) + return NULL; + r = malloc ((size_t) (l * sizeof (char) + 1)); + if (r == NULL) + return NULL; + s = memcpy (r, p, (size_t) (l)); + *(s + l) = '\0'; + return s; +} +char *mp_strdup (const char *p) { + if (p == NULL) + return NULL; + return mp_strldup (p, strlen (p)); +} + +@ @c +int mp_xstrcmp (const char *a, const char *b) { + if (a == NULL && b == NULL) + return 0; + if (a == NULL) + return -1; + if (b == NULL) + return 1; + return strcmp (a, b); +} +char *mp_xstrldup (MP mp, const char *s, size_t l) { + char *w; + if (s == NULL) + return NULL; + w = mp_strldup (s, l); + if (w == NULL) { + mp_fputs ("Out of memory!\n", mp->err_out); + mp->history = mp_system_error_stop; + mp_jump_out (mp); + } + return w; +} +char *mp_xstrdup (MP mp, const char *s) { + if (s == NULL) + return NULL; + return mp_xstrldup (mp, s, strlen (s)); +} + + +@ @c +void mp_initialize_strings (MP mp) { + mp->strings = avl_create (comp_strings_entry, + copy_strings_entry, + delete_strings_entry, malloc, free, NULL); + mp->cur_string = NULL; + mp->cur_length = 0; + mp->cur_string_size = 0; +} + +@ @c +void mp_dealloc_strings (MP mp) { + if (mp->strings != NULL) + avl_destroy (mp->strings); + mp->strings = NULL; + mp_xfree (mp->cur_string); + mp->cur_string = NULL; + mp->cur_length = 0; + mp->cur_string_size = 0; +} + +@ Here are the definitions +@<Definitions@>= +extern void mp_initialize_strings (MP mp); +extern void mp_dealloc_strings (MP mp); + +@ Most printing is done from |char *|s, but sometimes not. Here are +functions that convert an internal string into a |char *| for use +by the printing routines, and vice versa. + +@<Definitions@>= +char *mp_str (MP mp, mp_string s); +mp_string mp_rtsl (MP mp, const char *s, size_t l); +mp_string mp_rts (MP mp, const char *s); +mp_string mp_make_string (MP mp); + +@ @c +char *mp_str (MP mp, mp_string ss) { + (void) mp; + return (char *) ss->str; +} + +@ @c +mp_string mp_rtsl (MP mp, const char *s, size_t l) { + mp_string str, nstr; + str = new_strings_entry (mp); + str->str = (unsigned char *)mp_xstrldup (mp, s, l); + str->len = l; + nstr = (mp_string) avl_find (str, mp->strings); + if (nstr == NULL) { /* not yet known */ + assert (avl_ins (str, mp->strings, avl_false) > 0); + nstr = (mp_string) avl_find (str, mp->strings); + } + (void)delete_strings_entry(str); + add_str_ref(nstr); + return nstr; +} + +@ @c +mp_string mp_rts (MP mp, const char *s) { + return mp_rtsl (mp, s, strlen (s)); +} + + +@ Strings are created by appending character codes to |cur_string|. +The |append_char| macro, defined here, does not check to see if the +buffer overflows; this test is supposed to be +made before |append_char| is used. + +To test if there is room to append |l| more characters to |cur_string|, +we shall write |str_room(l)|, which tries to make sure there is enough room +in the |cur_string|. + +@<Definitions@>= +#define EXTRA_STRING 500 +#define append_char(A) do { \ + str_room(1); \ + *(mp->cur_string+mp->cur_length)=(unsigned char)(A); \ + mp->cur_length++; \ +} while (0) +#define str_room(wsize) do { \ + size_t nsize; \ + if ((mp->cur_length+(size_t)wsize) > mp->cur_string_size) { \ + nsize = mp->cur_string_size + mp->cur_string_size / 5 + EXTRA_STRING; \ + if (nsize < (size_t)(wsize)) { \ + nsize = (size_t)wsize + EXTRA_STRING; \ + } \ + mp->cur_string = (unsigned char *) mp_xrealloc(mp, mp->cur_string, (unsigned)nsize, sizeof(unsigned char)); \ + memset (mp->cur_string+mp->cur_length,0,(nsize-mp->cur_length)); \ + mp->cur_string_size = nsize; \ + } \ +} while (0) + + +@ At the very start of the metapost run and each time after +|make_string| has stored a new string in the avl tree, the +|cur_string| variable has to be prepared so that it will be ready to +start creating a new string. The initial size is fairly arbitrary, but +setting it a little higher than expected helps prevent |reallocs| + +@<Definitions@>= +void mp_reset_cur_string (MP mp); + +@ @c +void mp_reset_cur_string (MP mp) { + mp_xfree (mp->cur_string); + mp->cur_length = 0; + mp->cur_string_size = 63; + mp->cur_string = (unsigned char *) mp_xmalloc (mp, 64, sizeof (unsigned char)); + memset (mp->cur_string, 0, 64); +} + + +@ \MP's string expressions are implemented in a brute-force way: Every +new string or substring that is needed is simply stored into the string pool. +Space is eventually reclaimed using the aid of a simple system system +of reference counts. +@^reference counts@> + +The number of references to string number |s| will be |s->refs|. The +special value |s->refs=MAX_STR_REF=127| is used to denote an unknown +positive number of references; such strings will never be recycled. If +a string is ever referred to more than 126 times, simultaneously, we +put it in this category. + +@<Definitions@>= +#define MAX_STR_REF 127 /* ``infinite'' number of references */ +#define add_str_ref(A) { if ( (A)->refs < MAX_STR_REF ) ((A)->refs)++; } + +@ Here's what we do when a string reference disappears: + +@<Definitions@>= +#define delete_str_ref(A) do { \ + if ( (A)->refs < MAX_STR_REF ) { \ + if ( (A)->refs > 1 ) ((A)->refs)--; \ + else mp_flush_string(mp, (A)); \ + } \ + } while (0) + +@ @<Definitions@>= +void mp_flush_string (MP mp, mp_string s); + +@ @c +void mp_flush_string (MP mp, mp_string s) { + if (s->refs == 0) { + mp->strs_in_use--; + mp->pool_in_use = mp->pool_in_use - (integer) s->len; + (void) avl_del (s, mp->strings, NULL); + } +} + + +@ Some C literals that are used as values cannot be simply added, +their reference count has to be set such that they can not be flushed. + +@c +mp_string mp_intern (MP mp, const char *s) { + mp_string r; + r = mp_rts (mp, s); + r->refs = MAX_STR_REF; + return r; +} + +@ @<Definitions@>= +mp_string mp_intern (MP mp, const char *s); + + +@ Once a sequence of characters has been appended to |cur_string|, it +officially becomes a string when the function |make_string| is called. +This function returns a pointer to the new string as its value. + +@<Definitions@>= +mp_string mp_make_string (MP mp); + +@ @c +mp_string mp_make_string (MP mp) { /* current string enters the pool */ + mp_string str; + mp_lstring tmp; + tmp.str = mp->cur_string; + tmp.len = mp->cur_length; + str = (mp_string) avl_find (&tmp, mp->strings); + if (str == NULL) { /* not yet known */ + str = mp_xmalloc (mp, 1, sizeof (mp_lstring)); + str->str = mp->cur_string; + str->len = tmp.len; + assert (avl_ins (str, mp->strings, avl_false) > 0); + str = (mp_string) avl_find (&tmp, mp->strings); + mp->pool_in_use = mp->pool_in_use + (integer) str->len; + if (mp->pool_in_use > mp->max_pl_used) + mp->max_pl_used = mp->pool_in_use; + mp->strs_in_use++; + if (mp->strs_in_use > mp->max_strs_used) + mp->max_strs_used = mp->strs_in_use; + } + add_str_ref(str); + mp_reset_cur_string (mp); + return str; +} + + +@ Here is a routine that compares two strings in the string pool, +and it does not assume that they have the same length. If the first string +is lexicographically greater than, less than, or equal to the second, +the result is respectively positive, negative, or zero. + +@<Definitions@>= +integer mp_str_vs_str (MP mp, mp_string s, mp_string t); + +@ @c +integer mp_str_vs_str (MP mp, mp_string s, mp_string t) { + (void) mp; + return comp_strings_entry (NULL, (const void *) s, (const void *) t); +} + + + +@ @<Definitions@>= +mp_string mp_cat (MP mp, mp_string a, mp_string b); + +@ @c +mp_string mp_cat (MP mp, mp_string a, mp_string b) { + mp_string str; + size_t needed; + size_t saved_cur_length = mp->cur_length; + unsigned char *saved_cur_string = mp->cur_string; + size_t saved_cur_string_size = mp->cur_string_size; + needed = a->len + b->len; + mp->cur_length = 0; + /* mp->cur_string = NULL; */ /* needs malloc, spotted by clang */ + mp->cur_string = (unsigned char *) mp_xmalloc (mp, needed+1, sizeof (unsigned char)); + mp->cur_string_size = 0; + str_room (needed+1); + (void) memcpy (mp->cur_string, a->str, a->len); + (void) memcpy (mp->cur_string + a->len, b->str, b->len); + mp->cur_length = needed; + mp->cur_string[needed] = '\0'; + str = mp_make_string (mp); + mp_xfree(mp->cur_string); /* created by |mp_make_string| */ + mp->cur_length = saved_cur_length; + mp->cur_string = saved_cur_string; + mp->cur_string_size = saved_cur_string_size; + return str; +} + + +@ @<Definitions@>= +mp_string mp_chop_string (MP mp, mp_string s, integer a, integer b); + +@ @c +mp_string mp_chop_string (MP mp, mp_string s, integer a, integer b) { + integer l; /* length of the original string */ + integer k; /* runs from |a| to |b| */ + boolean reversed; /* was |a>b|? */ + if (a <= b) + reversed = false; + else { + reversed = true; + k = a; + a = b; + b = k; + } + l = (integer) s->len; + if (a < 0) { + a = 0; + if (b < 0) + b = 0; + } + if (b > l) { + b = l; + if (a > l) + a = l; + } + str_room ((size_t) (b - a)); + if (reversed) { + for (k = b - 1; k >= a; k--) { + append_char (*(s->str + k)); + } + } else { + for (k = a; k < b; k++) { + append_char (*(s->str + k)); + } + } + return mp_make_string (mp); +} + |