| 53 | #define BIG_SUM2HASH(sum) ((sum)%tablesize) |
| 54 | |
| 55 | static void build_hash_table(struct sum_struct *s) |
| 56 | { |
| 57 | static uint32 alloc_size; |
| 58 | int32 i; |
| 59 | |
| 60 | /* Dynamically calculate the hash table size so that the hash load |
| 61 | * for big files is about 80%. A number greater than the traditional |
| 62 | * size must be odd or s2 will not be able to span the entire set. */ |
| 63 | tablesize = (uint32)(s->count/8) * 10 + 11; |
| 64 | if (tablesize < TRADITIONAL_TABLESIZE) |
| 65 | tablesize = TRADITIONAL_TABLESIZE; |
| 66 | if (tablesize > alloc_size || tablesize < alloc_size - 16*1024) { |
| 67 | if (hash_table) |
| 68 | free(hash_table); |
| 69 | hash_table = new_array(int32, tablesize); |
| 70 | alloc_size = tablesize; |
| 71 | } |
| 72 | |
| 73 | memset(hash_table, 0xFF, tablesize * sizeof hash_table[0]); |
| 74 | |
| 75 | if (tablesize == TRADITIONAL_TABLESIZE) { |
| 76 | for (i = 0; i < s->count; i++) { |
| 77 | uint32 t = SUM2HASH(s->sums[i].sum1); |
| 78 | s->sums[i].chain = hash_table[t]; |
| 79 | hash_table[t] = i; |
| 80 | } |
| 81 | } else { |
| 82 | for (i = 0; i < s->count; i++) { |
| 83 | uint32 t = BIG_SUM2HASH(s->sums[i].sum1); |
| 84 | s->sums[i].chain = hash_table[t]; |
| 85 | hash_table[t] = i; |
| 86 | } |
| 87 | } |
| 88 | } |
| 89 | |
| 90 | |
| 91 | static OFF_T last_match; |