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.16.1 lcov report (development 28886-849b48cf87) Lines: 160 183 87.4 %
Date: 2023-12-02 07:53:29 Functions: 30 31 96.8 %
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       40568 : setlen(hashtable *h, ulong len) {
      32       40568 :   h->maxnb = (ulong)ceil(len * 0.65);
      33       40568 :   h->len  = len;
      34       40568 : }
      35             : 
      36             : static int
      37       37455 : get_prime_index(ulong len)
      38             : {
      39             :   int i;
      40       60180 :   for (i=0; i < hashprimes_len; i++)
      41       60180 :     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     1416407 : hash_link2(hashtable *h, hashentry *e, ulong hash)
      49             : {
      50             :   ulong index;
      51     1416407 :   e->hash = hash; index = e->hash % h->len;
      52     1416407 :   e->next = h->table[index]; h->table[index] = e;
      53     1416407 : }
      54             : INLINE void
      55       16475 : hash_link(hashtable *h, hashentry *e) { hash_link2(h,e,h->hash(e->key));}
      56             : 
      57             : hashtable *
      58       27445 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
      59             :             int use_stack)
      60             : {
      61       27445 :   int i = get_prime_index(minsize);
      62       27445 :   ulong len = hashprimes[i];
      63             :   hashtable *h;
      64             : 
      65       27445 :   if (use_stack)
      66             :   {
      67       23788 :     h = (hashtable*)stack_malloc(sizeof(hashtable));
      68       23788 :     h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
      69       23788 :     h->use_stack = 1;
      70             :   }
      71             :   else
      72             :   {
      73        3657 :     h = (hashtable*)pari_malloc(sizeof(hashtable));
      74        3657 :     h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
      75        3657 :     h->use_stack = 0;
      76             :   }
      77       27445 :   h->pindex = i;
      78       27445 :   h->nb = 0;
      79       27445 :   h->hash = hash;
      80       27445 :   h->eq   = eq;
      81       27445 :   setlen(h, len); return h;
      82             : }
      83             : static ulong
      84      648957 : hash_id(void *x) { return (ulong)x; }
      85             : static int
      86      303332 : eq_id(void *x, void *y) { return x == y; }
      87             : hashtable *
      88        1057 : hash_create_ulong(ulong s, long stack)
      89        1057 : { return hash_create(s, &hash_id, &eq_id, stack); }
      90             : 
      91             : void
      92       10010 : hash_init(hashtable *h, ulong minsize, ulong (*hash)(void*),
      93             :                                        int (*eq)(void*,void*), int use_stack)
      94             : {
      95       10010 :   int i = get_prime_index(minsize);
      96       10010 :   ulong len = hashprimes[i];
      97       10010 :   if (use_stack)
      98       10010 :     h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
      99             :   else
     100           0 :     h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
     101       10010 :   h->use_stack = use_stack;
     102       10010 :   h->pindex = i;
     103       10010 :   h->nb = 0;
     104       10010 :   h->hash = hash;
     105       10010 :   h->eq   = eq;
     106       10010 :   setlen(h, len);
     107       10010 : }
     108             : 
     109             : void
     110        9005 : hash_init_GEN(hashtable *h, ulong minsize, int (*eq)(GEN,GEN), int use_stack)
     111        9005 : { hash_init(h, minsize,(ulong (*)(void*)) hash_GEN,
     112             :                        (int (*)(void*,void*)) eq, use_stack);
     113        9005 : }
     114             : 
     115             : void
     116        1005 : hash_init_ulong(hashtable *h, ulong minsize, int use_stack)
     117        1005 : { hash_init(h, minsize,hash_id, eq_id, use_stack); }
     118             : 
     119             : void
     120     1399932 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
     121             : {
     122             :   hashentry *e;
     123             :   ulong index;
     124             : 
     125     1399932 :   if (h->use_stack)
     126     1390992 :     e = (hashentry*) stack_malloc(sizeof(hashentry));
     127             :   else
     128        8940 :     e = (hashentry*) pari_malloc(sizeof(hashentry));
     129             : 
     130     1399932 :   if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
     131             :   { /* double table size */
     132        3113 :     ulong i, newlen = hashprimes[++(h->pindex)];
     133             :     hashentry *E, **newtable;
     134        3113 :     if (h->use_stack)
     135        3113 :       newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
     136             :     else
     137           0 :       newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
     138     1243426 :     for (i = 0; i < h->len; i++)
     139     2048111 :       while ( (E = h->table[i]) )
     140             :       {
     141      807798 :         h->table[i] = E->next;
     142      807798 :         index = E->hash % newlen;
     143      807798 :         E->next = newtable[index];
     144      807798 :         newtable[index] = E;
     145             :       }
     146        3113 :     if (!h->use_stack) pari_free(h->table);
     147        3113 :     h->table = newtable;
     148        3113 :     setlen(h, newlen);
     149             :   }
     150     1399932 :   e->key = k;
     151     1399932 :   e->val = v; hash_link2(h, e, hash);
     152     1399932 : }
     153             : void
     154      572501 : hash_insert(hashtable *h, void *k, void *v)
     155      572501 : { hash_insert2(h,k,v,h->hash(k)); }
     156             : 
     157             : void
     158       54690 : hash_insert_long(hashtable *h, void *k, long v)
     159       54690 : { hash_insert2(h,k,(void*)v,h->hash(k)); }
     160             : 
     161             : /* the key 'k' may correspond to different values in the hash, return
     162             :  * one satisfying the selection callback */
     163             : hashentry *
     164          70 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
     165             : {
     166          70 :   ulong hash = h->hash(k);
     167          70 :   hashentry *e = h->table[ hash % h->len ];
     168         140 :   while (e)
     169             :   {
     170          91 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) return e;
     171          70 :     e = e->next;
     172             :   }
     173          49 :   return NULL;
     174             : }
     175             : 
     176             : GEN
     177        2215 : hash_keys(hashtable *h)
     178             : {
     179        2215 :   long k = 1;
     180             :   ulong i;
     181        2215 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     182      781814 :   for (i = 0; i < h->len; i++)
     183             :   {
     184      779599 :     hashentry *e = h->table[i];
     185     1017691 :     while (e) { v[k++] = (long)e->key; e = e->next; }
     186             :   }
     187        2215 :   return v;
     188             : }
     189             : GEN
     190        1946 : hash_values(hashtable *h)
     191             : {
     192        1946 :   long k = 1;
     193             :   ulong i;
     194        1946 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     195      377524 :   for (i = 0; i < h->len; i++)
     196             :   {
     197      375578 :     hashentry *e = h->table[i];
     198      383361 :     while (e) { v[k++] = (long)e->val; e = e->next; }
     199             :   }
     200        1946 :   return v;
     201             : }
     202             : 
     203             : /* assume hash = h->hash(k) */
     204             : hashentry *
     205     3190309 : hash_search2(hashtable *h, void *k, ulong hash)
     206             : {
     207     3190309 :   hashentry *e = h->table[ hash % h->len ];
     208     4036909 :   while (e)
     209             :   {
     210     2794711 :     if (hash == e->hash && h->eq(k, e->key)) return e;
     211      846600 :     e = e->next;
     212             :   }
     213     1242198 :   return NULL; /* not found */
     214             : }
     215             : /* returns entry attached to key k or NULL */
     216             : hashentry *
     217     1655591 : hash_search(hashtable *h, void *k)
     218             : {
     219     1655591 :   if (h->nb == 0) return NULL;
     220     1650333 :   return hash_search2(h, k, h->hash(k));
     221             : }
     222             : 
     223             : int
     224      335474 : hash_haskey_long(hashtable *h, void *k, long *v)
     225             : {
     226      335474 :   hashentry * e = hash_search(h, k);
     227      335474 :   if (e) { *v = (long) e->val; return 1; }
     228       48103 :   else return 0;
     229             : }
     230             : 
     231             : GEN
     232      151919 : hash_haskey_GEN(hashtable *h, void *k)
     233             : {
     234      151919 :   hashentry * e = hash_search(h, k);
     235      151919 :   return e ? (GEN) e->val: NULL;
     236             : }
     237             : 
     238             : hashentry *
     239        2954 : hash_remove_select(hashtable *h, void *k, void *E,
     240             :   int (*select)(void*,hashentry*))
     241             : {
     242        2954 :   ulong hash = h->hash(k), index = hash % h->len;
     243        2954 :   hashentry **pE = &(h->table[index]), *e = *pE;
     244        2954 :   while (e)
     245             :   {
     246        2954 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
     247        2954 :       *pE = e->next; h->nb--;
     248        2954 :       return e;
     249             :     }
     250           0 :     pE = &(e->next);
     251           0 :     e = e->next;
     252             :   }
     253           0 :   return NULL;
     254             : }
     255             : 
     256             : hashentry *
     257          24 : hash_remove(hashtable *h, void *k)
     258             : {
     259          24 :   ulong hash = h->hash(k), index = hash % h->len;
     260          24 :   hashentry **pE = &(h->table[index]), *e = *pE;
     261          24 :   while (e)
     262             :   {
     263          24 :     if (hash == e->hash && h->eq(k, e->key)) {
     264          24 :       *pE = e->next; h->nb--;
     265          24 :       return e;
     266             :     }
     267           0 :     pE = &(e->next);
     268           0 :     e = e->next;
     269             :   }
     270           0 :   return NULL;
     271             : }
     272             : void
     273        3612 : hash_destroy(hashtable *h)
     274             : {
     275             :   ulong i;
     276        3612 :   if (h->use_stack) return;
     277      447888 :   for (i = 0; i < h->len; i++)
     278             :   {
     279      444276 :     hashentry *e = h->table[i];
     280      450218 :     while (e) { hashentry *f = e; e = e->next; pari_free(f); }
     281             :   }
     282        3612 :   pari_free(h->table); pari_free(h);
     283             : }
     284             : 
     285             : static
     286       15764 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
     287             : hashtable *
     288        3657 : hash_create_str(ulong s, long stack)
     289        3657 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
     290             : 
     291             : hashtable *
     292          25 : hashstr_import_static(hashentry *e, ulong size)
     293             : {
     294          25 :   hashtable *h = hash_create_str(size, 0);
     295       16500 :   for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
     296          25 :   return h;
     297             : }
     298             : 
     299             : void
     300           0 : hash_dbg(hashtable *h)
     301             : {
     302           0 :   ulong n, Total = 0, Max = 0;
     303           0 :   hashentry *e, **table = h->table;
     304           0 :   for (n=0; n < h->len; n++)
     305             :   {
     306           0 :     ulong m=0;
     307           0 :     for (e=table[n]; e; e=e->next) m++;
     308           0 :     Total += m; if (Max < m) Max = m;
     309           0 :     pari_printf("%4ld:%2ld ",n,m);
     310           0 :     if (n%9 == 8) pari_putc('\n');
     311             :   }
     312           0 :   pari_printf("\nTotal = %ld, Max = %ld\n", Total, Max);
     313           0 : }
     314             : 
     315             : /********************************************************************/
     316             : /*                                                                  */
     317             : /*                          HASH FUNCTIONS                          */
     318             : /*                                                                  */
     319             : /********************************************************************/
     320             : 
     321             : INLINE ulong
     322   551846980 : glue(ulong h, ulong a) { return 404936533*h + a; }
     323             : ulong
     324   134493874 : hash_GEN(GEN x)
     325             : {
     326   134493874 :   ulong h = x[0] & ~CLONEBIT;
     327   134493874 :   long tx = typ(x), lx, i;
     328   134493874 :   switch(tx)
     329             :   { /* non recursive types */
     330    49991415 :     case t_INT:
     331    49991415 :       lx = lgefint(x);
     332    49991415 :       h &= TYPBITS;
     333   154302933 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     334    49991415 :       return h;
     335    67724838 :     case t_REAL:
     336             :     case t_STR:
     337             :     case t_VECSMALL:
     338    67724838 :       lx = lg(x);
     339   463627722 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     340    67724838 :       return h;
     341             :     /* one more special case */
     342           0 :     case t_LIST:
     343           0 :       x = list_data(x);
     344           0 :       if (!x) return h;
     345             :       /* fall through */
     346             :     default:
     347    16777621 :       if (lontyp[tx] == 2) { h = glue(h, x[1]); i = 2; } else i = 1;
     348    16777621 :       lx = lg(x);
     349    67376545 :       for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
     350    16777622 :       return h;
     351             :   }
     352             : }
     353             : ulong
     354       17507 : hash_zv(GEN x)
     355             : {
     356       17507 :   long i, lx = lg(x);
     357             :   ulong h;
     358       17507 :   if (lx == 1) return 0;
     359       15701 :   h = x[1];
     360      108514 :   for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     361       15701 :   return h;
     362             : }

Generated by: LCOV version 1.14