Mercurial > projects > ldc
annotate tango/lib/compiler/llvmdc/aaA.d @ 339:385a18242485 trunk
[svn r360] Another mostly rewrite of DtoArrayInit. Should be much more robust now, and probably faster code generated for the most common cases too!
Fixed issues with slice initialization (!!!) of multidimensional static arrays.
Attempt to fix issue with referencing nested 'this' pointers introduced in DMD 1.033 merge.
| author | lindquist |
|---|---|
| date | Sun, 13 Jul 2008 01:29:49 +0200 |
| parents | a8cd9bc1021a |
| children |
| rev | line source |
|---|---|
| 132 | 1 //_ aaA.d |
| 2 | |
| 3 /** | |
| 4 * Part of the D programming language runtime library. | |
| 5 * Implementation of associative arrays. | |
| 6 */ | |
| 7 | |
| 8 /* | |
| 9 * Copyright (C) 2000-2007 by Digital Mars, www.digitalmars.com | |
| 10 * Written by Walter Bright | |
| 11 * | |
| 12 * This software is provided 'as-is', without any express or implied | |
| 13 * warranty. In no event will the authors be held liable for any damages | |
| 14 * arising from the use of this software. | |
| 15 * | |
| 16 * Permission is granted to anyone to use this software for any purpose, | |
| 17 * including commercial applications, and to alter it and redistribute it | |
| 18 * freely, subject to the following restrictions: | |
| 19 * | |
| 20 * o The origin of this software must not be misrepresented; you must not | |
| 21 * claim that you wrote the original software. If you use this software | |
| 22 * in a product, an acknowledgment in the product documentation would be | |
| 23 * appreciated but is not required. | |
| 24 * o Altered source versions must be plainly marked as such, and must not | |
| 25 * be misrepresented as being the original software. | |
| 26 * o This notice may not be removed or altered from any source | |
| 27 * distribution. | |
| 28 */ | |
| 29 | |
| 30 /* | |
| 31 * Modified by Sean Kelly <sean@f4.ca> for use with Tango. | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
32 * Modified by Tomas Lindquist Olsen <tomas@famolsen.dk> for use with LLVMDC. |
| 132 | 33 */ |
| 34 | |
| 35 private | |
| 36 { | |
| 37 import tango.stdc.stdarg; | |
| 38 import tango.stdc.string; | |
| 39 | |
| 40 enum BlkAttr : uint | |
| 41 { | |
| 42 FINALIZE = 0b0000_0001, | |
| 43 NO_SCAN = 0b0000_0010, | |
| 44 NO_MOVE = 0b0000_0100, | |
| 45 ALL_BITS = 0b1111_1111 | |
| 46 } | |
| 47 | |
| 48 extern (C) void* gc_malloc( size_t sz, uint ba = 0 ); | |
| 49 extern (C) void* gc_calloc( size_t sz, uint ba = 0 ); | |
| 50 extern (C) void gc_free( void* p ); | |
| 51 } | |
| 52 | |
| 53 // Auto-rehash and pre-allocate - Dave Fladebo | |
| 54 | |
| 55 static size_t[] prime_list = [ | |
| 56 97UL, 389UL, | |
| 57 1543UL, 6151UL, | |
| 58 24593UL, 98317UL, | |
| 59 393241UL, 1572869UL, | |
| 60 6291469UL, 25165843UL, | |
| 61 100663319UL, 402653189UL, | |
| 62 1610612741UL, 4294967291UL | |
| 63 ]; | |
| 64 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
65 // This is the type of the return value for dynamic arrays. |
| 132 | 66 struct Array |
| 67 { | |
| 68 size_t length; | |
| 69 void* ptr; | |
| 70 } | |
| 71 | |
| 72 struct aaA | |
| 73 { | |
| 74 aaA *left; | |
| 75 aaA *right; | |
| 76 hash_t hash; | |
| 77 /* key */ | |
| 78 /* value */ | |
| 79 } | |
| 80 | |
| 81 struct BB | |
| 82 { | |
| 83 aaA*[] b; | |
| 84 size_t nodes; // total number of aaA nodes | |
| 85 } | |
| 86 | |
| 87 /* This is the type actually seen by the programmer, although | |
| 88 * it is completely opaque. | |
| 89 */ | |
| 90 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
91 // LLVMDC doesn't pass structs in registers so no need to wrap it ... |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
92 alias BB* AA; |
| 132 | 93 |
| 94 /********************************** | |
| 95 * Align to next pointer boundary, so that | |
| 96 * GC won't be faced with misaligned pointers | |
| 97 * in value. | |
| 98 */ | |
| 99 | |
| 100 size_t aligntsize(size_t tsize) | |
| 101 { | |
| 102 // Is pointer alignment on the x64 4 bytes or 8? | |
| 103 return (tsize + size_t.sizeof - 1) & ~(size_t.sizeof - 1); | |
| 104 } | |
| 105 | |
| 106 extern (C): | |
| 107 | |
| 108 /************************************************* | |
| 109 * Invariant for aa. | |
| 110 */ | |
| 111 | |
| 112 /+ | |
| 113 void _aaInvAh(aaA*[] aa) | |
| 114 { | |
| 115 for (size_t i = 0; i < aa.length; i++) | |
| 116 { | |
| 117 if (aa[i]) | |
| 118 _aaInvAh_x(aa[i]); | |
| 119 } | |
| 120 } | |
| 121 | |
| 122 private int _aaCmpAh_x(aaA *e1, aaA *e2) | |
| 123 { int c; | |
| 124 | |
| 125 c = e1.hash - e2.hash; | |
| 126 if (c == 0) | |
| 127 { | |
| 128 c = e1.key.length - e2.key.length; | |
| 129 if (c == 0) | |
| 130 c = memcmp((char *)e1.key, (char *)e2.key, e1.key.length); | |
| 131 } | |
| 132 return c; | |
| 133 } | |
| 134 | |
| 135 private void _aaInvAh_x(aaA *e) | |
| 136 { | |
| 137 hash_t key_hash; | |
| 138 aaA *e1; | |
| 139 aaA *e2; | |
| 140 | |
| 141 key_hash = getHash(e.key); | |
| 142 assert(key_hash == e.hash); | |
| 143 | |
| 144 while (1) | |
| 145 { int c; | |
| 146 | |
| 147 e1 = e.left; | |
| 148 if (e1) | |
| 149 { | |
| 150 _aaInvAh_x(e1); // ordinary recursion | |
| 151 do | |
| 152 { | |
| 153 c = _aaCmpAh_x(e1, e); | |
| 154 assert(c < 0); | |
| 155 e1 = e1.right; | |
| 156 } while (e1 != null); | |
| 157 } | |
| 158 | |
| 159 e2 = e.right; | |
| 160 if (e2) | |
| 161 { | |
| 162 do | |
| 163 { | |
| 164 c = _aaCmpAh_x(e, e2); | |
| 165 assert(c < 0); | |
| 166 e2 = e2.left; | |
| 167 } while (e2 != null); | |
| 168 e = e.right; // tail recursion | |
| 169 } | |
| 170 else | |
| 171 break; | |
| 172 } | |
| 173 } | |
| 174 +/ | |
| 175 | |
| 176 /**************************************************** | |
| 177 * Determine number of entries in associative array. | |
| 178 */ | |
| 179 | |
| 180 size_t _aaLen(AA aa) | |
| 181 in | |
| 182 { | |
| 183 //printf("_aaLen()+\n"); | |
| 184 //_aaInv(aa); | |
| 185 } | |
| 186 out (result) | |
| 187 { | |
| 188 size_t len = 0; | |
| 189 | |
| 190 void _aaLen_x(aaA* ex) | |
| 191 { | |
| 192 auto e = ex; | |
| 193 len++; | |
| 194 | |
| 195 while (1) | |
| 196 { | |
| 197 if (e.right) | |
| 198 _aaLen_x(e.right); | |
| 199 e = e.left; | |
| 200 if (!e) | |
| 201 break; | |
| 202 len++; | |
| 203 } | |
| 204 } | |
| 205 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
206 if (aa) |
| 132 | 207 { |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
208 foreach (e; aa.b) |
| 132 | 209 { |
| 210 if (e) | |
| 211 _aaLen_x(e); | |
| 212 } | |
| 213 } | |
| 214 assert(len == result); | |
| 215 | |
| 216 //printf("_aaLen()-\n"); | |
| 217 } | |
| 218 body | |
| 219 { | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
220 return aa ? aa.nodes : 0; |
| 132 | 221 } |
| 222 | |
| 223 | |
| 224 /************************************************* | |
| 225 * Get pointer to value in associative array indexed by key. | |
| 226 * Add entry for key if it is not already there. | |
| 227 */ | |
| 228 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
229 void* _aaGet(AA* aa_arg, TypeInfo keyti, size_t valuesize, void* pkey) |
| 132 | 230 in |
| 231 { | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
232 assert(aa_arg); |
| 132 | 233 } |
| 234 out (result) | |
| 235 { | |
| 236 assert(result); | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
237 assert(*aa_arg); |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
238 assert((*aa_arg).b.length); |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
239 //assert(_aaInAh(*aa, key)); |
| 132 | 240 } |
| 241 body | |
| 242 { | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
243 //auto pkey = cast(void *)(&valuesize + 1); |
| 132 | 244 size_t i; |
| 245 aaA *e; | |
| 246 auto keysize = aligntsize(keyti.tsize()); | |
| 247 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
248 if (!*aa_arg) |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
249 *aa_arg = new BB(); |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
250 auto aa = *aa_arg; |
| 132 | 251 |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
252 if (!aa.b.length) |
| 132 | 253 { |
| 254 alias aaA *pa; | |
| 255 auto len = prime_list[0]; | |
| 256 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
257 aa.b = new pa[len]; |
| 132 | 258 } |
| 259 | |
| 260 auto key_hash = keyti.getHash(pkey); | |
| 261 //printf("hash = %d\n", key_hash); | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
262 i = key_hash % aa.b.length; |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
263 auto pe = &aa.b[i]; |
| 132 | 264 while ((e = *pe) !is null) |
| 265 { | |
| 266 if (key_hash == e.hash) | |
| 267 { | |
| 268 auto c = keyti.compare(pkey, e + 1); | |
| 269 if (c == 0) | |
| 270 goto Lret; | |
| 271 pe = (c < 0) ? &e.left : &e.right; | |
| 272 } | |
| 273 else | |
| 274 pe = (key_hash < e.hash) ? &e.left : &e.right; | |
| 275 } | |
| 276 | |
| 277 // Not found, create new elem | |
| 278 //printf("create new one\n"); | |
| 279 size_t size = aaA.sizeof + keysize + valuesize; | |
| 280 uint bits = keysize < (void*).sizeof && | |
| 281 keysize > (void).sizeof && | |
| 282 valuesize < (void*).sizeof && | |
| 283 valuesize > (void).sizeof ? BlkAttr.NO_SCAN : 0; | |
| 284 e = cast(aaA *) gc_calloc(size, bits); | |
| 285 memcpy(e + 1, pkey, keysize); | |
| 286 e.hash = key_hash; | |
| 287 *pe = e; | |
| 288 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
289 auto nodes = ++aa.nodes; |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
290 //printf("length = %d, nodes = %d\n", (*aa).length, nodes); |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
291 if (nodes > aa.b.length * 4) |
| 132 | 292 { |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
293 _aaRehash(aa_arg,keyti); |
| 132 | 294 } |
| 295 | |
| 296 Lret: | |
| 297 return cast(void *)(e + 1) + keysize; | |
| 298 } | |
| 299 | |
| 300 | |
| 301 /************************************************* | |
| 302 * Get pointer to value in associative array indexed by key. | |
| 303 * Returns null if it is not already there. | |
| 304 */ | |
| 305 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
306 void* _aaGetRvalue(AA aa, TypeInfo keyti, size_t valuesize, void *pkey) |
| 132 | 307 { |
| 308 //printf("_aaGetRvalue(valuesize = %u)\n", valuesize); | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
309 if (!aa) |
| 132 | 310 return null; |
| 311 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
312 //auto pkey = cast(void *)(&valuesize + 1); |
| 132 | 313 auto keysize = aligntsize(keyti.tsize()); |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
314 auto len = aa.b.length; |
| 132 | 315 |
| 316 if (len) | |
| 317 { | |
| 318 auto key_hash = keyti.getHash(pkey); | |
| 319 //printf("hash = %d\n", key_hash); | |
| 320 size_t i = key_hash % len; | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
321 auto e = aa.b[i]; |
| 132 | 322 while (e !is null) |
| 323 { | |
| 324 if (key_hash == e.hash) | |
| 325 { | |
| 326 auto c = keyti.compare(pkey, e + 1); | |
| 327 if (c == 0) | |
| 328 return cast(void *)(e + 1) + keysize; | |
| 329 e = (c < 0) ? e.left : e.right; | |
| 330 } | |
| 331 else | |
| 332 e = (key_hash < e.hash) ? e.left : e.right; | |
| 333 } | |
| 334 } | |
| 335 return null; // not found, caller will throw exception | |
| 336 } | |
| 337 | |
| 338 | |
| 339 /************************************************* | |
| 340 * Determine if key is in aa. | |
| 341 * Returns: | |
| 342 * null not in aa | |
| 343 * !=null in aa, return pointer to value | |
| 344 */ | |
| 345 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
346 void* _aaIn(AA aa, TypeInfo keyti, void *pkey) |
| 132 | 347 in |
| 348 { | |
| 349 } | |
| 350 out (result) | |
| 351 { | |
| 352 //assert(result == 0 || result == 1); | |
| 353 } | |
| 354 body | |
| 355 { | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
356 if (aa) |
| 132 | 357 { |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
358 //auto pkey = cast(void *)(&keyti + 1); |
| 132 | 359 |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
360 //printf("_aaIn(), .length = %d, .ptr = %x\n", aa.length, cast(uint)aa.ptr); |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
361 auto len = aa.b.length; |
| 132 | 362 |
| 363 if (len) | |
| 364 { | |
| 365 auto key_hash = keyti.getHash(pkey); | |
| 366 //printf("hash = %d\n", key_hash); | |
| 367 size_t i = key_hash % len; | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
368 auto e = aa.b[i]; |
| 132 | 369 while (e !is null) |
| 370 { | |
| 371 if (key_hash == e.hash) | |
| 372 { | |
| 373 auto c = keyti.compare(pkey, e + 1); | |
| 374 if (c == 0) | |
| 375 return cast(void *)(e + 1) + aligntsize(keyti.tsize()); | |
| 376 e = (c < 0) ? e.left : e.right; | |
| 377 } | |
| 378 else | |
| 379 e = (key_hash < e.hash) ? e.left : e.right; | |
| 380 } | |
| 381 } | |
| 382 } | |
| 383 | |
| 384 // Not found | |
| 385 return null; | |
| 386 } | |
| 387 | |
| 388 /************************************************* | |
| 389 * Delete key entry in aa[]. | |
| 390 * If key is not in aa[], do nothing. | |
| 391 */ | |
| 392 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
393 void _aaDel(AA aa, TypeInfo keyti, void *pkey) |
| 132 | 394 { |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
395 //auto pkey = cast(void *)(&keyti + 1); |
| 132 | 396 aaA *e; |
| 397 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
398 if (aa && aa.b.length) |
| 132 | 399 { |
| 400 auto key_hash = keyti.getHash(pkey); | |
| 401 //printf("hash = %d\n", key_hash); | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
402 size_t i = key_hash % aa.b.length; |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
403 auto pe = &aa.b[i]; |
| 132 | 404 while ((e = *pe) !is null) // null means not found |
| 405 { | |
| 406 if (key_hash == e.hash) | |
| 407 { | |
| 408 auto c = keyti.compare(pkey, e + 1); | |
| 409 if (c == 0) | |
| 410 { | |
| 411 if (!e.left && !e.right) | |
| 412 { | |
| 413 *pe = null; | |
| 414 } | |
| 415 else if (e.left && !e.right) | |
| 416 { | |
| 417 *pe = e.left; | |
| 418 e.left = null; | |
| 419 } | |
| 420 else if (!e.left && e.right) | |
| 421 { | |
| 422 *pe = e.right; | |
| 423 e.right = null; | |
| 424 } | |
| 425 else | |
| 426 { | |
| 427 *pe = e.left; | |
| 428 e.left = null; | |
| 429 do | |
| 430 pe = &(*pe).right; | |
| 431 while (*pe); | |
| 432 *pe = e.right; | |
| 433 e.right = null; | |
| 434 } | |
| 435 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
436 aa.nodes--; |
| 132 | 437 |
| 438 // Should notify GC that e can be free'd now | |
| 439 break; | |
| 440 } | |
| 441 pe = (c < 0) ? &e.left : &e.right; | |
| 442 } | |
| 443 else | |
| 444 pe = (key_hash < e.hash) ? &e.left : &e.right; | |
| 445 } | |
| 446 } | |
| 447 } | |
| 448 | |
| 449 | |
| 450 /******************************************** | |
| 451 * Produce array of values from aa. | |
| 452 */ | |
| 453 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
454 Array _aaValues(AA aa, size_t keysize, size_t valuesize) |
| 132 | 455 in |
| 456 { | |
| 457 assert(keysize == aligntsize(keysize)); | |
| 458 } | |
| 459 body | |
| 460 { | |
| 461 size_t resi; | |
| 462 Array a; | |
| 463 | |
| 464 void _aaValues_x(aaA* e) | |
| 465 { | |
| 466 do | |
| 467 { | |
| 468 memcpy(a.ptr + resi * valuesize, | |
| 469 cast(byte*)e + aaA.sizeof + keysize, | |
| 470 valuesize); | |
| 471 resi++; | |
| 472 if (e.left) | |
| 473 { if (!e.right) | |
| 474 { e = e.left; | |
| 475 continue; | |
| 476 } | |
| 477 _aaValues_x(e.left); | |
| 478 } | |
| 479 e = e.right; | |
| 480 } while (e !is null); | |
| 481 } | |
| 482 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
483 if (aa) |
| 132 | 484 { |
| 485 a.length = _aaLen(aa); | |
| 486 a.ptr = cast(byte*) gc_malloc(a.length * valuesize, | |
| 487 valuesize < (void*).sizeof && | |
| 488 valuesize > (void).sizeof ? BlkAttr.NO_SCAN : 0); | |
| 489 resi = 0; | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
490 foreach (e; aa.b) |
| 132 | 491 { |
| 492 if (e) | |
| 493 _aaValues_x(e); | |
| 494 } | |
| 495 assert(resi == a.length); | |
| 496 } | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
497 return a; |
| 132 | 498 } |
| 499 | |
| 500 | |
| 501 /******************************************** | |
| 502 * Rehash an array. | |
| 503 */ | |
| 504 | |
| 505 void* _aaRehash(AA* paa, TypeInfo keyti) | |
| 506 in | |
| 507 { | |
| 508 //_aaInvAh(paa); | |
| 509 } | |
| 510 out (result) | |
| 511 { | |
| 512 //_aaInvAh(result); | |
| 513 } | |
| 514 body | |
| 515 { | |
| 516 BB newb; | |
| 517 | |
| 518 void _aaRehash_x(aaA* olde) | |
| 519 { | |
| 520 while (1) | |
| 521 { | |
| 522 auto left = olde.left; | |
| 523 auto right = olde.right; | |
| 524 olde.left = null; | |
| 525 olde.right = null; | |
| 526 | |
| 527 aaA *e; | |
| 528 | |
| 529 //printf("rehash %p\n", olde); | |
| 530 auto key_hash = olde.hash; | |
| 531 size_t i = key_hash % newb.b.length; | |
| 532 auto pe = &newb.b[i]; | |
| 533 while ((e = *pe) !is null) | |
| 534 { | |
| 535 //printf("\te = %p, e.left = %p, e.right = %p\n", e, e.left, e.right); | |
| 536 assert(e.left != e); | |
| 537 assert(e.right != e); | |
| 538 if (key_hash == e.hash) | |
| 539 { | |
| 540 auto c = keyti.compare(olde + 1, e + 1); | |
| 541 assert(c != 0); | |
| 542 pe = (c < 0) ? &e.left : &e.right; | |
| 543 } | |
| 544 else | |
| 545 pe = (key_hash < e.hash) ? &e.left : &e.right; | |
| 546 } | |
| 547 *pe = olde; | |
| 548 | |
| 549 if (right) | |
| 550 { | |
| 551 if (!left) | |
| 552 { olde = right; | |
| 553 continue; | |
| 554 } | |
| 555 _aaRehash_x(right); | |
| 556 } | |
| 557 if (!left) | |
| 558 break; | |
| 559 olde = left; | |
| 560 } | |
| 561 } | |
| 562 | |
| 563 //printf("Rehash\n"); | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
564 if (*paa) |
| 132 | 565 { |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
566 auto aa = *paa; |
|
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
567 auto len = _aaLen(aa); |
| 132 | 568 if (len) |
| 569 { size_t i; | |
| 570 | |
| 571 for (i = 0; i < prime_list.length - 1; i++) | |
| 572 { | |
| 573 if (len <= prime_list[i]) | |
| 574 break; | |
| 575 } | |
| 576 len = prime_list[i]; | |
| 577 newb.b = new aaA*[len]; | |
| 578 | |
| 579 foreach (e; aa.b) | |
| 580 { | |
| 581 if (e) | |
| 582 _aaRehash_x(e); | |
| 583 } | |
| 584 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
585 newb.nodes = (*aa).nodes; |
| 132 | 586 } |
| 587 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
588 **paa = newb; |
| 132 | 589 } |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
590 return *paa; |
| 132 | 591 } |
| 592 | |
| 593 | |
| 594 /******************************************** | |
| 595 * Produce array of N byte keys from aa. | |
| 596 */ | |
| 597 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
598 Array _aaKeys(AA aa, size_t keysize) |
| 132 | 599 { |
| 600 byte[] res; | |
| 601 size_t resi; | |
| 602 | |
| 603 void _aaKeys_x(aaA* e) | |
| 604 { | |
| 605 do | |
| 606 { | |
| 607 memcpy(&res[resi * keysize], cast(byte*)(e + 1), keysize); | |
| 608 resi++; | |
| 609 if (e.left) | |
| 610 { if (!e.right) | |
| 611 { e = e.left; | |
| 612 continue; | |
| 613 } | |
| 614 _aaKeys_x(e.left); | |
| 615 } | |
| 616 e = e.right; | |
| 617 } while (e !is null); | |
| 618 } | |
| 619 | |
| 620 auto len = _aaLen(aa); | |
| 621 if (!len) | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
622 return Array(); |
| 132 | 623 res = (cast(byte*) gc_malloc(len * keysize, |
| 624 keysize < (void*).sizeof && | |
| 625 keysize > (void).sizeof ? BlkAttr.NO_SCAN : 0))[0 .. len * keysize]; | |
| 626 resi = 0; | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
627 foreach (e; aa.b) |
| 132 | 628 { |
| 629 if (e) | |
| 630 _aaKeys_x(e); | |
| 631 } | |
| 632 assert(resi == len); | |
| 633 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
634 return Array(len, res.ptr); |
| 132 | 635 } |
| 636 | |
| 637 | |
| 638 /********************************************** | |
| 639 * 'apply' for associative arrays - to support foreach | |
| 640 */ | |
| 641 | |
| 642 // dg is D, but _aaApply() is C | |
| 643 extern (D) typedef int delegate(void *) dg_t; | |
| 644 | |
| 645 int _aaApply(AA aa, size_t keysize, dg_t dg) | |
| 646 in | |
| 647 { | |
| 648 assert(aligntsize(keysize) == keysize); | |
| 649 } | |
| 650 body | |
| 651 { int result; | |
| 652 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
653 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa, keysize, dg); |
| 132 | 654 |
| 655 int treewalker(aaA* e) | |
| 656 { int result; | |
| 657 | |
| 658 do | |
| 659 { | |
| 660 //printf("treewalker(e = %p, dg = x%llx)\n", e, dg); | |
| 661 result = dg(cast(void *)(e + 1) + keysize); | |
| 662 if (result) | |
| 663 break; | |
| 664 if (e.right) | |
| 665 { if (!e.left) | |
| 666 { | |
| 667 e = e.right; | |
| 668 continue; | |
| 669 } | |
| 670 result = treewalker(e.right); | |
| 671 if (result) | |
| 672 break; | |
| 673 } | |
| 674 e = e.left; | |
| 675 } while (e); | |
| 676 | |
| 677 return result; | |
| 678 } | |
| 679 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
680 if (aa) |
| 132 | 681 { |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
682 foreach (e; aa.b) |
| 132 | 683 { |
| 684 if (e) | |
| 685 { | |
| 686 result = treewalker(e); | |
| 687 if (result) | |
| 688 break; | |
| 689 } | |
| 690 } | |
| 691 } | |
| 692 return result; | |
| 693 } | |
| 694 | |
| 695 // dg is D, but _aaApply2() is C | |
| 696 extern (D) typedef int delegate(void *, void *) dg2_t; | |
| 697 | |
| 698 int _aaApply2(AA aa, size_t keysize, dg2_t dg) | |
| 699 in | |
| 700 { | |
| 701 assert(aligntsize(keysize) == keysize); | |
| 702 } | |
| 703 body | |
| 704 { int result; | |
| 705 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
706 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa, keysize, dg); |
| 132 | 707 |
| 708 int treewalker(aaA* e) | |
| 709 { int result; | |
| 710 | |
| 711 do | |
| 712 { | |
| 713 //printf("treewalker(e = %p, dg = x%llx)\n", e, dg); | |
| 714 result = dg(cast(void *)(e + 1), cast(void *)(e + 1) + keysize); | |
| 715 if (result) | |
| 716 break; | |
| 717 if (e.right) | |
| 718 { if (!e.left) | |
| 719 { | |
| 720 e = e.right; | |
| 721 continue; | |
| 722 } | |
| 723 result = treewalker(e.right); | |
| 724 if (result) | |
| 725 break; | |
| 726 } | |
| 727 e = e.left; | |
| 728 } while (e); | |
| 729 | |
| 730 return result; | |
| 731 } | |
| 732 | |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
733 if (aa) |
| 132 | 734 { |
|
163
a8cd9bc1021a
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
lindquist
parents:
132
diff
changeset
|
735 foreach (e; aa.b) |
| 132 | 736 { |
| 737 if (e) | |
| 738 { | |
| 739 result = treewalker(e); | |
| 740 if (result) | |
| 741 break; | |
| 742 } | |
| 743 } | |
| 744 } | |
| 745 return result; | |
| 746 } | |
| 747 | |
| 748 | |
| 749 /*********************************** | |
| 750 * Construct an associative array of type ti from | |
| 751 * length pairs of key/value pairs. | |
| 752 */ | |
| 753 | |
| 754 /+ | |
| 755 | |
| 756 extern (C) | |
| 757 BB* _d_assocarrayliteralT(TypeInfo_AssociativeArray ti, size_t length, ...) | |
| 758 { | |
| 759 auto valuesize = ti.next.tsize(); // value size | |
| 760 auto keyti = ti.key; | |
| 761 auto keysize = keyti.tsize(); // key size | |
| 762 BB* result; | |
| 763 | |
| 764 //printf("_d_assocarrayliteralT(keysize = %d, valuesize = %d, length = %d)\n", keysize, valuesize, length); | |
| 765 //printf("tivalue = %.*s\n", ti.next.classinfo.name); | |
| 766 if (length == 0 || valuesize == 0 || keysize == 0) | |
| 767 { | |
| 768 ; | |
| 769 } | |
| 770 else | |
| 771 { | |
| 772 va_list q; | |
| 773 va_start!(size_t)(q, length); | |
| 774 | |
| 775 result = new BB(); | |
| 776 size_t i; | |
| 777 | |
| 778 for (i = 0; i < prime_list.length - 1; i++) | |
| 779 { | |
| 780 if (length <= prime_list[i]) | |
| 781 break; | |
| 782 } | |
| 783 auto len = prime_list[i]; | |
| 784 result.b = new aaA*[len]; | |
| 785 | |
| 786 size_t keystacksize = (keysize + int.sizeof - 1) & ~(int.sizeof - 1); | |
| 787 size_t valuestacksize = (valuesize + int.sizeof - 1) & ~(int.sizeof - 1); | |
| 788 | |
| 789 size_t keytsize = aligntsize(keysize); | |
| 790 | |
| 791 for (size_t j = 0; j < length; j++) | |
| 792 { void* pkey = q; | |
| 793 q += keystacksize; | |
| 794 void* pvalue = q; | |
| 795 q += valuestacksize; | |
| 796 aaA* e; | |
| 797 | |
| 798 auto key_hash = keyti.getHash(pkey); | |
| 799 //printf("hash = %d\n", key_hash); | |
| 800 i = key_hash % len; | |
| 801 auto pe = &result.b[i]; | |
| 802 while (1) | |
| 803 { | |
| 804 e = *pe; | |
| 805 if (!e) | |
| 806 { | |
| 807 // Not found, create new elem | |
| 808 //printf("create new one\n"); | |
| 809 e = cast(aaA *) cast(void*) new void[aaA.sizeof + keytsize + valuesize]; | |
| 810 memcpy(e + 1, pkey, keysize); | |
| 811 e.hash = key_hash; | |
| 812 *pe = e; | |
| 813 result.nodes++; | |
| 814 break; | |
| 815 } | |
| 816 if (key_hash == e.hash) | |
| 817 { | |
| 818 auto c = keyti.compare(pkey, e + 1); | |
| 819 if (c == 0) | |
| 820 break; | |
| 821 pe = (c < 0) ? &e.left : &e.right; | |
| 822 } | |
| 823 else | |
| 824 pe = (key_hash < e.hash) ? &e.left : &e.right; | |
| 825 } | |
| 826 memcpy(cast(void *)(e + 1) + keytsize, pvalue, valuesize); | |
| 827 } | |
| 828 | |
| 829 va_end(q); | |
| 830 } | |
| 831 return result; | |
| 832 } | |
| 833 | |
| 834 +/ |