Statistics
| Branch: | Revision:

grapes / som / TopologyManager / topocache.c @ eb29e340

History | View | Annotate | Download (11.8 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

    
17
#define MAX_TIMESTAMP 5
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
};
30

    
31
static inline void int_cpy(uint8_t *p, int v)
32
{
33
  int tmp;
34

    
35
  tmp = htonl(v);
36
  memcpy(p, &tmp, 4);
37
}
38

    
39
static inline int int_rcpy(const uint8_t *p)
40
{
41
  int tmp;
42
  
43
  memcpy(&tmp, p, 4);
44
  tmp = ntohl(tmp);
45

    
46
  return tmp;
47
}
48

    
49
struct nodeID *nodeid(const struct peer_cache *c, int i)
50
{
51
  if (i < c->current_size) {
52
    return c->entries[i].id;
53
  }
54

    
55
  return NULL;
56
}
57

    
58
const void *get_metadata(const struct peer_cache *c, int *size)
59
{
60
  *size = c->metadata_size;
61
  return c->metadata;
62
}
63

    
64
int cache_metadata_update(struct peer_cache *c, struct nodeID *p, const void *meta, int meta_size)
65
{
66
  int i;
67

    
68
  if (!meta_size || meta_size != c->metadata_size) {
69
    return -3;
70
  }
71
  for (i = 0; i < c->current_size; i++) {
72
    if (nodeid_equal(c->entries[i].id, p)) {
73
      memcpy(c->metadata + i * meta_size, meta, meta_size);
74
      return 1;
75
    }
76
  }
77

    
78
  return 0;
79
}
80

    
81
int cache_add_ranked(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size, ranking_function f, const void *tmeta)
82
{
83
  int i, pos = 0;
84

    
85
  if (meta_size && meta_size != c->metadata_size) {
86
    return -3;
87
  }
88
  for (i = 0; i < c->current_size; i++) {
89
    if (nodeid_equal(c->entries[i].id, neighbour)) {
90
      if (f != NULL) {
91
        cache_del(c,c->entries[i].id);
92
        if (i == c->current_size) break;
93
      } else return -1;
94
    }
95
    if ((f != NULL) && f(tmeta, meta, c->metadata+(c->metadata_size * i)) == 2) {
96
      pos++;
97
    }
98
  }
99
  if (c->current_size == c->cache_size) {
100
    return -2;
101
  }
102
  if (c->metadata_size) {
103
    memmove(c->metadata + (pos + 1) * c->metadata_size, c->metadata + pos * c->metadata_size, (c->current_size - pos) * c->metadata_size);
104
    if (meta_size) {
105
      memcpy(c->metadata + pos * c->metadata_size, meta, meta_size);
106
    } else {
107
      memset(c->metadata + pos * c->metadata_size, 0, c->metadata_size);
108
    }
109
  }
110
  for (i = c->current_size; i > pos; i--) {
111
    c->entries[i] = c->entries[i - 1];
112
  }
113
  c->entries[pos].id = nodeid_dup(neighbour);
114
  c->entries[pos].timestamp = 1;
115
  c->current_size++;
116

    
117
  return c->current_size;
118
}
119

    
120
int cache_add(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size)
121
{
122
  return cache_add_ranked(c, neighbour, meta, meta_size, NULL, NULL);
123
}
124

    
125
int cache_del(struct peer_cache *c, struct nodeID *neighbour)
126
{
127
  int i;
128
  int found = 0;
129

    
130
  for (i = 0; i < c->current_size; i++) {
131
    if (nodeid_equal(c->entries[i].id, neighbour)) {
132
      nodeid_free(c->entries[i].id);
133
      c->current_size--;
134
      found = 1;
135
      if (c->metadata_size && (i < c->current_size)) {
136
        memmove(c->metadata + c->metadata_size * i,
137
                c->metadata + c->metadata_size * (i + 1),
138
                c->metadata_size * (c->current_size - i));
139
      }
140
    }
141
    if (found && (i < c->current_size)) {
142
      c->entries[i] = c->entries[i + 1];
143
    }
144
  }
145

    
146
  return c->current_size;
147
}
148

    
149
void cache_update_tout(struct peer_cache *c)
150
{
151
  int i;
152
  
153
  for (i = 0; i < c->current_size; i++) {
154
    if (c->entries[i].timestamp == MAX_TIMESTAMP) {
155
      int j = i;
156

    
157
      while(j < c->current_size && c->entries[j].id) {
158
        nodeid_free(c->entries[j].id);
159
        c->entries[j++].id = NULL;
160
      }
161
      c->current_size = i;        /* The cache is ordered by timestamp...
162
                                   all the other entries wiil be older than
163
                                   this one, so remove all of them
164
                                */
165
    } else {
166
      c->entries[i].timestamp++;
167
    }
168
  }
169
}
170

    
171
void cache_update(struct peer_cache *c)
172
{
173
  int i;
174
  
175
  for (i = 0; i < c->current_size; i++) {
176
      c->entries[i].timestamp++;
177
  }
178
}
179

    
180
struct peer_cache *cache_init(int n, int metadata_size)
181
{
182
  struct peer_cache *res;
183

    
184
  res = malloc(sizeof(struct peer_cache));
185
  if (res == NULL) {
186
    return NULL;
187
  }
188
  res->cache_size = n;
189
  res->current_size = 0;
190
  res->entries = malloc(sizeof(struct cache_entry) * n);
191
  if (res->entries == NULL) {
192
    free(res);
193

    
194
    return NULL;
195
  }
196
  
197
  memset(res->entries, 0, sizeof(struct cache_entry) * n);
198
  if (metadata_size) {
199
    res->metadata = malloc(metadata_size * n);
200
  } else {
201
    res->metadata = NULL;
202
  }
203

    
204
  if (res->metadata) {
205
    res->metadata_size = metadata_size;
206
    memset(res->metadata, 0, metadata_size * n);
207
  } else {
208
    res->metadata_size = 0;
209
  }
210

    
211
  return res;
212
}
213

    
214
void cache_free(struct peer_cache *c)
215
{
216
  int i;
217

    
218
  for (i = 0; i < c->current_size; i++) {
219
    if(c->entries[i].id) {
220
      nodeid_free(c->entries[i].id);
221
    }
222
  }
223
  free(c->entries);
224
  free(c->metadata);
225
  free(c);
226
}
227

    
228
static int in_cache(const struct peer_cache *c, const struct cache_entry *elem)
229
{
230
  int i;
231

    
232
  for (i = 0; i < c->current_size; i++) {
233
    if (nodeid_equal(c->entries[i].id, elem->id)) {
234
      return i;
235
    }
236
  }
237

    
238
  return -1;
239
}
240

    
241
struct nodeID *rand_peer(struct peer_cache *c, void **meta)
242
{
243
  int j;
244

    
245
  if (c->current_size == 0) {
246
    return NULL;
247
  }
248
  j = ((double)rand() / (double)RAND_MAX) * c->current_size;
249

    
250
  if (meta) {
251
    *meta = c->metadata + (j * c->metadata_size);
252
  }
253

    
254
  return c->entries[j].id;
255
}
256

    
257
struct peer_cache *entries_undump(const uint8_t *buff, int size)
258
{
259
  struct peer_cache *res;
260
  int i = 0;
261
  const uint8_t *p = buff;
262
  uint8_t *meta;
263
  int cache_size, metadata_size;
264

    
265
  cache_size = int_rcpy(buff);
266
  metadata_size = int_rcpy(buff + 4);
267
  p = buff + 8;
268
  res = cache_init(cache_size, metadata_size);
269
  meta = res->metadata;
270
  while (p - buff < size) {
271
    int len;
272

    
273
    res->entries[i].timestamp = int_rcpy(p);
274
    p += sizeof(uint32_t);
275
    res->entries[i++].id = nodeid_undump(p, &len);
276
    p += len;
277
    if (metadata_size) {
278
      memcpy(meta, p, metadata_size);
279
      p += metadata_size;
280
      meta += metadata_size;
281
    }
282
  }
283
  res->current_size = i;
284
if (p - buff != size) { fprintf(stderr, "Waz!! %d != %d\n", p - buff, size); exit(-1);}
285

    
286
  return res;
287
}
288

    
289
int cache_header_dump(uint8_t *b, const struct peer_cache *c)
290
{
291
  int_cpy(b, c->cache_size);
292
  int_cpy(b + 4, c->metadata_size);
293

    
294
  return 8;
295
}
296

    
297
int entry_dump(uint8_t *b, struct peer_cache *c, int i)
298
{
299
  int res;
300
 
301
  if (i && (i >= c->cache_size - 1)) {
302
    return 0;
303
  }
304
  int_cpy(b, c->entries[i].timestamp);
305
  res = 4;
306
  res += nodeid_dump(b + res, c->entries[i].id);
307
  if (c->metadata_size) {
308
    memcpy(b + res, c->metadata + c->metadata_size * i, c->metadata_size);
309
    res += c->metadata_size;
310
  }
311

    
312
  return res;
313
}
314

    
315
struct peer_cache *cache_rank (const struct peer_cache *c, ranking_function rank, const struct nodeID *target, const void *target_meta)
316
{
317
        struct peer_cache *res;
318
        int i,j,pos;
319

    
320
        res = cache_init(c->cache_size,c->metadata_size);
321
        if (res == NULL) {
322
                return res;
323
        }
324

    
325
        for (i = 0; i < c->current_size; i++) {
326
                if (!target || !nodeid_equal(c->entries[i].id,target)) {
327
                        pos = 0;
328
                        for (j=0; j<res->current_size;j++) {
329
                                if (((rank != NULL) && rank(target_meta, c->metadata+(c->metadata_size * i), res->metadata+(res->metadata_size * j)) == 2) ||
330
                                        ((rank == NULL) && res->entries[j].timestamp < c->entries[i].timestamp)) {
331
                                        pos++;
332
                                }
333
                        }
334
                        if (c->metadata_size) {
335
                                memmove(res->metadata + (pos + 1) * res->metadata_size, res->metadata + pos * res->metadata_size, (res->current_size - pos) * res->metadata_size);
336
                                memcpy(res->metadata + pos * res->metadata_size, c->metadata+(c->metadata_size * i), res->metadata_size);
337
                        }
338
                        for (j = res->current_size; j > pos; j--) {
339
                                res->entries[j] = res->entries[j - 1];
340
                        }
341
                        res->entries[pos].id = nodeid_dup(c->entries[i].id);
342
                        res->entries[pos].timestamp = c->entries[i].timestamp;
343
                        res->current_size++;
344
                }
345
        }
346

    
347
        return res;
348
}
349

    
350
struct peer_cache *cache_union(struct peer_cache *c1, struct peer_cache *c2, int *size) {
351
        int n,pos;
352
        struct peer_cache *new_cache;
353
        uint8_t *meta;
354

    
355
        if (c1->metadata_size != c2->metadata_size) {
356
                return NULL;
357
        }
358

    
359
        *size = c1->current_size + c2->current_size;
360
        new_cache = cache_init(*size, c1->metadata_size);
361
        if (new_cache == NULL) {
362
                return NULL;
363
        }
364

    
365
        meta = new_cache->metadata;
366

    
367
        for (n = 0; n < c1->current_size; n++) {
368
                if (new_cache->metadata_size) {
369
                        memcpy(meta, c1->metadata + n * c1->metadata_size, c1->metadata_size);
370
                        meta += new_cache->metadata_size;
371
                }
372
                new_cache->entries[new_cache->current_size++] = c1->entries[n];
373
                c1->entries[n].id = NULL;
374
        }
375
  
376
        for (n = 0; n < c2->current_size; n++) {
377
                pos = in_cache(new_cache, &c2->entries[n]);
378
                if (pos >= 0) {
379
                        if (new_cache->entries[pos].timestamp > c2->entries[n].timestamp) {
380
                                cache_del(new_cache,new_cache->entries[pos].id);
381
                                meta -= new_cache->metadata_size;
382
                                pos = -1;
383
                        }
384
                }
385
                if (pos < 0) {
386
                        if (new_cache->metadata_size) {
387
                                memcpy(meta, c2->metadata + n * c2->metadata_size, c2->metadata_size);
388
                                meta += new_cache->metadata_size;
389
                        }
390
                        new_cache->entries[new_cache->current_size++] = c2->entries[n];
391
                        c2->entries[n].id = NULL;
392
                }
393
        }
394

    
395
        return new_cache;
396
}
397

    
398
int cache_resize (struct peer_cache *c, int size) {
399

    
400
        int dif = size - c->cache_size;
401
        if (!dif) {
402
                return c->current_size;
403
        }
404

    
405
        c->entries = realloc(c->entries, sizeof(struct cache_entry) * size);
406
        if (dif > 0) {
407
                memset(c->entries + sizeof(struct cache_entry) * c->cache_size, 0, sizeof(struct cache_entry) * dif);
408
        }
409
        else if (c->current_size > size) {
410
                c->current_size = size;
411
        }
412

    
413
        if (c->metadata_size) {
414
                c->metadata = realloc(c->metadata, c->metadata_size * size);
415
                if (dif > 0) {
416
                        memset(c->metadata + c->metadata_size * c->cache_size, 0, c->metadata_size * dif);
417
                }
418
        }
419

    
420
        c->cache_size = size;
421

    
422
        return c->current_size;
423

    
424
}
425
  
