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 - language - hash.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 21203-392a176) Lines: 124 156 79.5 %
Date: 2017-10-23 06:23:29 Functions: 23 26 88.5 %
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       19157 : setlen(hashtable *h, ulong len) {
      31       19157 :   h->maxnb = (ulong)ceil(len * 0.65);
      32       19157 :   h->len  = len;
      33       19157 : }
      34             : 
      35             : static int
      36       17145 : get_prime_index(ulong len)
      37             : {
      38             :   int i;
      39       27569 :   for (i=0; i < hashprimes_len; i++)
      40       27569 :     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      772805 : hash_link2(hashtable *h, hashentry *e, ulong hash)
      48             : {
      49             :   ulong index;
      50      772805 :   e->hash = hash; index = e->hash % h->len;
      51      772805 :   e->next = h->table[index]; h->table[index] = e;
      52      772805 : }
      53             : INLINE void
      54        7249 : hash_link(hashtable *h, hashentry *e) { hash_link2(h,e,h->hash(e->key));}
      55             : 
      56             : hashtable *
      57       17145 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
      58             :             int use_stack)
      59             : {
      60       17145 :   int i = get_prime_index(minsize);
      61       17145 :   ulong len = hashprimes[i];
      62             :   hashtable *h;
      63             : 
      64       17145 :   if (use_stack)
      65             :   {
      66       15596 :     h = (hashtable*)stack_malloc(sizeof(hashtable));
      67       15596 :     h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
      68       15596 :     h->use_stack = 1;
      69             :   }
      70             :   else
      71             :   {
      72        1549 :     h = (hashtable*)pari_malloc(sizeof(hashtable));
      73        1549 :     h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
      74        1549 :     h->use_stack = 0;
      75             :   }
      76       17145 :   h->pindex = i;
      77       17145 :   h->nb = 0;
      78       17145 :   h->hash = hash;
      79       17145 :   h->eq   = eq;
      80       17145 :   setlen(h, len); return h;
      81             : }
      82             : 
      83             : void
      84      765556 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
      85             : {
      86             :   hashentry *e;
      87             :   ulong index;
      88             : 
      89      765556 :   if (h->use_stack)
      90      757258 :     e = (hashentry*) stack_malloc(sizeof(hashentry));
      91             :   else
      92        8298 :     e = (hashentry*) pari_malloc(sizeof(hashentry));
      93             : 
      94      765556 :   if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
      95             :   { /* double table size */
      96        2012 :     ulong i, newlen = hashprimes[++(h->pindex)];
      97             :     hashentry *E, **newtable;
      98        2012 :     if (h->use_stack)
      99        2012 :       newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
     100             :     else
     101           0 :       newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
     102      734570 :     for (i = 0; i < h->len; i++)
     103     1942290 :       while ( (E = h->table[i]) )
     104             :       {
     105      477174 :         h->table[i] = E->next;
     106      477174 :         index = E->hash % newlen;
     107      477174 :         E->next = newtable[index];
     108      477174 :         newtable[index] = E;
     109             :       }
     110        2012 :     if (!h->use_stack) pari_free(h->table);
     111        2012 :     h->table = newtable;
     112        2012 :     setlen(h, newlen);
     113             :   }
     114      765556 :   e->key = k;
     115      765556 :   e->val = v; hash_link2(h, e, hash);
     116      765556 : }
     117             : void
     118      257524 : hash_insert(hashtable *h, void *k, void *v)
     119      257524 : { hash_insert2(h,k,v,h->hash(k)); }
     120             : 
     121             : /* the key 'k' may correspond to different values in the hash, return
     122             :  * one satisfying the selection callback */
     123             : hashentry *
     124          70 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
     125             : {
     126          70 :   ulong hash = h->hash(k);
     127          70 :   hashentry *e = h->table[ hash % h->len ];
     128         210 :   while (e)
     129             :   {
     130          91 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) return e;
     131          70 :     e = e->next;
     132             :   }
     133          49 :   return NULL;
     134             : }
     135             : 
     136             : GEN
     137         196 : hash_keys(hashtable *h)
     138             : {
     139         196 :   long k = 1;
     140             :   ulong i;
     141         196 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     142       31164 :   for (i = 0; i < h->len; i++)
     143             :   {
     144       30968 :     hashentry *e = h->table[i];
     145       30968 :     while (e) { v[k++] = (long)e->key; e = e->next; }
     146             :   }
     147         196 :   return v;
     148             : }
     149             : GEN
     150         140 : hash_values(hashtable *h)
     151             : {
     152         140 :   long k = 1;
     153             :   ulong i;
     154         140 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     155       27160 :   for (i = 0; i < h->len; i++)
     156             :   {
     157       27020 :     hashentry *e = h->table[i];
     158       27020 :     while (e) { v[k++] = (long)e->val; e = e->next; }
     159             :   }
     160         140 :   return v;
     161             : }
     162             : 
     163             : /* assume hash = h->hash(k) */
     164             : hashentry *
     165     2247557 : hash_search2(hashtable *h, void *k, ulong hash)
     166             : {
     167     2247557 :   hashentry *e = h->table[ hash % h->len ];
     168     5088490 :   while (e)
     169             :   {
     170     2162903 :     if (hash == e->hash && h->eq(k, e->key)) return e;
     171      593376 :     e = e->next;
     172             :   }
     173      678030 :   return NULL; /* not found */
     174             : }
     175             : /* returns entry attached to key k or NULL */
     176             : hashentry *
     177     1076121 : hash_search(hashtable *h, void *k)
     178             : {
     179     1076121 :   if (h->nb == 0) return NULL;
     180     1074826 :   return hash_search2(h, k, h->hash(k));
     181             : }
     182             : 
     183             : hashentry *
     184        3129 : hash_remove_select(hashtable *h, void *k, void *E,
     185             :   int (*select)(void*,hashentry*))
     186             : {
     187        3129 :   ulong hash = h->hash(k), index = hash % h->len;
     188        3129 :   hashentry **pE = &(h->table[index]), *e = *pE;
     189        6258 :   while (e)
     190             :   {
     191        3129 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
     192        3129 :       *pE = e->next; h->nb--;
     193        3129 :       return e;
     194             :     }
     195           0 :     pE = &(e->next);
     196           0 :     e = e->next;
     197             :   }
     198           0 :   return NULL;
     199             : }
     200             : 
     201             : hashentry *
     202           0 : hash_remove(hashtable *h, void *k)
     203             : {
     204           0 :   ulong hash = h->hash(k), index = hash % h->len;
     205           0 :   hashentry **pE = &(h->table[index]), *e = *pE;
     206           0 :   while (e)
     207             :   {
     208           0 :     if (hash == e->hash && h->eq(k, e->key)) {
     209           0 :       *pE = e->next; h->nb--;
     210           0 :       return e;
     211             :     }
     212           0 :     pE = &(e->next);
     213           0 :     e = e->next;
     214             :   }
     215           0 :   return NULL;
     216             : }
     217             : void
     218        1536 : hash_destroy(hashtable *h)
     219             : {
     220             :   ulong i;
     221        3072 :   if (h->use_stack) return;
     222      297984 :   for (i = 0; i < h->len; i++)
     223             :   {
     224      296448 :     hashentry *e = h->table[i];
     225      296448 :     while (e) { hashentry *f = e; e = e->next; pari_free(f); }
     226             :   }
     227        1536 :   pari_free(h->table); pari_free(h);
     228             : }
     229             : static ulong
     230       42259 : hash_id(void *x) { return (ulong)x; }
     231             : static int
     232       39263 : eq_id(void *x, void *y) { return x == y; }
     233             : hashtable *
     234         399 : hash_create_ulong(ulong s, long stack)
     235         399 : { return hash_create(s, &hash_id, &eq_id, stack); }
     236             : 
     237             : static
     238        7438 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
     239             : hashtable *
     240        1549 : hash_create_str(ulong s, long stack)
     241        1549 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
     242             : 
     243             : hashtable *
     244          11 : hashstr_import_static(hashentry *e, ulong size)
     245             : {
     246          11 :   hashtable *h = hash_create_str(size, 0);
     247          11 :   for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
     248          11 :   return h;
     249             : }
     250             : 
     251             : void
     252           0 : hash_dbg(hashtable *h)
     253             : {
     254           0 :   ulong n, Total = 0, Max = 0;
     255           0 :   hashentry *e, **table = h->table;
     256           0 :   for (n=0; n < h->len; n++)
     257             :   {
     258           0 :     ulong m=0;
     259           0 :     for (e=table[n]; e; e=e->next) m++;
     260           0 :     Total += m; if (Max < m) Max = m;
     261           0 :     pari_printf("%4ld:%2ld ",n,m);
     262           0 :     if (n%9 == 8) pari_putc('\n');
     263             :   }
     264           0 :   pari_printf("\nTotal = %ld, Max = %ld\n", Total, Max);
     265           0 : }
     266             : 
     267             : /********************************************************************/
     268             : /*                                                                  */
     269             : /*                          HASH FUNCTIONS                          */
     270             : /*                                                                  */
     271             : /********************************************************************/
     272             : 
     273             : INLINE ulong
     274   619301449 : glue(ulong h, ulong a) { return 404936533*h + a; }
     275             : ulong
     276   185875444 : hash_GEN(GEN x)
     277             : {
     278   185875444 :   ulong h = x[0];
     279   185875444 :   long tx = typ(x), lx, i;
     280   185875444 :   switch(tx)
     281             :   { /* non recursive types */
     282             :     case t_INT:
     283    90920076 :       lx = lgefint(x);
     284    90920076 :       h &= TYPBITS;
     285    90920076 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     286    90920076 :       return h;
     287             :     case t_REAL:
     288             :     case t_STR:
     289             :     case t_VECSMALL:
     290    61531756 :       lx = lg(x);
     291    61531756 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     292    61531752 :       return h;
     293             :     /* one more special case */
     294             :     case t_LIST:
     295           0 :       x = list_data(x);
     296           0 :       if (!x) return h;
     297             :       /* fall through */
     298             :     default:
     299    33423612 :       if (lontyp[tx] == 2) { h = glue(h, x[1]); i = 2; } else i = 1;
     300    33423612 :       lx = lg(x);
     301    33423612 :       for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
     302    33423612 :       return h;
     303             :   }
     304             : }
     305             : 
     306             : /* djb's hash */
     307             : ulong
     308       22964 : hash_str(const char *str)
     309             : {
     310       22964 :   ulong hash = 5381, c;
     311      178538 :   while ( (c = (ulong)*str++) )
     312      132610 :     hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
     313       22964 :   return hash;
     314             : }
     315             : 
     316             : /* hashvalue's underlying hash function */
     317             : ulong
     318           0 : hash_str2(const char *s)
     319             : {
     320           0 :   ulong n = 0, c;
     321           0 :   while ( (c = (ulong)*s++) ) n = (n<<1) ^ c;
     322           0 :   return n;
     323             : }

Generated by: LCOV version 1.11