Mercurial > projects > ldc
annotate tango/lib/compiler/llvmdc/aaA.d @ 163:a8cd9bc1021a trunk
[svn r179] lots and lots of fixes, much more of tango now compiles/works.
| author | lindquist |
|---|---|
| date | Mon, 05 May 2008 07:36:29 +0200 |
| parents | 1700239cab2e |
| 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 +/ |