LCOV - code coverage report
Current view: top level - src/base - pdf-hash.c (source / functions) Hit Total Coverage
Test: libgnupdf.info Lines: 106 120 88.3 %
Date: 2011-12-09 Functions: 17 18 94.4 %
Branches: 49 82 59.8 %

           Branch data     Line data    Source code
       1                 :            : /* -*- mode: C -*-
       2                 :            :  *
       3                 :            :  *       File:         pdf-hash.c
       4                 :            :  *       Date:         Sat Apr  12 12:22:05 2008
       5                 :            :  *
       6                 :            :  *       GNU PDF Library - Implementation file for the Hash module
       7                 :            :  *
       8                 :            :  */
       9                 :            : 
      10                 :            : /* Copyright (C) 2008-2011 Free Software Foundation, Inc. */
      11                 :            : 
      12                 :            : /* This program is free software: you can redistribute it and/or modify
      13                 :            :  * it under the terms of the GNU General Public License as published by
      14                 :            :  * the Free Software Foundation, either version 3 of the License, or
      15                 :            :  * (at your option) any later version.
      16                 :            :  *
      17                 :            :  * This program is distributed in the hope that it will be useful,
      18                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      19                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      20                 :            :  * GNU General Public License for more details.
      21                 :            :  *
      22                 :            :  * You should have received a copy of the GNU General Public License
      23                 :            :  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
      24                 :            :  */
      25                 :            : 
      26                 :            : #include <config.h>
      27                 :            : 
      28                 :            : #include <limits.h>
      29                 :            : #include <stdio.h>
      30                 :            : #include <stdlib.h>
      31                 :            : #include <string.h>
      32                 :            : 
      33                 :            : #include <pdf-global.h>
      34                 :            : #include <pdf-error.h>
      35                 :            : #include <pdf-alloc.h>
      36                 :            : #include <gl_rbtreehash_list.h>
      37                 :            : 
      38                 :            : #include <pdf-hash.h>
      39                 :            : 
      40                 :            : #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
      41                 :            : 
      42                 :            : struct pdf_hash_element_s
      43                 :            : {
      44                 :            :   const pdf_char_t *key;
      45                 :            :   const void *value;
      46                 :            :   pdf_hash_value_dispose_fn_t value_disp_fn;
      47                 :            : };
      48                 :            : 
      49                 :            : typedef struct pdf_hash_element_s pdf_hash_element_t;
      50                 :            : 
      51                 :            : /* Returns <0,=0,>0 if key1 is <,==, or > than key2 */
      52                 :            : static int hash_element_compare (const pdf_hash_element_t *elt1,
      53                 :            :                                  const pdf_hash_element_t *elt2);
      54                 :            : 
      55                 :            : /* Returns true if both keys in the elements are equal */
      56                 :            : static pdf_bool_t hash_element_equal (const pdf_hash_element_t *elt1,
      57                 :            :                                       const pdf_hash_element_t *elt2);
      58                 :            : 
      59                 :            : /* Compute a hash code for a NUL-terminated string starting at X,
      60                 :            :  * and return the hash code.
      61                 :            :  * The result is platform dependent: it depends on the size of the 'size_t'
      62                 :            :  * type and on the signedness of the 'char' type.  */
      63                 :            : static pdf_size_t hash_element_pjw (const pdf_hash_element_t *elt);
      64                 :            : 
      65                 :            : /* Dispose a hash element */
      66                 :            : static void hash_element_dispose (pdf_hash_element_t *elt);
      67                 :            : 
      68                 :            : /* Find a hash element by key in the hash table */
      69                 :            : static pdf_hash_element_t *hash_search_key (const pdf_hash_t *table,
      70                 :            :                                             const pdf_char_t *key,
      71                 :            :                                             gl_list_node_t   *p_node);
      72                 :            : 
      73                 :            : pdf_hash_t *
      74                 :        809 : pdf_hash_new (pdf_error_t **error)
      75                 :            : {
      76                 :            :   gl_list_t list;
      77                 :            : 
      78                 :       1618 :   list = gl_list_nx_create_empty (GL_RBTREEHASH_LIST,
      79                 :            :                                   (gl_listelement_equals_fn) hash_element_equal,
      80                 :            :                                   (gl_listelement_hashcode_fn) hash_element_pjw,
      81                 :            :                                   (gl_listelement_dispose_fn) hash_element_dispose,
      82                 :            :                                   PDF_FALSE);
      83         [ -  + ]:        809 :   if (list == NULL)
      84                 :          0 :     pdf_set_error (error,
      85                 :            :                    PDF_EDOMAIN_BASE_HASH,
      86                 :            :                    PDF_ENOMEM,
      87                 :            :                    "not enough memory: couldn't create new hash table");
      88                 :            : 
      89                 :        809 :   return (pdf_hash_t *)list;
      90                 :            : }
      91                 :            : 
      92                 :            : void
      93                 :        809 : pdf_hash_destroy (pdf_hash_t *table)
      94                 :            : {
      95         [ +  - ]:        809 :   if (table != NULL)
      96                 :        809 :     gl_list_free ((gl_list_t) table);
      97                 :        809 : }
      98                 :            : 
      99                 :            : pdf_size_t
     100                 :        746 : pdf_hash_size (const pdf_hash_t *table)
     101                 :            : {
     102         [ +  - ]:       1492 :   return (table != NULL ?
     103                 :        746 :           gl_list_size ((gl_list_t) table) :
     104                 :            :           0);;
     105                 :            : }
     106                 :            : 
     107                 :            : pdf_bool_t
     108                 :        829 : pdf_hash_key_p (const pdf_hash_t *table,
     109                 :            :                 const pdf_char_t *key)
     110                 :            : {
     111         [ -  + ]:        829 :   PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
     112         [ -  + ]:        829 :   PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
     113                 :            : 
     114                 :        829 :   return (hash_search_key (table, key, NULL) != NULL ?
     115                 :            :           PDF_TRUE : PDF_FALSE);
     116                 :            : }
     117                 :            : 
     118                 :            : pdf_bool_t
     119                 :          2 : pdf_hash_rename_key (pdf_hash_t        *table,
     120                 :            :                      const pdf_char_t  *key,
     121                 :            :                      const pdf_char_t  *new_key,
     122                 :            :                      pdf_error_t      **error)
     123                 :            : {
     124                 :            :   pdf_hash_element_t *elt;
     125                 :          2 :   gl_list_node_t node = NULL;
     126                 :          2 :   pdf_error_t *inner_error = NULL;
     127                 :            : 
     128         [ -  + ]:          2 :   PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
     129         [ -  + ]:          2 :   PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
     130         [ -  + ]:          2 :   PDF_ASSERT_POINTER_RETURN_VAL (new_key, PDF_FALSE);
     131                 :            : 
     132                 :          2 :   elt = hash_search_key (table, key, &node);
     133                 :            : 
     134                 :            :   /* If element not found, return */
     135         [ +  + ]:          2 :   if (elt == NULL)
     136                 :          1 :     return PDF_FALSE;
     137                 :            : 
     138                 :            :   /* Add the same element with the new key */
     139         [ -  + ]:          1 :   if (!pdf_hash_add (table,
     140                 :            :                      new_key,
     141                 :            :                      elt->value,
     142                 :            :                      elt->value_disp_fn,
     143                 :            :                      &inner_error))
     144                 :            :     {
     145                 :          0 :       pdf_propagate_error (error, inner_error);
     146                 :          0 :       return PDF_FALSE;
     147                 :            :     }
     148                 :            : 
     149                 :            :   /* Remove the element with the old key */
     150                 :          1 :   gl_list_remove_node ((gl_list_t) table, node);
     151                 :            : 
     152                 :          2 :   return PDF_TRUE;
     153                 :            : }
     154                 :            : 
     155                 :            : static pdf_bool_t
     156                 :        852 : hash_add (pdf_hash_t                   *table,
     157                 :            :           const pdf_char_t             *key,
     158                 :            :           const void                   *value,
     159                 :            :           pdf_hash_value_dispose_fn_t   value_disp_fn,
     160                 :            :           pdf_bool_t                    allow_replace,
     161                 :            :           pdf_error_t                 **error)
     162                 :            : {
     163                 :        852 :   gl_list_node_t node = NULL;
     164                 :            :   pdf_hash_element_t *elt;
     165                 :            :   pdf_char_t *key_dup;
     166                 :            : 
     167                 :            :   /* Look for an element with same key */
     168         [ +  + ]:        852 :   if (hash_search_key (table, key, &node))
     169                 :            :     {
     170                 :            :       /* Key already exists. */
     171         [ +  + ]:          2 :       if (!allow_replace)
     172                 :            :         {
     173                 :          1 :           pdf_set_error (error,
     174                 :            :                          PDF_EDOMAIN_BASE_HASH,
     175                 :            :                          PDF_EEXIST,
     176                 :            :                          "key '%s' already exits, cannot add it again",
     177                 :            :                          key);
     178                 :          1 :           return PDF_FALSE;
     179                 :            :         }
     180                 :            : 
     181                 :            :       /* Remove the previous element */
     182                 :          1 :       gl_list_remove_node ((gl_list_t) table, node);
     183                 :            :     }
     184                 :            : 
     185                 :            :   /* New hash table element */
     186                 :        851 :   elt = pdf_alloc (sizeof (*elt));
     187                 :        851 :   key_dup = strdup (key);
     188         [ -  + ]:        851 :   if (elt == NULL || key_dup == NULL)
     189                 :            :     {
     190                 :          0 :       pdf_set_error (error,
     191                 :            :                      PDF_EDOMAIN_BASE_HASH,
     192                 :            :                      PDF_ENOMEM,
     193                 :            :                      "not enough memory: couldn't add new hash table item");
     194         [ #  # ]:          0 :       if (elt)
     195                 :          0 :         pdf_dealloc (elt);
     196         [ #  # ]:          0 :       if (key_dup)
     197                 :          0 :         pdf_dealloc (key_dup);
     198                 :          0 :       return PDF_FALSE;
     199                 :            :     }
     200                 :            : 
     201                 :            :   /* Set new element contents */
     202                 :        851 :   elt->key = key_dup;
     203                 :        851 :   elt->value = value;
     204                 :        851 :   elt->value_disp_fn = value_disp_fn;
     205                 :            : 
     206                 :            :   /* Add to the list */
     207         [ -  + ]:        851 :   if (!gl_sortedlist_nx_add ((gl_list_t) table,
     208                 :            :                              (gl_listelement_compar_fn) hash_element_compare,
     209                 :            :                              elt))
     210                 :            :     {
     211                 :          0 :       pdf_set_error (error,
     212                 :            :                      PDF_EDOMAIN_BASE_HASH,
     213                 :            :                      PDF_ENOMEM,
     214                 :            :                      "not enough memory: "
     215                 :            :                      "couldn't add new element to the hash table");
     216                 :          0 :       hash_element_dispose (elt);
     217                 :          0 :       return PDF_FALSE;
     218                 :            :     }
     219                 :            : 
     220                 :        852 :   return PDF_TRUE;
     221                 :            : }
     222                 :            : 
     223                 :            : pdf_bool_t
     224                 :        848 : pdf_hash_add (pdf_hash_t                   *table,
     225                 :            :               const pdf_char_t             *key,
     226                 :            :               const void                   *value,
     227                 :            :               pdf_hash_value_dispose_fn_t   value_disp_fn,
     228                 :            :               pdf_error_t                 **error)
     229                 :            : {
     230         [ -  + ]:        848 :   PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
     231         [ -  + ]:        848 :   PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
     232                 :            : 
     233                 :        848 :   return hash_add (table, key, value, value_disp_fn, PDF_FALSE, error);
     234                 :            : }
     235                 :            : 
     236                 :            : pdf_bool_t
     237                 :          4 : pdf_hash_replace (pdf_hash_t                   *table,
     238                 :            :                   const pdf_char_t             *key,
     239                 :            :                   const void                   *value,
     240                 :            :                   pdf_hash_value_dispose_fn_t   value_disp_fn,
     241                 :            :                   pdf_error_t                 **error)
     242                 :            : {
     243         [ -  + ]:          4 :   PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
     244         [ -  + ]:          4 :   PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
     245                 :            : 
     246                 :          4 :   return hash_add (table, key, value, value_disp_fn, PDF_TRUE, error);
     247                 :            : }
     248                 :            : 
     249                 :            : pdf_bool_t
     250                 :        747 : pdf_hash_remove (pdf_hash_t       *table,
     251                 :            :                  const pdf_char_t *key)
     252                 :            : {
     253                 :        747 :   gl_list_node_t node = NULL;
     254                 :            : 
     255         [ -  + ]:        747 :   PDF_ASSERT_POINTER_RETURN_VAL (table, PDF_FALSE);
     256         [ -  + ]:        747 :   PDF_ASSERT_POINTER_RETURN_VAL (key, PDF_FALSE);
     257                 :            : 
     258         [ +  + ]:        747 :   if (hash_search_key (table, key, &node))
     259                 :            :     {
     260                 :            :       /* Remove the element  */
     261                 :        746 :       gl_list_remove_node ((gl_list_t) table, node);
     262                 :        746 :       return PDF_TRUE;
     263                 :            :     }
     264                 :            : 
     265                 :            :   /* Not found */
     266                 :        747 :   return PDF_FALSE;
     267                 :            : }
     268                 :            : 
     269                 :            : const void *
     270                 :        177 : pdf_hash_get_value (const pdf_hash_t *table,
     271                 :            :                     const pdf_char_t *key)
     272                 :            : {
     273                 :            :   pdf_hash_element_t *elt;
     274                 :            : 
     275         [ -  + ]:        177 :   PDF_ASSERT_POINTER_RETURN_VAL (table, NULL);
     276         [ -  + ]:        177 :   PDF_ASSERT_POINTER_RETURN_VAL (key, NULL);
     277                 :            : 
     278                 :        177 :   elt = hash_search_key (table, key, NULL);
     279                 :            : 
     280         [ +  + ]:        177 :   return (elt != NULL ? elt->value : NULL);
     281                 :            : }
     282                 :            : 
     283                 :            : void
     284                 :          2 : pdf_hash_iterator_init (pdf_hash_iterator_t *itr,
     285                 :            :                         const pdf_hash_t    *table)
     286                 :            : {
     287         [ -  + ]:          2 :   PDF_ASSERT_POINTER_RETURN (itr);
     288         [ -  + ]:          2 :   PDF_ASSERT_POINTER_RETURN (table);
     289                 :            : 
     290                 :          2 :   *((gl_list_iterator_t *)itr) = gl_list_iterator ((gl_list_t) table);
     291                 :            : }
     292                 :            : 
     293                 :            : pdf_bool_t
     294                 :          2 : pdf_hash_iterator_next (pdf_hash_iterator_t  *itr,
     295                 :            :                         const pdf_char_t    **key,
     296                 :            :                         const void          **value)
     297                 :            : {
     298                 :            :   const pdf_hash_element_t *element;
     299                 :            :   gl_list_node_t node;
     300                 :            : 
     301         [ -  + ]:          2 :   PDF_ASSERT_POINTER_RETURN_VAL (itr, PDF_FALSE);
     302                 :            : 
     303         [ +  + ]:          2 :   if (!gl_list_iterator_next (((gl_list_iterator_t *) itr),
     304                 :            :                               (const void **)&element,
     305                 :            :                               &node))
     306                 :            :     {
     307         [ +  - ]:          1 :       if (key)
     308                 :          1 :         *key = NULL;
     309         [ +  - ]:          1 :       if (value)
     310                 :          1 :         *value = NULL;
     311                 :          1 :       return PDF_FALSE;
     312                 :            :     }
     313                 :            : 
     314         [ +  - ]:          1 :   if (key)
     315                 :          1 :     *key = element->key;
     316         [ +  - ]:          1 :   if (value)
     317                 :          1 :     *value = element->value;
     318                 :          2 :   return PDF_TRUE;
     319                 :            : }
     320                 :            : 
     321                 :            : void
     322                 :          2 : pdf_hash_iterator_deinit (pdf_hash_iterator_t *itr)
     323                 :            : {
     324         [ +  - ]:          2 :   if (itr)
     325                 :          2 :     gl_list_iterator_free ((gl_list_iterator_t *) itr);
     326                 :          2 : }
     327                 :            : 
     328                 :            : static pdf_hash_element_t *
     329                 :       2607 : hash_search_key (const pdf_hash_t *table,
     330                 :            :                  const pdf_char_t *key,
     331                 :            :                  gl_list_node_t   *p_node)
     332                 :            : {
     333                 :            :   gl_list_node_t node;
     334                 :            :   pdf_hash_element_t aux;
     335                 :            : 
     336                 :            :   /* Setup aux element in stack to use during search comparisons */
     337                 :       2607 :   aux.key = key;
     338                 :       5214 :   node = gl_sortedlist_search ((gl_list_t) table,
     339                 :            :                                (gl_listelement_compar_fn) hash_element_compare,
     340                 :            :                                (const void *) &aux);
     341         [ +  + ]:       2607 :   if (p_node)
     342                 :       1601 :     *p_node = node;
     343                 :            : 
     344         [ +  + ]:       3614 :   return (pdf_hash_element_t *) (node != NULL ?
     345                 :       1007 :                                  gl_list_node_value ((gl_list_t) table, node) :
     346                 :            :                                  NULL);
     347                 :            : }
     348                 :            : 
     349                 :            : static pdf_size_t
     350                 :        851 : hash_element_pjw (const pdf_hash_element_t *elt)
     351                 :            : {
     352                 :            :   const pdf_char_t *s;
     353                 :        851 :   pdf_size_t h = 0;
     354                 :            : 
     355         [ +  + ]:       4329 :   for (s = elt->key; *s; s++)
     356                 :       3478 :     h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
     357                 :            : 
     358                 :        851 :   return h;
     359                 :            : }
     360                 :            : 
     361                 :            : static void
     362                 :        851 : hash_element_dispose (pdf_hash_element_t *elt)
     363                 :            : {
     364         [ +  - ]:        851 :   if (elt)
     365                 :            :     {
     366         [ +  - ]:        851 :       if (elt->key)
     367                 :        851 :         pdf_dealloc (elt->key);
     368         [ +  + ]:        851 :       if (elt->value_disp_fn)
     369                 :        750 :         elt->value_disp_fn (elt->value);
     370                 :        851 :       pdf_dealloc (elt);
     371                 :            :     }
     372                 :        851 : }
     373                 :            : 
     374                 :            : static int
     375                 :       1170 : hash_element_compare (const pdf_hash_element_t *elt1,
     376                 :            :                       const pdf_hash_element_t *elt2)
     377                 :            : {
     378                 :       1170 :   return strcmp (elt1->key, elt2->key);
     379                 :            : }
     380                 :            : 
     381                 :            : static pdf_bool_t
     382                 :          0 : hash_element_equal (const pdf_hash_element_t *elt1,
     383                 :            :                     const pdf_hash_element_t *elt2)
     384                 :            : {
     385                 :          0 :   return (hash_element_compare (elt1, elt2) == 0 ?
     386                 :            :           PDF_TRUE : PDF_FALSE);
     387                 :            : }
     388                 :            : 
     389                 :            : /* End of pdf-hash.c */

Generated by: LCOV version 1.8