Optimise single-character insertions
[platform/upstream/glib.git] / glib / gstring.c
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
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 #ifdef HAVE_UNISTD_H
34 #include <unistd.h>
35 #endif
36 #include <stdarg.h>
37 #include <stdlib.h>
38 #include <stdio.h>
39 #include <string.h>
40 #include <ctype.h>
41
42 #include "glib.h"
43 #include "gprintf.h"
44
45 #include "galias.h"
46
47 struct _GStringChunk
48 {
49   GHashTable *const_table;
50   GSList     *storage_list;
51   gsize       storage_next;    
52   gsize       this_size;       
53   gsize       default_size;    
54 };
55
56 G_LOCK_DEFINE_STATIC (string_mem_chunk);
57 static GMemChunk *string_mem_chunk = NULL;
58
59 /* Hash Functions.
60  */
61
62 /**
63  * g_str_equal:
64  * @v1: a key. 
65  * @v2: a key to compare with @v1.
66  * 
67  * Compares two strings and returns %TRUE if they are equal.
68  * It can be passed to g_hash_table_new() as the @key_equal_func
69  * parameter, when using strings as keys in a #GHashTable.
70  *
71  * Returns: %TRUE if the two keys match.
72  */
73 gboolean
74 g_str_equal (gconstpointer v1,
75              gconstpointer v2)
76 {
77   const gchar *string1 = v1;
78   const gchar *string2 = v2;
79   
80   return strcmp (string1, string2) == 0;
81 }
82
83 /**
84  * g_str_hash:
85  * @v: a string key.
86  *
87  * Converts a string to a hash value.
88  * It can be passed to g_hash_table_new() as the @hash_func parameter, 
89  * when using strings as keys in a #GHashTable.
90  *
91  * Returns: a hash value corresponding to the key.
92  */
93 guint
94 g_str_hash (gconstpointer v)
95 {
96   /* 31 bit hash function */
97   const signed char *p = v;
98   guint32 h = *p;
99
100   if (h)
101     for (p += 1; *p != '\0'; p++)
102       h = (h << 5) - h + *p;
103
104   return h;
105 }
106
107 #define MY_MAXSIZE ((gsize)-1)
108
109 static inline gsize
110 nearest_power (gsize base, gsize num)    
111 {
112   if (num > MY_MAXSIZE / 2)
113     {
114       return MY_MAXSIZE;
115     }
116   else
117     {
118       gsize n = base;
119
120       while (n < num)
121         n <<= 1;
122       
123       return n;
124     }
125 }
126
127 /* String Chunks.
128  */
129
130 GStringChunk*
131 g_string_chunk_new (gsize default_size)    
132 {
133   GStringChunk *new_chunk = g_new (GStringChunk, 1);
134   gsize size = 1;    
135
136   size = nearest_power (1, default_size);
137
138   new_chunk->const_table       = NULL;
139   new_chunk->storage_list      = NULL;
140   new_chunk->storage_next      = size;
141   new_chunk->default_size      = size;
142   new_chunk->this_size         = size;
143
144   return new_chunk;
145 }
146
147 void
148 g_string_chunk_free (GStringChunk *chunk)
149 {
150   GSList *tmp_list;
151
152   g_return_if_fail (chunk != NULL);
153
154   if (chunk->storage_list)
155     {
156       for (tmp_list = chunk->storage_list; tmp_list; tmp_list = tmp_list->next)
157         g_free (tmp_list->data);
158
159       g_slist_free (chunk->storage_list);
160     }
161
162   if (chunk->const_table)
163     g_hash_table_destroy (chunk->const_table);
164
165   g_free (chunk);
166 }
167
168 gchar*
169 g_string_chunk_insert (GStringChunk *chunk,
170                        const gchar  *string)
171 {
172   g_return_val_if_fail (chunk != NULL, NULL);
173
174   return g_string_chunk_insert_len (chunk, string, -1);
175 }
176
177 gchar*
178 g_string_chunk_insert_const (GStringChunk *chunk,
179                              const gchar  *string)
180 {
181   char* lookup;
182
183   g_return_val_if_fail (chunk != NULL, NULL);
184
185   if (!chunk->const_table)
186     chunk->const_table = g_hash_table_new (g_str_hash, g_str_equal);
187
188   lookup = (char*) g_hash_table_lookup (chunk->const_table, (gchar *)string);
189
190   if (!lookup)
191     {
192       lookup = g_string_chunk_insert (chunk, string);
193       g_hash_table_insert (chunk->const_table, lookup, lookup);
194     }
195
196   return lookup;
197 }
198
199 /**
200  * g_string_chunk_insert_len:
201  * @chunk: a #GStringChunk
202  * @string: bytes to insert
203  * @len: number of bytes of @string to insert, or -1 to insert a 
204  *     nul-terminated string. 
205  * 
206  * Adds a copy of the first @len bytes of @string to the #GStringChunk. The
207  * copy is nul-terminated.
208  * 
209  * The characters in the string can be changed, if necessary, though you
210  * should not change anything after the end of the string.
211  * 
212  * Return value: a pointer to the copy of @string within the #GStringChunk
213  * 
214  * Since: 2.4
215  **/
216 gchar*
217 g_string_chunk_insert_len (GStringChunk *chunk,
218                            const gchar  *string, 
219                            gssize        len)
220 {
221   gssize size;
222   gchar* pos;
223
224   g_return_val_if_fail (chunk != NULL, NULL);
225
226   if (len < 0)
227     size = strlen (string);
228   else
229     size = len;
230   
231   if ((chunk->storage_next + size + 1) > chunk->this_size)
232     {
233       gsize new_size = nearest_power (chunk->default_size, size + 1);
234
235       chunk->storage_list = g_slist_prepend (chunk->storage_list,
236                                              g_new (gchar, new_size));
237
238       chunk->this_size = new_size;
239       chunk->storage_next = 0;
240     }
241
242   pos = ((gchar *) chunk->storage_list->data) + chunk->storage_next;
243
244   *(pos + size) = '\0';
245
246   strncpy (pos, string, size);
247   if (len > 0)
248     size = strlen (pos);
249
250   chunk->storage_next += size + 1;
251
252   return pos;
253 }
254
255 /* Strings.
256  */
257 static void
258 g_string_maybe_expand (GString* string,
259                        gsize    len) 
260 {
261   if (string->len + len >= string->allocated_len)
262     {
263       string->allocated_len = nearest_power (1, string->len + len + 1);
264       string->str = g_realloc (string->str, string->allocated_len);
265     }
266 }
267
268 GString*
269 g_string_sized_new (gsize dfl_size)    
270 {
271   GString *string;
272
273   G_LOCK (string_mem_chunk);
274   if (!string_mem_chunk)
275     string_mem_chunk = g_mem_chunk_new ("string mem chunk",
276                                         sizeof (GString),
277                                         1024, G_ALLOC_AND_FREE);
278
279   string = g_chunk_new (GString, string_mem_chunk);
280   G_UNLOCK (string_mem_chunk);
281
282   string->allocated_len = 0;
283   string->len   = 0;
284   string->str   = NULL;
285
286   g_string_maybe_expand (string, MAX (dfl_size, 2));
287   string->str[0] = 0;
288
289   return string;
290 }
291
292 GString*
293 g_string_new (const gchar *init)
294 {
295   GString *string;
296
297   if (init == NULL || *init == '\0')
298     string = g_string_sized_new (2);
299   else 
300     {
301       gint len;
302
303       len = strlen (init);
304       string = g_string_sized_new (len + 2);
305
306       g_string_append_len (string, init, len);
307     }
308
309   return string;
310 }
311
312 GString*
313 g_string_new_len (const gchar *init,
314                   gssize       len)    
315 {
316   GString *string;
317
318   if (len < 0)
319     return g_string_new (init);
320   else
321     {
322       string = g_string_sized_new (len);
323       
324       if (init)
325         g_string_append_len (string, init, len);
326       
327       return string;
328     }
329 }
330
331 gchar*
332 g_string_free (GString *string,
333                gboolean free_segment)
334 {
335   gchar *segment;
336
337   g_return_val_if_fail (string != NULL, NULL);
338
339   if (free_segment)
340     {
341       g_free (string->str);
342       segment = NULL;
343     }
344   else
345     segment = string->str;
346
347   G_LOCK (string_mem_chunk);
348   g_mem_chunk_free (string_mem_chunk, string);
349   G_UNLOCK (string_mem_chunk);
350
351   return segment;
352 }
353
354 gboolean
355 g_string_equal (const GString *v,
356                 const GString *v2)
357 {
358   gchar *p, *q;
359   GString *string1 = (GString *) v;
360   GString *string2 = (GString *) v2;
361   gsize i = string1->len;    
362
363   if (i != string2->len)
364     return FALSE;
365
366   p = string1->str;
367   q = string2->str;
368   while (i)
369     {
370       if (*p != *q)
371         return FALSE;
372       p++;
373       q++;
374       i--;
375     }
376   return TRUE;
377 }
378
379 /* 31 bit hash function */
380 guint
381 g_string_hash (const GString *str)
382 {
383   const gchar *p = str->str;
384   gsize n = str->len;    
385   guint h = 0;
386
387   while (n--)
388     {
389       h = (h << 5) - h + *p;
390       p++;
391     }
392
393   return h;
394 }
395
396 GString*
397 g_string_assign (GString     *string,
398                  const gchar *rval)
399 {
400   g_return_val_if_fail (string != NULL, NULL);
401   g_return_val_if_fail (rval != NULL, string);
402
403   /* Make sure assigning to itself doesn't corrupt the string.  */
404   if (string->str != rval)
405     {
406       /* Assigning from substring should be ok since g_string_truncate
407          does not realloc.  */
408       g_string_truncate (string, 0);
409       g_string_append (string, rval);
410     }
411
412   return string;
413 }
414
415 GString*
416 g_string_truncate (GString *string,
417                    gsize    len)    
418 {
419   g_return_val_if_fail (string != NULL, NULL);
420
421   string->len = MIN (len, string->len);
422   string->str[string->len] = 0;
423
424   return string;
425 }
426
427 /**
428  * g_string_set_size:
429  * @string: a #GString
430  * @len: the new length
431  * 
432  * Sets the length of a #GString. If the length is less than
433  * the current length, the string will be truncated. If the
434  * length is greater than the current length, the contents
435  * of the newly added area are undefined. (However, as
436  * always, string->str[string->len] will be a nul byte.) 
437  * 
438  * Return value: @string
439  **/
440 GString*
441 g_string_set_size (GString *string,
442                    gsize    len)    
443 {
444   g_return_val_if_fail (string != NULL, NULL);
445
446   if (len >= string->allocated_len)
447     g_string_maybe_expand (string, len - string->len);
448   
449   string->len = len;
450   string->str[len] = 0;
451
452   return string;
453 }
454
455 GString*
456 g_string_insert_len (GString     *string,
457                      gssize       pos,    
458                      const gchar *val,
459                      gssize       len)    
460 {
461   g_return_val_if_fail (string != NULL, NULL);
462   g_return_val_if_fail (val != NULL, string);
463
464   if (len < 0)
465     len = strlen (val);
466
467   if (pos < 0)
468     pos = string->len;
469   else
470     g_return_val_if_fail (pos <= string->len, string);
471
472   /* Check whether val represents a substring of string.  This test
473      probably violates chapter and verse of the C standards, since
474      ">=" and "<=" are only valid when val really is a substring.
475      In practice, it will work on modern archs.  */
476   if (val >= string->str && val <= string->str + string->len)
477     {
478       gsize offset = val - string->str;
479       gsize precount = 0;
480
481       g_string_maybe_expand (string, len);
482       val = string->str + offset;
483       /* At this point, val is valid again.  */
484
485       /* Open up space where we are going to insert.  */
486       if (pos < string->len)
487         g_memmove (string->str + pos + len, string->str + pos, string->len - pos);
488
489       /* Move the source part before the gap, if any.  */
490       if (offset < pos)
491         {
492           precount = MIN (len, pos - offset);
493           memcpy (string->str + pos, val, precount);
494         }
495
496       /* Move the source part after the gap, if any.  */
497       if (len > precount)
498         memcpy (string->str + pos + precount,
499                 val + /* Already moved: */ precount + /* Space opened up: */ len,
500                 len - precount);
501     }
502   else
503     {
504       g_string_maybe_expand (string, len);
505
506       /* If we aren't appending at the end, move a hunk
507        * of the old string to the end, opening up space
508        */
509       if (pos < string->len)
510         g_memmove (string->str + pos + len, string->str + pos, string->len - pos);
511
512       /* insert the new string */
513       if (len == 1)
514         string->str[pos] = *val;
515       else
516         memcpy (string->str + pos, val, len);
517     }
518
519   string->len += len;
520
521   string->str[string->len] = 0;
522
523   return string;
524 }
525
526 GString*
527 g_string_append (GString     *string,
528                  const gchar *val)
529 {  
530   g_return_val_if_fail (string != NULL, NULL);
531   g_return_val_if_fail (val != NULL, string);
532
533   return g_string_insert_len (string, -1, val, -1);
534 }
535
536 GString*
537 g_string_append_len (GString     *string,
538                      const gchar *val,
539                      gssize       len)    
540 {
541   g_return_val_if_fail (string != NULL, NULL);
542   g_return_val_if_fail (val != NULL, string);
543
544   return g_string_insert_len (string, -1, val, len);
545 }
546
547 #undef g_string_append_c
548 GString*
549 g_string_append_c (GString *string,
550                    gchar    c)
551 {
552   g_return_val_if_fail (string != NULL, NULL);
553
554   return g_string_insert_c (string, -1, c);
555 }
556
557 /**
558  * g_string_append_unichar:
559  * @string: a #GString
560  * @wc: a Unicode character
561  * 
562  * Converts a Unicode character into UTF-8, and appends it
563  * to the string.
564  * 
565  * Return value: @string
566  **/
567 GString*
568 g_string_append_unichar (GString  *string,
569                          gunichar  wc)
570 {  
571   g_return_val_if_fail (string != NULL, NULL);
572   
573   return g_string_insert_unichar (string, -1, wc);
574 }
575
576 GString*
577 g_string_prepend (GString     *string,
578                   const gchar *val)
579 {
580   g_return_val_if_fail (string != NULL, NULL);
581   g_return_val_if_fail (val != NULL, string);
582   
583   return g_string_insert_len (string, 0, val, -1);
584 }
585
586 GString*
587 g_string_prepend_len (GString     *string,
588                       const gchar *val,
589                       gssize       len)    
590 {
591   g_return_val_if_fail (string != NULL, NULL);
592   g_return_val_if_fail (val != NULL, string);
593
594   return g_string_insert_len (string, 0, val, len);
595 }
596
597 GString*
598 g_string_prepend_c (GString *string,
599                     gchar    c)
600 {  
601   g_return_val_if_fail (string != NULL, NULL);
602   
603   return g_string_insert_c (string, 0, c);
604 }
605
606 /**
607  * g_string_prepend_unichar:
608  * @string: a #GString.
609  * @wc: a Unicode character.
610  * 
611  * Converts a Unicode character into UTF-8, and prepends it
612  * to the string.
613  * 
614  * Return value: @string.
615  **/
616 GString*
617 g_string_prepend_unichar (GString  *string,
618                           gunichar  wc)
619 {  
620   g_return_val_if_fail (string != NULL, NULL);
621   
622   return g_string_insert_unichar (string, 0, wc);
623 }
624
625 GString*
626 g_string_insert (GString     *string,
627                  gssize       pos,    
628                  const gchar *val)
629 {
630   g_return_val_if_fail (string != NULL, NULL);
631   g_return_val_if_fail (val != NULL, string);
632   if (pos >= 0)
633     g_return_val_if_fail (pos <= string->len, string);
634   
635   return g_string_insert_len (string, pos, val, -1);
636 }
637
638 GString*
639 g_string_insert_c (GString *string,
640                    gssize   pos,    
641                    gchar    c)
642 {
643   g_return_val_if_fail (string != NULL, NULL);
644
645   g_string_maybe_expand (string, 1);
646
647   if (pos < 0)
648     pos = string->len;
649   else
650     g_return_val_if_fail (pos <= string->len, string);
651   
652   /* If not just an append, move the old stuff */
653   if (pos < string->len)
654     g_memmove (string->str + pos + 1, string->str + pos, string->len - pos);
655
656   string->str[pos] = c;
657
658   string->len += 1;
659
660   string->str[string->len] = 0;
661
662   return string;
663 }
664
665 /**
666  * g_string_insert_unichar:
667  * @string: a #GString
668  * @pos: the position at which to insert character, or -1 to
669  *       append at the end of the string.
670  * @wc: a Unicode character
671  * 
672  * Converts a Unicode character into UTF-8, and insert it
673  * into the string at the given position.
674  * 
675  * Return value: @string
676  **/
677 GString*
678 g_string_insert_unichar (GString *string,
679                          gssize   pos,    
680                          gunichar wc)
681 {
682   gint charlen, first, i;
683   gchar *dest;
684
685   g_return_val_if_fail (string != NULL, NULL);
686
687   /* Code copied from g_unichar_to_utf() */
688   if (wc < 0x80)
689     {
690       first = 0;
691       charlen = 1;
692     }
693   else if (wc < 0x800)
694     {
695       first = 0xc0;
696       charlen = 2;
697     }
698   else if (wc < 0x10000)
699     {
700       first = 0xe0;
701       charlen = 3;
702     }
703    else if (wc < 0x200000)
704     {
705       first = 0xf0;
706       charlen = 4;
707     }
708   else if (wc < 0x4000000)
709     {
710       first = 0xf8;
711       charlen = 5;
712     }
713   else
714     {
715       first = 0xfc;
716       charlen = 6;
717     }
718   /* End of copied code */
719
720   g_string_maybe_expand (string, charlen);
721
722   if (pos < 0)
723     pos = string->len;
724   else
725     g_return_val_if_fail (pos <= string->len, string);
726
727   /* If not just an append, move the old stuff */
728   if (pos < string->len)
729     g_memmove (string->str + pos + charlen, string->str + pos, string->len - pos);
730
731   dest = string->str + pos;
732   /* Code copied from g_unichar_to_utf() */
733   for (i = charlen - 1; i > 0; --i)
734     {
735       dest[i] = (wc & 0x3f) | 0x80;
736       wc >>= 6;
737     }
738   dest[0] = wc | first;
739   /* End of copied code */
740   
741   string->len += charlen;
742
743   string->str[string->len] = 0;
744
745   return string;
746 }
747
748 GString*
749 g_string_erase (GString *string,
750                 gssize   pos,
751                 gssize   len)
752 {
753   g_return_val_if_fail (string != NULL, NULL);
754   g_return_val_if_fail (pos >= 0, string);
755   g_return_val_if_fail (pos <= string->len, string);
756
757   if (len < 0)
758     len = string->len - pos;
759   else
760     {
761       g_return_val_if_fail (pos + len <= string->len, string);
762
763       if (pos + len < string->len)
764         g_memmove (string->str + pos, string->str + pos + len, string->len - (pos + len));
765     }
766
767   string->len -= len;
768   
769   string->str[string->len] = 0;
770
771   return string;
772 }
773
774 /**
775  * g_string_ascii_down:
776  * @string: a GString
777  * 
778  * Converts all upper case ASCII letters to lower case ASCII letters.
779  * 
780  * Return value: passed-in @string pointer, with all the upper case
781  *               characters converted to lower case in place, with
782  *               semantics that exactly match g_ascii_tolower.
783  **/
784 GString*
785 g_string_ascii_down (GString *string)
786 {
787   gchar *s;
788   gint n;
789
790   g_return_val_if_fail (string != NULL, NULL);
791
792   n = string->len;
793   s = string->str;
794
795   while (n)
796     {
797       *s = g_ascii_tolower (*s);
798       s++;
799       n--;
800     }
801
802   return string;
803 }
804
805 /**
806  * g_string_ascii_up:
807  * @string: a GString
808  * 
809  * Converts all lower case ASCII letters to upper case ASCII letters.
810  * 
811  * Return value: passed-in @string pointer, with all the lower case
812  *               characters converted to upper case in place, with
813  *               semantics that exactly match g_ascii_toupper.
814  **/
815 GString*
816 g_string_ascii_up (GString *string)
817 {
818   gchar *s;
819   gint n;
820
821   g_return_val_if_fail (string != NULL, NULL);
822
823   n = string->len;
824   s = string->str;
825
826   while (n)
827     {
828       *s = g_ascii_toupper (*s);
829       s++;
830       n--;
831     }
832
833   return string;
834 }
835
836 /**
837  * g_string_down:
838  * @string: a #GString
839  *  
840  * Converts a #GString to lowercase.
841  *
842  * Returns: the #GString.
843  *
844  * Deprecated: This function uses the locale-specific tolower() function, 
845  * which is almost never the right thing. Use g_string_ascii_down() or 
846  * g_utf8_strdown() instead.
847  */
848 GString*
849 g_string_down (GString *string)
850 {
851   guchar *s;
852   glong n;
853
854   g_return_val_if_fail (string != NULL, NULL);
855
856   n = string->len;    
857   s = (guchar *) string->str;
858
859   while (n)
860     {
861       if (isupper (*s))
862         *s = tolower (*s);
863       s++;
864       n--;
865     }
866
867   return string;
868 }
869
870 /**
871  * g_string_up:
872  * @string: a #GString 
873  * 
874  * Converts a #GString to uppercase.
875  * 
876  * Return value: the #GString
877  *
878  * Deprecated: This function uses the locale-specific toupper() function, 
879  * which is almost never the right thing. Use g_string_ascii_up() or 
880  * g_utf8_strup() instead.
881  **/
882 GString*
883 g_string_up (GString *string)
884 {
885   guchar *s;
886   glong n;
887
888   g_return_val_if_fail (string != NULL, NULL);
889
890   n = string->len;
891   s = (guchar *) string->str;
892
893   while (n)
894     {
895       if (islower (*s))
896         *s = toupper (*s);
897       s++;
898       n--;
899     }
900
901   return string;
902 }
903
904 static void
905 g_string_append_printf_internal (GString     *string,
906                                  const gchar *fmt,
907                                  va_list      args)
908 {
909   gchar *buffer;
910   gint length;
911   
912   length = g_vasprintf (&buffer, fmt, args);
913   g_string_append_len (string, buffer, length);
914   g_free (buffer);
915 }
916
917 void
918 g_string_printf (GString *string,
919                  const gchar *fmt,
920                  ...)
921 {
922   va_list args;
923
924   g_string_truncate (string, 0);
925
926   va_start (args, fmt);
927   g_string_append_printf_internal (string, fmt, args);
928   va_end (args);
929 }
930
931 void
932 g_string_append_printf (GString *string,
933                         const gchar *fmt,
934                         ...)
935 {
936   va_list args;
937
938   va_start (args, fmt);
939   g_string_append_printf_internal (string, fmt, args);
940   va_end (args);
941 }
942
943 #define __G_STRING_C__
944 #include "galiasdef.c"