1 /** 2 * Implementation of dynamic array property support routines. 3 * 4 * Copyright: Copyright Digital Mars 2000 - 2015. 5 * License: Distributed under the 6 * $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0). 7 * (See accompanying file LICENSE) 8 * Authors: Walter Bright 9 * Source: $(DRUNTIMESRC src/rt/_adi.d) 10 */ 11 12 module rt.adi; 13 14 //debug=adi; // uncomment to turn on debugging printf's 15 16 private 17 { 18 debug(adi) import core.stdc.stdio; 19 import core.stdc.string; 20 import core.stdc.stdlib; 21 import core.memory; 22 import rt.util.utf; 23 24 extern (C) void[] _adSort(void[] a, TypeInfo ti); 25 } 26 27 private dchar[] mallocUTF32(C)(in C[] s) 28 { 29 size_t j = 0; 30 auto p = cast(dchar*)malloc(dchar.sizeof * s.length); 31 auto r = p[0..s.length]; // r[] will never be longer than s[] 32 foreach (dchar c; s) 33 r[j++] = c; 34 return r[0 .. j]; 35 } 36 37 /********************************************** 38 * Sort array of chars. 39 */ 40 41 extern (C) char[] _adSortChar(char[] a) 42 { 43 if (a.length > 1) 44 { 45 auto da = mallocUTF32(a); 46 _adSort(*cast(void[]*)&da, typeid(da[0])); 47 size_t i = 0; 48 foreach (dchar d; da) 49 { char[4] buf; 50 auto t = toUTF8(buf, d); 51 a[i .. i + t.length] = t[]; 52 i += t.length; 53 } 54 free(da.ptr); 55 } 56 return a; 57 } 58 59 /********************************************** 60 * Sort array of wchars. 61 */ 62 63 extern (C) wchar[] _adSortWchar(wchar[] a) 64 { 65 if (a.length > 1) 66 { 67 auto da = mallocUTF32(a); 68 _adSort(*cast(void[]*)&da, typeid(da[0])); 69 size_t i = 0; 70 foreach (dchar d; da) 71 { wchar[2] buf; 72 auto t = toUTF16(buf, d); 73 a[i .. i + t.length] = t[]; 74 i += t.length; 75 } 76 free(da.ptr); 77 } 78 return a; 79 } 80 81 /*************************************** 82 * Support for array equality test. 83 * Returns: 84 * 1 equal 85 * 0 not equal 86 */ 87 88 extern (C) int _adEq(void[] a1, void[] a2, TypeInfo ti) 89 { 90 debug(adi) printf("_adEq(a1.length = %d, a2.length = %d)\n", a1.length, a2.length); 91 if (a1.length != a2.length) 92 return 0; // not equal 93 auto sz = ti.tsize; 94 auto p1 = a1.ptr; 95 auto p2 = a2.ptr; 96 97 if (sz == 1) 98 // We should really have a ti.isPOD() check for this 99 return (memcmp(p1, p2, a1.length) == 0); 100 101 for (size_t i = 0; i < a1.length; i++) 102 { 103 if (!ti.equals(p1 + i * sz, p2 + i * sz)) 104 return 0; // not equal 105 } 106 return 1; // equal 107 } 108 109 extern (C) int _adEq2(void[] a1, void[] a2, TypeInfo ti) 110 { 111 debug(adi) printf("_adEq2(a1.length = %d, a2.length = %d)\n", a1.length, a2.length); 112 if (a1.length != a2.length) 113 return 0; // not equal 114 if (!ti.equals(&a1, &a2)) 115 return 0; 116 return 1; 117 } 118 unittest 119 { 120 debug(adi) printf("array.Eq unittest\n"); 121 122 auto a = "hello"c; 123 124 assert(a != "hel"); 125 assert(a != "helloo"); 126 assert(a != "betty"); 127 assert(a == "hello"); 128 assert(a != "hxxxx"); 129 130 float[] fa = [float.nan]; 131 assert(fa != fa); 132 } 133 134 /*************************************** 135 * Support for array compare test. 136 */ 137 138 extern (C) int _adCmp(void[] a1, void[] a2, TypeInfo ti) 139 { 140 debug(adi) printf("adCmp()\n"); 141 auto len = a1.length; 142 if (a2.length < len) 143 len = a2.length; 144 auto sz = ti.tsize; 145 void *p1 = a1.ptr; 146 void *p2 = a2.ptr; 147 148 if (sz == 1) 149 { // We should really have a ti.isPOD() check for this 150 auto c = memcmp(p1, p2, len); 151 if (c) 152 return c; 153 } 154 else 155 { 156 for (size_t i = 0; i < len; i++) 157 { 158 auto c = ti.compare(p1 + i * sz, p2 + i * sz); 159 if (c) 160 return c; 161 } 162 } 163 if (a1.length == a2.length) 164 return 0; 165 return (a1.length > a2.length) ? 1 : -1; 166 } 167 168 extern (C) int _adCmp2(void[] a1, void[] a2, TypeInfo ti) 169 { 170 debug(adi) printf("_adCmp2(a1.length = %d, a2.length = %d)\n", a1.length, a2.length); 171 return ti.compare(&a1, &a2); 172 } 173 unittest 174 { 175 debug(adi) printf("array.Cmp unittest\n"); 176 177 auto a = "hello"c; 178 179 assert(a > "hel"); 180 assert(a >= "hel"); 181 assert(a < "helloo"); 182 assert(a <= "helloo"); 183 assert(a > "betty"); 184 assert(a >= "betty"); 185 assert(a == "hello"); 186 assert(a <= "hello"); 187 assert(a >= "hello"); 188 assert(a < "я"); 189 } 190 191 /*************************************** 192 * Support for array compare test. 193 */ 194 195 extern (C) int _adCmpChar(void[] a1, void[] a2) 196 { 197 version (D_InlineAsm_X86) 198 { 199 asm 200 { naked ; 201 202 push EDI ; 203 push ESI ; 204 205 mov ESI,a1+4[4+ESP] ; 206 mov EDI,a2+4[4+ESP] ; 207 208 mov ECX,a1[4+ESP] ; 209 mov EDX,a2[4+ESP] ; 210 211 cmp ECX,EDX ; 212 jb GotLength ; 213 214 mov ECX,EDX ; 215 216 GotLength: 217 cmp ECX,4 ; 218 jb DoBytes ; 219 220 // Do alignment if neither is dword aligned 221 test ESI,3 ; 222 jz Aligned ; 223 224 test EDI,3 ; 225 jz Aligned ; 226 DoAlign: 227 mov AL,[ESI] ; //align ESI to dword bounds 228 mov DL,[EDI] ; 229 230 cmp AL,DL ; 231 jnz Unequal ; 232 233 inc ESI ; 234 inc EDI ; 235 236 test ESI,3 ; 237 238 lea ECX,[ECX-1] ; 239 jnz DoAlign ; 240 Aligned: 241 mov EAX,ECX ; 242 243 // do multiple of 4 bytes at a time 244 245 shr ECX,2 ; 246 jz TryOdd ; 247 248 repe ; 249 cmpsd ; 250 251 jnz UnequalQuad ; 252 253 TryOdd: 254 mov ECX,EAX ; 255 DoBytes: 256 // if still equal and not end of string, do up to 3 bytes slightly 257 // slower. 258 259 and ECX,3 ; 260 jz Equal ; 261 262 repe ; 263 cmpsb ; 264 265 jnz Unequal ; 266 Equal: 267 mov EAX,a1[4+ESP] ; 268 mov EDX,a2[4+ESP] ; 269 270 sub EAX,EDX ; 271 pop ESI ; 272 273 pop EDI ; 274 ret ; 275 276 UnequalQuad: 277 mov EDX,[EDI-4] ; 278 mov EAX,[ESI-4] ; 279 280 cmp AL,DL ; 281 jnz Unequal ; 282 283 cmp AH,DH ; 284 jnz Unequal ; 285 286 shr EAX,16 ; 287 288 shr EDX,16 ; 289 290 cmp AL,DL ; 291 jnz Unequal ; 292 293 cmp AH,DH ; 294 Unequal: 295 sbb EAX,EAX ; 296 pop ESI ; 297 298 or EAX,1 ; 299 pop EDI ; 300 301 ret ; 302 } 303 } 304 else 305 { 306 debug(adi) printf("adCmpChar()\n"); 307 auto len = a1.length; 308 if (a2.length < len) 309 len = a2.length; 310 auto c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len); 311 if (!c) 312 c = cast(int)a1.length - cast(int)a2.length; 313 return c; 314 } 315 } 316 317 unittest 318 { 319 debug(adi) printf("array.CmpChar unittest\n"); 320 321 auto a = "hello"c; 322 323 assert(a > "hel"); 324 assert(a >= "hel"); 325 assert(a < "helloo"); 326 assert(a <= "helloo"); 327 assert(a > "betty"); 328 assert(a >= "betty"); 329 assert(a == "hello"); 330 assert(a <= "hello"); 331 assert(a >= "hello"); 332 } 333