Sort map by hash value */
| 1328 | |
| 1329 | /* Sort map by hash value */ |
| 1330 | static void dx_sort_map (struct dx_map_entry *map, unsigned count) |
| 1331 | { |
| 1332 | struct dx_map_entry *p, *q, *top = map + count - 1; |
| 1333 | int more; |
| 1334 | /* Combsort until bubble sort doesn't suck */ |
| 1335 | while (count > 2) |
| 1336 | { |
| 1337 | count = count*10/13; |
| 1338 | if (count - 9 < 2) /* 9, 10 -> 11 */ |
| 1339 | count = 11; |
| 1340 | for (p = top, q = p - count; q >= map; p--, q--) |
| 1341 | if (p->hash < q->hash) |
| 1342 | swap(struct dx_map_entry, *p, *q); |
| 1343 | } |
| 1344 | /* Garden variety bubble sort */ |
| 1345 | do { |
| 1346 | more = 0; |
| 1347 | q = top; |
| 1348 | while (q-- > map) |
| 1349 | { |
| 1350 | if (q[1].hash >= q[0].hash) |
| 1351 | continue; |
| 1352 | swap(struct dx_map_entry, *(q+1), *q); |
| 1353 | more = 1; |
| 1354 | } |
| 1355 | } while (more); |
| 1356 | } |
| 1357 | |
| 1358 | static void dx_insert_block(struct dx_frame *frame, u32 hash, u32 block) |
| 1359 | { |