Statistics
| Branch: | Revision:

grapes / som / TopologyManager / topocache.c @ 18d83f26

History | View | Annotate | Download (8.91 KB)

1
/*
2
 *  Copyright (c) 2010 Luca Abeni
3
 *
4
 *  This is free software; see lgpl-2.1.txt
5
 */
6

    
7
#include <arpa/inet.h>
8
#include <stdint.h>
9
#include <stdlib.h>
10
#include <string.h>
11

    
12
#include <stdio.h>
13

    
14
#include "net_helper.h"
15
#include "topocache.h"
16
#include "int_coding.h"
17

    
18
struct cache_entry {
19
  struct nodeID *id;
20
  uint32_t timestamp;
21
};
22

    
23
struct peer_cache {
24
  struct cache_entry *entries;
25
  int cache_size;
26
  int current_size;
27
  int metadata_size;
28
  uint8_t *metadata;
29
  int max_timestamp;
30
};
31

    
32
struct nodeID *nodeid(const struct peer_cache *c, int i)
33
{
34
  if (i < c->current_size) {
35
    return c->entries[i].id;
36
  }
37

    
38
  return NULL;
39
}
40

    
41
const void *get_metadata(const struct peer_cache *c, int *size)
42
{
43
  *size = c->metadata_size;
44
  return c->metadata;
45
}
46

    
47
int cache_metadata_update(struct peer_cache *c, struct nodeID *p, const void *meta, int meta_size)
48
{
49
  int i;
50

    
51
  if (!meta_size || meta_size != c->metadata_size) {
52
    return -3;
53
  }
54
  for (i = 0; i < c->current_size; i++) {
55
    if (nodeid_equal(c->entries[i].id, p)) {
56
      memcpy(c->metadata + i * meta_size, meta, meta_size);
57
      return 1;
58
    }
59
  }
60

    
61
  return 0;
62
}
63

    
64
int cache_add_ranked(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size, ranking_function f, const void *tmeta)
65
{
66
  int i, pos = 0;
67

    
68
  if (meta_size && meta_size != c->metadata_size) {
69
    return -3;
70
  }
71
  if (c->current_size == c->cache_size) {
72
    return -2;
73
  }
74
  for (i = 0; i < c->current_size; i++) {
75
    if (nodeid_equal(c->entries[i].id, neighbour)) {
76
      return -1;
77
    }
78
    if ((f != NULL) && f(tmeta, meta, c->metadata+(c->metadata_size * i)) == 2) {
79
      pos++;
80
    }
81
  }
82
  if (meta_size) {
83
    memmove(c->metadata + (pos + 1) * meta_size, c->metadata + pos * meta_size, (c->current_size - pos) * meta_size);
84
    memcpy(c->metadata + pos * meta_size, meta, meta_size);
85
  }
86
  for (i = c->current_size; i > pos; i--) {
87
    c->entries[i] = c->entries[i - 1];
88
  }
89
  c->entries[pos].id = nodeid_dup(neighbour);
90
  c->entries[pos].timestamp = 1;
91
  c->current_size++;
92

    
93
  return c->current_size;
94
}
95

    
96
int cache_add(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size)
97
{
98
  return cache_add_ranked(c, neighbour, meta, meta_size, NULL, NULL);
99
}
100

    
101
int cache_del(struct peer_cache *c, struct nodeID *neighbour)
102
{
103
  int i;
104
  int found = 0;
105

    
106
  for (i = 0; i < c->current_size; i++) {
107
    if (nodeid_equal(c->entries[i].id, neighbour)) {
108
      nodeid_free(c->entries[i].id);
109
      c->current_size--;
110
      found = 1;
111
      if (c->metadata_size && (i < c->current_size)) {
112
        memmove(c->metadata + c->metadata_size * i,
113
                c->metadata + c->metadata_size * (i + 1),
114
                c->metadata_size * (c->current_size - i));
115
      }
116
    }
117
    if (found && (i < c->current_size)) {
118
      c->entries[i] = c->entries[i + 1];
119
    }
120
  }
121

    
122
  return c->current_size;
123
}
124

    
125
void cache_update_tout(struct peer_cache *c)
126
{
127
  int i;
128
  
129
  for (i = 0; i < c->current_size; i++) {
130
    if (c->max_timestamp && (c->entries[i].timestamp == c->max_timestamp)) {
131
      int j = i;
132

    
133
      while(j < c->current_size && c->entries[j].id) {
134
        nodeid_free(c->entries[j].id);
135
        c->entries[j++].id = NULL;
136
      }
137
      c->current_size = i;        /* The cache is ordered by timestamp...
138
                                   all the other entries wiil be older than
139
                                   this one, so remove all of them
140
                                */
141
    } else {
142
      c->entries[i].timestamp++;
143
    }
144
  }
145
}
146

    
147
void cache_update(struct peer_cache *c)
148
{
149
  int i;
150
  
151
  for (i = 0; i < c->current_size; i++) {
152
      c->entries[i].timestamp++;
153
  }
154
}
155

    
156
struct peer_cache *cache_init(int n, int metadata_size, int max_timestamp)
157
{
158
  struct peer_cache *res;
159

    
160
  res = malloc(sizeof(struct peer_cache));
161
  if (res == NULL) {
162
    return NULL;
163
  }
164
  res->max_timestamp = max_timestamp;
165
  res->cache_size = n;
166
  res->current_size = 0;
167
  res->entries = malloc(sizeof(struct cache_entry) * n);
168
  if (res->entries == NULL) {
169
    free(res);
170

    
171
    return NULL;
172
  }
173
  
174
  memset(res->entries, 0, sizeof(struct cache_entry) * n);
175
  if (metadata_size) {
176
    res->metadata = malloc(metadata_size * n);
177
  } else {
178
    res->metadata = NULL;
179
  }
180

    
181
  if (res->metadata) {
182
    res->metadata_size = metadata_size;
183
    memset(res->metadata, 0, metadata_size * n);
184
  } else {
185
    res->metadata_size = 0;
186
  }
187

    
188
  return res;
189
}
190

    
191
void cache_free(struct peer_cache *c)
192
{
193
  int i;
194

    
195
  for (i = 0; i < c->current_size; i++) {
196
    if(c->entries[i].id) {
197
      nodeid_free(c->entries[i].id);
198
    }
199
  }
200
  free(c->entries);
201
  free(c->metadata);
202
  free(c);
203
}
204

    
205
static int in_cache(const struct peer_cache *c, const struct cache_entry *elem)
206
{
207
  int i;
208

    
209
  for (i = 0; i < c->current_size; i++) {
210
    if (nodeid_equal(c->entries[i].id, elem->id)) {
211
      return 1;
212
    }
213
  }
214

    
215
  return 0;
216
}
217

    
218
struct nodeID *rand_peer(struct peer_cache *c, void **meta)
219
{
220
  int j;
221

    
222
  if (c->current_size == 0) {
223
    return NULL;
224
  }
225
  j = ((double)rand() / (double)RAND_MAX) * c->current_size;
226

    
227
  if (meta) {
228
    *meta = c->metadata + (j * c->metadata_size);
229
  }
230

    
231
  return c->entries[j].id;
232
}
233

    
234
struct peer_cache *entries_undump(const uint8_t *buff, int size)
235
{
236
  struct peer_cache *res;
237
  int i = 0;
238
  const uint8_t *p = buff;
239
  uint8_t *meta;
240
  int cache_size, metadata_size;
241

    
242
  cache_size = int_rcpy(buff);
243
  metadata_size = int_rcpy(buff + 4);
244
  p = buff + 8;
245
  res = cache_init(cache_size, metadata_size, 0);
246
  meta = res->metadata;
247
  while (p - buff < size) {
248
    int len;
249

    
250
    res->entries[i].timestamp = int_rcpy(p);
251
    p += sizeof(uint32_t);
252
    res->entries[i++].id = nodeid_undump(p, &len);
253
    p += len;
254
    if (metadata_size) {
255
      memcpy(meta, p, metadata_size);
256
      p += metadata_size;
257
      meta += metadata_size;
258
    }
259
  }
260
  res->current_size = i;
261
if (p - buff != size) { fprintf(stderr, "Waz!! %d != %d\n", (int)(p - buff), size); exit(-1);}
262

    
263
  return res;
264
}
265

    
266
int cache_header_dump(uint8_t *b, const struct peer_cache *c)
267
{
268
  int_cpy(b, c->cache_size);
269
  int_cpy(b + 4, c->metadata_size);
270

    
271
  return 8;
272
}
273

    
274
int entry_dump(uint8_t *b, struct peer_cache *c, int i)
275
{
276
  int res;
277
 
278
  if (i && (i >= c->cache_size - 1)) {
279
    return 0;
280
  }
281
  int_cpy(b, c->entries[i].timestamp);
282
  res = 4;
283
  res += nodeid_dump(b + res, c->entries[i].id);
284
  if (c->metadata_size) {
285
    memcpy(b + res, c->metadata + c->metadata_size * i, c->metadata_size);
286
    res += c->metadata_size;
287
  }
288

    
289
  return res;
290
}
291

    
292
struct peer_cache *merge_caches_ranked(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source, ranking_function rank, void *mymetadata)
293
{
294
  int n1, n2;
295
  struct peer_cache *new_cache;
296
  uint8_t *meta;
297

    
298
  new_cache = cache_init(newsize, c1->metadata_size, c1->max_timestamp);
299
  if (new_cache == NULL) {
300
    return NULL;
301
  }
302

    
303
  meta = new_cache->metadata;
304
  *source = 0;
305
  for (n1 = 0, n2 = 0; new_cache->current_size < new_cache->cache_size;) {
306
    if ((n1 == c1->current_size) && (n2 == c2->current_size)) {
307
      return new_cache;
308
    }
309
    if (n1 == c1->current_size) {
310
      if (!in_cache(new_cache, &c2->entries[n2])) {
311
        if (new_cache->metadata_size) {
312
          memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
313
          meta += new_cache->metadata_size;
314
        }
315
        new_cache->entries[new_cache->current_size++] = c2->entries[n2];
316
        c2->entries[n2].id = NULL;
317
        *source |= 0x02;
318
      }
319
      n2++;
320
    } else if (n2 == c2->current_size) {
321
      if (!in_cache(new_cache, &c1->entries[n1])) {
322
        if (new_cache->metadata_size) {
323
          memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
324
          meta += new_cache->metadata_size;
325
        }
326
        new_cache->entries[new_cache->current_size++] = c1->entries[n1];
327
        c1->entries[n1].id = NULL;
328
        *source |= 0x01;
329
      }
330
      n1++;
331
    } else {
332
      int nowFirst;
333

    
334
      nowFirst = 0;
335
      if (rank) {
336
        nowFirst = rank(mymetadata, c1->metadata + n1 * c1->metadata_size,
337
                        c2->metadata + n2 * c2->metadata_size);
338
      }
339
      if (nowFirst == 0) {
340
        nowFirst = c2->entries[n2].timestamp > c1->entries[n1].timestamp ? 1 : 2;
341
      }
342
      if (nowFirst == 1) {
343
        if (!in_cache(new_cache, &c1->entries[n1])) {
344
          if (new_cache->metadata_size) {
345
            memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
346
            meta += new_cache->metadata_size;
347
          }
348
          new_cache->entries[new_cache->current_size++] = c1->entries[n1];
349
          c1->entries[n1].id = NULL;
350
          *source |= 0x01;
351
        }
352
        n1++;
353
      } else {
354
        if (!in_cache(new_cache, &c2->entries[n2])) {
355
          if (new_cache->metadata_size) {
356
            memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
357
            meta += new_cache->metadata_size;
358
          }
359
          new_cache->entries[new_cache->current_size++] = c2->entries[n2];
360
          c2->entries[n2].id = NULL;
361
          *source |= 0x02;
362
        }
363
        n2++;
364
      }
365
    }
366
  }
367

    
368
  return new_cache;
369
}
370

    
371
struct peer_cache *merge_caches(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source)
372
{
373
  return merge_caches_ranked(c1, c2, newsize, source, NULL, NULL);
374
}