Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - map.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.0 lcov report (development 23332-367b47754) Lines: 215 219 98.2 %
Date: 2018-12-10 05:41:52 Functions: 27 27 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2015  The PARI group.
       2             : 
       3             : This file is part of the PARI package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : #define tvalue(i)  gmael(t,(i),1)
      18             : #define tleft(i)   mael3(t,(i),2,1)
      19             : #define tright(i)  mael3(t,(i),2,2)
      20             : #define theight(i) mael3(t,(i),2,3)
      21             : 
      22             : static GEN
      23        2366 : treesearch(GEN T, GEN x)
      24             : {
      25        2366 :   long i = 1;
      26        2366 :   GEN t = list_data(T);
      27        2366 :   if (!t || lg(t)==1) return NULL;
      28       24899 :   while (i)
      29             :   {
      30       20748 :     long c = cmp_universal(x, gel(tvalue(i),1));
      31       20748 :     if (!c) return tvalue(i);
      32       20181 :     i = c < 0 ? tleft(i): tright(i);
      33             :   }
      34        1792 :   return NULL;
      35             : }
      36             : 
      37             : static long
      38      205576 : treeparent_r(GEN t, GEN x, long i, long parent)
      39             : {
      40             :   long c;
      41      205576 :   if (i==0) return parent;
      42      205576 :   c = cmp_universal(x, gel(tvalue(i),1));
      43      205576 :   if (c < 0)
      44       94388 :     return treeparent_r(t,x,tleft(i),i);
      45      111188 :   else if (c > 0)
      46       90748 :     return treeparent_r(t,x,tright(i),i);
      47             :   else
      48       20440 :     return parent;
      49             : }
      50             : 
      51             : static void
      52         133 : treekeys(GEN t, long i, GEN V, long *n)
      53             : {
      54         133 :   if (i==0) return;
      55          56 :   treekeys(t, tleft(i), V, n);
      56          56 :   gel(V, ++*n) = gel(tvalue(i),1);
      57          56 :   treekeys(t, tright(i), V, n);
      58             : }
      59             : 
      60             : GEN
      61          21 : mapdomain_shallow(GEN T)
      62             : {
      63          21 :   GEN V, t = list_data(T);
      64          21 :   long n = 0;
      65          21 :   if (!t || lg(t)==1) return cgetg(1, t_VEC);
      66          21 :   V = cgetg(lg(t), t_VEC); treekeys(t, 1, V, &n); return V;
      67             : }
      68             : 
      69             : static void
      70       12600 : treemat(GEN t, long i, GEN V, long *n)
      71             : {
      72       12600 :   if (i==0) return;
      73        5985 :   treemat(t, tleft(i), V, n);
      74        5985 :   ++*n;
      75        5985 :   gmael(V, 1, *n) = gel(tvalue(i), 1);
      76        5985 :   gmael(V, 2, *n) = gel(tvalue(i), 2);
      77        5985 :   treemat(t, tright(i), V, n);
      78             : }
      79             : 
      80             : GEN
      81         637 : maptomat_shallow(GEN T)
      82             : {
      83         637 :   GEN V, t = list_data(T);
      84         637 :   long n = 0;
      85         637 :   if (!t || lg(t)==1) return cgetg(1, t_MAT);
      86         630 :   V = cgetg(3, t_MAT);
      87         630 :   gel(V,1) = cgetg(lg(t), t_COL);
      88         630 :   gel(V,2) = cgetg(lg(t), t_COL);
      89         630 :   treemat(t, 1, V, &n); return V;
      90             : }
      91             : 
      92             : static void
      93         497 : treemap_i_r(GEN t, long i, long a, long c, GEN p, GEN M)
      94             : {
      95         497 :   long b = (a+c)>>1;
      96         497 :   GEN x = mkvec2(gcopy(gmael(M, 1, p[b])), gcopy(gmael(M, 2, p[b])));
      97         497 :   if (a == c)
      98         210 :     gel(t, i) = mkvec2(x, mkvecsmall3(0, 0, 1));
      99         287 :   else if (a+1 == c)
     100             :   {
     101         147 :     treemap_i_r(t, i+1, a+1, c, p, M);
     102         147 :     gel(t, i) = mkvec2(x, mkvecsmall3(0, i+1, theight(i+1) + 1));
     103             :   }
     104             :   else
     105             :   {
     106         140 :     long l = i+1, r = l + b - a, h;
     107         140 :     treemap_i_r(t, l, a, b-1, p, M);
     108         140 :     treemap_i_r(t, r, b+1, c, p, M);
     109         140 :     h = maxss(theight(l), theight(r))+1;
     110         140 :     gel(t, i) = mkvec2(x, mkvecsmall3(l, r, h));
     111             :   }
     112         497 : }
     113             : 
     114             : static void
     115          70 : treemap_i(GEN t, GEN p, GEN M) { treemap_i_r(t, 1, 1, lg(p)-1, p, M); }
     116             : 
     117             : #define value(i)  gmael(list_data(T),(i),1)
     118             : #define left(i)   mael3(list_data(T),(i),2,1)
     119             : #define right(i)  mael3(list_data(T),(i),2,2)
     120             : #define height(i) mael3(list_data(T),(i),2,3)
     121             : 
     122             : static long
     123     3077578 : treeheight(GEN T, long i) { return i? height(i): 0; }
     124             : 
     125             : static void
     126          21 : change_leaf(GEN T, GEN x, long p)
     127             : {
     128          21 :   pari_sp av = avma;
     129          21 :   listput(T, mkvec2(x, gmael(list_data(T), p, 2)), p);
     130          21 :   set_avma(av);
     131          21 : }
     132             : 
     133             : static long
     134       50981 : new_leaf(GEN T, GEN x)
     135             : {
     136       50981 :   pari_sp av = avma;
     137       50981 :   listput(T, mkvec2(x, mkvecsmall3(0,0,1)), 0);
     138       50981 :   return gc_long(av, lg(list_data(T))-1);
     139             : }
     140             : 
     141             : static void
     142      809319 : fix_height(GEN T, long x)
     143      809319 : { height(x) = maxss(treeheight(T,left(x)), treeheight(T,right(x)))+1; }
     144             : static long
     145      729470 : treebalance(GEN T, long i)
     146      729470 : { return i ? treeheight(T,left(i)) - treeheight(T,right(i)): 0; }
     147             : 
     148             : static long
     149       21672 : rotright(GEN T, long y)
     150             : {
     151       21672 :   long x = left(y), t = right(x);
     152       21672 :   right(x) = y;
     153       21672 :   left(y)  = t;
     154       21672 :   fix_height(T, y);
     155       21672 :   fix_height(T, x);
     156       21672 :   return x;
     157             : }
     158             : 
     159             : static long
     160       22575 : rotleft(GEN T, long x)
     161             : {
     162       22575 :   long y = right(x), t = left(y);
     163       22575 :   left(y)  = x;
     164       22575 :   right(x) = t;
     165       22575 :   fix_height(T, x);
     166       22575 :   fix_height(T, y);
     167       22575 :   return y;
     168             : }
     169             : 
     170             : static long
     171      568708 : treeinsert_r(GEN T, GEN x, long i, long *d)
     172             : {
     173             :   long b, c;
     174      568708 :   if (i==0 || !list_data(T) || lg(list_data(T))==1) return new_leaf(T, x);
     175      517727 :   c = cmp_universal(gel(x,1), gel(value(i),1));
     176      517727 :   if (c < 0)
     177             :   {
     178      265048 :     long s = treeinsert_r(T, x, left(i), d);
     179      265048 :     if (s < 0) return s;
     180      265041 :     left(i) = s;
     181             :   }
     182      252679 :   else if (c > 0)
     183             :   {
     184      252658 :     long s = treeinsert_r(T, x, right(i), d);
     185      252658 :     if (s < 0) return s;
     186      252651 :     right(i) = s;
     187             :   }
     188          21 :   else return -i;
     189      517692 :   fix_height(T, i);
     190      517692 :   b = treebalance(T, i);
     191      517692 :   if (b > 1)
     192             :   {
     193       12061 :     if (*d > 0) left(i) = rotleft(T, left(i));
     194       12061 :     return rotright(T, i);
     195             :   }
     196      505631 :   if (b < -1)
     197             :   {
     198       11718 :     if (*d < 0) right(i) = rotright(T, right(i));
     199       11718 :     return rotleft(T, i);
     200             :   }
     201      493913 :   *d = c; return i;
     202             : }
     203             : 
     204             : static long
     205       51002 : treeinsert(GEN T, GEN x)
     206             : {
     207       51002 :   long c = 0, r = treeinsert_r(T, x, 1, &c);
     208             :   GEN d;
     209       51002 :   if (r < 0) return -r;
     210       50981 :   if (r == 1) return 0;
     211          98 :   d = list_data(T);
     212             :   /* By convention we want the root to be 1 */
     213          98 :   swap(gel(d,1), gel(d,r));
     214          98 :   if (left(1) == 1) left(1) = r;
     215           0 :   else if (right(1) == 1) right(1) = r;
     216           0 :   else pari_err_BUG("treeadd");
     217          98 :   return 0;
     218             : }
     219             : 
     220             : static long
     221      225029 : treedelete_r(GEN T, GEN x, long i, long *dead)
     222             : {
     223             :   long b, c;
     224      225029 :   if (i==0 || !list_data(T) || lg(list_data(T))==1) return -1;
     225      225022 :   c = cmp_universal(x, gel(value(i),1));
     226      225022 :   if (c < 0)
     227             :   {
     228      106694 :     long s = treedelete_r(T, x, left(i), dead);
     229      106694 :     if (s < 0) return s;
     230      106694 :     left(i) = s;
     231             :   }
     232      118328 :   else if (c > 0)
     233             :   {
     234       84959 :     long s = treedelete_r(T, x, right(i), dead);
     235       84959 :     if (s < 0) return s;
     236       84945 :     right(i) = s;
     237             :   }
     238             :   else
     239             :   {
     240       33369 :     *dead = i;
     241       33369 :     if (left(i)==0 && right(i)==0) return 0;
     242       16961 :     else if (left(i)==0) return right(i);
     243       12817 :     else if (right(i)==0) return left(i);
     244             :     else
     245             :     {
     246       11494 :       GEN v, d = list_data(T);
     247       11494 :       long j = right(i);
     248       11494 :       while (left(j)) j = left(j);
     249       11494 :       v = gel(value(j), 1);
     250       11494 :       right(i) = treedelete_r(T, v, right(i), dead);
     251       11494 :       swap(gel(d,i), gel(d,j));
     252       11494 :       lswap(left(i),left(j));
     253       11494 :       lswap(right(i),right(j));
     254       11494 :       lswap(height(i),height(j));
     255             :     }
     256             :   }
     257      203133 :   fix_height(T, i);
     258      203133 :   b = treebalance(T, i);
     259      203133 :   if (b > 1 && treebalance(T, left(i)) >= 0) return rotright(T, i);
     260      201579 :   if (b > 1 && treebalance(T, left(i)) < 0)
     261        1323 :   { left(i) = rotleft(T, left(i)); return rotright(T, i); }
     262      200256 :   if (b < -1 && treebalance(T, right(i)) <= 0) return rotleft(T,i);
     263      198121 :   if (b < -1 && treebalance(T, right(i)) > 0)
     264        1155 :   { right(i) = rotright(T, right(i)); return rotleft(T, i); }
     265      196966 :   return i;
     266             : }
     267             : 
     268             : static long
     269       21882 : treedelete(GEN T, GEN x)
     270             : {
     271       21882 :   long dead, l, r = treedelete_r(T, x, 1, &dead);
     272             :   GEN d;
     273       21882 :   if (r < 0) return 0;
     274       21875 :   d = list_data(T); /* != NULL and non-empty */
     275       21875 :   if (r > 1)
     276             :   { /* By convention we want the root to be 1 */
     277          42 :     swap(gel(d,1), gel(d,r));
     278          42 :     if (left(1) == 1) left(1) = r;
     279          28 :     else if (right(1) == 1) right(1) = r;
     280           0 :     else dead = r;
     281             :   }
     282             :   /* We want the dead to be last */
     283       21875 :   l = lg(d)-1;
     284       21875 :   if (dead != l)
     285             :   {
     286       20440 :     long p = treeparent_r(d, gel(value(l),1), 1, 0);
     287       20440 :     if (left(p) == l) left(p) = dead;
     288       10171 :     else if (right(p) == l) right(p) = dead;
     289           0 :     else pari_err_BUG("treedelete2");
     290       20440 :     swap(gel(d, dead),gel(d, l));
     291             :   }
     292       21875 :   listpop(T,0); return 1;
     293             : }
     294             : 
     295             : static int
     296       75313 : ismap(GEN T) { return typ(T) == t_LIST && list_typ(T) == t_LIST_MAP; }
     297             : 
     298             : void
     299       51002 : mapput(GEN T, GEN a, GEN b)
     300             : {
     301       51002 :   pari_sp av = avma;
     302       51002 :   GEN p = mkvec2(a, b);
     303             :   long i;
     304       51002 :   if (!ismap(T)) pari_err_TYPE("mapput",T);
     305       51002 :   i = treeinsert(T, p); if (i) change_leaf(T, p, i);
     306       51002 :   set_avma(av);
     307       51002 : }
     308             : 
     309             : void
     310       21896 : mapdelete(GEN T, GEN a)
     311             : {
     312       21896 :   pari_sp av = avma;
     313             :   long s;
     314       21896 :   if (!ismap(T)) pari_err_TYPE("mapdelete",T);
     315       21882 :   s = treedelete(T, a); set_avma(av);
     316       21882 :   if (!s) pari_err_COMPONENT("mapdelete", "not in", strtoGENstr("map"), a);
     317       21875 : }
     318             : 
     319             : GEN
     320         581 : mapget(GEN T, GEN a)
     321             : {
     322             :   GEN x;
     323         581 :   if (!ismap(T)) pari_err_TYPE("mapget",T);
     324         567 :   x = treesearch(T, a);
     325         567 :   if (!x) pari_err_COMPONENT("mapget", "not in", strtoGENstr("map"), a);
     326         560 :   return gcopy(gel(x, 2));
     327             : }
     328             : 
     329             : int
     330        1813 : mapisdefined(GEN T, GEN a, GEN *pt_z)
     331             : {
     332             :   GEN x;
     333        1813 :   if (!ismap(T)) pari_err_TYPE("mapisdefined",T);
     334        1799 :   x = treesearch(T, a); if (!x) return 0;
     335           7 :   if (pt_z) *pt_z = gcopy(gel(x, 2));
     336           7 :   return 1;
     337             : }
     338             : 
     339             : GEN
     340          14 : mapdomain(GEN T)
     341             : {
     342             :   long i, l;
     343             :   GEN V;
     344          14 :   if (!ismap(T)) pari_err_TYPE("mapdomain",T);
     345          14 :   V = mapdomain_shallow(T); l = lg(V);
     346          14 :   for (i = 1; i < l; i++) gel(V,i) = gcopy(gel(V,i));
     347          14 :   return V;
     348             : }
     349             : 
     350             : GEN
     351           7 : maptomat(GEN T)
     352             : {
     353             :   long i, l;
     354             :   GEN V;
     355           7 :   if (!ismap(T)) pari_err_TYPE("maptomat",T);
     356           7 :   V = maptomat_shallow(T); if (lg(V) == 1) return V;
     357           7 :   l = lgcols(V);
     358          28 :   for (i = 1; i < l; i++)
     359             :   {
     360          21 :     gcoeff(V,i,1) = gcopy(gcoeff(V,i,1));
     361          21 :     gcoeff(V,i,2) = gcopy(gcoeff(V,i,2));
     362             :   }
     363           7 :   return V;
     364             : }
     365             : 
     366             : GEN
     367         126 : gtomap(GEN x)
     368             : {
     369         126 :   if (!x) return mkmap();
     370          84 :   switch(typ(x))
     371             :   {
     372             :   case t_MAT:
     373             :     {
     374          77 :       long l = lg(x);
     375             :       GEN M, p;
     376          77 :       if (l == 1 || lgcols(x)==1) return mkmap();
     377          77 :       if (l != 3) pari_err_TYPE("Map",x);
     378          77 :       p = gen_indexsort_uniq(gel(x,1),(void*)&cmp_universal, cmp_nodata);
     379          77 :       l = lgcols(x);
     380          77 :       if (lg(p) != l)
     381           7 :         pari_err_DOMAIN("Map","x","is not",strtoGENstr("one-to-one"),x);
     382          70 :       M = cgetg(3, t_LIST);
     383          70 :       M[1] = evaltyp(t_LIST_MAP)|evallg(l-1);
     384          70 :       list_data(M) = cgetg(l, t_VEC);
     385          70 :       treemap_i(list_data(M), p, x);
     386          70 :       return M;
     387             :     }
     388             :   default:
     389           7 :     pari_err_TYPE("Map",x);
     390             :   }
     391             :   return NULL; /* LCOV_EXCL_LINE */
     392             : }

Generated by: LCOV version 1.13