Coverage Report

Created: 2017-08-21 19:50

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_hash.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 *
4
 * Use of this software is governed by the MIT license
5
 *
6
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8
 */
9
10
#include <stdlib.h>
11
#include <isl_hash_private.h>
12
#include <isl/ctx.h>
13
#include "isl_config.h"
14
15
uint32_t isl_hash_string(uint32_t hash, const char *s)
16
140k
{
17
1.30M
  for (; 
*s1.30M
;
s++1.16M
)
18
1.16M
    isl_hash_byte(hash, *s);
19
140k
  return hash;
20
140k
}
21
22
uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
23
13.8k
{
24
13.8k
  int i;
25
13.8k
  const char *s = p;
26
124k
  for (i = 0; 
i < len124k
;
++i110k
)
27
110k
    isl_hash_byte(hash, s[i]);
28
13.8k
  return hash;
29
13.8k
}
30
31
static unsigned int round_up(unsigned int v)
32
310k
{
33
310k
  int old_v = v;
34
310k
35
1.05M
  while (
v1.05M
)
{745k
36
745k
    old_v = v;
37
745k
    v ^= v & -v;
38
745k
  }
39
310k
  return old_v << 1;
40
310k
}
41
42
int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
43
      int min_size)
44
310k
{
45
310k
  size_t size;
46
310k
47
310k
  if (!table)
48
0
    return -1;
49
310k
50
310k
  
if (310k
min_size < 2310k
)
51
136k
    min_size = 2;
52
310k
  table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
53
310k
  table->n = 0;
54
310k
55
310k
  size = 1 << table->bits;
56
310k
  table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
57
310k
            size);
58
310k
  if (!table->entries)
59
6
    return -1;
60
310k
61
310k
  return 0;
62
310k
}
63
64
/* Dummy comparison function that always returns false.
65
 */
66
static int no(const void *entry, const void *val)
67
34.3k
{
68
34.3k
  return 0;
69
34.3k
}
70
71
/* Extend "table" to twice its size.
72
 * Return 0 on success and -1 on error.
73
 *
74
 * We reuse isl_hash_table_find to create entries in the extended table.
75
 * Since all entries in the original table are assumed to be different,
76
 * there is no need to compare them against each other.
77
 */
78
static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)
79
4.19k
{
80
4.19k
  int n;
81
4.19k
  size_t old_size, size;
82
4.19k
  struct isl_hash_table_entry *entries;
83
4.19k
  uint32_t h;
84
4.19k
85
4.19k
  entries = table->entries;
86
4.19k
  old_size = 1 << table->bits;
87
4.19k
  size = 2 * old_size;
88
4.19k
  table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
89
4.19k
            size);
90
4.19k
  if (
!table->entries4.19k
)
{0
91
0
    table->entries = entries;
92
0
    return -1;
93
4.19k
  }
94
4.19k
95
4.19k
  n = table->n;
96
4.19k
  table->n = 0;
97
4.19k
  table->bits++;
98
4.19k
99
44.1k
  for (h = 0; 
h < old_size44.1k
;
++h39.9k
)
{39.9k
100
39.9k
    struct isl_hash_table_entry *entry;
101
39.9k
102
39.9k
    if (!entries[h].data)
103
9.98k
      continue;
104
39.9k
105
39.9k
    entry = isl_hash_table_find(ctx, table, entries[h].hash,
106
29.9k
              &no, NULL, 1);
107
29.9k
    if (
!entry29.9k
)
{0
108
0
      table->bits--;
109
0
      free(table->entries);
110
0
      table->entries = entries;
111
0
      table->n = n;
112
0
      return -1;
113
29.9k
    }
114
29.9k
115
29.9k
    *entry = entries[h];
116
29.9k
  }
117
4.19k
118
4.19k
  free(entries);
119
4.19k
120
4.19k
  return 0;
