Statistics
| Branch: | Revision:

grapes / som / Scheduler / sched.c @ 8ab58ec7

History | View | Annotate | Download (10.9 KB)

1 8ab58ec7 Luca Abeni
/*
2
 *  Copyright (c) 2010 Csaba Kiraly
3
 *
4
 *  This is free software; see lgpl-2.1.txt
5
 */
6
7 4f4e8c34 Luca Abeni
#include <string.h>
8
#include <stdlib.h>
9
#include "scheduler_la.h"
10
11
#define MAX(A,B)    ((A)>(B) ? (A) : (B))
12
#define MIN(A,B)    ((A)<(B) ? (A) : (B))
13
14
/**
15
  * casted evaluator for generic use in generic selector functions
16
  */
17
typedef double (*evaluateFunction)(void*);
18
19
20
/**
21
  * qsort like sorting function to select the index of the N best, based on a given evaluator function
22
  * @TODO: randomize if tie
23
  */
24
void selectBestIndexes(double *weights,size_t weights_len,int *bests,size_t *bests_len){
25
  int e;
26
  int s=0;
27
  int s_max=*bests_len;
28
29
  for (e=0; e<weights_len; e++){
30
    //find insert position
31
    int i;
32
    for (i=0; i < s; i++) {
33
      if (weights[e] > weights[bests[i]]) break;
34
    }
35
36
    if (i<s_max) {
37
      memmove(&bests[i+1], &bests[i], sizeof(int)*(s_max-i-1)); //shift later ones
38
      s = MIN(s+1,s_max);
39
      //put new one in the list
40
      bests[i]=e;
41
    }
42
  }
43
44
  *bests_len = s;
45
}
46
47
/**
48
  * Select best N of K based using a given evaluator function
49
  */
50
void selectBests(size_t size,unsigned char *base, size_t nmemb, double(*evaluate)(void *),unsigned char *bests,size_t *bests_len){
51
  double weights[nmemb];
52
  int selected_index[*bests_len];
53
  int i;
54
  // calculate weights
55
  for (i=0; i<nmemb; i++){
56
     weights[i] = evaluate(base + size*i);
57
  }
58
  selectBestIndexes(weights,nmemb,selected_index,bests_len);
59
  
60
  // copy bests in their place
61
  for (i=0; i<*bests_len; i++){
62
     memcpy(bests + size*i, base + size*selected_index[i], size);
63
  }
64
  
65
}
66
67
/**
68
  * Select N of K with weigthed random choice, without replacement (multiple selection), based on a given evaluator function
69
  */
70
void selectWeighted(size_t size,unsigned char *base, size_t nmemb, double(*weight)(void *),unsigned char *selected,size_t *selected_len){
71
  int i,j,k;
72
  double weights[nmemb];
73
  double w_sum=0;
74
  double selected_index[nmemb];
75
  int s=0;
76
  int s_max = MIN (*selected_len, nmemb);;
77
78
  // calculate weights
79
  for (i=0; i<nmemb; i++){
80
     weights[i] = weight(base + size*i);
81
     w_sum += weights[i];
82
  }
83
84
  while (s < s_max) {
85
    // select one randomly
86
    double t = w_sum * (rand() / (RAND_MAX + 1.0));
87
    //search for it in the CDF
88
    double cdf = 0;
89
    for (j=0; j<nmemb; j++){
90
      cdf += weights[j];
91
      //printf("(%f <? %f\n",t,cdf);
92
      if (t < cdf) {
93
        int already_selected=0;
94
        for (k=0; k<s; k++) {
95
          if (selected_index[k] == j)  already_selected=1;
96
        }
97
        if (!already_selected){ 
98
          //printf("selected %d(%f) for %d\n",j,weights[j],k);
99
          memcpy(selected + size*s, base + size*j, size);
100
          selected_index[s++]=j;
101
        }
102
        break;
103
      }
104
    }
105
  }
106
  *selected_len=s;
107
}
108
109
/**
110
  * Select best N of K with the given ordering method
111
  */
112
void selectWithOrdering(SchedOrdering ordering, size_t size, unsigned char *base, size_t nmemb, double(*evaluate)(void *), unsigned char *selected,size_t *selected_len){
113
  if (ordering == SCHED_WEIGHTED) selectWeighted(size, base, nmemb, evaluate, selected, selected_len);
114
  else selectBests(size, base, nmemb, evaluate, selected, selected_len);
115
}
116
117
/**
118
  * Select best N of K peers with the given ordering method
119
  */
