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.18.1 lcov report (development 30499-74bdd0ac5b) Lines: 168 190 88.4 %
Date: 2025-09-16 09:24:07 Functions: 34 35 97.1 %
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; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : /********************************************************************/
      18             : /*                                                                  */
      19             : /*                    GENERAL HASHTABLES                            */
      20             : /*                                                                  */
      21             : /********************************************************************/
      22             : /* http://planetmath.org/encyclopedia/GoodHashTablePrimes.html */
      23             : static const ulong hashprimes[] = {
      24             :   53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613,
      25             :   393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
      26             :   100663319, 201326611, 402653189, 805306457, 1610612741
      27             : };
      28             : static const int hashprimes_len = numberof(hashprimes);
      29             : 
      30             : INLINE void
      31       61992 : setlen(hashtable *h, ulong len) {
      32       61992 :   h->maxnb = (ulong)ceil(len * 0.65);
      33       61992 :   h->len  = len;
      34       61992 : }
      35             : 
      36             : static int
      37       57089 : get_prime_index(ulong len)
      38             : {
      39             :   int i;
      40       88045 :   for (i=0; i < hashprimes_len; i++)
      41       88045 :     if (hashprimes[i] > len) return i;
      42           0 :   pari_err_OVERFLOW("hash table [too large]");
      43             :   return -1; /* LCOV_EXCL_LINE */
      44             : }
      45             : 
      46             : /* link hashentry e to hashtable h, setting e->hash / e->next */
      47             : INLINE void
      48     1797476 : hash_link2(hashtable *h, hashentry *e, ulong hash)
      49             : {
      50             :   ulong index;
      51     1797476 :   e->hash = hash; index = e->hash % h->len;
      52     1797476 :   e->next = h->table[index]; h->table[index] = e;
      53     1797476 : }
      54             : INLINE void
      55       16475 : hash_link(hashtable *h, hashentry *e) { hash_link2(h,e,h->hash(e->key));}
      56             : 
      57             : hashtable *
      58       41306 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
      59             :             int use_stack)
      60             : {
      61       41306 :   hashtable *h = (hashtable*)(use_stack? stack_malloc(sizeof(hashtable))
      62        3825 :                                        : pari_malloc(sizeof(hashtable)));
      63       41306 :   hash_init(h, minsize, hash, eq, use_stack); return h;
      64             : }
      65             : static ulong
      66      646675 : hash_id(void *x) { return (ulong)x; }
      67             : static int
      68      309191 : eq_id(void *x, void *y) { return x == y; }
      69             : hashtable *
      70        1288 : hash_create_ulong(ulong s, long stack)
      71        1288 : { return hash_create(s, &hash_id, &eq_id, stack); }
      72             : hashtable *
      73         259 : hash_create_INT(ulong s, long use_stack)
      74         259 : { return hash_create(s, (ulong(*)(void*))&hash_GEN,
      75             :                         (int(*)(void*,void*))&equalii, use_stack); }
      76             : hashtable *
      77       35262 : hash_create_GEN(ulong s, long use_stack)
      78       35262 : { return hash_create(s, (ulong(*)(void*))&hash_GEN,
      79             :                         (int(*)(void*,void*))&gidentical, use_stack); }
      80             : void
      81       57089 : hash_init(hashtable *h, ulong minsize, ulong (*hash)(void*),
      82             :                                        int (*eq)(void*,void*), int use_stack)
      83             : {
      84       57089 :   int i = get_prime_index(minsize);
      85       57089 :   ulong len = hashprimes[i];
      86       57089 :   if (use_stack)
      87       53264 :     h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
      88             :   else
      89        3825 :     h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
      90       57089 :   h->use_stack = use_stack;
      91       57089 :   h->pindex = i;
      92       57089 :   h->nb = 0;
      93       57089 :   h->hash = hash;
      94       57089 :   h->eq   = eq;
      95       57089 :   setlen(h, len);
      96       57089 : }
      97             : 
      98             : void
      99       12119 : hash_init_GEN(hashtable *h, ulong minsize, int (*eq)(GEN,GEN), int use_stack)
     100       12119 : { hash_init(h, minsize,(ulong (*)(void*)) hash_GEN,
     101             :                        (int (*)(void*,void*)) eq, use_stack);
     102       12119 : }
     103             : 
     104             : void
     105        3664 : hash_init_ulong(hashtable *h, ulong minsize, int use_stack)
     106        3664 : { hash_init(h, minsize,hash_id, eq_id, use_stack); }
     107             : 
     108             : void
     109     1781001 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
     110             : {
     111             :   hashentry *e;
     112             :   ulong index;
     113             : 
     114     1781001 :   if (h->use_stack)
     115     1771578 :     e = (hashentry*) stack_malloc(sizeof(hashentry));
     116             :   else
     117        9423 :     e = (hashentry*) pari_malloc(sizeof(hashentry));
     118             : 
     119     1781001 :   if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
     120             :   { /* double table size */
     121        4903 :     ulong i, newlen = hashprimes[++(h->pindex)];
     122             :     hashentry *E, **newtable;
     123        4903 :     if (h->use_stack)
     124        4903 :       newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
     125             :     else
     126           0 :       newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
     127     1372512 :     for (i = 0; i < h->len; i++)
     128     2259457 :       while ( (E = h->table[i]) )
     129             :       {
     130      891848 :         h->table[i] = E->next;
     131      891848 :         index = E->hash % newlen;
     132      891848 :         E->next = newtable[index];
     133      891848 :         newtable[index] = E;
     134             :       }
     135        4903 :     if (!h->use_stack) pari_free(h->table);
     136        4903 :     h->table = newtable;
     137        4903 :     setlen(h, newlen);
     138             :   }
     139     1781001 :   e->key = k;
     140     1781001 :   e->val = v; hash_link2(h, e, hash);
     141     1781001 : }
     142             : void
     143      792872 : hash_insert(hashtable *h, void *k, void *v)
     144      792872 : { hash_insert2(h,k,v,h->hash(k)); }
     145             : 
     146             : void
     147       54725 : hash_insert_long(hashtable *h, void *k, long v)
     148       54725 : { hash_insert2(h,k,(void*)v,h->hash(k)); }
     149             : 
     150             : /* the key 'k' may correspond to different values in the hash, return
     151             :  * one satisfying the selection callback */
     152             : hashentry *
     153          77 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
     154             : {
     155          77 :   ulong hash = h->hash(k);
     156          77 :   hashentry *e = h->table[ hash % h->len ];
     157         147 :   while (e)
     158             :   {
     159          91 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) return e;
     160          70 :     e = e->next;
     161             :   }
     162          56 :   return NULL;
     163             : }
     164             : 
     165             : GEN
     166        1294 : hash_keys(hashtable *h)
     167             : {
     168        1294 :   long k = 1;
     169             :   ulong i;
     170        1294 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     171      250196 :   for (i = 0; i < h->len; i++)
     172             :   {
     173      248902 :     hashentry *e = h->table[i];
     174      249970 :     while (e) { v[k++] = (long)e->key; e = e->next; }
     175             :   }
     176        1294 :   return v;
     177             : }
     178             : 
     179             : GEN
     180        3901 : hash_keys_GEN(hashtable *h)
     181             : {
     182        3901 :   long k = 1;
     183             :   ulong i;
     184        3901 :   GEN v = cgetg(h->nb+1, t_VEC);
     185      912940 :   for (i = 0; i < h->len; i++)
     186             :   {
     187      909039 :     hashentry *e = h->table[i];
     188     1303332 :     while (e) { gel(v,k++) = (GEN)e->key; e = e->next; }
     189             :   }
     190        3901 :   return v;
     191             : }
     192             : 
     193             : GEN
     194        2030 : hash_values(hashtable *h)
     195             : {
     196        2030 :   long k = 1;
     197             :   ulong i;
     198        2030 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     199      393820 :   for (i = 0; i < h->len; i++)
     200             :   {
     201      391790 :     hashentry *e = h->table[i];
     202      400000 :     while (e) { v[k++] = (long)e->val; e = e->next; }
     203             :   }
     204        2030 :   return v;
     205             : }
     206             : 
     207             : GEN
     208         420 : hash_values_GEN(hashtable *h)
     209             : {
     210         420 :   long k = 1;
     211             :   ulong i;
     212         420 :   GEN v = cgetg(h->nb+1, t_VEC);
     213       23604 :   for (i = 0; i < h->len; i++)
     214             :   {
     215       23184 :     hashentry *e = h->table[i];
     216       27818 :     while (e) { gel(v,k++) = (GEN)e->val; e = e->next; }
     217             :   }
     218         420 :   return v;
     219             : }
     220             : 
     221             : /* assume hash = h->hash(k) */
     222             : hashentry *
     223     3508063 : hash_search2(hashtable *h, void *k, ulong hash)
     224             : {
     225     3508063 :   hashentry *e = h->table[ hash % h->len ];
     226     4407969 :   while (e)
     227             :   {
     228     2861150 :     if (hash == e->hash && h->eq(k, e->key)) return e;
     229      899906 :     e = e->next;
     230             :   }
     231     1546819 :   return NULL; /* not found */
     232             : }
     233             : /* returns entry attached to key k or NULL */
     234             : hashentry *
     235     1667873 : hash_search(hashtable *h, void *k)
     236             : {
     237     1667873 :   if (h->nb == 0) return NULL;
     238     1661950 :   return hash_search2(h, k, h->hash(k));
     239             : }
     240             : 
     241             : int
     242      335509 : hash_haskey_long(hashtable *h, void *k, long *v)
     243             : {
     244      335509 :   hashentry * e = hash_search(h, k);
     245      335509 :   if (e) { *v = (long) e->val; return 1; }
     246       48138 :   else return 0;
     247             : }
     248             : 
     249             : GEN
     250      152437 : hash_haskey_GEN(hashtable *h, void *k)
     251             : {
     252      152437 :   hashentry * e = hash_search(h, k);
     253      152437 :   return e ? (GEN) e->val: NULL;
     254             : }
     255             : 
     256             : hashentry *
     257        3010 : hash_remove_select(hashtable *h, void *k, void *E,
     258             :   int (*select)(void*,hashentry*))
     259             : {
     260        3010 :   ulong hash = h->hash(k), index = hash % h->len;
     261        3010 :   hashentry **pE = &(h->table[index]), *e = *pE;
     262        3010 :   while (e)
     263             :   {
     264        3010 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
     265        3010 :       *pE = e->next; h->nb--;
     266        3010 :       return e;
     267             :     }
     268           0 :     pE = &(e->next);
     269           0 :     e = e->next;
     270             :   }
     271           0 :   return NULL;
     272             : }
     273             : 
     274             : hashentry *
     275          24 : hash_remove(hashtable *h, void *k)
     276             : {
     277          24 :   ulong hash = h->hash(k), index = hash % h->len;
     278          24 :   hashentry **pE = &(h->table[index]), *e = *pE;
     279          24 :   while (e)
     280             :   {
     281          24 :     if (hash == e->hash && h->eq(k, e->key)) {
     282          24 :       *pE = e->next; h->nb--;
     283          24 :       return e;
     284             :     }
     285           0 :     pE = &(e->next);
     286           0 :     e = e->next;
     287             :   }
     288           0 :   return NULL;
     289             : }
     290             : void
     291        3780 : hash_destroy(hashtable *h)
     292             : {
     293             :   ulong i;
     294        3780 :   if (h->use_stack) return;
     295      468720 :   for (i = 0; i < h->len; i++)
     296             :   {
     297      464940 :     hashentry *e = h->table[i];
     298      471309 :     while (e) { hashentry *f = e; e = e->next; pari_free(f); }
     299             :   }
     300        3780 :   pari_free(h->table); pari_free(h);
     301             : }
     302             : 
     303             : static
     304       15862 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
     305             : hashtable *
     306        3825 : hash_create_str(ulong s, long stack)
     307        3825 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
     308             : 
     309             : hashtable *
     310          25 : hashstr_import_static(hashentry *e, ulong size)
     311             : {
     312          25 :   hashtable *h = hash_create_str(size, 0);
     313       16500 :   for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
     314          25 :   return h;
     315             : }
     316             : 
     317             : void
     318           0 : hash_dbg(hashtable *h)
     319             : {
     320           0 :   ulong n, Total = 0, Max = 0;
     321           0 :   hashentry *e, **table = h->table;
     322           0 :   for (n=0; n < h->len; n++)
     323             :   {
     324           0 :     ulong m=0;
     325           0 :     for (e=table[n]; e; e=e->next) m++;
     326           0 :     Total += m; if (Max < m) Max = m;
     327           0 :     pari_printf("%4ld:%2ld ",n,m);
     328           0 :     if (n%9 == 8) pari_putc('\n');
     329             :   }
     330           0 :   pari_printf("\nTotal = %ld, Max = %ld\n", Total, Max);
     331           0 : }
     332             : 
     333             : /********************************************************************/
     334             : /*                                                                  */
     335             : /*                          HASH FUNCTIONS                          */
     336             : /*                                                                  */
     337             : /********************************************************************/
     338             : 
     339             : INLINE ulong
     340   559554309 : glue(ulong h, ulong a) { return 404936533*h + a; }
     341             : ulong
     342   141623952 : hash_GEN(GEN x)
     343             : {
     344   141623952 :   ulong h = x[0] & ~CLONEBIT;
     345   141623952 :   long tx = typ(x), lx, i;
     346   141623952 :   switch(tx)
     347             :   { /* non recursive types */
     348    53443167 :     case t_INT:
     349    53443167 :       lx = lgefint(x);
     350    53443167 :       h &= TYPBITS;
     351   164993382 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     352    53443167 :       return h;
     353    69520270 :     case t_REAL:
     354             :     case t_STR:
     355             :     case t_VECSMALL:
     356    69520270 :       lx = lg(x);
     357   460834809 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     358    69520270 :       return h;
     359             :     /* one more special case */
     360           0 :     case t_LIST:
     361           0 :       x = list_data(x);
     362           0 :       if (!x) return h;
     363             :       /* fall through */
     364             :     default:
     365    18660515 :       lx = lg(x);
     366    19816105 :       for(i = 1; i < lontyp[tx]; i++) h = glue(h, x[i]);
     367    74101671 :       for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
     368    18660517 :       return h;
     369             :   }
     370             : }
     371             : ulong
     372       17507 : hash_zv(GEN x)
     373             : {
     374       17507 :   long i, lx = lg(x);
     375             :   ulong h;
     376       17507 :   if (lx == 1) return 0;
     377       15701 :   h = x[1];
     378      108514 :   for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     379       15701 :   return h;
     380             : }

Generated by: LCOV version 1.16