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 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.10.0 lcov report (development 21059-cbe0d6a) Lines: 260 288 90.3 %
Date: 2017-09-22 06:24:58 Functions: 30 33 90.9 %
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, long mode)
      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       41496 :     long c = mode == 0 ? cmp_universal(x, tvalue(i)):
      31       20748 :                          cmp_universal(x, gel(tvalue(i),1));
      32       20748 :     if (c)
      33       20181 :       i = c < 0 ? tleft(i): tright(i);
      34             :     else
      35         567 :       return tvalue(i);
      36             :   }
      37        1792 :   return NULL;
      38             : }
      39             : 
      40             : static long
      41      205576 : treeparent_r(GEN t, GEN x, long i, long mode, long parent)
      42             : {
      43             :   long c;
      44      205576 :   if (i==0) return parent;
      45      411152 :   c = mode == 0 ? cmp_universal(x, tvalue(i)):
      46      205576 :                   cmp_universal(x, gel(tvalue(i),1));
      47      205576 :   if (c < 0)
      48       94388 :     return treeparent_r(t,x,tleft(i),mode,i);
      49      111188 :   else if (c > 0)
      50       90748 :     return treeparent_r(t,x,tright(i),mode,i);
      51             :   else
      52       20440 :     return parent;
      53             : }
      54             : 
      55             : static long
      56       20440 : treeparent(GEN T, GEN x, long mode)
      57             : {
      58       20440 :   GEN t = list_data(T);
      59       20440 :   return t ? treeparent_r(t, x, 1, mode, 0): 0;
      60             : }
      61             : 
      62             : static void
      63          98 : treekeys_r(GEN t, long i, GEN V, long *n, long mode)
      64             : {
      65         196 :   if (i==0) return;
      66          42 :   treekeys_r(t, tleft(i), V, n, mode);
      67          42 :   gel(V, ++*n) = gcopy(mode == 0 ? tvalue(i): gel(tvalue(i),1));
      68          42 :   treekeys_r(t, tright(i), V, n, mode);
      69             : }
      70             : 
      71             : static GEN
      72          14 : treekeys(GEN T, long mode)
      73             : {
      74          14 :   long n = 0;
      75          14 :   GEN t = list_data(T);
      76             :   GEN V;
      77          14 :   if (!t || lg(t)==1) return cgetg(1, t_VEC);
      78          14 :   V = cgetg(lg(t), t_VEC);
      79          14 :   treekeys_r(t, 1, V, &n, mode);
      80          14 :   return V;
      81             : }
      82             : 
      83             : static void
      84           0 : treekeys_i_r(GEN t, long i, GEN V, long *n, long mode)
      85             : {
      86           0 :   if (i==0) return;
      87           0 :   treekeys_i_r(t, tleft(i), V, n, mode);
      88           0 :   gel(V, ++*n) = mode == 0 ? tvalue(i): gel(tvalue(i),1);
      89           0 :   treekeys_r(t, tright(i), V, n, mode);
      90             : }
      91             : 
      92             : static GEN
      93           0 : treekeys_i(GEN T, long mode)
      94             : {
      95           0 :   long n = 0;
      96           0 :   GEN t = list_data(T);
      97             :   GEN V;
      98           0 :   if (!t || lg(t)==1) return cgetg(1, t_VEC);
      99           0 :   V = cgetg(lg(t), t_VEC);
     100           0 :   treekeys_i_r(t, 1, V, &n, mode);
     101           0 :   return V;
     102             : }
     103             : 
     104             : static void
     105        9660 : treemat_r(GEN t, long i, GEN V, long *n)
     106             : {
     107       19320 :   if (i==0) return;
     108        3962 :   treemat_r(t, tleft(i), V, n);
     109        3962 :   ++*n;
     110        3962 :   gmael(V, 1, *n) = gcopy(gel(tvalue(i), 1));
     111        3962 :   gmael(V, 2, *n) = gcopy(gel(tvalue(i), 2));
     112        3962 :   treemat_r(t, tright(i), V, n);
     113             : }
     114             : 
     115             : static GEN
     116           7 : treemat(GEN T)
     117             : {
     118           7 :   long n = 0;
     119           7 :   GEN t = list_data(T);
     120             :   GEN V;
     121           7 :   if (!t || lg(t)==1) return cgetg(1, t_MAT);
     122           7 :   V = cgetg(3, t_MAT);
     123           7 :   gel(V,1) = cgetg(lg(t), t_COL);
     124           7 :   gel(V,2) = cgetg(lg(t), t_COL);
     125           7 :   treemat_r(t, 1, V, &n);
     126           7 :   return V;
     127             : }
     128             : 
     129             : static void
     130        2317 : treemat_i_r(GEN t, long i, GEN V, long *n)
     131             : {
     132        4634 :   if (i==0) return;
     133        1729 :   treemat_i_r(t, tleft(i), V, n);
     134        1729 :   ++*n;
     135        1729 :   gmael(V, 1, *n) = gel(tvalue(i), 1);
     136        1729 :   gmael(V, 2, *n) = gel(tvalue(i), 2);
     137        1729 :   treemat_r(t, tright(i), V, n);
     138             : }
     139             : 
     140             : static GEN
     141         595 : treemat_i(GEN T)
     142             : {
     143         595 :   long n = 0;
     144         595 :   GEN t = list_data(T);
     145             :   GEN V;
     146         595 :   if (!t || lg(t)==1) return cgetg(1, t_MAT);
     147         588 :   V = cgetg(3, t_MAT);
     148         588 :   gel(V,1) = cgetg(lg(t), t_COL);
     149         588 :   gel(V,2) = cgetg(lg(t), t_COL);
     150         588 :   treemat_i_r(t, 1, V, &n);
     151         588 :   return V;
     152             : }
     153             : 
     154             : static void
     155         469 : treemap_i_r(GEN t, long i, long a, long c, GEN p, GEN M)
     156             : {
     157         469 :   long b = (a+c)>>1;
     158         469 :   GEN x = mkvec2(gcopy(gmael(M, 1, p[b])), gcopy(gmael(M, 2, p[b])));
     159         469 :   if (a == c)
     160         196 :     gel(t, i) = mkvec2(x, mkvecsmall3(0, 0, 1));
     161         273 :   else if (a+1 == c)
     162             :   {
     163         133 :     treemap_i_r(t, i+1, a+1, c, p, M);
     164         133 :     gel(t, i) = mkvec2(x, mkvecsmall3(0, i+1, theight(i+1) + 1));
     165             :   }
     166             :   else
     167             :   {
     168         140 :     long l = i+1, r = l + b - a, h;
     169         140 :     treemap_i_r(t, l, a, b-1, p, M);
     170         140 :     treemap_i_r(t, r, b+1, c, p, M);
     171         140 :     h = maxss(theight(l), theight(r))+1;
     172         140 :     gel(t, i) = mkvec2(x, mkvecsmall3(l, r, h));
     173             :   }
     174         469 : }
     175             : 
     176             : static void
     177          56 : treemap_i(GEN t, GEN p, GEN M)
     178             : {
     179          56 :   treemap_i_r(t, 1, 1, lg(p)-1, p, M);
     180          56 : }
     181             : 
     182             : #define value(i)  gmael(list_data(T),(i),1)
     183             : #define left(i)   mael3(list_data(T),(i),2,1)
     184             : #define right(i)  mael3(list_data(T),(i),2,2)
     185             : #define height(i) mael3(list_data(T),(i),2,3)
     186             : 
     187             : static long
     188     3077578 : treeheight(GEN T, long i)
     189     3077578 : { return i? height(i): 0; }
     190             : 
     191             : static void
     192          21 : change_leaf(GEN T, GEN x, long p)
     193             : {
     194          21 :   pari_sp av = avma;
     195          21 :   listput(T, mkvec2(x, gmael(list_data(T), p, 2)), p);
     196          21 :   avma = av;
     197          21 : }
     198             : 
     199             : static long
     200       50981 : new_leaf(GEN T, GEN x)
     201             : {
     202       50981 :   pari_sp av = avma;
     203       50981 :   listput(T, mkvec2(x, mkvecsmall3(0,0,1)), 0);
     204       50981 :   avma = av;
     205       50981 :   return lg(list_data(T))-1;
     206             : }
     207             : 
     208             : static void
     209      809319 : fix_height(GEN T, long x)
     210             : {
     211      809319 :   height(x) = maxss(treeheight(T,left(x)), treeheight(T,right(x)))+1;
     212      809319 : }
     213             : static long
     214      729470 : treebalance(GEN T, long i)
     215             : {
     216      729470 :   return i ? treeheight(T,left(i)) - treeheight(T,right(i)): 0;
     217             : }
     218             : 
     219             : static long
     220       21672 : rotright(GEN T, long y)
     221             : {
     222       21672 :   long x = left(y);
     223       21672 :   long t = right(x);
     224       21672 :   right(x) = y;
     225       21672 :   left(y)  = t;
     226       21672 :   fix_height(T, y);
     227       21672 :   fix_height(T, x);
     228       21672 :   return x;
     229             : }
     230             : 
     231             : static long
     232       22575 : rotleft(GEN T, long x)
     233             : {
     234       22575 :   long y = right(x);
     235       22575 :   long t = left(y);
     236       22575 :   left(y)  = x;
     237       22575 :   right(x) = t;
     238       22575 :   fix_height(T, x);
     239       22575 :   fix_height(T, y);
     240       22575 :   return y;
     241             : }
     242             : 
     243             : static long
     244      568708 : treeinsert_r(GEN T, GEN x, long i, long *d, long mode)
     245             : {
     246             :   long b, c;
     247      568708 :   if (i==0 || !list_data(T) || lg(list_data(T))==1)
     248       50981 :     return new_leaf(T, x);
     249     1035454 :   c = mode == 0 ? cmp_universal(x, value(i)):
     250      517727 :                   cmp_universal(gel(x,1), gel(value(i),1));
     251      517727 :   if (c < 0)
     252             :   {
     253      265048 :     long s = treeinsert_r(T, x, left(i), d, mode);
     254      265048 :     if (s < 0) return s;
     255      265041 :     left(i) = s;
     256             :   }
     257      252679 :   else if (c > 0)
     258             :   {
     259      252658 :     long s = treeinsert_r(T, x, right(i), d, mode);
     260      252658 :     if (s < 0) return s;
     261      252651 :     right(i) = s;
     262             :   }
     263          21 :   else return -i;
     264      517692 :   fix_height(T, i);
     265      517692 :   b = treebalance(T, i);
     266      517692 :   if (b > 1)
     267             :   {
     268       12061 :     if (*d > 0)
     269        6244 :       left(i) = rotleft(T, left(i));
     270       12061 :     return rotright(T, i);
     271             :   }
     272      505631 :   if (b < -1)
     273             :   {
     274       11718 :     if (*d < 0)
     275        5579 :       right(i) = rotright(T, right(i));
     276       11718 :     return rotleft(T, i);
     277             :   }
     278      493913 :   *d = c;
     279      493913 :   return i;
     280             : }
     281             : 
     282             : static long
     283       51002 : treeinsert(GEN T, GEN x, long mode)
     284             : {
     285             :   GEN d;
     286       51002 :   long c = 0;
     287       51002 :   long r = treeinsert_r(T, x, 1, &c, mode);
     288       51002 :   if (r < 0) return -r;
     289       50981 :   if (r == 1) return 0;
     290          98 :   d = list_data(T);
     291             :   /* By convention we want the root to be 1 */
     292          98 :   swap(gel(d,1), gel(d,r));
     293          98 :   if (left(1) == 1) left(1)=r;
     294           0 :   else if (right(1) == 1) right(1)=r;
     295           0 :   else pari_err_BUG("treeadd");
     296          98 :   return 0;
     297             : }
     298             : 
     299             : static long
     300      225029 : treedelete_r(GEN T, GEN x, long i, long mode, long *dead)
     301             : {
     302             :   long b, c;
     303      225029 :   if (i==0 || !list_data(T) || lg(list_data(T))==1)
     304           7 :     return -1;
     305      450044 :   c = mode == 0 ? cmp_universal(x, value(i)):
     306      225022 :                   cmp_universal(x, gel(value(i),1));
     307      225022 :   if (c < 0)
     308             :   {
     309      106694 :     long s = treedelete_r(T, x, left(i), mode, dead);
     310      106694 :     if (s < 0) return s;
     311      106694 :     left(i) = s;
     312             :   }
     313      118328 :   else if (c > 0)
     314             :   {
     315       84959 :     long s = treedelete_r(T, x, right(i), mode, dead);
     316       84959 :     if (s < 0) return s;
     317       84945 :     right(i) = s;
     318             :   }
     319             :   else
     320             :   {
     321       33369 :     *dead = i;
     322       33369 :     if (left(i)==0 && right(i)==0)
     323       16408 :       return 0;
     324       16961 :     else if (left(i)==0)
     325        4144 :       return right(i);
     326       12817 :     else if (right(i)==0)
     327        1323 :       return left(i);
     328             :     else
     329             :     {
     330             :       GEN v;
     331       11494 :       GEN d = list_data(T);
     332       11494 :       long j = right(i);
     333       11494 :       while (left(j)) j = left(j);
     334       11494 :       v = mode == 0 ? value(j): gel(value(j), 1);
     335       11494 :       right(i) = treedelete_r(T, v, right(i), mode, dead);
     336       11494 :       swap(gel(d,i), gel(d,j));
     337       11494 :       lswap(left(i),left(j));
     338       11494 :       lswap(right(i),right(j));
     339       11494 :       lswap(height(i),height(j));
     340             :     }
     341             :   }
     342      203133 :   fix_height(T, i);
     343      203133 :   b = treebalance(T, i);
     344      203133 :   if (b > 1 && treebalance(T, left(i)) >= 0)
     345        1554 :     return rotright(T, i);
     346      201579 :   if (b > 1 && treebalance(T, left(i)) < 0)
     347             :   {
     348        1323 :     left(i) = rotleft(T, left(i));
     349        1323 :     return rotright(T, i);
     350             :   }
     351      200256 :   if (b < -1 && treebalance(T, right(i)) <= 0)
     352        2135 :     return rotleft(T,i);
     353      198121 :   if (b < -1 && treebalance(T, right(i)) > 0)
     354             :   {
     355        1155 :     right(i) = rotright(T, right(i));
     356        1155 :     return rotleft(T, i);
     357             :   }
     358      196966 :   return i;
     359             : }
     360             : 
     361             : static long
     362       21882 : treedelete(GEN T, GEN x, long mode)
     363             : {
     364       21882 :   GEN  d = list_data(T);
     365             :   long dead, l;
     366       21882 :   long r = treedelete_r(T, x, 1, mode, &dead);
     367       21882 :   if (r < 0) return 0;
     368       21875 :   if (r > 1)
     369             :   {
     370             :     /* By convention we want the root to be 1 */
     371          42 :     swap(gel(d,1), gel(d,r));
     372          42 :     if (left(1) == 1) left(1) = r;
     373          28 :     else if (right(1) == 1) right(1) = r;
     374           0 :     else dead = r;
     375             :   }
     376             :   /* We want the dead to be last */
     377       21875 :   l = lg(d)-1;
     378       21875 :   if (dead != l)
     379             :   {
     380       20440 :     long p = treeparent(T, gel(value(l), 1), mode);
     381       20440 :     if (left(p) == l) left(p) = dead;
     382       10171 :     else if (right(p) == l) right(p) = dead;
     383           0 :     else pari_err_BUG("treedelete2");
     384       20440 :     swap(gel(d, dead),gel(d, l));
     385             :   }
     386       21875 :   listpop(T, 0);
     387       21875 :   return 1;
     388             : }
     389             : 
     390             : void
     391       51002 : mapput(GEN T, GEN a, GEN b)
     392             : {
     393       51002 :   pari_sp av = avma;
     394             :   long i;
     395             :   GEN p;
     396       51002 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     397           0 :     pari_err_TYPE("mapput",T);
     398       51002 :   p = mkvec2(a, b);
     399       51002 :   i = treeinsert(T, p, 1);
     400       51002 :   if (i) change_leaf(T, p, i);
     401       51002 :   avma = av;
     402       51002 : }
     403             : 
     404             : void
     405       21882 : mapdelete(GEN T, GEN a)
     406             : {
     407       21882 :   pari_sp av = avma;
     408             :   long s;
     409       21882 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     410           0 :     pari_err_TYPE("mapdelete",T);
     411       21882 :   s = treedelete(T, a, 1);
     412       21882 :   if (!s) pari_err_COMPONENT("mapdelete", "not in", strtoGENstr("map"), a);
     413       21875 :   avma = av;
     414       21875 : }
     415             : 
     416             : GEN
     417         567 : mapget(GEN T, GEN a)
     418             : {
     419             :   GEN x;
     420         567 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     421           0 :     pari_err_TYPE("mapget",T);
     422         567 :   x = treesearch(T, a, 1);
     423         567 :   if (!x) pari_err_COMPONENT("mapget", "not in", strtoGENstr("map"), a);
     424         560 :   return gcopy(gel(x, 2));
     425             : }
     426             : 
     427             : int
     428        1799 : mapisdefined(GEN T, GEN a, GEN *pt_z)
     429             : {
     430             :   GEN x;
     431        1799 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     432           0 :     pari_err_TYPE("mapisdefined",T);
     433        1799 :   x = treesearch(T, a, 1);
     434        1799 :   if (!x) return 0;
     435           7 :   if (pt_z) *pt_z = gcopy(gel(x, 2));
     436           7 :   return 1;
     437             : }
     438             : 
     439             : GEN
     440          14 : mapdomain(GEN T)
     441             : {
     442          14 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     443           0 :     pari_err_TYPE("mapdomain",T);
     444          14 :   return treekeys(T,1);
     445             : }
     446             : 
     447             : GEN
     448           0 : mapdomain_shallow(GEN T)
     449             : {
     450           0 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     451           0 :     pari_err_TYPE("mapdomain_shallow",T);
     452           0 :   return treekeys_i(T,1);
     453             : }
     454             : 
     455             : GEN
     456           7 : maptomat(GEN T)
     457             : {
     458           7 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     459           0 :     pari_err_TYPE("maptomat",T);
     460           7 :   return treemat(T);
     461             : }
     462             : 
     463             : GEN
     464         595 : maptomat_shallow(GEN T)
     465             : {
     466         595 :   if (typ(T)!=t_LIST || list_typ(T)!=t_LIST_MAP)
     467           0 :     pari_err_TYPE("maptomap_shallow",T);
     468         595 :   return treemat_i(T);
     469             : }
     470             : 
     471             : GEN
     472          98 : gtomap(GEN x)
     473             : {
     474          98 :   if (!x) return mkmap();
     475          63 :   switch(typ(x))
     476             :   {
     477             :   case t_MAT:
     478             :     {
     479          63 :       long n, l = lg(x);
     480             :       GEN M, p;
     481          63 :       if (l == 1 || lgcols(x)==1) return mkmap();
     482          63 :       if (l != 3) pari_err_TYPE("Map",x);
     483          63 :       p = gen_indexsort_uniq(gel(x,1),(void*)&cmp_universal, cmp_nodata);
     484          63 :       if (lg(p) != lgcols(x))
     485           7 :         pari_err_DOMAIN("Map","x","is not",strtoGENstr("one-to-one"),x);
     486          56 :       n = lg(p)-1;
     487          56 :       M = cgetg(3, t_LIST);
     488          56 :       M[1] = evaltyp(t_LIST_MAP)|evallg(n);
     489          56 :       list_data(M) = cgetg(n+1, t_VEC);
     490          56 :       treemap_i(list_data(M), p, x);
     491          56 :       return M;
     492             :     }
     493             :   default:
     494           0 :     pari_err_TYPE("Map",x);
     495             :   }
     496             :   return NULL; /* LCOV_EXCL_LINE */
     497             : }

Generated by: LCOV version 1.11