Function weight_based_sort

modules/drouting/drouting.c:2962–3017

sort based on the weight of the gws */

/* sort based on the weight of the gws */
static int weight_based_sort(pgw_list_t *pgwl, int size, unsigned short *idx)
{
	static unsigned short *running_sum = NULL;
	static unsigned short sum_buf_size = 0;

	unsigned int i, first, weight_sum, rand_no;

	/* populate the index array */
	for( i=0 ; i<size ; i++ ) idx[i] = i;
	first = 0;

	while (size-first>1) {
		resize_dr_sort_buffer( running_sum, sum_buf_size, size, err);
		/* calculate the running sum */
		for( i=first,weight_sum=0 ; i<size ; i++ ) {
			weight_sum += pgwl[ idx[i] ].weight ;
			running_sum[i] = weight_sum;
			LM_DBG("elem %d, weight=%d, sum=%d\n",i,
					pgwl[ idx[i] ].weight, running_sum[i]);
		}
		if (weight_sum) {
			/* randomly select number */
			rand_no = (unsigned int)(weight_sum*((double)rand()/((double)1+RAND_MAX)));
			LM_DBG("random number is %d\n",rand_no);
			/* select the element */
			for( i=first ; i<size ; i++ )
				if (running_sum[i]>rand_no) break;
			if (i==size) {
				LM_CRIT("bug in weight sort, first=%u, size=%u, rand_no=%u, total weight=%u\n",
					first, size, rand_no, weight_sum);
				for(i=first; i<size;i++)
					LM_CRIT("i %d, idx %u, weight %u, running sum %u\n",
						i, idx[i], pgwl[idx[i]].weight, running_sum[i]);
				/* try to recover here by picking the last gw */
				i = size - 1;
				// return -1;
			}
		} else {
			/* all remaining gateways have weight 0, treat them as equal
			   and randomly select one with uniform distribution */
			i = first + (unsigned int)((size - first) * ((double)rand() / ((double)RAND_MAX + 1.0)));
		}
		LM_DBG("selecting element %d with weight %d\n",
				idx[i], pgwl[ idx[i] ].weight);
		/* "i" is the selected element : swap it with first position and
		   retake alg without first elem */
		rand_no = idx[i];
		idx[i] = idx[first];
		idx[first] = rand_no;
		first ++;
	}

	return 0;
err:
	return -1;
}