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 - language - hash.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 24988-2584e74448) Lines: 152 174 87.4 %
Date: 2020-01-26 05:57:03 Functions: 29 30 96.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP 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             : #include "pari.h"
      14             : #include "paripriv.h"
      15             : 
      16             : /********************************************************************/
      17             : /*                                                                  */
      18             : /*                    GENERAL HASHTABLES                            */
      19             : /*                                                                  */
      20             : /********************************************************************/
      21             : /* http://planetmath.org/encyclopedia/GoodHashTablePrimes.html */
      22             : static const ulong hashprimes[] = {
      23             :   53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613,
      24             :   393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
      25             :   100663319, 201326611, 402653189, 805306457, 1610612741
      26             : };
      27             : static const int hashprimes_len = numberof(hashprimes);
      28             : 
      29             : INLINE void
      30       33478 : setlen(hashtable *h, ulong len) {
      31       33478 :   h->maxnb = (ulong)ceil(len * 0.65);
      32       33478 :   h->len  = len;
      33       33478 : }
      34             : 
      35             : static int
      36       31064 : get_prime_index(ulong len)
      37             : {
      38             :   int i;
      39       48973 :   for (i=0; i < hashprimes_len; i++)
      40       48973 :     if (hashprimes[i] > len) return i;
      41           0 :   pari_err_OVERFLOW("hash table [too large]");
      42             :   return -1; /* LCOV_EXCL_LINE */
      43             : }
      44             : 
      45             : /* link hashentry e to hashtable h, setting e->hash / e->next */
      46             : INLINE void
      47     1286855 : hash_link2(hashtable *h, hashentry *e, ulong hash)
      48             : {
      49             :   ulong index;
      50     1286855 :   e->hash = hash; index = e->hash % h->len;
      51     1286855 :   e->next = h->table[index]; h->table[index] = e;
      52     1286855 : }
      53             : INLINE void
      54       11862 : hash_link(hashtable *h, hashentry *e) { hash_link2(h,e,h->hash(e->key));}
      55             : 
      56             : hashtable *
      57       25851 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
      58             :             int use_stack)
      59             : {
      60       25851 :   int i = get_prime_index(minsize);
      61       25851 :   ulong len = hashprimes[i];
      62             :   hashtable *h;
      63             : 
      64       25851 :   if (use_stack)
      65             :   {
      66       22575 :     h = (hashtable*)stack_malloc(sizeof(hashtable));
      67       22575 :     h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
      68       22575 :     h->use_stack = 1;
      69             :   }
      70             :   else
      71             :   {
      72        3276 :     h = (hashtable*)pari_malloc(sizeof(hashtable));
      73        3276 :     h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
      74        3276 :     h->use_stack = 0;
      75             :   }
      76       25851 :   h->pindex = i;
      77       25851 :   h->nb = 0;
      78       25851 :   h->hash = hash;
      79       25851 :   h->eq   = eq;
      80       25851 :   setlen(h, len); return h;
      81             : }
      82             : static ulong
      83      340124 : hash_id(void *x) { return (ulong)x; }
      84             : static int
      85       22896 : eq_id(void *x, void *y) { return x == y; }
      86             : hashtable *
      87         966 : hash_create_ulong(ulong s, long stack)
      88         966 : { return hash_create(s, &hash_id, &eq_id, stack); }
      89             : 
      90             : void
      91        5213 : hash_init(hashtable *h, ulong minsize, ulong (*hash)(void*),
      92             :                                        int (*eq)(void*,void*), int use_stack)
      93             : {
      94        5213 :   int i = get_prime_index(minsize);
      95        5213 :   ulong len = hashprimes[i];
      96        5213 :   if (use_stack)
      97        5213 :     h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
      98             :   else
      99           0 :     h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
     100        5213 :   h->use_stack = use_stack;
     101        5213 :   h->pindex = i;
     102        5213 :   h->nb = 0;
     103        5213 :   h->hash = hash;
     104        5213 :   h->eq   = eq;
     105        5213 :   setlen(h, len);
     106        5213 : }
     107             : 
     108             : void
     109        4878 : hash_init_GEN(hashtable *h, ulong minsize, int (*eq)(GEN,GEN), int use_stack)
     110        4878 : { hash_init(h, minsize,(ulong (*)(void*)) hash_GEN,
     111             :                        (int (*)(void*,void*)) eq, use_stack);
     112        4878 : }
     113             : 
     114             : void
     115         335 : hash_init_ulong(hashtable *h, ulong minsize, int use_stack)
     116         335 : { hash_init(h, minsize,hash_id, eq_id, use_stack); }
     117             : 
     118             : void
     119     1274993 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
     120             : {
     121             :   hashentry *e;
     122             :   ulong index;
     123             : 
     124     1274993 :   if (h->use_stack)
     125     1266463 :     e = (hashentry*) stack_malloc(sizeof(hashentry));
     126             :   else
     127        8530 :     e = (hashentry*) pari_malloc(sizeof(hashentry));
     128             : 
     129     1274993 :   if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
     130             :   { /* double table size */
     131        2414 :     ulong i, newlen = hashprimes[++(h->pindex)];
     132             :     hashentry *E, **newtable;
     133        2414 :     if (h->use_stack)
     134        2414 :       newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
     135             :     else
     136           0 :       newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
     137     1181222 :     for (i = 0; i < h->len; i++)
     138     3125014 :       while ( (E = h->table[i]) )
     139             :       {
     140      767398 :         h->table[i] = E->next;
     141      767398 :         index = E->hash % newlen;
     142      767398 :         E->next = newtable[index];
     143      767398 :         newtable[index] = E;
     144             :       }
     145        2414 :     if (!h->use_stack) pari_free(h->table);
     146        2414 :     h->table = newtable;
     147        2414 :     setlen(h, newlen);
     148             :   }
     149     1274993 :   e->key = k;
     150     1274993 :   e->val = v; hash_link2(h, e, hash);
     151     1274993 : }
     152             : void
     153      579697 : hash_insert(hashtable *h, void *k, void *v)
     154      579697 : { hash_insert2(h,k,v,h->hash(k)); }
     155             : 
     156             : void
     157       15295 : hash_insert_long(hashtable *h, void *k, long v)
     158       15295 : { hash_insert2(h,k,(void*)v,h->hash(k)); }
     159             : 
     160             : /* the key 'k' may correspond to different values in the hash, return
     161             :  * one satisfying the selection callback */
     162             : hashentry *
     163          70 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
     164             : {
     165          70 :   ulong hash = h->hash(k);
     166          70 :   hashentry *e = h->table[ hash % h->len ];
     167         210 :   while (e)
     168             :   {
     169          91 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) return e;
     170          70 :     e = e->next;
     171             :   }
     172          49 :   return NULL;
     173             : }
     174             : 
     175             : GEN
     176        1492 : hash_keys(hashtable *h)
     177             : {
     178        1492 :   long k = 1;
     179             :   ulong i;
     180        1492 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     181      543302 :   for (i = 0; i < h->len; i++)
     182             :   {
     183      541810 :     hashentry *e = h->table[i];
     184      541810 :     while (e) { v[k++] = (long)e->key; e = e->next; }
     185             :   }
     186        1492 :   return v;
     187             : }
     188             : GEN
     189        1759 : hash_values(hashtable *h)
     190             : {
     191        1759 :   long k = 1;
     192             :   ulong i;
     193        1759 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     194      341246 :   for (i = 0; i < h->len; i++)
     195             :   {
     196      339487 :     hashentry *e = h->table[i];
     197      339487 :     while (e) { v[k++] = (long)e->val; e = e->next; }
     198             :   }
     199        1759 :   return v;
     200             : }
     201             : 
     202             : /* assume hash = h->hash(k) */
     203             : hashentry *
     204     2780713 : hash_search2(hashtable *h, void *k, ulong hash)
     205             : {
     206     2780713 :   hashentry *e = h->table[ hash % h->len ];
     207     6352725 :   while (e)
     208             :   {
     209     2447744 :     if (hash == e->hash && h->eq(k, e->key)) return e;
     210      791299 :     e = e->next;
     211             :   }
     212     1124268 :   return NULL; /* not found */
     213             : }
     214             : /* returns entry attached to key k or NULL */
     215             : hashentry *
     216     1334789 : hash_search(hashtable *h, void *k)
     217             : {
     218     1334789 :   if (h->nb == 0) return NULL;
     219     1333064 :   return hash_search2(h, k, h->hash(k));
     220             : }
     221             : 
     222             : int
     223       11004 : hash_haskey_long(hashtable *h, void *k, long *v)
     224             : {
     225       11004 :   hashentry * e = hash_search(h, k);
     226       11004 :   if (e) { *v = (long) e->val; return 1; }
     227        8883 :   else return 0;
     228             : }
     229             : 
     230             : GEN
     231      176487 : hash_haskey_GEN(hashtable *h, void *k)
     232             : {
     233      176487 :   hashentry * e = hash_search(h, k);
     234      176487 :   return e ? (GEN) e->val: NULL;
     235             : }
     236             : 
     237             : hashentry *
     238        2926 : hash_remove_select(hashtable *h, void *k, void *E,
     239             :   int (*select)(void*,hashentry*))
     240             : {
     241        2926 :   ulong hash = h->hash(k), index = hash % h->len;
     242        2926 :   hashentry **pE = &(h->table[index]), *e = *pE;
     243        5852 :   while (e)
     244             :   {
     245        2926 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
     246        2926 :       *pE = e->next; h->nb--;
     247        2926 :       return e;
     248             :     }
     249           0 :     pE = &(e->next);
     250           0 :     e = e->next;
     251             :   }
     252           0 :   return NULL;
     253             : }
     254             : 
     255             : hashentry *
     256           8 : hash_remove(hashtable *h, void *k)
     257             : {
     258           8 :   ulong hash = h->hash(k), index = hash % h->len;
     259           8 :   hashentry **pE = &(h->table[index]), *e = *pE;
     260          16 :   while (e)
     261             :   {
     262           8 :     if (hash == e->hash && h->eq(k, e->key)) {
     263           8 :       *pE = e->next; h->nb--;
     264           8 :       return e;
     265             :     }
     266           0 :     pE = &(e->next);
     267           0 :     e = e->next;
     268             :   }
     269           0 :   return NULL;
     270             : }
     271             : void
     272        3238 : hash_destroy(hashtable *h)
     273             : {
     274             :   ulong i;
     275        3238 :   if (h->use_stack) return;
     276      401512 :   for (i = 0; i < h->len; i++)
     277             :   {
     278      398274 :     hashentry *e = h->table[i];
     279      398274 :     while (e) { hashentry *f = e; e = e->next; pari_free(f); }
     280             :   }
     281        3238 :   pari_free(h->table); pari_free(h);
     282             : }
     283             : 
     284             : static
     285       14082 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
     286             : hashtable *
     287        3276 : hash_create_str(ulong s, long stack)
     288        3276 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
     289             : 
     290             : hashtable *
     291          18 : hashstr_import_static(hashentry *e, ulong size)
     292             : {
     293          18 :   hashtable *h = hash_create_str(size, 0);
     294          18 :   for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
     295          18 :   return h;
     296             : }
     297             : 
     298             : void
     299           0 : hash_dbg(hashtable *h)
     300             : {
     301           0 :   ulong n, Total = 0, Max = 0;
     302           0 :   hashentry *e, **table = h->table;
     303           0 :   for (n=0; n < h->len; n++)
     304             :   {
     305           0 :     ulong m=0;
     306           0 :     for (e=table[n]; e; e=e->next) m++;
     307           0 :     Total += m; if (Max < m) Max = m;
     308           0 :     pari_printf("%4ld:%2ld ",n,m);
     309           0 :     if (n%9 == 8) pari_putc('\n');
     310             :   }
     311           0 :   pari_printf("\nTotal = %ld, Max = %ld\n", Total, Max);
     312           0 : }
     313             : 
     314             : /********************************************************************/
     315             : /*                                                                  */
     316             : /*                          HASH FUNCTIONS                          */
     317             : /*                                                                  */
     318             : /********************************************************************/
     319             : 
     320             : INLINE ulong
     321   499650724 : glue(ulong h, ulong a) { return 404936533*h + a; }
     322             : ulong
     323   172705078 : hash_GEN(GEN x)
     324             : {
     325   172705078 :   ulong h = x[0] & ~CLONEBIT;
     326   172705078 :   long tx = typ(x), lx, i;
     327   172705078 :   switch(tx)
     328             :   { /* non recursive types */
     329             :     case t_INT:
     330    96807601 :       lx = lgefint(x);
     331    96807601 :       h &= TYPBITS;
     332    96807601 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     333    96807601 :       return h;
     334             :     case t_REAL:
     335             :     case t_STR:
     336             :     case t_VECSMALL:
     337    39845668 :       lx = lg(x);
     338    39845668 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     339    39845668 :       return h;
     340             :     /* one more special case */
     341             :     case t_LIST:
     342           0 :       x = list_data(x);
     343           0 :       if (!x) return h;
     344             :       /* fall through */
     345             :     default:
     346    36051809 :       if (lontyp[tx] == 2) { h = glue(h, x[1]); i = 2; } else i = 1;
     347    36051809 :       lx = lg(x);
     348    36051809 :       for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
     349    36051809 :       return h;
     350             :   }
     351             : }

Generated by: LCOV version 1.13