426
struct peer_cache *merge_caches(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source)
427
{
428
  int n1, n2;
429
  struct peer_cache *new_cache;
430
  uint8_t *meta;
431

    
432
  new_cache = cache_init(newsize, c1->metadata_size);
433
  if (new_cache == NULL) {
434
    return NULL;
435
  }
436

    
437
  meta = new_cache->metadata;
438
  *source = 0;
439
  for (n1 = 0, n2 = 0; new_cache->current_size < new_cache->cache_size;) {
440
    if ((n1 == c1->current_size) && (n2 == c2->current_size)) {
441
      return new_cache;
442
    }
443
    if (n1 == c1->current_size) {
444
      if (in_cache(new_cache, &c2->entries[n2]) < 0) {
445
        if (new_cache->metadata_size) {
446
          memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
447
          meta += new_cache->metadata_size;
448
        }
449
        new_cache->entries[new_cache->current_size++] = c2->entries[n2];
450
        c2->entries[n2].id = NULL;
451
        *source |= 0x02;
452
      }
453
      n2++;
454
    } else if (n2 == c2->current_size) {
455
      if (in_cache(new_cache, &c1->entries[n1]) < 0) {
456
        if (new_cache->metadata_size) {
457
          memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
458
          meta += new_cache->metadata_size;
459
        }
460
        new_cache->entries[new_cache->current_size++] = c1->entries[n1];
461
        c1->entries[n1].id = NULL;
462
        *source |= 0x01;
463
      }
464
      n1++;
465
    } else {
466
      if (c2->entries[n2].timestamp > c1->entries[n1].timestamp) {
467
        if (in_cache(new_cache, &c1->entries[n1]) < 0) {
468
          if (new_cache->metadata_size) {
469
            memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
470
            meta += new_cache->metadata_size;
471
          }
472
          new_cache->entries[new_cache->current_size++] = c1->entries[n1];
473
          c1->entries[n1].id = NULL;
474
          *source |= 0x01;
475
        }
476
        n1++;
477
      } else {
478
        if (in_cache(new_cache, &c2->entries[n2]) < 0) {
479
          if (new_cache->metadata_size) {
480
            memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
481
            meta += new_cache->metadata_size;
482
          }
483
          new_cache->entries[new_cache->current_size++] = c2->entries[n2];
484
          c2->entries[n2].id = NULL;
485
          *source |= 0x02;
486
        }
487
        n2++;
488
      }
489
    }
490
  }
491

    
492
  return new_cache;
493
}