Branch data     Line data    Source code

       1                 :            : /* GLIB - Library of useful routines for C programming
       2                 :            :  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
       3                 :            :  *
       4                 :            :  * SPDX-License-Identifier: LGPL-2.1-or-later
       5                 :            :  *
       6                 :            :  * This library is free software; you can redistribute it and/or
       7                 :            :  * modify it under the terms of the GNU Lesser General Public
       8                 :            :  * License as published by the Free Software Foundation; either
       9                 :            :  * version 2.1 of the License, or (at your option) any later version.
      10                 :            :  *
      11                 :            :  * This library is distributed in the hope that it will be useful,
      12                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      14                 :            :  * Lesser General Public License for more details.
      15                 :            :  *
      16                 :            :  * You should have received a copy of the GNU Lesser General Public
      17                 :            :  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
      18                 :            :  */
      19                 :            : 
      20                 :            : /*
      21                 :            :  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
      22                 :            :  * file for a list of people on the GLib Team.  See the ChangeLog
      23                 :            :  * files for a list of changes.  These files are distributed with
      24                 :            :  * GLib at ftp://ftp.gtk.org/pub/gtk/.
      25                 :            :  */
      26                 :            : 
      27                 :            : /*
      28                 :            :  * MT safe
      29                 :            :  */
      30                 :            : 
      31                 :            : #include "config.h"
      32                 :            : 
      33                 :            : #include <string.h>
      34                 :            : 
      35                 :            : #include "gstringchunk.h"
      36                 :            : 
      37                 :            : #include "ghash.h"
      38                 :            : #include "gslist.h"
      39                 :            : #include "gmessages.h"
      40                 :            : 
      41                 :            : #include "gutils.h"
      42                 :            : #include "gutilsprivate.h"
      43                 :            : 
      44                 :            : /**
      45                 :            :  * GStringChunk:
      46                 :            :  *
      47                 :            :  * `GStringChunk` provides efficient storage of groups of strings
      48                 :            :  *
      49                 :            :  * String chunks are used to store groups of strings. Memory is
      50                 :            :  * allocated in blocks, and as strings are added to the `GStringChunk`
      51                 :            :  * they are copied into the next free position in a block. When a block
      52                 :            :  * is full a new block is allocated.
      53                 :            :  *
      54                 :            :  * When storing a large number of strings, string chunks are more
      55                 :            :  * efficient than using [func@GLib.strdup] since fewer calls to `malloc()`
      56                 :            :  * are needed, and less memory is wasted in memory allocation overheads.
      57                 :            :  *
      58                 :            :  * By adding strings with [method@GLib.StringChunk.insert_const] it is also
      59                 :            :  * possible to remove duplicates.
      60                 :            :  *
      61                 :            :  * To create a new `GStringChunk` use [func@GLib.StringChunk.new].
      62                 :            :  *
      63                 :            :  * To add strings to a `GStringChunk` use [method@GLib.StringChunk.insert].
      64                 :            :  *
      65                 :            :  * To add strings to a `GStringChunk`, but without duplicating strings
      66                 :            :  * which are already in the `GStringChunk`, use [method@GLib.StringChunk.insert_const].
      67                 :            :  *
      68                 :            :  * To free the entire `GStringChunk` use [method@GLib.StringChunk.free].
      69                 :            :  * It is not possible to free individual strings.
      70                 :            :  */
      71                 :            : 
      72                 :            : struct _GStringChunk
      73                 :            : {
      74                 :            :   GHashTable *const_table;
      75                 :            :   GSList     *storage_list;
      76                 :            :   gsize       storage_next;
      77                 :            :   gsize       this_size;
      78                 :            :   gsize       default_size;
      79                 :            : };
      80                 :            : 
      81                 :            : /**
      82                 :            :  * g_string_chunk_new: (constructor)
      83                 :            :  * @size: the default size of the blocks of memory which are
      84                 :            :  *     allocated to store the strings. If a particular string
      85                 :            :  *     is larger than this default size, a larger block of
      86                 :            :  *     memory will be allocated for it.
      87                 :            :  *
      88                 :            :  * Creates a new #GStringChunk.
      89                 :            :  *
      90                 :            :  * Returns: (transfer full): a new #GStringChunk
      91                 :            :  */
      92                 :            : GStringChunk *
      93                 :          3 : g_string_chunk_new (gsize size)
      94                 :            : {
      95                 :          3 :   GStringChunk *new_chunk = g_new (GStringChunk, 1);
      96                 :          3 :   gsize actual_size = 1;
      97                 :            : 
      98         [ +  - ]:          3 :   actual_size = g_nearest_pow (MAX (1, size));
      99                 :            : 
     100                 :          3 :   new_chunk->const_table  = NULL;
     101                 :          3 :   new_chunk->storage_list = NULL;
     102                 :          3 :   new_chunk->storage_next = actual_size;
     103                 :          3 :   new_chunk->default_size = actual_size;
     104                 :          3 :   new_chunk->this_size    = actual_size;
     105                 :            : 
     106                 :          3 :   return new_chunk;
     107                 :            : }
     108                 :            : 
     109                 :            : /**
     110                 :            :  * g_string_chunk_free:
     111                 :            :  * @chunk: (transfer full): a #GStringChunk
     112                 :            :  *
     113                 :            :  * Frees all memory allocated by the #GStringChunk.
     114                 :            :  * After calling g_string_chunk_free() it is not safe to
     115                 :            :  * access any of the strings which were contained within it.
     116                 :            :  */
     117                 :            : void
     118                 :          3 : g_string_chunk_free (GStringChunk *chunk)
     119                 :            : {
     120                 :          3 :   g_return_if_fail (chunk != NULL);
     121                 :            : 
     122         [ +  + ]:          3 :   if (chunk->storage_list)
     123                 :          1 :     g_slist_free_full (chunk->storage_list, g_free);
     124                 :            : 
     125         [ +  + ]:          3 :   if (chunk->const_table)
     126                 :          1 :     g_hash_table_destroy (chunk->const_table);
     127                 :            : 
     128                 :          3 :   g_free (chunk);
     129                 :            : }
     130                 :            : 
     131                 :            : /**
     132                 :            :  * g_string_chunk_clear:
     133                 :            :  * @chunk: a #GStringChunk
     134                 :            :  *
     135                 :            :  * Frees all strings contained within the #GStringChunk.
     136                 :            :  * After calling g_string_chunk_clear() it is not safe to
     137                 :            :  * access any of the strings which were contained within it.
     138                 :            :  *
     139                 :            :  * Since: 2.14
     140                 :            :  */
     141                 :            : void
     142                 :          1 : g_string_chunk_clear (GStringChunk *chunk)
     143                 :            : {
     144                 :          1 :   g_return_if_fail (chunk != NULL);
     145                 :            : 
     146         [ +  - ]:          1 :   if (chunk->storage_list)
     147                 :            :     {
     148                 :          1 :       g_slist_free_full (chunk->storage_list, g_free);
     149                 :            : 
     150                 :          1 :       chunk->storage_list = NULL;
     151                 :          1 :       chunk->storage_next = chunk->default_size;
     152                 :          1 :       chunk->this_size    = chunk->default_size;
     153                 :            :     }
     154                 :            : 
     155         [ +  - ]:          1 :   if (chunk->const_table)
     156                 :          1 :       g_hash_table_remove_all (chunk->const_table);
     157                 :            : }
     158                 :            : 
     159                 :            : /**
     160                 :            :  * g_string_chunk_insert:
     161                 :            :  * @chunk: a #GStringChunk
     162                 :            :  * @string: the string to add
     163                 :            :  *
     164                 :            :  * Adds a copy of @string to the #GStringChunk.
     165                 :            :  * It returns a pointer to the new copy of the string
     166                 :            :  * in the #GStringChunk. The characters in the string
     167                 :            :  * can be changed, if necessary, though you should not
     168                 :            :  * change anything after the end of the string.
     169                 :            :  *
     170                 :            :  * Unlike g_string_chunk_insert_const(), this function
     171                 :            :  * does not check for duplicates. Also strings added
     172                 :            :  * with g_string_chunk_insert() will not be searched
     173                 :            :  * by g_string_chunk_insert_const() when looking for
     174                 :            :  * duplicates.
     175                 :            :  *
     176                 :            :  * Returns: a pointer to the copy of @string within
     177                 :            :  *     the #GStringChunk
     178                 :            :  */
     179                 :            : gchar*
     180                 :     100003 : g_string_chunk_insert (GStringChunk *chunk,
     181                 :            :                        const gchar  *string)
     182                 :            : {
     183                 :     100003 :   g_return_val_if_fail (chunk != NULL, NULL);
     184                 :            : 
     185                 :     100003 :   return g_string_chunk_insert_len (chunk, string, -1);
     186                 :            : }
     187                 :            : 
     188                 :            : /**
     189                 :            :  * g_string_chunk_insert_const:
     190                 :            :  * @chunk: a #GStringChunk
     191                 :            :  * @string: the string to add
     192                 :            :  *
     193                 :            :  * Adds a copy of @string to the #GStringChunk, unless the same
     194                 :            :  * string has already been added to the #GStringChunk with
     195                 :            :  * g_string_chunk_insert_const().
     196                 :            :  *
     197                 :            :  * This function is useful if you need to copy a large number
     198                 :            :  * of strings but do not want to waste space storing duplicates.
     199                 :            :  * But you must remember that there may be several pointers to
     200                 :            :  * the same string, and so any changes made to the strings
     201                 :            :  * should be done very carefully.
     202                 :            :  *
     203                 :            :  * Note that g_string_chunk_insert_const() will not return a
     204                 :            :  * pointer to a string added with g_string_chunk_insert(), even
     205                 :            :  * if they do match.
     206                 :            :  *
     207                 :            :  * Returns: a pointer to the new or existing copy of @string
     208                 :            :  *     within the #GStringChunk
     209                 :            :  */
     210                 :            : gchar*
     211                 :          2 : g_string_chunk_insert_const (GStringChunk *chunk,
     212                 :            :                              const gchar  *string)
     213                 :            : {
     214                 :            :   char* lookup;
     215                 :            : 
     216                 :          2 :   g_return_val_if_fail (chunk != NULL, NULL);
     217                 :            : 
     218         [ +  + ]:          2 :   if (!chunk->const_table)
     219                 :          1 :     chunk->const_table = g_hash_table_new (g_str_hash, g_str_equal);
     220                 :            : 
     221                 :          2 :   lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
     222                 :            : 
     223         [ +  + ]:          2 :   if (!lookup)
     224                 :            :     {
     225                 :          1 :       lookup = g_string_chunk_insert (chunk, string);
     226                 :          1 :       g_hash_table_add (chunk->const_table, lookup);
     227                 :            :     }
     228                 :            : 
     229                 :          2 :   return lookup;
     230                 :            : }
     231                 :            : 
     232                 :            : /**
     233                 :            :  * g_string_chunk_insert_len:
     234                 :            :  * @chunk: a #GStringChunk
     235                 :            :  * @string: bytes to insert
     236                 :            :  * @len: number of bytes of @string to insert, or -1 to insert a
     237                 :            :  *     nul-terminated string
     238                 :            :  *
     239                 :            :  * Adds a copy of the first @len bytes of @string to the #GStringChunk.
     240                 :            :  * The copy is nul-terminated.
     241                 :            :  *
     242                 :            :  * Since this function does not stop at nul bytes, it is the caller's
     243                 :            :  * responsibility to ensure that @string has at least @len addressable
     244                 :            :  * bytes.
     245                 :            :  *
     246                 :            :  * The characters in the returned string can be changed, if necessary,
     247                 :            :  * though you should not change anything after the end of the string.
     248                 :            :  *
     249                 :            :  * Returns: a pointer to the copy of @string within the #GStringChunk
     250                 :            :  *
     251                 :            :  * Since: 2.4
     252                 :            :  */
     253                 :            : gchar*
     254                 :     100004 : g_string_chunk_insert_len (GStringChunk *chunk,
     255                 :            :                            const gchar  *string,
     256                 :            :                            gssize        len)
     257                 :            : {
     258                 :            :   gsize size;
     259                 :            :   gchar* pos;
     260                 :            : 
     261                 :     100004 :   g_return_val_if_fail (chunk != NULL, NULL);
     262                 :            : 
     263         [ +  + ]:     100004 :   if (len < 0)
     264                 :     100003 :     size = strlen (string);
     265                 :            :   else
     266                 :          1 :     size = (gsize) len;
     267                 :            : 
     268   [ +  -  +  + ]:     100004 :   if ((G_MAXSIZE - chunk->storage_next < size + 1) || (chunk->storage_next + size + 1) > chunk->this_size)
     269                 :            :     {
     270                 :        783 :       gsize new_size = g_nearest_pow (MAX (chunk->default_size, size + 1));
     271                 :            : 
     272                 :            :       /* If size is bigger than G_MAXSIZE / 2 then store it in its own
     273                 :            :        * allocation instead of failing here */
     274         [ -  + ]:        783 :       if (new_size == 0)
     275                 :          0 :         new_size = size + 1;
     276                 :            : 
     277                 :        783 :       chunk->storage_list = g_slist_prepend (chunk->storage_list,
     278                 :            :                                              g_new (gchar, new_size));
     279                 :            : 
     280                 :        783 :       chunk->this_size = new_size;
     281                 :        783 :       chunk->storage_next = 0;
     282                 :            :     }
     283                 :            : 
     284                 :     100004 :   pos = ((gchar *) chunk->storage_list->data) + chunk->storage_next;
     285                 :            : 
     286                 :     100004 :   *(pos + size) = '\0';
     287                 :            : 
     288                 :     100004 :   memcpy (pos, string, size);
     289                 :            : 
     290                 :     100004 :   chunk->storage_next += size + 1;
     291                 :            : 
     292                 :     100004 :   return pos;
     293                 :            : }