Statistics
| Branch: | Revision:

grapes / src / Scheduler / sched.c @ d242a2c6

History | View | Annotate | Download (11 KB)

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

    
7
#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
struct iw {
15
  int index;
16
  double weight;
17
};
18

    
19
static int cmp_iw_reverse(const void *a, const void *b)
20
{
21
  const struct iw *a1 = (const struct iw *) a;
22
  const struct iw *b1 = (const struct iw *) b;
23
  return a1->weight==b1->weight ? 0 : (a1->weight<b1->weight ? 1 : -1);
24
}
25

    
26
/**
27
  * Select best N of K based using a given evaluator function
28
  */
29
void selectBests(size_t size,unsigned char *base, size_t nmemb, double(*evaluate)(void *),unsigned char *bests,size_t *bests_len){
30
  struct iw iws[nmemb];
31
  int i;
32

    
33
  // calculate weights
34
  for (i=0; i<nmemb; i++){
35
     iws[i].index = i;
36
     iws[i].weight = evaluate(base + size*i);
37
  }
38

    
39
  // sort in descending order
40
  qsort(iws, nmemb, sizeof(struct iw), cmp_iw_reverse);
41

    
42
  // ensure uniform random tie
43
  for (i=0; i<nmemb; i++){
44
    int j, k;
45
    for (j=i; j<nmemb && iws[i].weight == iws[j].weight; j++);
46
    for (k=i; k<j; k++){
47
      struct iw iwt = iws[k];
48
      int r = i + (rand() % (j-i));
49
      iws[k] = iws[r];
50
      iws[r] = iwt;
51
    }
52
  }
53

    
54
  *bests_len = MIN(*bests_len, nmemb);
55

    
56
  // copy bests in their place
57
  for (i=0; i<*bests_len; i++){
58
     memcpy(bests + size*i, base + size*iws[i].index, size);
59
  }
60
  
61
}
62

    
63
/**
64
  * Select N of K with weigthed random choice, without replacement (multiple selection), based on a given evaluator function
65
  */
66
void selectWeighted(size_t size,unsigned char *base, size_t nmemb, double(*weight)(void *),unsigned char *selected,size_t *selected_len){
67
  int i,j,k;
68
  double weights[nmemb];
69
  double w_sum=0;
70
  double selected_index[nmemb];
71
  int s=0;
72
  int s_max = MIN (*selected_len, nmemb);;
73

    
74
  // calculate weights
75
  for (i=0; i<nmemb; i++){
76
     weights[i] = weight(base + size*i);
77
     // weights should not be negative
78
     weights[i] = MAX (weights[i], 0);
79
     w_sum += weights[i];
80
  }
81

    
82
  // all weights shuold not be zero, but if if happens, do something
83
  if (w_sum == 0) {
84
    for (i=0; i<nmemb; i++){
85
      weights[i] = 1;
86
      w_sum += weights[i];
87
    }
88
  }
89

    
90
  while (s < s_max) {
91
    // select one randomly
92
    double t = w_sum * (rand() / (RAND_MAX + 1.0));
93
    //search for it in the CDF
94
    double cdf = 0;
95
    for (j=0; j<nmemb; j++){
96
      cdf += weights[j];
97
      //printf("(%f <? %f\n",t,cdf);
98
      if (t < cdf) {
99
        int already_selected=0;
100
        for (k=0; k<s; k++) {
101
          if (selected_index[k] == j)  already_selected=1;
102
        }
103
        if (!already_selected){ 
104
          //printf("selected %d(%f) for %d\n",j,weights[j],k);
105
          memcpy(selected + size*s, base + size*j, size);
106
          selected_index[s++]=j;
107
        }
108
        break;
109
      }
110
    }
111
  }
112
  *selected_len=s;
113
}
114

    
115
/**
116
  * Select best N of K with the given ordering method
117
  */
118
void selectWithOrdering(SchedOrdering ordering, size_t size, unsigned char *base, size_t nmemb, double(*evaluate)(void *), unsigned char *selected,size_t *selected_len){
119
  if (ordering == SCHED_WEIGHTED) selectWeighted(size, base, nmemb, evaluate, selected, selected_len);
120
  else selectBests(size, base, nmemb, evaluate, selected, selected_len);
121
}
122

    
123
/**
124
  * Select best N of K peers with the given ordering method
125
  */
