src/sortSet.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2003 University of Virginia,
   4 **         Massachusetts Institute of Technology
   5 **
   6 ** This program is free software; you can redistribute it and/or modify it
   7 ** under the terms of the GNU General Public License as published by the
   8 ** Free Software Foundation; either version 2 of the License, or (at your
   9 ** option) any later version.
  10 **
  11 ** This program is distributed in the hope that it will be useful, but
  12 ** WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 ** General Public License for more details.
  15 **
  16 ** The GNU General Public License is available from http://www.gnu.org/ or
  17 ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  18 ** MA 02111-1307, USA.
  19 **
  20 ** For information on splint: info@splint.org
  21 ** To report a bug: splint-bug@splint.org
  22 ** For more information: http://www.splint.org
  23 */
  24 /*
  25 ** sortSet.c
  26 **
  27 ** based on set_template.c
  28 **
  29 ** where T has T_equal (or change this) and T_unparse
  30 */
  31
  32 # include "splintMacros.nf"
  33 # include "basic.h"
  34
  35 /*@constant int sortSetBASESIZE;@*/
  36 # define sortSetBASESIZE MIDBASESIZE
  37
  38 sortSet sortSet_new (void)
  39 {
  40   sortSet s = (sortSet) dmalloc (sizeof (*s));
  41
  42   s->entries = 0;
  43   s->nspace = sortSetBASESIZE;
  44   s->elements = (sort *) dmalloc (sizeof (*s->elements) * sortSetBASESIZE);
  45
  46   return (s);
  47 }
  48
  49 static /*@notnull@*/ sortSet
  50 sortSet_predict (int size)
  51 {
  52   sortSet s = (sortSet) dmalloc (sizeof (*s));
  53
  54   s->entries = 0;
  55
  56   if (size > 0)
  57     {
  58       s->nspace = size;
  59       s->elements = (sort *) dmalloc (sizeof (*s->elements) * size);
  60     }
  61   else
  62     {
  63       s->nspace = 0;
  64       s->elements = NULL;
  65     }
  66
  67   return (s);
  68 }
  69
  70 static void
  71 sortSet_grow (/*@notnull@*/ sortSet s)
  72 {
  73   int i;
  74   sort *newelements;
  75
  76   s->nspace = sortSetBASESIZE;
  77   newelements = (sort *) dmalloc (sizeof (*newelements) * (s->entries + s->nspace));
  78
  79   if (newelements == (sort *) 0)
  80     {
  81       llfatalerror (cstring_makeLiteral ("sortSet_grow: out of memory!"));
  82     }
  83
  84   for (i = 0; i < s->entries; i++)
  85     {
  86       newelements[i] = s->elements[i];
  87     }
  88
  89   sfree (s->elements);
  90   s->elements = newelements;
  91 }
  92
  93 /*
  94 ** Ensures: if *e \in *s
  95 **          then unchanged (*s) & result = false
  96 **          else *s' = insert (*s, *e) & result = true
  97 ** Modifies: *s
  98 */
  99
 100 bool
 101 sortSet_insert (sortSet s, sort el)
 102 {
 103   llassert (sortSet_isDefined (s));
 104
 105   if (sortSet_member (s, el))
 106     {
 107       return FALSE;
 108     }
 109   else
 110     {
 111       if (s->nspace <= 0)
 112         sortSet_grow (s);
 113       s->nspace--;
 114       s->elements[s->entries] = el;
 115       s->entries++;
 116       return TRUE;
 117     }
 118 }
 119
 120 sort
 121 sortSet_choose (sortSet s)
 122 {
 123   llassert (sortSet_isDefined (s) && s->entries > 0);
 124   return (s->elements[0]);
 125 }
 126
 127 bool
 128 sortSet_member (sortSet s, sort el)
 129 {
 130   if (sortSet_isDefined (s))
 131     {
 132       int i;
 133
 134       for (i = 0; i < s->entries; i++)
 135         {
 136           if (sort_equal (el, s->elements[i]))
 137             {
 138               return TRUE;
 139             }
 140         }
 141     }
 142
 143   return FALSE;
 144 }
 145
 146 # ifdef DEADCODE
 147 /*@only@*/ cstring
 148 sortSet_unparse (sortSet s)
 149 {
 150   return (message ("{ %q }", sortSet_unparseClean (s)));
 151 }
 152 # endif /* DEADCODE */
 153
 154 /*@only@*/ cstring
 155 sortSet_unparseClean (sortSet s)
 156 {
 157   cstring st = cstring_undefined;
 158
 159   if (sortSet_isDefined (s))
 160     {
 161       int i;
 162
 163       for (i = 0; i < s->entries; i++)
 164         {
 165           if (i == 0)
 166             {
 167               st = message ("%q%s", st, sort_unparseName (s->elements[i]));
 168             }
 169           else
 170             {
 171               st = message ("%q, %s", st, sort_unparseName (s->elements[i]));
 172             }
 173         }
 174     }
 175
 176   return st;
 177 }
 178
 179 /*@only@*/ cstring
 180 sortSet_unparseOr (sortSet s)
 181 {
 182   cstring st = cstring_undefined;
 183
 184   if (sortSet_isDefined (s))
 185     {
 186       int i;
 187       int last = s->entries - 1;
 188
 189       for (i = 0; i < s->entries; i++)
 190         {
 191           if (i == 0)
 192             {
 193               st = cstring_concatFree (st, sort_unparse (s->elements[i]));
 194             }
 195           else
 196             {
 197               if (i == last)
 198                 {
 199                   /* was sort_unparse ??? */
 200                   st = message ("%q or %q", st, sort_unparse (s->elements[i]));
 201                 }
 202               else
 203                 {
 204                   st = message ("%q, %q", st, sort_unparse (s->elements[i]));
 205                 }
 206             }
 207         }
 208     }
 209
 210   return st;
 211 }
 212
 213 void
 214 sortSet_free (sortSet s)
 215 {
 216   if (sortSet_isDefined (s))
 217     {
 218       sfree (s->elements);
 219       sfree (s);
 220     }
 221 }
 222
 223 /*@only@*/ sortSet
 224 sortSet_copy (sortSet s)
 225 {
 226   sortSet t = sortSet_predict (sortSet_size (s));
 227   int i;
 228
 229   if (sortSet_isDefined (s))
 230     {
 231       for (i = 0; i < sortSet_size (s); i++)
 232         {
 233           (void) sortSet_insert (t, s->elements[i]);
 234         }
 235     }
 236
 237   return t;
 238 }
 239
 240
 241