Statistics
| Branch: | Revision:

grapes / som / TopologyManager / topocache.c @ 28399cdc

History | View | Annotate | Download (9.26 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
  if (c->current_size == c->cache_size) {
89
    return -2;
90
  }
91
  for (i = 0; i < c->current_size; i++) {
92
    if (nodeid_equal(c->entries[i].id, neighbour)) {
93
      return -1;
94
    }
95
    if ((f != NULL) && f(tmeta, meta, c->metadata+(c->metadata_size * i)) == 2) {
96
      pos++;
97
    }
98
  }
99
  if (meta_size) {
100
    memmove(c->metadata + (pos + 1) * meta_size, c->metadata + pos * meta_size, (c->current_size - pos) * meta_size);
101
    memcpy(c->metadata + pos * meta_size, meta, meta_size);
102
  }
103
  for (i = c->current_size; i > pos; i--) {
104
    c->entries[i] = c->entries[i - 1];
105
  }
106
  c->entries[pos].id = nodeid_dup(neighbour);
107
  c->entries[pos].timestamp = 1;
108
  c->current_size++;
109

    
110
  return c->current_size;
111
}
112

    
113
int cache_add(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size)
114
{
115
  return cache_add_ranked(c, neighbour, meta, meta_size, NULL, NULL);
116
}
117

    
118
int cache_del(struct peer_cache *c, struct nodeID *neighbour)
119
{
120
  int i;
121
  int found = 0;
122

    
123
  for (i = 0; i < c->current_size; i++) {
124
    if (nodeid_equal(c->entries[i].id, neighbour)) {
125
      nodeid_free(c->entries[i].id);
126
      c->current_size--;
127
      found = 1;
128
      if (c->metadata_size && (i < c->current_size)) {
129
        memmove(c->metadata + c->metadata_size * i,
130
                c->metadata + c->metadata_size * (i + 1),
131
                c->metadata_size * (c->current_size - i));
132
      }
133
    }
134
    if (found && (i < c->current_size)) {
135
      c->entries[i] = c->entries[i + 1];
136
    }
137
  }
138

    
139
  return c->current_size;
140
}
141

    
142
void cache_update_tout(struct peer_cache *c)
143
{
144
  int i;
145
  
146
  for (i = 0; i < c->current_size; i++) {
147
    if (c->entries[i].timestamp == MAX_TIMESTAMP) {
148
      int j = i;
149

    
150
      while(j < c->current_size && c->entries[j].id) {
151
        nodeid_free(c->entries[j].id);
152
        c->entries[j++].id = NULL;
153
      }
154
      c->current_size = i;        /* The cache is ordered by timestamp...
155
                                   all the other entries wiil be older than
156
                                   this one, so remove all of them
157
                                */
158
    } else {
159
      c->entries[i].timestamp++;
160
    }
161
  }
162
}
163

    
164
void cache_update(struct peer_cache *c)
165
{
166
  int i;
167
  
168
  for (i = 0; i < c->current_size; i++) {
169
      c->entries[i].timestamp++;
170
  }
171
}
172

    
173
struct peer_cache *cache_init(int n, int metadata_size)
174
{
175
  struct peer_cache *res;
176

    
177
  res = malloc(sizeof(struct peer_cache));
178
  if (res == NULL) {
179
    return NULL;
180
  }
181
  res->cache_size = n;
182
  res->current_size = 0;
183
  res->entries = malloc(sizeof(struct cache_entry) * n);
184
  if (res->entries == NULL) {
185
    free(res);
186

    
187
    return NULL;
188
  }
189
  
190
  memset(res->entries, 0, sizeof(struct cache_entry) * n);
191
  if (metadata_size) {
192
    res->metadata = malloc(metadata_size * n);
193
  } else {
194
    res->metadata = NULL;
195
  }
196

    
197
  if (res->metadata) {
198
    res->metadata_size = metadata_size;
199
    memset(res->metadata, 0, metadata_size * n);
200
  } else {
201
    res->metadata_size = 0;
202
  }
203

    
204
  return res;
205
}
206

    
207
void cache_free(struct peer_cache *c)
208
{
209
  int i;
210

    
211
  for (i = 0; i < c->current_size; i++) {
212
    if(c->entries[i].id) {
213
      nodeid_free(c->entries[i].id);
214
    }
215
  }
216
  free(c->entries);
217
  free(c->metadata);
218
  free(c);
219
}
220

    
221
static int in_cache(const struct peer_cache *c, const struct cache_entry *elem)
222
{
223
  int i;
224

    
225
  for (i = 0; i < c->current_size; i++) {
226
    if (nodeid_equal(c->entries[i].id, elem->id)) {
227
      return 1;
228
    }
229
  }
230

    
231
  return 0;
232
}
233

    
234
struct nodeID *rand_peer(struct peer_cache *c, void **meta)
235
{
236
  int j;
237

    
238
  if (c->current_size == 0) {
239
    return NULL;
240
  }
241
  j = ((double)rand() / (double)RAND_MAX) * c->current_size;
242

    
243
  if (meta) {
244
    *meta = c->metadata + (j * c->metadata_size);
245
  }
246

    
247
  return c->entries[j].id;
248
}
249

    
250
struct peer_cache *entries_undump(const uint8_t *buff, int size)
251
{
252
  struct peer_cache *res;
253
  int i = 0;
254
  const uint8_t *p = buff;
255
  uint8_t *meta;
256
  int cache_size, metadata_size;
257

    
258
  cache_size = int_rcpy(buff);
259
  metadata_size = int_rcpy(buff + 4);
260
  p = buff + 8;
261
  res = cache_init(cache_size, metadata_size);
262
  meta = res->metadata;
263
  while (p - buff < size) {
264
    int len;
265

    
266
    res->entries[i].timestamp = int_rcpy(p);
267
    p += sizeof(uint32_t);
268
    res->entries[i++].id = nodeid_undump(p, &len);
269
    p += len;
270
    if (metadata_size) {
271
      memcpy(meta, p, metadata_size);
272
      p += metadata_size;
273
      meta += metadata_size;
274
    }
275
  }
276
  res->current_size = i;
277
if (p - buff != size) { fprintf(stderr, "Waz!! %d != %d\n", (int)(p - buff), size); exit(-1);}
278

    
279
  return res;
280
}
281

    
282
int cache_header_dump(uint8_t *b, const struct peer_cache *c)
283
{
284
  int_cpy(b, c->cache_size);
285
  int_cpy(b + 4, c->metadata_size);
286

    
287
  return 8;
288
}
289

    
290
int entry_dump(uint8_t *b, struct peer_cache *c, int i, size_t max_write_size)
291
{
292
  int res;
293
  int size = 0;
294
 
295
  if (i && (i >= c->cache_size - 1)) {
296
    return 0;
297
  }
298
  int_cpy(b, c->entries[i].timestamp);
299
  size = +4;
300
  res = nodeid_dump(b + size, c->entries[i].id, max_write_size - size);
301
  if (res < 0 ) {
302
    fprintf (stderr,"cavolo1\n");
303
    return -1;
304
  }
305
  size += res;
306
  if (c->metadata_size) {
307
    if (c->metadata_size > max_write_size - size) {
308
      fprintf (stderr,"cavolo2\n");
309
      return -1;
310
    }
311
    memcpy(b + size, c->metadata + c->metadata_size * i, c->metadata_size);
312
    size += c->metadata_size;
313
  }
314

    
315
  return size;
316
}
317

    
318
struct peer_cache *merge_caches_ranked(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source, ranking_function rank, void *mymetadata)
319
{
320
  int n1, n2;
321
  struct peer_cache *new_cache;
322
  uint8_t *meta;
323

    
324
  new_cache = cache_init(newsize, c1->metadata_size);
325
  if (new_cache == NULL) {
326
    return NULL;
327
  }
328

    
329
  meta = new_cache->metadata;
330
  *source = 0;
331
  for (n1 = 0, n2 = 0; new_cache->current_size < new_cache->cache_size;) {
332
    if ((n1 == c1->current_size) && (n2 == c2->current_size)) {
333
      return new_cache;
334
    }
335
    if (n1 == c1->current_size) {
336
      if (!in_cache(new_cache, &c2->entries[n2])) {
337
        if (new_cache->metadata_size) {
338
          memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
339
          meta += new_cache->metadata_size;
340
        }
341
        new_cache->entries[new_cache->current_size++] = c2->entries[n2];
342
        c2->entries[n2].id = NULL;
343
        *source |= 0x02;
344
      }
345
      n2++;
346
    } else if (n2 == c2->current_size) {
347
      if (!in_cache(new_cache, &c1->entries[n1])) {
348
        if (new_cache->metadata_size) {
349
          memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
350
          meta += new_cache->metadata_size;
351
        }
352
        new_cache->entries[new_cache->current_size++] = c1->entries[n1];
353
        c1->entries[n1].id = NULL;
354
        *source |= 0x01;
355
      }
356
      n1++;
357
    } else {
358
      int nowFirst;
359

    
360
      nowFirst = 0;
361
      if (rank) {
362
        nowFirst = rank(mymetadata, c1->metadata + n1 * c1->metadata_size,
363
                        c2->metadata + n2 * c2->metadata_size);
364
      }
365
      if (nowFirst == 0) {
366
        nowFirst = c2->entries[n2].timestamp > c1->entries[n1].timestamp ? 1 : 2;
367
      }
368
      if (nowFirst == 1) {
369
        if (!in_cache(new_cache, &c1->entries[n1])) {
370
          if (new_cache->metadata_size) {
371
            memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
372
            meta += new_cache->metadata_size;
373
          }
374
          new_cache->entries[new_cache->current_size++] = c1->entries[n1];
375
          c1->entries[n1].id = NULL;
376
          *source |= 0x01;
377
        }
378
        n1++;
379
      } else {
380
        if (!in_cache(new_cache, &c2->entries[n2])) {
381
          if (new_cache->metadata_size) {
382
            memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
383
            meta += new_cache->metadata_size;
384
          }
385
          new_cache->entries[new_cache->current_size++] = c2->entries[n2];
386
          c2->entries[n2].id = NULL;
387
          *source |= 0x02;
388
        }
389
        n2++;
390
      }
391
    }
392
  }
393

    
394
  return new_cache;
395
}
396

    
397
struct peer_cache *merge_caches(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source)
398
{
399
  return merge_caches_ranked(c1, c2, newsize, source, NULL, NULL);
400
}