1                 : /*
       2                 :  * Copyright (c) 2012 The Native Client Authors. All rights reserved.
       3                 :  * Use of this source code is governed by a BSD-style license that can be
       4                 :  * found in the LICENSE file.
       5                 :  */
       6                 : 
       7                 : #include "native_client/src/shared/platform/nacl_log.h"
       8                 : #include "native_client/src/trusted/interval_multiset/nacl_interval_list.h"
       9                 : #include "native_client/src/trusted/interval_multiset/nacl_interval_list_intern.h"
      10                 : #include "native_client/src/trusted/interval_multiset/nacl_interval_multiset.h"
      11                 : 
      12                 : struct NaClIntervalNode {
      13                 :   struct NaClIntervalNode *next;
      14                 :   uint32_t range_left;
      15                 :   uint32_t range_right;
      16                 : };
      17                 : 
      18                 : struct NaClIntervalMultisetVtbl const kNaClIntervalListMultisetVtbl;  /* fwd */
      19                 : 
      20               4 : int NaClIntervalListMultisetCtor(struct NaClIntervalListMultiset *self) {
      21               4 :   self->intervals = NULL;
      22               4 :   self->base.vtbl = &kNaClIntervalListMultisetVtbl;
      23               4 :   return 1;
      24                 : }
      25                 : 
      26               4 : static void NaClIntervalListMultisetDtor(struct NaClIntervalMultiset *vself) {
      27               4 :   struct NaClIntervalListMultiset *self = (struct NaClIntervalListMultiset *)
      28                 :       vself;
      29               4 :   struct NaClIntervalNode *interval;
      30               4 :   struct NaClIntervalNode *next_interval;
      31                 : 
      32             578 :   for (interval = self->intervals; NULL != interval; interval = next_interval) {
      33             285 :     next_interval = interval->next;
      34             285 :     free(interval);
      35             285 :   }
      36               4 :   self->intervals = NULL;
      37                 : 
      38                 :   /* no base class dtor */
      39               4 :   self->base.vtbl = NULL;
      40               4 : }
      41                 : 
      42                 : static void NaClIntervalListMultisetAddInterval(
      43          211064 :     struct NaClIntervalMultiset *vself,
      44          211064 :     uint32_t first_val,
      45          211064 :     uint32_t last_val) {
      46          211064 :   struct NaClIntervalListMultiset *self = (struct NaClIntervalListMultiset *)
      47                 :       vself;
      48          211064 :   struct NaClIntervalNode *interval;
      49                 : 
      50          211064 :   interval = malloc(sizeof *interval);
      51          211064 :   if (NULL == interval) {
      52               0 :     NaClLog(LOG_FATAL, "No memory in NaClIntervalListSetAdd\n");
      53               0 :   }
      54          211064 :   interval->range_left = first_val;
      55          211064 :   interval->range_right = last_val;
      56          211064 :   interval->next = self->intervals;
      57          211064 :   self->intervals = interval;
      58          211064 : }
      59                 : 
      60                 : static void NaClIntervalListMultisetRemoveInterval(
      61          210779 :     struct NaClIntervalMultiset *vself,
      62          210779 :     uint32_t first_val,
      63          210779 :     uint32_t last_val) {
      64          210779 :   struct NaClIntervalListMultiset *self = (struct NaClIntervalListMultiset *)
      65                 :       vself;
      66          210779 :   struct NaClIntervalNode *p;
      67          210779 :   struct NaClIntervalNode **pp;
      68                 : 
      69        35922202 :   for (pp = &self->intervals; NULL != *pp; pp = &p->next) {
      70        17961101 :     p = *pp;
      71        18171880 :     if (p->range_left == first_val && last_val == p->range_right) {
      72          210779 :       *pp = p->next;
      73          210779 :       free(p);
      74          210779 :       return;
      75                 :     }
      76        17750322 :   }
      77               0 :   NaClLog(LOG_FATAL, "NaClIntervalListMultisetRemove: [%u,%u] not found\n",
      78                 :           first_val, last_val);
      79          210779 : }
      80                 : 
      81                 : static int NaClIntervalListMultisetOverlapsWith(
      82          632007 :     struct NaClIntervalMultiset *vself,
      83          632007 :     uint32_t first_val,
      84          632007 :     uint32_t last_val) {
      85          632007 :   struct NaClIntervalListMultiset *self = (struct NaClIntervalListMultiset *)
      86                 :       vself;
      87          632007 :   struct NaClIntervalNode *p;
      88                 : 
      89       148410242 :   for (p = self->intervals; NULL != p; p = p->next) {
      90       110801924 :     if (p->range_left <= last_val && first_val <= p->range_right) {
      91          279804 :       return 1;
      92                 :     }
      93        73573114 :   }
      94          352203 :   return 0;
      95          632007 : }
      96                 : 
      97                 : struct NaClIntervalMultisetVtbl const kNaClIntervalListMultisetVtbl = {
      98                 :   NaClIntervalListMultisetDtor,
      99                 :   NaClIntervalListMultisetAddInterval,
     100                 :   NaClIntervalListMultisetRemoveInterval,
     101                 :   NaClIntervalListMultisetOverlapsWith,
     102                 : };