xref: /netbsd-src/external/gpl3/gcc.old/dist/libphobos/libdruntime/rt/switch_.d (revision 70f7362772ba52b749c976fb5e86e39a8b2c9afc) 
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 }
425