120
void selectPeers(SchedOrdering ordering, struct peer **peers, size_t peers_len, peerEvaluateFunction peerevaluate, struct peer **selected, size_t *selected_len ){
121
  selectWithOrdering(ordering, sizeof(peers[0]), (void*)peers, peers_len, (evaluateFunction)peerevaluate, (void*)selected, selected_len);
122
}
123
124
/**
125
  * Select best N of K chunks with the given ordering method
126
  */
127
void selectChunks(SchedOrdering ordering, struct chunk **chunks, size_t chunks_len, chunkEvaluateFunction chunkevaluate, struct chunk **selected, size_t *selected_len ){
128
  selectWithOrdering(ordering, sizeof(chunks[0]), (void*)chunks,chunks_len, (evaluateFunction)chunkevaluate, (void*)selected, selected_len);
129
}
130
131
/**
132
  * Select best N of K peer-chunk pairs with the given ordering method
133
  */
134
void selectPairs(SchedOrdering ordering, struct PeerChunk *pairs, size_t pairs_len, pairEvaluateFunction evaluate, struct PeerChunk *selected, size_t *selected_len ){
135
  selectWithOrdering(ordering, sizeof(pairs[0]), (void*)pairs, pairs_len, (evaluateFunction)evaluate, (void*)selected, selected_len);
136
}
137
138
139
/**
140
  * Filter a list of peers. Include a peer if the filter function is true with at least one of the given chunks
141
  */
142
void filterPeers2(struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,
143
                     struct peer **filteredpeers, size_t *filtered_len,        //out, inout
144
                     filterFunction filter){
145
  int p,c;
146
  int f=0;
147
  for (p=0; p<peers_len; p++){
148
    for (c=0; c<chunks_len; c++){
149
      if (!filter || filter(peers[p],chunks[c])) {
150
        filteredpeers[f++]=peers[p];
151
        break;
152
      }
153
    }
154
    if (*filtered_len==f) break;
155
  }
156
  *filtered_len=f;
157
}
158
159
/**
160
  * Filter a list of chunks. Include a chunk if the filter function is true with at least one of the given peers
161
  */
162
void filterChunks2(struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,
163
                     struct chunk **filtered, size_t *filtered_len,        //out, inout
164
                     filterFunction filter){
165
  int p,c;
166
  int f=0;
167
  for (c=0; c<chunks_len; c++){
168
    for (p=0; p<peers_len; p++){
169
      if (!filter || filter(peers[p],chunks[c])) {
170
        filtered[f++]=chunks[c];
171
        break;
172
      }
173
    }
174
    if (*filtered_len==f) break;
175
  }
176
  *filtered_len=f;
177
}
178
179
/**
180
  * Filter a list of peer-chunk pairs (in place)
181
  */
182
void filterPairs(struct PeerChunk *pairs, size_t *pairs_len,
183
                     filterFunction filter){
184
  int pc;
185
  int f=0;
186
  for (pc=0; pc<(*pairs_len); pc++){
187
    if (!filter || filter(pairs[pc].peer,pairs[pc].chunk)) {
188
      pairs[f++]=pairs[pc];
189
    }
190
  }
191
  *pairs_len=f;
192
}
193
194
/**
195
  * Select at most N of K peers, among those where filter is true with at least one of the chunks.
196
  */
