src/compiler/dmd/switch_.d

   1 /*
   2  *  Copyright (C) 2004-2007 by Digital Mars, www.digitalmars.com
   3  *  Written by Walter Bright
   4  *
   5  *  This software is provided 'as-is', without any express or implied
   6  *  warranty. In no event will the authors be held liable for any damages
   7  *  arising from the use of this software.
   8  *
   9  *  Permission is granted to anyone to use this software for any purpose,
  10  *  including commercial applications, and to alter it and redistribute it
  11  *  freely, in both source and binary form, subject to the following
  12  *  restrictions:
  13  *
  14  *  o  The origin of this software must not be misrepresented; you must not
  15  *     claim that you wrote the original software. If you use this software
  16  *     in a product, an acknowledgment in the product documentation would be
  17  *     appreciated but is not required.
  18  *  o  Altered source versions must be plainly marked as such, and must not
  19  *     be misrepresented as being the original software.
  20  *  o  This notice may not be removed or altered from any source
  21  *     distribution.
  22  */
  23
  24 /*
  25  *  Modified by Sean Kelly for use with the D Runtime Project
  26  */
  27
  28 module rt.switch_;
  29
  30 private import stdc.string;
  31
  32 /******************************************************
  33  * Support for switch statements switching on strings.
  34  * Input:
  35  *      table[]         sorted array of strings generated by compiler
  36  *      ca              string to look up in table
  37  * Output:
  38  *      result          index of match in table[]
  39  *                      -1 if not in table
  40  */
  41
  42 extern (C):
  43
  44 int _d_switch_string(char[][] table, char[] ca)
  45 in
  46 {
  47     //printf("in _d_switch_string()\n");
  48     assert(table.length >= 0);
  49     assert(ca.length >= 0);
  50
  51     // Make sure table[] is sorted correctly
  52     int j;
  53
  54     for (j = 1; j < table.length; j++)
  55     {
  56         int len1 = table[j - 1].length;
  57         int len2 = table[j].length;
  58
  59         assert(len1 <= len2);
  60         if (len1 == len2)
  61         {
  62             int ci;
  63
  64             ci = memcmp(table[j - 1].ptr, table[j].ptr, len1);
  65             assert(ci < 0); // ci==0 means a duplicate
  66         }
  67     }
  68 }
  69 out (result)
  70 {
  71     int i;
  72     int cj;
  73
  74     //printf("out _d_switch_string()\n");
  75     if (result == -1)
  76     {
  77         // Not found
  78         for (i = 0; i < table.length; i++)
  79         {
  80             if (table[i].length == ca.length)
  81             {   cj = memcmp(table[i].ptr, ca.ptr, ca.length);
  82                 assert(cj != 0);
  83             }
  84         }
  85     }
  86     else
  87     {
  88         assert(0 <= result && result < table.length);
  89         for (i = 0; 1; i++)
  90         {
  91             assert(i < table.length);
  92             if (table[i].length == ca.length)
  93             {
  94                 cj = memcmp(table[i].ptr, ca.ptr, ca.length);
  95                 if (cj == 0)
  96                 {
  97                     assert(i == result);
  98                     break;
  99                 }
 100             }
 101         }
 102     }
 103 }
 104 body
 105 {
 106     //printf("body _d_switch_string(%.*s)\n", ca);
 107     int low;
 108     int high;
 109     int mid;
 110     int c;
 111     char[] pca;
 112
 113     low = 0;
 114     high = table.length;
 115
 116     version (none)
 117     {
 118         // Print table
 119         printf("ca[] = '%s'\n", cast(char *)ca);
 120         for (mid = 0; mid < high; mid++)
 121         {
 122             pca = table[mid];
 123             printf("table[%d] = %d, '%.*s'\n", mid, pca.length, pca);
 124         }
 125     }
 126     if (high &&
 127         ca.length >= table[0].length &&
 128         ca.length <= table[high - 1].length)
 129     {
 130         // Looking for 0 length string, which would only be at the beginning
 131         if (ca.length == 0)
 132             return 0;
 133
 134         char c1 = ca[0];
 135
 136         // Do binary search
 137         while (low < high)
 138         {
 139             mid = (low + high) >> 1;
 140             pca = table[mid];
 141             c = ca.length - pca.length;
 142             if (c == 0)
 143             {
 144                 c = cast(ubyte)c1 - cast(ubyte)pca[0];
 145                 if (c == 0)
 146                 {
 147                     c = memcmp(ca.ptr, pca.ptr, ca.length);
 148                     if (c == 0)
 149                     {   //printf("found %d\n", mid);
 150                         return mid;
 151                     }
 152                 }
 153             }
 154             if (c < 0)
 155             {
 156                 high = mid;
 157             }
 158             else
 159             {
 160                 low = mid + 1;
 161             }
 162         }
 163     }
 164
 165     //printf("not found\n");
 166     return -1; // not found
 167 }
 168
 169 unittest
 170 {
 171     switch (cast(char []) "c")
 172     {
 173          case "coo":
 174          default:
 175              break;
 176     }
 177 }
 178
 179 /**********************************
 180  * Same thing, but for wide chars.
 181  */
 182
 183 int _d_switch_ustring(wchar[][] table, wchar[] ca)
 184 in
 185 {
 186     //printf("in _d_switch_ustring()\n");
 187     assert(table.length >= 0);
 188     assert(ca.length >= 0);
 189
 190     // Make sure table[] is sorted correctly
 191     int j;
 192
 193     for (j = 1; j < table.length; j++)
 194     {
 195         int len1 = table[j - 1].length;
 196         int len2 = table[j].length;
 197
 198         assert(len1 <= len2);
 199         if (len1 == len2)
 200         {
 201             int c;
 202
 203             c = memcmp(table[j - 1].ptr, table[j].ptr, len1 * wchar.sizeof);
 204             assert(c < 0);  // c==0 means a duplicate
 205         }
 206     }
 207 }
 208 out (result)
 209 {
 210     int i;
 211     int c;
 212
 213     //printf("out _d_switch_string()\n");
 214     if (result == -1)
 215     {
 216         // Not found
 217         for (i = 0; i < table.length; i++)
 218         {
 219             if (table[i].length == ca.length)
 220             {   c = memcmp(table[i].ptr, ca.ptr, ca.length * wchar.sizeof);
 221                 assert(c != 0);
 222             }
 223         }
 224     }
 225     else
 226     {
 227         assert(0 <= result && result < table.length);
 228         for (i = 0; 1; i++)
 229         {
 230             assert(i < table.length);
 231             if (table[i].length == ca.length)
 232             {
 233                 c = memcmp(table[i].ptr, ca.ptr, ca.length * wchar.sizeof);
 234                 if (c == 0)
 235                 {
 236                     assert(i == result);
 237                     break;
 238                 }
 239             }
 240         }
 241     }
 242 }
 243 body
 244 {
 245     //printf("body _d_switch_ustring()\n");
 246     int low;
 247     int high;
 248     int mid;
 249     int c;
 250     wchar[] pca;
 251
 252     low = 0;
 253     high = table.length;
 254
 255 /*
 256     // Print table
 257     wprintf("ca[] = '%.*s'\n", ca);
 258     for (mid = 0; mid < high; mid++)
 259     {
 260         pca = table[mid];
 261         wprintf("table[%d] = %d, '%.*s'\n", mid, pca.length, pca);
 262     }
 263 */
 264
 265     // Do binary search
 266     while (low < high)
 267     {
 268         mid = (low + high) >> 1;
 269         pca = table[mid];
 270         c = ca.length - pca.length;
 271         if (c == 0)
 272         {
 273             c = memcmp(ca.ptr, pca.ptr, ca.length * wchar.sizeof);
 274             if (c == 0)
 275             {   //printf("found %d\n", mid);
 276                 return mid;
 277             }
 278         }
 279         if (c < 0)
 280         {
 281             high = mid;
 282         }
 283         else
 284         {
 285             low = mid + 1;
 286         }
 287     }
 288     //printf("not found\n");
 289     return -1;              // not found
 290 }
 291
 292
 293 unittest
 294 {
 295     switch (cast(wchar []) "c")
 296     {
 297          case "coo":
 298          default:
 299              break;
 300     }
 301 }
 302
 303
 304 /**********************************
 305  * Same thing, but for wide chars.
 306  */
 307
 308 int _d_switch_dstring(dchar[][] table, dchar[] ca)
 309 in
 310 {
 311     //printf("in _d_switch_dstring()\n");
 312     assert(table.length >= 0);
 313     assert(ca.length >= 0);
 314
 315     // Make sure table[] is sorted correctly
 316     int j;
 317
 318     for (j = 1; j < table.length; j++)
 319     {
 320         int len1 = table[j - 1].length;
 321         int len2 = table[j].length;
 322
 323         assert(len1 <= len2);
 324         if (len1 == len2)
 325         {
 326             int c;
 327
 328             c = memcmp(table[j - 1].ptr, table[j].ptr, len1 * dchar.sizeof);
 329             assert(c < 0);  // c==0 means a duplicate
 330         }
 331     }
 332 }
 333 out (result)
 334 {
 335     int i;
 336     int c;
 337
 338     //printf("out _d_switch_string()\n");
 339     if (result == -1)
 340     {
 341         // Not found
 342         for (i = 0; i < table.length; i++)
 343         {
 344             if (table[i].length == ca.length)
 345             {   c = memcmp(table[i].ptr, ca.ptr, ca.length * dchar.sizeof);
 346                 assert(c != 0);
 347             }
 348         }
 349     }
 350     else
 351     {
 352         assert(0 <= result && result < table.length);
 353         for (i = 0; 1; i++)
 354         {
 355             assert(i < table.length);
 356             if (table[i].length == ca.length)
 357             {
 358                 c = memcmp(table[i].ptr, ca.ptr, ca.length * dchar.sizeof);
 359                 if (c == 0)
 360                 {
 361                     assert(i == result);
 362                     break;
 363                 }
 364             }
 365         }
 366     }
 367 }
 368 body
 369 {
 370     //printf("body _d_switch_ustring()\n");
 371     int low;
 372     int high;
 373     int mid;
 374     int c;
 375     dchar[] pca;
 376
 377     low = 0;
 378     high = table.length;
 379
 380 /*
 381     // Print table
 382     wprintf("ca[] = '%.*s'\n", ca);
 383     for (mid = 0; mid < high; mid++)
 384     {
 385         pca = table[mid];
 386         wprintf("table[%d] = %d, '%.*s'\n", mid, pca.length, pca);
 387     }
 388 */
 389
 390     // Do binary search
 391     while (low < high)
 392     {
 393         mid = (low + high) >> 1;
 394         pca = table[mid];
 395         c = ca.length - pca.length;
 396         if (c == 0)
 397         {
 398             c = memcmp(ca.ptr, pca.ptr, ca.length * dchar.sizeof);
 399             if (c == 0)
 400             {   //printf("found %d\n", mid);
 401                 return mid;
 402             }
 403         }
 404         if (c < 0)
 405         {
 406             high = mid;
 407         }
 408         else
 409         {
 410             low = mid + 1;
 411         }
 412     }
 413     //printf("not found\n");
 414     return -1; // not found
 415 }
 416
 417
 418 unittest
 419 {
 420     switch (cast(dchar []) "c")
 421     {
 422          case "coo":
 423          default:
 424              break;
 425     }
 426 }