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                 :   struct NaClIntervalNode *interval;
      30                 :   struct NaClIntervalNode *next_interval;
      31                 : 
      32             810 :   for (interval = self->intervals; NULL != interval; interval = next_interval) {
      33             806 :     next_interval = interval->next;
      34             806 :     free(interval);
      35                 :   }
      36               4 :   self->intervals = NULL;
      37                 : 
      38                 :   /* no base class dtor */
      39               4 :   self->base.vtbl = NULL;
      40               4 : }
      41                 : 
      42          211838 : static void NaClIntervalListMultisetAddInterval(
      43                 :     struct NaClIntervalMultiset *vself,
      44                 :     uint32_t first_val,
      45                 :     uint32_t last_val) {
      46          211838 :   struct NaClIntervalListMultiset *self = (struct NaClIntervalListMultiset *)
      47                 :       vself;
      48                 :   struct NaClIntervalNode *interval;
      49                 : 
      50          211838 :   interval = malloc(sizeof *interval);
      51          211838 :   if (NULL == interval) {
      52               0 :     NaClLog(LOG_FATAL, "No memory in NaClIntervalListSetAdd\n");
      53                 :   }
      54          211838 :   interval->range_left = first_val;
      55          211838 :   interval->range_right = last_val;
      56          211838 :   interval->next = self->intervals;
      57          211838 :   self->intervals = interval;
      58          211838 : }
      59                 : 
      60          211032 : static void NaClIntervalListMultisetRemoveInterval(
      61                 :     struct NaClIntervalMultiset *vself,
      62                 :     uint32_t first_val,
      63                 :     uint32_t last_val) {
      64          211032 :   struct NaClIntervalListMultiset *self = (struct NaClIntervalListMultiset *)
      65                 :       vself;
      66                 :   struct NaClIntervalNode *p;
      67                 :   struct NaClIntervalNode **pp;
      68                 : 
      69        33959103 :   for (pp = &self->intervals; NULL != *pp; pp = &p->next) {
      70        33959103 :     p = *pp;
      71        33959103 :     if (p->range_left == first_val && last_val == p->range_right) {
      72          211032 :       *pp = p->next;
      73          211032 :       free(p);
      74          422064 :       return;
      75                 :     }
      76                 :   }
      77               0 :   NaClLog(LOG_FATAL, "NaClIntervalListMultisetRemove: [%u,%u] not found\n",
      78                 :           first_val, last_val);
      79                 : }
      80                 : 
      81          630980 : static int NaClIntervalListMultisetOverlapsWith(
      82                 :     struct NaClIntervalMultiset *vself,
      83                 :     uint32_t first_val,
      84                 :     uint32_t last_val) {
      85          630980 :   struct NaClIntervalListMultiset *self = (struct NaClIntervalListMultiset *)
      86                 :       vself;
      87                 :   struct NaClIntervalNode *p;
      88                 : 
      89        96782588 :   for (p = self->intervals; NULL != p; p = p->next) {
      90        96508037 :     if (p->range_left <= last_val && first_val <= p->range_right) {
      91          356429 :       return 1;
      92                 :     }
      93                 :   }
      94          274551 :   return 0;
      95                 : }
      96                 : 
      97                 : struct NaClIntervalMultisetVtbl const kNaClIntervalListMultisetVtbl = {
      98                 :   NaClIntervalListMultisetDtor,
      99                 :   NaClIntervalListMultisetAddInterval,
     100                 :   NaClIntervalListMultisetRemoveInterval,
     101                 :   NaClIntervalListMultisetOverlapsWith,
     102                 : };