home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 7 / FreshFishVol7.bin / bbs / gnu / libg++-2.6-fsf.lha / libg++-2.6 / libg++ / src / String.cc < prev    next >
C/C++ Source or Header  |  1994-07-18  |  28KB  |  1,314 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   String class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <String.h>
  26. #include <std.h>
  27. #include <ctype.h>
  28. #include <limits.h>
  29. #include <new.h>
  30. #include <builtin.h>
  31.  
  32. // extern "C" {
  33. #include <regex.h>
  34. // }
  35.  
  36. void String::error(const char* msg) const
  37. {
  38.   (*lib_error_handler)("String", msg);
  39. }
  40.  
  41. String::operator const char*() const
  42. { 
  43.   return (const char*)chars();
  44. }
  45.  
  46. //  globals
  47.  
  48. StrRep  _nilStrRep = { 0, 1, { 0 } }; // nil strings point here
  49. String _nilString;               // nil SubStrings point here
  50.  
  51.  
  52.  
  53.  
  54. /*
  55.  the following inline fcts are specially designed to work
  56.  in support of String classes, and are not meant as generic replacements
  57.  for libc "str" functions.
  58.  
  59.  inline copy fcts -  I like left-to-right from->to arguments.
  60.  all versions assume that `to' argument is non-null
  61.  
  62.  These are worth doing inline, rather than through calls because,
  63.  via procedural integration, adjacent copy calls can be smushed
  64.  together by the optimizer.
  65. */
  66.  
  67. // copy n bytes
  68. inline static void ncopy(const char* from, char* to, int n)
  69. {
  70.   if (from != to) while (--n >= 0) *to++ = *from++;
  71. }
  72.  
  73. // copy n bytes, null-terminate
  74. inline static void ncopy0(const char* from, char* to, int n)
  75. {
  76.   if (from != to) 
  77.   {
  78.     while (--n >= 0) *to++ = *from++;
  79.     *to = 0;
  80.   }
  81.   else
  82.     to[n] = 0;
  83. }
  84.  
  85. // copy until null
  86. inline static void scopy(const char* from, char* to)
  87. {
  88.   if (from != 0) while((*to++ = *from++) != 0);
  89. }
  90.  
  91. // copy right-to-left
  92. inline static void revcopy(const char* from, char* to, short n)
  93. {
  94.   if (from != 0) while (--n >= 0) *to-- = *from--;
  95. }
  96.  
  97.  
  98. inline static int slen(const char* t) // inline  strlen
  99. {
  100.   if (t == 0)
  101.     return 0;
  102.   else
  103.   {
  104.     const char* a = t;
  105.     while (*a++ != 0);
  106.     return a - 1 - t;
  107.   }
  108. }
  109.  
  110. // minimum & maximum representable rep size
  111.  
  112. #define MAXStrRep_SIZE   ((1 << (sizeof(short) * CHAR_BIT - 1)) - 1)
  113. #define MINStrRep_SIZE   16
  114.  
  115. #ifndef MALLOC_MIN_OVERHEAD
  116. #define MALLOC_MIN_OVERHEAD  4
  117. #endif
  118.  
  119. // The basic allocation primitive:
  120. // Always round request to something close to a power of two.
  121. // This ensures a bit of padding, which often means that
  122. // concatenations don't have to realloc. Plus it tends to
  123. // be faster when lots of Strings are created and discarded,
  124. // since just about any version of malloc (op new()) will
  125. // be faster when it can reuse identically-sized chunks
  126.  
  127. inline static StrRep* Snew(int newsiz)
  128. {
  129.   unsigned int siz = sizeof(StrRep) + newsiz + MALLOC_MIN_OVERHEAD;
  130.   unsigned int allocsiz = MINStrRep_SIZE;
  131.   while (allocsiz < siz) allocsiz <<= 1;
  132.   allocsiz -= MALLOC_MIN_OVERHEAD;
  133.   if (allocsiz >= MAXStrRep_SIZE)
  134.     (*lib_error_handler)("String", "Requested length out of range");
  135.     
  136.   StrRep* rep = (StrRep *) new char[allocsiz];
  137.   rep->sz = allocsiz - sizeof(StrRep);
  138.   return rep;
  139. }
  140.  
  141. // Do-something-while-allocating routines.
  142.  
  143. // We live with two ways to signify empty Sreps: either the
  144. // null pointer (0) or a pointer to the nilStrRep.
  145.  
  146. // We always signify unknown source lengths (usually when fed a char*)
  147. // via len == -1, in which case it is computed.
  148.  
  149. // allocate, copying src if nonull
  150.  
  151. StrRep* Salloc(StrRep* old, const char* src, int srclen, int newlen)
  152. {
  153.   if (old == &_nilStrRep) old = 0;
  154.   if (srclen < 0) srclen = slen(src);
  155.   if (newlen < srclen) newlen = srclen;
  156.   StrRep* rep;
  157.   if (old == 0 || newlen > old->sz)
  158.     rep = Snew(newlen);
  159.   else
  160.     rep = old;
  161.  
  162.   rep->len = newlen;
  163.   ncopy0(src, rep->s, srclen);
  164.  
  165.   if (old != rep && old != 0) delete old;
  166.  
  167.   return rep;
  168. }
  169.  
  170. // reallocate: Given the initial allocation scheme, it will
  171. // generally be faster in the long run to get new space & copy
  172. // than to call realloc
  173.  
  174. StrRep* Sresize(StrRep* old, int newlen)
  175. {
  176.   if (old == &_nilStrRep) old = 0;
  177.   StrRep* rep;
  178.   if (old == 0)
  179.     rep = Snew(newlen);
  180.   else if (newlen > old->sz)
  181.   {
  182.     rep = Snew(newlen);
  183.     ncopy0(old->s, rep->s, old->len);
  184.     delete old;
  185.   }
  186.   else
  187.     rep = old;
  188.  
  189.   rep->len = newlen;
  190.  
  191.   return rep;
  192. }
  193.  
  194. // like allocate, but we know that src is a StrRep
  195.  
  196. StrRep* Scopy(StrRep* old, const StrRep* s)
  197. {
  198.   if (old == &_nilStrRep) old = 0;
  199.   if (s == &_nilStrRep) s = 0;
  200.   if (old == s) 
  201.     return (old == 0)? &_nilStrRep : old;
  202.   else if (s == 0)
  203.   {
  204.     old->s[0] = 0;
  205.     old->len = 0;
  206.     return old;
  207.   }
  208.   else 
  209.   {
  210.     StrRep* rep;
  211.     int newlen = s->len;
  212.     if (old == 0 || newlen > old->sz)
  213.     {
  214.       if (old != 0) delete old;
  215.       rep = Snew(newlen);
  216.     }
  217.     else
  218.       rep = old;
  219.     rep->len = newlen;
  220.     ncopy0(s->s, rep->s, newlen);
  221.     return rep;
  222.   }
  223. }
  224.  
  225. // allocate & concatenate
  226.  
  227. StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen)
  228. {
  229.   if (old == &_nilStrRep) old = 0;
  230.   if (srclen < 0) srclen = slen(s);
  231.   if (tlen < 0) tlen = slen(t);
  232.   int newlen = srclen + tlen;
  233.   StrRep* rep;
  234.  
  235.   if (old == 0 || newlen > old->sz || 
  236.       (t >= old->s && t < &(old->s[old->len]))) // beware of aliasing
  237.     rep = Snew(newlen);
  238.   else
  239.     rep = old;
  240.  
  241.   rep->len = newlen;
  242.  
  243.   ncopy(s, rep->s, srclen);
  244.   ncopy0(t, &(rep->s[srclen]), tlen);
  245.  
  246.   if (old != rep && old != 0) delete old;
  247.  
  248.   return rep;
  249. }
  250.  
  251. // double-concatenate
  252.  
  253. StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen,
  254.              const char* u, int ulen)
  255. {
  256.   if (old == &_nilStrRep) old = 0;
  257.   if (srclen < 0) srclen = slen(s);
  258.   if (tlen < 0) tlen = slen(t);
  259.   if (ulen < 0) ulen = slen(u);
  260.   int newlen = srclen + tlen + ulen;
  261.   StrRep* rep;
  262.   if (old == 0 || newlen > old->sz || 
  263.       (t >= old->s && t < &(old->s[old->len])) ||
  264.       (u >= old->s && u < &(old->s[old->len])))
  265.     rep = Snew(newlen);
  266.   else
  267.     rep = old;
  268.  
  269.   rep->len = newlen;
  270.  
  271.   ncopy(s, rep->s, srclen);
  272.   ncopy(t, &(rep->s[srclen]), tlen);
  273.   ncopy0(u, &(rep->s[srclen+tlen]), ulen);
  274.  
  275.   if (old != rep && old != 0) delete old;
  276.  
  277.   return rep;
  278. }
  279.  
  280. // like cat, but we know that new stuff goes in the front of existing rep
  281.  
  282. StrRep* Sprepend(StrRep* old, const char* t, int tlen)
  283. {
  284.   char* s;
  285.   int srclen;
  286.   if (old == &_nilStrRep || old == 0)
  287.   {
  288.     s = 0; old = 0; srclen = 0;
  289.   }
  290.   else
  291.   {
  292.     s = old->s; srclen = old->len;
  293.   }
  294.   if (tlen < 0) tlen = slen(t);
  295.   int newlen = srclen + tlen;
  296.   StrRep* rep;
  297.   if (old == 0 || newlen > old->sz || 
  298.       (t >= old->s && t < &(old->s[old->len])))
  299.     rep = Snew(newlen);
  300.   else
  301.     rep = old;
  302.  
  303.   rep->len = newlen;
  304.  
  305.   revcopy(&(s[srclen]), &(rep->s[newlen]), srclen+1);
  306.   ncopy(t, rep->s, tlen);
  307.  
  308.   if (old != rep && old != 0) delete old;
  309.  
  310.   return rep;
  311. }
  312.  
  313.  
  314. // string compare: first argument is known to be non-null
  315.  
  316. inline static int scmp(const char* a, const char* b)
  317. {
  318.   if (b == 0)
  319.     return *a != 0;
  320.   else
  321.   {
  322.     signed char diff = 0;
  323.     while ((diff = *a - *b++) == 0 && *a++ != 0);
  324.     return diff;
  325.   }
  326. }
  327.  
  328.  
  329. inline static int ncmp(const char* a, int al, const char* b, int bl)
  330. {
  331.   int n = (al <= bl)? al : bl;
  332.   signed char diff;
  333.   while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  334.   return al - bl;
  335. }
  336.  
  337. int fcompare(const String& x, const String& y)
  338. {
  339.   const char* a = x.chars();
  340.   const char* b = y.chars();
  341.   int al = x.length();
  342.   int bl = y.length();
  343.   int n = (al <= bl)? al : bl;
  344.   signed char diff = 0;
  345.   while (n-- > 0)
  346.   {
  347.     char ac = *a++;
  348.     char bc = *b++;
  349.     if ((diff = ac - bc) != 0)
  350.     {
  351.       if (ac >= 'a' && ac <= 'z')
  352.         ac = ac - 'a' + 'A';
  353.       if (bc >= 'a' && bc <= 'z')
  354.         bc = bc - 'a' + 'A';
  355.       if ((diff = ac - bc