126
void selectPeers(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, peerEvaluateFunction peerevaluate, schedPeerID *selected, size_t *selected_len ){
127
  selectWithOrdering(ordering, sizeof(peers[0]), (void*)peers, peers_len, (evaluateFunction)peerevaluate, (void*)selected, selected_len);
128
}
129

    
130
/**
131
  * Select best N of K chunks with the given ordering method
132
  */
133
void selectChunks(SchedOrdering ordering, schedChunkID *chunks, size_t chunks_len, chunkEvaluateFunction chunkevaluate, schedChunkID *selected, size_t *selected_len ){
134
  selectWithOrdering(ordering, sizeof(chunks[0]), (void*)chunks,chunks_len, (evaluateFunction)chunkevaluate, (void*)selected, selected_len);
135
}
136

    
137
/**
138
  * Select best N of K peer-chunk pairs with the given ordering method
139
  */
140
void selectPairs(SchedOrdering ordering, struct PeerChunk *pairs, size_t pairs_len, pairEvaluateFunction evaluate, struct PeerChunk *selected, size_t *selected_len ){
141
  selectWithOrdering(ordering, sizeof(pairs[0]), (void*)pairs, pairs_len, (evaluateFunction)evaluate, (void*)selected, selected_len);
142
}
143

    
144

    
145
/**
146
  * Filter a list of peers. Include a peer if the filter function is true with at least one of the given chunks
147
  */
148
void filterPeers2(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,
149
                     schedPeerID *filteredpeers, size_t *filtered_len,        //out, inout
150
                     filterFunction filter){
151
  int p,c;
152
  int f=0;
153
  for (p=0; p<peers_len; p++){
154
    for (c=0; c<chunks_len; c++){
155
      if (!filter || filter(peers[p],chunks[c])) {
156
        filteredpeers[f++]=peers[p];
157
        break;
158
      }
159
    }
160
    if (*filtered_len==f) break;
161
  }
162
  *filtered_len=f;
163
}
164

    
165
/**
166
  * Filter a list of chunks. Include a chunk if the filter function is true with at least one of the given peers
167
  */
168
void filterChunks2(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,
169
                     schedChunkID *filtered, size_t *filtered_len,        //out, inout
170
                     filterFunction filter){
171
  int p,c;
172
  int f=0;
173
  for (c=0; c<chunks_len; c++){
174
    for (p=0; p<peers_len; p++){
175
      if (!filter || filter(peers[p],chunks[c])) {
176
        filtered[f++]=chunks[c];
177
        break;
178
      }
179
    }
180
    if (*filtered_len==f) break;
181
  }
182
  *filtered_len=f;
183
}
184

    
185
/**
186
  * Filter a list of peer-chunk pairs (in place)
187
  */
188
void filterPairs(struct PeerChunk *pairs, size_t *pairs_len,
189
                     filterFunction filter){
190
  int pc;
191
  int f=0;
192
  for (pc=0; pc<(*pairs_len); pc++){
193
    if (!filter || filter(pairs[pc].peer,pairs[pc].chunk)) {
194
      pairs[f++]=pairs[pc];
195
    }
196
  }
197
  *pairs_len=f;
198
}
199

    
200
/**
201
  * Select at most N of K peers, among those where filter is true with at least one of the chunks.
202
  */
