VNFs/DPPD-PROX/cdf.h

   1 /*
   2 // Copyright (c) 2010-2017 Intel Corporation
   3 //
   4 // Licensed under the Apache License, Version 2.0 (the "License");
   5 // you may not use this file except in compliance with the License.
   6 // You may obtain a copy of the License at
   7 //
   8 //     http://www.apache.org/licenses/LICENSE-2.0
   9 //
  10 // Unless required by applicable law or agreed to in writing, software
  11 // distributed under the License is distributed on an "AS IS" BASIS,
  12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 // See the License for the specific language governing permissions and
  14 // limitations under the License.
  15 */
  16
  17 struct cdf {
  18         uint32_t rand_max;
  19         uint32_t seed;
  20         uint32_t first_child;
  21         uint32_t elems[0];
  22 };
  23
  24 struct cdf *cdf_create(uint32_t n_vals, int socket_id);
  25 void cdf_add(struct cdf *cdf, uint32_t len);
  26 int cdf_setup(struct cdf *cdf);
  27
  28 static uint32_t cdf_sample(struct cdf *cdf)
  29 {
  30         uint32_t left_child, right_child;
  31         uint32_t rand;
  32
  33         do {
  34                 rand = rand_r(&cdf->seed);
  35         } while (rand > cdf->rand_max);
  36
  37         uint32_t cur = 1;
  38
  39         while (1) {
  40                 left_child = cur * 2;
  41                 right_child = cur * 2 + 1;
  42                 if (right_child < cdf->elems[0])
  43                         cur = rand > cdf->elems[cur]? right_child : left_child;
  44                 else if (left_child < cdf->elems[0])
  45                         cur = left_child;
  46                 else
  47                         return cur - cdf->first_child;
  48         }
  49 }