197
void selectPeersForChunks(SchedOrdering ordering, struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
198
                     struct peer **selected, size_t *selected_len,        //out, inout
199
                     filterFunction filter,
200
                     peerEvaluateFunction evaluate){
201
202
  size_t filtered_len=peers_len;
203
  struct peer *filtered[filtered_len];
204
205
  filterPeers2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
206
207
  selectPeers(ordering, filtered, filtered_len, evaluate, selected, selected_len);
208
}
209
210
void selectChunksForPeers(SchedOrdering ordering, struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
211
                     struct chunk **selected, size_t *selected_len,        //out, inout
212
                     filterFunction filter,
213
                     chunkEvaluateFunction evaluate){
214
215
  size_t filtered_len=chunks_len;
216
  struct chunk *filtered[filtered_len];
217
218
  filterChunks2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
219
220
  selectChunks(ordering, filtered, filtered_len, evaluate, selected, selected_len);
221
}
222
223
224
void toPairsPeerFirst(struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
225
                     struct PeerChunk *pairs, size_t *pairs_len) {        //out, inout
226
  size_t p,c;
227
  size_t i=0;
228
  for (p=0; p<peers_len; p++){
229
    for (c=0; c<chunks_len; c++){
230
      pairs[i  ].peer  = peers[p];
231
      pairs[i++].chunk = chunks[c];
232
    }
233
    if (*pairs_len==i) break;
234
  }
235
  *pairs_len=i;
236
}
237
238
void toPairsChunkFirst(struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
239
                     struct PeerChunk *pairs, size_t *pairs_len) {        //out, inout
240
  size_t p,c;
241
  size_t i=0;
242
  for (c=0; c<chunks_len; c++){
243
    for (p=0; p<peers_len; p++){
244
      pairs[i  ].peer  = peers[p];
245
      pairs[i++].chunk = chunks[c];
246
    }
247
    if (*pairs_len==i) break;
248
  }
249
  *pairs_len=i;
250
}
251
252
void toPairs(struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
253
                     struct PeerChunk *pairs, size_t *pairs_len)        //out, inout
254
{
255
  toPairsChunkFirst(peers, peers_len, chunks, chunks_len, pairs, pairs_len);
256
}
257
258
/*----------------- scheduler_la implementations --------------*/
259
260
void schedSelectPeerFirst(SchedOrdering ordering, struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
261
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
262
                     filterFunction filter,
263
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate){
264
265
  size_t p_len=1;
266
  struct peer *p[p_len];
267
  size_t c_len=*selected_len;
268
  struct chunk *c[c_len];
269
  selectPeersForChunks(ordering, peers, peers_len, chunks, chunks_len, p, &p_len, filter, peerevaluate);
270
  selectChunksForPeers(ordering, p, p_len, chunks, chunks_len, c, &c_len, filter, chunkevaluate);
271
272
  toPairsPeerFirst(p,p_len,c,c_len,selected,selected_len);
273
}
274
275
void schedSelectChunkFirst(SchedOrdering ordering, struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
276
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
277
                     filterFunction filter,
278
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate){
279
280
  size_t p_len=*selected_len;
281
  struct peer *p[p_len];
282
  size_t c_len=1;
283
  struct chunk *c[c_len];
284
  selectChunksForPeers(ordering, peers, peers_len, chunks, chunks_len, c, &c_len, filter, chunkevaluate);
285
  selectPeersForChunks(ordering, peers, peers_len, c, c_len, p, &p_len, filter, peerevaluate);
286
287
  toPairsChunkFirst(p,p_len,c,c_len,selected,selected_len);
288
}
289
290
void schedSelectHybrid(SchedOrdering ordering, struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
291
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
292
                     filterFunction filter,
293
                     pairEvaluateFunction pairevaluate)
294
{
295
  size_t pairs_len=peers_len*chunks_len;
296
  struct PeerChunk pairs[pairs_len];
297
  toPairs(peers,peers_len,chunks,chunks_len,pairs,&pairs_len);
298
  filterPairs(pairs,&pairs_len,filter);
299
  selectPairs(ordering,pairs,pairs_len,pairevaluate,selected,selected_len);
300
}
301
302
303
peerEvaluateFunction peer_ev;
304
chunkEvaluateFunction chunk_ev;
305
double2op peerchunk_wc;
306
307
double combinedWeight(struct PeerChunk* pc){
308
  return peerchunk_wc(peer_ev(&pc->peer),chunk_ev(&pc->chunk));
309
}
310
311
/**
312
  * Convenience function for combining peer and chunk weights
313
  * not thread safe!
314
  */
315
void schedSelectComposed(SchedOrdering ordering, struct peer **peers, size_t peers_len, struct chunk **chunks, size_t chunks_len,         //in
316
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
317
                     filterFunction filter,
318
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate, double2op weightcombine)
319
{
320
  peer_ev=peerevaluate;
321
  chunk_ev=chunkevaluate;
322
  peerchunk_wc=weightcombine;
323
  schedSelectHybrid(ordering,peers,peers_len,chunks,chunks_len,selected,selected_len,filter,combinedWeight);
324
325
}