summaryrefslogtreecommitdiffstats
path: root/.gitignore
blob: f6ef061f9adcfe9aeb474079a913892ad34c52f8 (plain) 
1
2
3
4
5
6
7

*~
*.pyc
.*.sw?
.coverage
/docs_build/
/docs_output/
/releng/
t .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */ } 
/*
// Copyright (c) 2010-2017 Intel Corporation
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
*/

struct cdf {
	uint32_t rand_max;
	uint32_t seed;
	uint32_t first_child;
	uint32_t elems[0];
};

struct cdf *cdf_create(uint32_t n_vals, int socket_id);
void cdf_add(struct cdf *cdf, uint32_t len);
int cdf_setup(struct cdf *cdf);

static uint32_t cdf_sample(struct cdf *cdf)
{
	uint32_t left_child, right_child;
	uint32_t rand;

	do {
		rand = rand_r(&cdf->seed);
	} while (rand > cdf->rand_max);

	uint32_t cur = 1;

	while (1) {
		left_child = cur * 2;
		right_child = cur * 2 + 1;
		if (right_child < cdf->elems[0])
			cur = rand > cdf->elems[cur]? right_child : left_child;
		else if (left_child < cdf->elems[0])
			cur = left_child;
		else
			return cur - cdf->first_child;
	}
}