121
4.19k
}
122
123
struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
124
17.0k
{
125
17.0k
  struct isl_hash_table *table = NULL;
126
17.0k
127
17.0k
  table = isl_alloc_type(ctx, struct isl_hash_table);
128
17.0k
  if (isl_hash_table_init(ctx, table, min_size))
129
0
    goto error;
130
17.0k
  return table;
131
17.0k
error:
132
0
  isl_hash_table_free(ctx, table);
133
17.0k
  return NULL;
134
17.0k
}
135
136
void isl_hash_table_clear(struct isl_hash_table *table)
137
309k
{
138
309k
  if (!table)
139
0
    return;
140
309k
  free(table->entries);
141
309k
}
142
143
void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
144
17.1k
{
145
17.1k
  if (!table)
146
108
    return;
147
17.1k
  isl_hash_table_clear(table);
148
17.0k
  free(table);
149
17.1k
}
150
151
/* A dummy entry that can be used to make a distinction between
152
 * a missing entry and an error condition.
153
 * It is used by isl_union_*_find_part_entry.
154
 */
155
static struct isl_hash_table_entry none = { 0, NULL };
156
struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
157
158
struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
159
        struct isl_hash_table *table,
160
        uint32_t key_hash,
161
        int (*eq)(const void *entry, const void *val),
162
        const void *val, int reserve)
163
782k
{
164
782k
  size_t size;
165
782k
  uint32_t h, key_bits;
166
782k
167
782k
  key_bits = isl_hash_bits(key_hash, table->bits);
168
782k
  size = 1 << table->bits;
169
1.18M
  for (h = key_bits; 
table->entries[h].data1.18M
;
h = (h+1) % size401k
)
170
613k
    
if (613k
table->entries[h].hash == key_hash &&613k
171
334k
        eq(table->entries[h].data, val))
172
211k
      return &table->entries[h];
173
782k
174
570k
  
if (570k
!reserve570k
)
175
65.3k
    return NULL;
176
570k
177
505k
  
if (505k
4 * table->n >= 3 * size505k
)
{4.19k
178
4.19k
    if (grow_table(ctx, table) < 0)
179
0
      return NULL;
180
4.19k
    return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
181
505k
  }
182
505k
183
505k
  table->n++;
184
500k
  table->entries[h].hash = key_hash;
185
500k
186
505k
  return &table->entries[h];
187
782k
}
188
189
isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
190
  isl_stat (*fn)(void **entry, void *user), void *user)
191
770k
{
192
770k
  size_t size;
193
770k
  uint32_t h;
194
770k
195
770k
  if (!table->entries)
196
6
    return isl_stat_error;
197
770k
198
770k
  size = 1 << table->bits;
199
14.1M
  for (h = 0; 
h < size14.1M
;
++ h13.4M
)
200
13.4M
    
if (13.4M
table->entries[h].data &&13.4M
201
956k
        fn(&table->entries[h].data, user) < 0)
202
79.4k
      return isl_stat_error;
203
770k
  
204
691k
  return isl_stat_ok;
205
770k
}
206
207
void isl_hash_table_remove(struct isl_ctx *ctx,
208
        struct isl_hash_table *table,
209
        struct isl_hash_table_entry *entry)
210
68.7k
{
211
68.7k
  int h, h2;
212
68.7k
  size_t size;
213
68.7k
214
68.7k
  if (
!table || 68.7k
!entry68.7k
)
215
0
    return;
216
68.7k
217
68.7k
  size = 1 << table->bits;
218
68.7k
  h = entry - table->entries;
219
68.7k
  isl_assert(ctx, h >= 0 && h < size, return);
220
68.7k
221
208k
  
for (h2 = h+1; 68.7k
table->entries[h2 % size].data208k
;
h2++139k
)
{139k
222
139k
    uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
223
139k
            table->bits);
224
139k
    uint32_t offset = (size + bits - (h+1)) % size;
225
139k
    if (offset <= h2 - (h+1))
226
50.9k
      continue;
227
139k
    *entry = table->entries[h2 % size];
228
88.6k
    h = h2;
229
88.6k
    entry = &table->entries[h % size];
230
88.6k
  }
231
68.7k
232
68.7k
  entry->hash = 0;
233
68.7k
  entry->data = NULL;
234
68.7k
  table->n--;
235
68.7k
}