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 sortSet sortSet_new ()
  36 {
  37   sortSet s = (sortSet) dmalloc (sizeof (*s));
  38
  39   s->entries = 0;
  40   s->nspace = sortSetBASESIZE;
  41   s->elements = (sort *) dmalloc (sizeof (*s->elements) * sortSetBASESIZE);
  42
  43   return (s);
  44 }
  45
  46 static /*@notnull@*/ sortSet
  47 sortSet_predict (int size)
  48 {
  49   sortSet s = (sortSet) dmalloc (sizeof (*s));
  50
  51   s->entries = 0;
  52
  53   if (size > 0)
  54     {
  55       s->nspace = size;
  56       s->elements = (sort *) dmalloc (sizeof (*s->elements) * size);
  57     }
  58   else
  59     {
  60       s->nspace = 0;
  61       s->elements = NULL;
  62     }
  63
  64   return (s);
  65 }
  66
  67 static void
  68 sortSet_grow (/*@notnull@*/ sortSet s)
  69 {
  70   int i;
  71   sort *newelements;
  72
  73   s->nspace = sortSetBASESIZE;
  74   newelements = (sort *) dmalloc (sizeof (*newelements) * (s->entries + s->nspace));
  75
  76   if (newelements == (sort *) 0)
  77     {
  78       llfatalerror (cstring_makeLiteral ("sortSet_grow: out of memory!"));
  79     }
  80
  81   for (i = 0; i < s->entries; i++)
  82     {
  83       newelements[i] = s->elements[i];
  84     }
  85
  86   sfree (s->elements);
  87   s->elements = newelements;
  88 }
  89
  90 /*
  91 ** Ensures: if *e \in *s
  92 **          then unchanged (*s) & result = false
  93 **          else *s' = insert (*s, *e) & result = true
  94 ** Modifies: *s
  95 */
  96
  97 bool
  98 sortSet_insert (sortSet s, sort el)
  99 {
 100   llassert (sortSet_isDefined (s));
 101
 102   if (sortSet_member (s, el))
 103     {
 104       return FALSE;
 105     }
 106   else
 107     {
 108       if (s->nspace <= 0)
 109         sortSet_grow (s);
 110       s->nspace--;
 111       s->elements[s->entries] = el;
 112       s->entries++;
 113       return TRUE;
 114     }
 115 }
 116
 117 sort
 118 sortSet_choose (sortSet s)
 119 {
 120   llassert (sortSet_isDefined (s) && s->entries > 0);
 121   return (s->elements[0]);
 122 }
 123
 124 bool
 125 sortSet_member (sortSet s, sort el)
 126 {
 127   if (sortSet_isDefined (s))
 128     {
 129       int i;
 130
 131       for (i = 0; i < s->entries; i++)
 132         {
 133           if (sort_equal (el, s->elements[i]))
 134             {
 135               return TRUE;
 136             }
 137         }
 138     }
 139
 140   return FALSE;
 141 }
 142
 143 /*@only@*/ cstring
 144 sortSet_unparse (sortSet s)
 145 {
 146   return (message ("{ %q }", sortSet_unparseClean (s)));
 147 }
 148
 149 /*@only@*/ cstring
 150 sortSet_unparseClean (sortSet s)
 151 {
 152   cstring st = cstring_undefined;
 153
 154   if (sortSet_isDefined (s))
 155     {
 156       int i;
 157
 158       for (i = 0; i < s->entries; i++)
 159         {
 160           if (i == 0)
 161             {
 162               st = message ("%q%s", st, sort_unparseName (s->elements[i]));
 163             }
 164           else
 165             {
 166               st = message ("%q, %s", st, sort_unparseName (s->elements[i]));
 167             }
 168         }
 169     }
 170
 171   return st;
 172 }
 173
 174 /*@only@*/ cstring
 175 sortSet_unparseOr (sortSet s)
 176 {
 177   cstring st = cstring_undefined;
 178
 179   if (sortSet_isDefined (s))
 180     {
 181       int i;
 182       int last = s->entries - 1;
 183
 184       for (i = 0; i < s->entries; i++)
 185         {
 186           if (i == 0)
 187             {
 188               st = cstring_concatFree (st, sort_unparse (s->elements[i]));
 189             }
 190           else
 191             {
 192               if (i == last)
 193                 {
 194                   /* was sort_unparse ??? */
 195                   st = message ("%q or %q", st, sort_unparse (s->elements[i]));
 196                 }
 197               else
 198                 {
 199                   st = message ("%q, %q", st, sort_unparse (s->elements[i]));
 200                 }
 201             }
 202         }
 203     }
 204
 205   return st;
 206 }
 207
 208 void
 209 sortSet_free (sortSet s)
 210 {
 211   if (sortSet_isDefined (s))
 212     {
 213       sfree (s->elements);
 214       sfree (s);
 215     }
 216 }
 217
 218 /*@only@*/ sortSet
 219 sortSet_copy (sortSet s)
 220 {
 221   sortSet t = sortSet_predict (sortSet_size (s));
 222   int i;
 223
 224   if (sortSet_isDefined (s))
 225     {
 226       for (i = 0; i < sortSet_size (s); i++)
 227         {
 228           (void) sortSet_insert (t, s->elements[i]);
 229         }
 230     }
 231
 232   return t;
 233 }
 234
 235
 236