203
void selectPeersForChunks(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
204
                     schedPeerID *selected, size_t *selected_len,        //out, inout
205
                     filterFunction filter,
206
                     peerEvaluateFunction evaluate){
207

    
208
  size_t filtered_len=peers_len;
209
  schedPeerID filtered[filtered_len];
210

    
211
  filterPeers2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
212

    
213
  selectPeers(ordering, filtered, filtered_len, evaluate, selected, selected_len);
214
}
215

    
216
void selectChunksForPeers(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
217
                     schedChunkID *selected, size_t *selected_len,        //out, inout
218
                     filterFunction filter,
219
                     chunkEvaluateFunction evaluate){
220

    
221
  size_t filtered_len=chunks_len;
222
  schedChunkID filtered[filtered_len];
223

    
224
  filterChunks2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
225

    
226
  selectChunks(ordering, filtered, filtered_len, evaluate, selected, selected_len);
227
}
228

    
229

    
230
void toPairsPeerFirst(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
231
                     struct PeerChunk *pairs, size_t *pairs_len) {        //out, inout
232
  size_t p,c;
233
  size_t i=0;
234
  for (p=0; p<peers_len; p++){
235
    for (c=0; c<chunks_len; c++){
236
      pairs[i  ].peer  = peers[p];
237
      pairs[i++].chunk = chunks[c];
238
    }
239
    if (*pairs_len==i) break;
240
  }
241
  *pairs_len=i;
242
}
243

    
244
void toPairsChunkFirst(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
245
                     struct PeerChunk *pairs, size_t *pairs_len) {        //out, inout
246
  size_t p,c;
247
  size_t i=0;
248
  for (c=0; c<chunks_len; c++){
249
    for (p=0; p<peers_len; p++){
250
      pairs[i  ].peer  = peers[p];
251
      pairs[i++].chunk = chunks[c];
252
    }
253
    if (*pairs_len==i) break;
254
  }
255
  *pairs_len=i;
256
}
257

    
258
void toPairs(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
259
                     struct PeerChunk *pairs, size_t *pairs_len)        //out, inout
260
{
261
  toPairsChunkFirst(peers, peers_len, chunks, chunks_len, pairs, pairs_len);
262
}
263

    
264
/*----------------- scheduler_la implementations --------------*/
265

    
266
void schedSelectPeerFirst(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
267
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
268
                     filterFunction filter,
269
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate){
270

    
271
  size_t p_len=1;
272
  schedPeerID p[p_len];
273
  size_t c_len=*selected_len;
274
  schedChunkID c[c_len];
275
  selectPeersForChunks(ordering, peers, peers_len, chunks, chunks_len, p, &p_len, filter, peerevaluate);
276
  selectChunksForPeers(ordering, p, p_len, chunks, chunks_len, c, &c_len, filter, chunkevaluate);
277

    
278
  toPairsPeerFirst(p,p_len,c,c_len,selected,selected_len);
279
}
280

    
281
void schedSelectChunkFirst(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
282
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
283
                     filterFunction filter,
284
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate){
285

    
286
  size_t p_len=*selected_len;
287
  schedPeerID p[p_len];
288
  size_t c_len=1;
289
  schedChunkID c[c_len];
290
  selectChunksForPeers(ordering, peers, peers_len, chunks, chunks_len, c, &c_len, filter, chunkevaluate);
291
  selectPeersForChunks(ordering, peers, peers_len, c, c_len, p, &p_len, filter, peerevaluate);
292

    
293
  toPairsChunkFirst(p,p_len,c,c_len,selected,selected_len);
294
}
295

    
296
void schedSelectHybrid(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
297
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
298
                     filterFunction filter,
299
                     pairEvaluateFunction pairevaluate)
300
{
301
  size_t pairs_len=peers_len*chunks_len;
302
  struct PeerChunk pairs[pairs_len];
303
  toPairs(peers,peers_len,chunks,chunks_len,pairs,&pairs_len);
304
  filterPairs(pairs,&pairs_len,filter);
305
  selectPairs(ordering,pairs,pairs_len,pairevaluate,selected,selected_len);
306
}
307

    
308

    
309
peerEvaluateFunction peer_ev;
310
chunkEvaluateFunction chunk_ev;
311
double2op peerchunk_wc;
312

    
313
double combinedWeight(struct PeerChunk* pc){
314
  return peerchunk_wc(peer_ev(&pc->peer),chunk_ev(&pc->chunk));
315
}
316

    
317
/**
318
  * Convenience function for combining peer and chunk weights
319
  * not thread safe!
320
  */
321
void schedSelectComposed(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
322
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
323
                     filterFunction filter,
324
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate, double2op weightcombine)
325
{
326
  peer_ev=peerevaluate;
327
  chunk_ev=chunkevaluate;
328
  peerchunk_wc=weightcombine;
329
  schedSelectHybrid(ordering,peers,peers_len,chunks,chunks_len,selected,selected_len,filter,combinedWeight);
330

    
331
}