src/usymIdSet.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 ** usymIdSet.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 usymIdSet
  36 usymIdSet_new ()
  37 {
  38   return usymIdSet_undefined;
  39 }
  40
  41 static /*@notnull@*/ /*@only@*/ usymIdSet
  42 usymIdSet_newEmpty (void)
  43 {
  44   usymIdSet s = (usymIdSet) dmalloc (sizeof (*s));
  45
  46   s->entries = 0;
  47   s->nspace = usymIdSetBASESIZE;
  48   s->elements = (usymId *) dmalloc (sizeof (*s->elements) * usymIdSetBASESIZE);
  49
  50   return (s);
  51 }
  52
  53 static void
  54 usymIdSet_grow (/*@notnull@*/ usymIdSet s)
  55 {
  56   int i;
  57   usymId *newelements;
  58
  59   s->nspace = usymIdSetBASESIZE;
  60   newelements = (usymId *) dmalloc (sizeof (*newelements) * (s->entries + s->nspace));
  61
  62   for (i = 0; i < s->entries; i++)
  63     {
  64       newelements[i] = s->elements[i];
  65     }
  66
  67   sfree (s->elements);
  68   s->elements = newelements;
  69 }
  70
  71 /*@only@*/ usymIdSet
  72 usymIdSet_single (usymId t)
  73 {
  74   usymIdSet s = (usymIdSet) dmalloc (sizeof (*s));
  75
  76   s->entries = 1;
  77   s->nspace = usymIdSetBASESIZE - 1;
  78   s->elements = (usymId *) dmalloc (sizeof (*s->elements) * usymIdSetBASESIZE);
  79   s->elements[0] = t;
  80
  81   return (s);
  82 }
  83
  84 static usymIdSet
  85   usymIdSet_insert (/*@returned@*/ usymIdSet s, usymId el)
  86 {
  87   if (usymIdSet_isUndefined (s))
  88     {
  89       s = usymIdSet_newEmpty ();
  90     }
  91
  92   if (usymIdSet_member (s, el))
  93     {
  94       return s;
  95     }
  96   else
  97     {
  98       if (s->nspace <= 0)
  99         usymIdSet_grow (s);
 100       s->nspace--;
 101       s->elements[s->entries] = el;
 102       s->entries++;
 103       return s;
 104     }
 105 }
 106
 107 static usymIdSet
 108 usymIdSet_copy (/*@notnull@*/ usymIdSet s)
 109 {
 110   int size = s->entries + 1;
 111   usymIdSet t = (usymIdSet) dmalloc (sizeof (*t));
 112   int i;
 113
 114   t->entries = s->entries;
 115   t->nspace = 1;
 116   t->elements = (usymId *) dmalloc (sizeof (*t->elements) * size);
 117
 118   for (i = 0; i < s->entries; i++)
 119     {
 120       t->elements[i] = s->elements[i];
 121     }
 122
 123   return t;
 124 }
 125
 126 usymIdSet
 127 usymIdSet_add (usymIdSet s, usymId el)
 128 {
 129   if (usymIdSet_isDefined (s))
 130     {
 131       llassert (!usymIdSet_member (s, el));
 132
 133       return (usymIdSet_insert (usymIdSet_copy (s), el));
 134     }
 135   else
 136     {
 137       return (usymIdSet_single (el));
 138     }
 139 }
 140
 141 usymIdSet
 142 usymIdSet_removeFresh (/*@temp@*/ usymIdSet s, usymId el)
 143 {
 144   if (usymIdSet_isDefined (s))
 145     {
 146       usymIdSet t = usymIdSet_newEmpty ();
 147       int i;
 148
 149       for (i = 0; i < s->entries; i++)
 150         {
 151           if (!usymId_equal (el, s->elements[i]))
 152             {
 153               t = usymIdSet_insert (t, s->elements[i]);
 154             }
 155         }
 156
 157       return t;
 158     }
 159   else
 160     {
 161       return usymIdSet_undefined;
 162     }
 163 }
 164
 165 usymIdSet
 166 usymIdSet_newUnion (usymIdSet s1, usymIdSet s2)
 167 {
 168   usymIdSet t = usymIdSet_new ();
 169
 170   usymIdSet_elements (s1, current)
 171     {
 172       t = usymIdSet_insert (t, current);
 173     } end_usymIdSet_elements;
 174
 175   usymIdSet_elements (s2, current)
 176     {
 177       t = usymIdSet_insert (t, current);
 178     } end_usymIdSet_elements;
 179
 180   return t;
 181 }
 182
 183 /*
 184 ** returns a new usymIdSet comprised of all elements
 185 ** in s which are not in t.
 186 */
 187
 188 usymIdSet
 189 usymIdSet_subtract (usymIdSet s, usymIdSet t)
 190 {
 191   usymIdSet r = usymIdSet_new ();
 192
 193   usymIdSet_elements (s, current)
 194     {
 195       if (!usymIdSet_member (t, current))
 196         {
 197           r = usymIdSet_insert (r, current);
 198         }
 199     } end_usymIdSet_elements;
 200
 201   return r;
 202 }
 203
 204 bool
 205 usymIdSet_member (usymIdSet s, usymId el)
 206 {
 207   if (usymIdSet_isUndefined (s))
 208     {
 209       return FALSE;
 210     }
 211   else
 212     {
 213       int i;
 214
 215       for (i = 0; i < s->entries; i++)
 216         {
 217           if (usymId_equal (el, s->elements[i]))
 218             return TRUE;
 219         }
 220       return FALSE;
 221     }
 222 }
 223
 224 void
 225 usymIdSet_free (/*@only@*/ usymIdSet s)
 226 {
 227   if (!usymIdSet_isUndefined (s))
 228     {
 229       int i;
 230       for (i = 0; i < s->entries; i++)
 231         {
 232           /*      usymId_free (s->elements[i]); */
 233         }
 234
 235       sfree (s->elements);
 236       sfree (s);
 237     }
 238 }
 239
 240 cstring usymIdSet_dump (usymIdSet lset)
 241 {
 242   cstring st = cstring_undefined;
 243
 244   if (!usymIdSet_isUndefined (lset))
 245     {
 246       bool first = TRUE;
 247       int i;
 248
 249       for (i = 0; i < lset->entries; i++)
 250         {
 251           usymId current = lset->elements[i];
 252
 253           if (!usymId_isInvalid (current))
 254             {
 255               current = usymtab_convertId (current);
 256
 257               if (first)
 258                 {
 259                   st = message ("%d", current);
 260                   first = FALSE;
 261                 }
 262               else
 263                 {
 264                   st = message ("%q,%d", st, current);
 265                 }
 266             }
 267         }
 268     }
 269   return (st);
 270 }
 271
 272 /*
 273 ** end of list is '@' or '\0'
 274 */
 275
 276 usymIdSet
 277 usymIdSet_undump (char **s)
 278 {
 279   usymIdSet t = usymIdSet_new ();
 280   char *olds = *s;
 281   char c;
 282
 283
 284   while ((c = **s) != '\0' && c != '@' && c != '#' && c != '\n')
 285     {
 286       int tid = 0;
 287
 288       while (c != '@' && c != '#' && c != ',' && c != '\0' && c != '\n')
 289         {
 290           while (c >= '0' && c <= '9')
 291             {
 292               tid *= 10;
 293               tid += (int) (c - '0');
 294               (*s)++;
 295               c = **s;
 296             }
 297
 298           if (*s == olds)
 299             {
 300               llcontbug (message ("usymIdSet_undump: loop: %s",
 301                                   cstring_fromChars (*s)));
 302
 303               while (**s != '\0')
 304                 {
 305                   (*s)++;
 306                 }
 307
 308               /*@innerbreak@*/ break;
 309             }
 310
 311           olds = *s;
 312
 313           t = usymIdSet_insert (t, usymId_fromInt (tid));
 314         }
 315
 316       if (c == ',')
 317         {
 318           (*s)++;
 319         }
 320     }
 321
 322   return t;
 323 }
 324
 325 /*@only@*/ cstring
 326 usymIdSet_unparse (usymIdSet ll)
 327 {
 328   cstring s = cstring_undefined;
 329
 330   if (!usymIdSet_isUndefined (ll))
 331     {
 332       int i;
 333
 334       for (i = 0; i < ll->entries; i++)
 335         {
 336           usymId current = ll->elements[i];
 337
 338           if (i == 0)
 339             s = uentry_getName (usymtab_getGlobalEntry (current));
 340           else
 341             s = message ("%q, %q", s, uentry_getName (usymtab_getGlobalEntry (current)));
 342         }
 343     }
 344
 345   return s;
 346 }
 347
 348 int
 349 usymIdSet_compare (usymIdSet l1, usymIdSet l2)
 350 {
 351   if (usymIdSet_isUndefined (l1))
 352     {
 353       return (usymIdSet_size (l2) == 0 ? 0 : 1);
 354     }
 355
 356   if (usymIdSet_isUndefined (l2))
 357     {
 358       return (usymIdSet_size (l1) == 0 ? 0 : 1);
 359     }
 360
 361   {
 362     int li1 = l1->entries;
 363     int li2 = l2->entries;
 364     int leastelements = (li1 < li2) ? li1 : li2;
 365     int i = 0;
 366
 367     while (i < leastelements)
 368       {
 369         if (usymId_equal (l1->elements[i], l2->elements[i]))
 370           {
 371             i++;
 372           }
 373         else
 374           {
 375             if (l1->elements[i] > l2->elements[i])
 376               {
 377                 return 1;
 378               }
 379             else
 380               {
 381                 return -1;
 382               }
 383           }
 384       }
 385
 386     return (int_compare (li1, li2));
 387   }
 388 }