Quake III Arena: lcc/src/string.c Source File

00001 #include "c.h"
00002 
00003 
00004 static struct string {
00005     char *str;
00006     int len;
00007     struct string *link;
00008 } *buckets[1024];
00009 static int scatter[] = {    /* map characters to random values */
00010     2078917053, 143302914, 1027100827, 1953210302, 755253631,
00011     2002600785, 1405390230, 45248011, 1099951567, 433832350,
00012     2018585307, 438263339, 813528929, 1703199216, 618906479,
00013     573714703, 766270699, 275680090, 1510320440, 1583583926,
00014     1723401032, 1965443329, 1098183682, 1636505764, 980071615,
00015     1011597961, 643279273, 1315461275, 157584038, 1069844923,
00016     471560540, 89017443, 1213147837, 1498661368, 2042227746,
00017     1968401469, 1353778505, 1300134328, 2013649480, 306246424,
00018     1733966678, 1884751139, 744509763, 400011959, 1440466707,
00019     1363416242, 973726663, 59253759, 1639096332, 336563455,
00020     1642837685, 1215013716, 154523136, 593537720, 704035832,
00021     1134594751, 1605135681, 1347315106, 302572379, 1762719719,
00022     269676381, 774132919, 1851737163, 1482824219, 125310639,
00023     1746481261, 1303742040, 1479089144, 899131941, 1169907872,
00024     1785335569, 485614972, 907175364, 382361684, 885626931,
00025     200158423, 1745777927, 1859353594, 259412182, 1237390611,
00026     48433401, 1902249868, 304920680, 202956538, 348303940,
00027     1008956512, 1337551289, 1953439621, 208787970, 1640123668,
00028     1568675693, 478464352, 266772940, 1272929208, 1961288571,
00029     392083579, 871926821, 1117546963, 1871172724, 1771058762,
00030     139971187, 1509024645, 109190086, 1047146551, 1891386329,
00031     994817018, 1247304975, 1489680608, 706686964, 1506717157,
00032     579587572, 755120366, 1261483377, 884508252, 958076904,
00033     1609787317, 1893464764, 148144545, 1415743291, 2102252735,
00034     1788268214, 836935336, 433233439, 2055041154, 2109864544,
00035     247038362, 299641085, 834307717, 1364585325, 23330161,
00036     457882831, 1504556512, 1532354806, 567072918, 404219416,
00037     1276257488, 1561889936, 1651524391, 618454448, 121093252,
00038     1010757900, 1198042020, 876213618, 124757630, 2082550272,
00039     1834290522, 1734544947, 1828531389, 1982435068, 1002804590,
00040     1783300476, 1623219634, 1839739926, 69050267, 1530777140,
00041     1802120822, 316088629, 1830418225, 488944891, 1680673954,
00042     1853748387, 946827723, 1037746818, 1238619545, 1513900641,
00043     1441966234, 367393385, 928306929, 946006977, 985847834,
00044     1049400181, 1956764878, 36406206, 1925613800, 2081522508,
00045     2118956479, 1612420674, 1668583807, 1800004220, 1447372094,
00046     523904750, 1435821048, 923108080, 216161028, 1504871315,
00047     306401572, 2018281851, 1820959944, 2136819798, 359743094,
00048     1354150250, 1843084537, 1306570817, 244413420, 934220434,
00049     672987810, 1686379655, 1301613820, 1601294739, 484902984,
00050     139978006, 503211273, 294184214, 176384212, 281341425,
00051     228223074, 147857043, 1893762099, 1896806882, 1947861263,
00052     1193650546, 273227984, 1236198663, 2116758626, 489389012,
00053     593586330, 275676551, 360187215, 267062626, 265012701,
00054     719930310, 1621212876, 2108097238, 2026501127, 1865626297,
00055     894834024, 552005290, 1404522304, 48964196, 5816381,
00056     1889425288, 188942202, 509027654, 36125855, 365326415,
00057     790369079, 264348929, 513183458, 536647531, 13672163,
00058     313561074, 1730298077, 286900147, 1549759737, 1699573055,
00059     776289160, 2143346068, 1975249606, 1136476375, 262925046,
00060     92778659, 1856406685, 1884137923, 53392249, 1735424165,
00061     1602280572
00062 };
00063 char *string(const char *str) {
00064     const char *s;
00065 
00066     for (s = str; *s; s++)
00067         ;
00068     return stringn(str, s - str);
00069 }
00070 char *stringd(long n) {
00071     char str[25], *s = str + sizeof (str);
00072     unsigned long m;
00073 
00074     if (n == LONG_MIN)
00075         m = (unsigned long)LONG_MAX + 1;
00076     else if (n < 0)
00077         m = -n;
00078     else
00079         m = n;
00080     do
00081         *--s = m%10 + '0';
00082     while ((m /= 10) != 0);
00083     if (n < 0)
00084         *--s = '-';
00085     return stringn(s, str + sizeof (str) - s);
00086 }
00087 char *stringn(const char *str, int len) {
00088     int i;
00089     unsigned int h;
00090     const char *end;
00091     struct string *p;
00092 
00093     assert(str);
00094     for (h = 0, i = len, end = str; i > 0; i--)
00095         h = (h<<1) + scatter[*(unsigned char *)end++];
00096     h &= NELEMS(buckets)-1;
00097     for (p = buckets[h]; p; p = p->link)
00098         if (len == p->len) {
00099             const char *s1 = str;
00100             char *s2 = p->str;
00101             do {
00102                 if (s1 == end)
00103                     return p->str;
00104             } while (*s1++ == *s2++);
00105         }
00106     {
00107         static char *next, *strlimit;
00108         if (len + 1 >= strlimit - next) {
00109             int n = len + 4*1024;
00110             next = allocate(n, PERM);
00111             strlimit = next + n;
00112         }
00113         NEW(p, PERM);
00114         p->len = len;
00115         for (p->str = next; str < end; )
00116             *next++ = *str++;
00117         *next++ = 0;
00118         p->link = buckets[h];
00119         buckets[h] = p;
00120         return p->str;
00121     }
00122 }