libphobos/libdruntime/rt/switch_.d

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