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