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.8.0 lcov report (development 18894-f1ef88e) Lines: 126 157 80.3 %
Date: 2016-05-03 Functions: 23 26 88.5 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 62 92 67.4 %

           Branch data     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                 :      13034 : setlen(hashtable *h, ulong len) {
      31                 :      13034 :   h->maxnb = (ulong)ceil(len * 0.65);
      32                 :      13034 :   h->len  = len;
      33                 :      13034 : }
      34                 :            : 
      35                 :            : static int
      36                 :      11601 : get_prime_index(ulong len)
      37                 :            : {
      38                 :            :   int i;
      39         [ +  - ]:      26679 :   for (i=0; i < hashprimes_len; i++)
      40         [ +  + ]:      26679 :     if (hashprimes[i] > len) return i;
      41                 :          0 :   pari_err_OVERFLOW("hash table [too large]");
      42                 :      11601 :   return -1; /* not reached */
      43                 :            : }
      44                 :            : 
      45                 :            : /* link hashentry e to hashtable h, setting e->hash / e->next */
      46                 :            : INLINE void
      47                 :    1205053 : hash_link2(hashtable *h, hashentry *e, ulong hash)
      48                 :            : {
      49                 :            :   ulong index;
      50                 :    1205053 :   e->hash = hash; index = e->hash % h->len;
      51                 :    1205053 :   e->next = h->table[index]; h->table[index] = e;
      52                 :    1205053 : }
      53                 :            : INLINE void
      54                 :     674157 : hash_link(hashtable *h, hashentry *e) {return hash_link2(h,e,h->hash(e->key));}
      55                 :            : 
      56                 :            : hashtable *
      57                 :      11601 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
      58                 :            :             int use_stack)
      59                 :            : {
      60                 :      11601 :   int i = get_prime_index(minsize);
      61                 :      11601 :   ulong len = hashprimes[i];
      62                 :            :   hashtable *h;
      63                 :            : 
      64         [ +  + ]:      11601 :   if (use_stack)
      65                 :            :   {
      66                 :       8234 :     h = (hashtable*)stack_malloc(sizeof(hashtable));
      67                 :       8234 :     h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
      68                 :       8234 :     h->use_stack = 1;
      69                 :            :   }
      70                 :            :   else
      71                 :            :   {
      72                 :       3367 :     h = (hashtable*)pari_malloc(sizeof(hashtable));
      73                 :       3367 :     h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
      74                 :       3367 :     h->use_stack = 0;
      75                 :            :   }
      76                 :      11601 :   h->pindex = i;
      77                 :      11601 :   h->nb = 0;
      78                 :      11601 :   h->hash = hash;
      79                 :      11601 :   h->eq   = eq;
      80                 :      11601 :   setlen(h, len); return h;
      81                 :            : }
      82                 :            : 
      83                 :            : void
      84                 :     530896 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
      85                 :            : {
      86                 :            :   hashentry *e;
      87                 :            :   ulong index;
      88                 :            : 
      89         [ +  + ]:     530896 :   if (h->use_stack)
      90                 :     520491 :     e = (hashentry*) stack_malloc(sizeof(hashentry));
      91                 :            :   else
      92                 :      10405 :     e = (hashentry*) pari_malloc(sizeof(hashentry));
      93                 :            : 
      94 [ +  + ][ +  - ]:     530896 :   if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
      95                 :            :   { /* double table size */
      96                 :       1433 :     ulong i, newlen = hashprimes[++(h->pindex)];
      97                 :            :     hashentry *E, **newtable;
      98         [ +  - ]:       1433 :     if (h->use_stack)
      99                 :       1433 :       newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
     100                 :            :     else
     101                 :          0 :       newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
     102         [ +  + ]:     544006 :     for (i = 0; i < h->len; i++)
     103         [ +  + ]:     895900 :       while ( (E = h->table[i]) )
     104                 :            :       {
     105                 :     353327 :         h->table[i] = E->next;
     106                 :     353327 :         index = E->hash % newlen;
     107                 :     353327 :         E->next = newtable[index];
     108                 :     353327 :         newtable[index] = E;
     109                 :            :       }
     110         [ -  + ]:       1433 :     if (!h->use_stack) pari_free(h->table);
     111                 :       1433 :     h->table = newtable;
     112                 :       1433 :     setlen(h, newlen);
     113                 :            :   }
     114                 :     530896 :   e->key = k;
     115                 :     530896 :   e->val = v; hash_link2(h, e, hash);
     116                 :     530896 : }
     117                 :            : void
     118                 :     160743 : hash_insert(hashtable *h, void *k, void *v)
     119                 :     160743 : { return 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                 :         56 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
     125                 :            : {
     126                 :         56 :   ulong hash = h->hash(k);
     127                 :         56 :   hashentry *e = h->table[ hash % h->len ];
     128         [ +  + ]:        126 :   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                 :         56 :   return NULL;
     134                 :            : }
     135                 :            : 
     136                 :            : GEN
     137                 :          7 : hash_keys(hashtable *h)
     138                 :            : {
     139                 :          7 :   long k = 1;
     140                 :            :   ulong i;
     141                 :          7 :   GEN v = cgetg(h->nb+1, t_VECSMALL);
     142         [ +  + ]:       1358 :   for (i = 0; i < h->len; i++)
     143                 :            :   {
     144                 :       1351 :     hashentry *e = h->table[i];
     145         [ +  + ]:       1386 :     while (e) { v[k++] = (long)e->key; e = e->next; }
     146                 :            :   }
     147                 :          7 :   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         [ +  + ]:      28875 :     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                 :    1109796 : hash_search2(hashtable *h, void *k, ulong hash)
     166                 :            : {
     167                 :    1109796 :   hashentry *e = h->table[ hash % h->len ];
     168         [ +  + ]:    1401048 :   while (e)
     169                 :            :   {
     170 [ +  + ][ +  + ]:     929982 :     if (hash == e->hash && h->eq(k, e->key)) return e;
     171                 :     291252 :     e = e->next;
     172                 :            :   }
     173                 :    1109796 :   return NULL; /* not found */
     174                 :            : }
     175                 :            : /* returns entry associated with key k or NULL */
     176                 :            : hashentry *
     177                 :     320112 : hash_search(hashtable *h, void *k)
     178                 :            : {
     179         [ +  + ]:     320112 :   if (h->nb == 0) return NULL;
     180                 :     320112 :   return hash_search2(h, k, h->hash(k));
     181                 :            : }
     182                 :            : 
     183                 :            : hashentry *
     184                 :       4058 : hash_remove_select(hashtable *h, void *k, void *E,
     185                 :            :   int (*select)(void*,hashentry*))
     186                 :            : {
     187                 :       4058 :   ulong hash = h->hash(k), index = hash % h->len;
     188                 :       4058 :   hashentry **pE = &(h->table[index]), *e = *pE;
     189         [ +  - ]:       4058 :   while (e)
     190                 :            :   {
     191 [ +  - ][ +  - ]:       4058 :     if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
                 [ +  - ]
     192                 :       4058 :       *pE = e->next; h->nb--;
     193                 :       4058 :       return e;
     194                 :            :     }
     195                 :          0 :     pE = &(e->next);
     196                 :          0 :     e = e->next;
     197                 :            :   }
     198                 :       4058 :   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                 :       1836 : hash_destroy(hashtable *h)
     219                 :            : {
     220                 :            :   ulong i;
     221         [ -  + ]:       3672 :   if (h->use_stack) return;
     222         [ +  + ]:     356184 :   for (i = 0; i < h->len; i++)
     223                 :            :   {
     224                 :     354348 :     hashentry *e = h->table[i];
     225         [ +  + ]:     359679 :     while (e) { hashentry *f = e; e = e->next; pari_free(f); }
     226                 :            :   }
     227                 :       1836 :   pari_free(h->table); pari_free(h);
     228                 :            : }
     229                 :            : static ulong
     230                 :        112 : hash_id(void *x) { return (ulong)x; }
     231                 :            : static int
     232                 :         49 : eq_id(void *x, void *y) { return x == y; }
     233                 :            : hashtable *
     234                 :          7 : hash_create_ulong(ulong s, long stack)
     235                 :          7 : { return hash_create(s, &hash_id, &eq_id, stack); }
     236                 :            : 
     237                 :            : static
     238                 :     309899 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
     239                 :            : hashtable *
     240                 :       3367 : hash_create_str(ulong s, long stack)
     241                 :       3367 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
     242                 :            : 
     243                 :            : hashtable *
     244                 :       1023 : hashstr_import_static(hashentry *e, ulong size)
     245                 :            : {
     246                 :       1023 :   hashtable *h = hash_create_str(size, 0);
     247         [ +  + ]:     675180 :   for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
     248                 :       1023 :   return h;
     249                 :            : }
     250                 :            : 
     251                 :            : void
     252                 :          0 : hashstr_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                 :  391474110 : glue(ulong h, ulong a) { return 404936533*h + a; }
     275                 :            : ulong
     276                 :   89216424 : hash_GEN(GEN x)
     277                 :            : {
     278                 :   89216424 :   ulong h = x[0];
     279                 :   89216424 :   long tx = typ(x), lx, i;
     280   [ +  +  -  + ]:   89216424 :   switch(tx)
     281                 :            :   { /* non recursive types */
     282                 :            :     case t_INT:
     283                 :   23510620 :       lx = lgefint(x);
     284                 :   23510620 :       h &= TYPBITS;
     285         [ +  + ]:   74902537 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     286                 :   23510620 :       return h;
     287                 :            :     case t_REAL:
     288                 :            :     case t_STR:
     289                 :            :     case t_VECSMALL:
     290                 :   56419237 :       lx = lg(x);
     291         [ +  + ]:  371014900 :       for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
     292                 :   56419237 :       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         [ +  + ]:    9286567 :       if (lontyp[tx] == 2) { h = glue(h, x[1]); i = 2; } else i = 1;
     300                 :    9286567 :       lx = lg(x);
     301         [ +  + ]:   33685060 :       for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
     302                 :   89216424 :       return h;
     303                 :            :   }
     304                 :            : }
     305                 :            : 
     306                 :            : /* djb's hash */
     307                 :            : ulong
     308                 :     994426 : hash_str(const char *str)
     309                 :            : {
     310                 :     994426 :   ulong hash = 5381, c;
     311         [ +  + ]:    8160982 :   while ( (c = (ulong)*str++) )
     312                 :    7166556 :     hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
     313                 :     994426 :   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.9