eina: fix eina_stringshare format warning after commit 912924a
[platform/upstream/efl.git] / src / lib / eina / eina_stringshare.c
1 /* EINA - EFL data type library
2  * Copyright (C) 2002,2003,2004,2005,2006,2007,2008,2010
3  *                         Carsten Haitzler,
4  *                         Jorge Luis Zapata Muga,
5  *                         Cedric Bail,
6  *                         Gustavo Sverzut Barbieri
7  *                         Tom Hacohen
8  *                         Brett Nash
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Lesser General Public
12  * License as published by the Free Software Foundation; either
13  * version 2.1 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public
21  * License along with this library;
22  * if not, see <http://www.gnu.org/licenses/>.
23  */
24
25 #ifdef HAVE_CONFIG_H
26 # include "config.h"
27 #endif
28
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32
33 #ifdef HAVE_EVIL
34 # include <Evil.h>
35 #endif
36
37 #include "eina_config.h"
38 #include "eina_private.h"
39 #include "eina_alloca.h"
40 #include "eina_log.h"
41 #include "eina_lock.h"
42 #include "eina_share_common.h"
43
44 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
45 #include "eina_safety_checks.h"
46 #include "eina_stringshare.h"
47
48
49 #ifdef CRI
50 #undef CRI
51 #endif
52 #define CRI(...) EINA_LOG_DOM_CRIT(_eina_share_stringshare_log_dom, __VA_ARGS__)
53
54 #ifdef ERR
55 #undef ERR
56 #endif
57 #define ERR(...) EINA_LOG_DOM_ERR(_eina_share_stringshare_log_dom, __VA_ARGS__)
58
59 #ifdef DBG
60 #undef DBG
61 #endif
62 #define DBG(...) EINA_LOG_DOM_DBG(_eina_share_stringshare_log_dom, __VA_ARGS__)
63
64 static int _eina_share_stringshare_log_dom = -1;
65
66 /* The actual share */
67 static Eina_Share *stringshare_share;
68 static const char EINA_MAGIC_STRINGSHARE_NODE_STR[] = "Eina Stringshare Node";
69
70 extern Eina_Bool _share_common_threads_activated;
71 static Eina_Spinlock _mutex_small;
72
73 /* Stringshare optimizations */
74 static const unsigned char _eina_stringshare_single[512] = {
75    0,0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10,0,11,0,12,0,13,0,14,0,15,0,
76    16,0,17,0,18,0,19,0,20,0,21,0,22,0,23,0,24,0,25,0,26,0,27,0,28,0,29,0,30,0,
77    31,0,32,0,33,0,34,0,35,0,36,0,37,0,38,0,39,0,40,0,41,0,42,0,43,0,44,0,45,0,
78    46,0,47,0,48,0,49,0,50,0,51,0,52,0,53,0,54,0,55,0,56,0,57,0,58,0,59,0,60,0,
79    61,0,62,0,63,0,64,0,65,0,66,0,67,0,68,0,69,0,70,0,71,0,72,0,73,0,74,0,75,0,
80    76,0,77,0,78,0,79,0,80,0,81,0,82,0,83,0,84,0,85,0,86,0,87,0,88,0,89,0,90,0,
81    91,0,92,0,93,0,94,0,95,0,96,0,97,0,98,0,99,0,100,0,101,0,102,0,103,0,104,0,
82    105,0,
83    106,0,107,0,108,0,109,0,110,0,111,0,112,0,113,0,114,0,115,0,116,0,117,0,118,
84    0,119,0,120,0,
85    121,0,122,0,123,0,124,0,125,0,126,0,127,0,128,0,129,0,130,0,131,0,132,0,133,
86    0,134,0,135,0,
87    136,0,137,0,138,0,139,0,140,0,141,0,142,0,143,0,144,0,145,0,146,0,147,0,148,
88    0,149,0,150,0,
89    151,0,152,0,153,0,154,0,155,0,156,0,157,0,158,0,159,0,160,0,161,0,162,0,163,
90    0,164,0,165,0,
91    166,0,167,0,168,0,169,0,170,0,171,0,172,0,173,0,174,0,175,0,176,0,177,0,178,
92    0,179,0,180,0,
93    181,0,182,0,183,0,184,0,185,0,186,0,187,0,188,0,189,0,190,0,191,0,192,0,193,
94    0,194,0,195,0,
95    196,0,197,0,198,0,199,0,200,0,201,0,202,0,203,0,204,0,205,0,206,0,207,0,208,
96    0,209,0,210,0,
97    211,0,212,0,213,0,214,0,215,0,216,0,217,0,218,0,219,0,220,0,221,0,222,0,223,
98    0,224,0,225,0,
99    226,0,227,0,228,0,229,0,230,0,231,0,232,0,233,0,234,0,235,0,236,0,237,0,238,
100    0,239,0,240,0,
101    241,0,242,0,243,0,244,0,245,0,246,0,247,0,248,0,249,0,250,0,251,0,252,0,253,
102    0,254,0,255,0
103 };
104
105 typedef struct _Eina_Stringshare_Small Eina_Stringshare_Small;
106 typedef struct _Eina_Stringshare_Small_Bucket Eina_Stringshare_Small_Bucket;
107
108 struct _Eina_Stringshare_Small_Bucket
109 {
110    /* separate arrays for faster lookups */
111    const char **strings;
112    unsigned char *lengths;
113    unsigned int *references;
114    int count;
115    int size;
116 };
117
118 struct _Eina_Stringshare_Small
119 {
120    Eina_Stringshare_Small_Bucket *buckets[256];
121 };
122
123 #define EINA_STRINGSHARE_SMALL_BUCKET_STEP 8
124 static Eina_Stringshare_Small _eina_small_share;
125
126 static inline int
127 _eina_stringshare_small_cmp(const Eina_Stringshare_Small_Bucket *bucket,
128                             int i,
129                             const char *pstr,
130                             unsigned char plength)
131 {
132    /* pstr and plength are from second char and on, since the first is
133     * always the same.
134     *
135     * First string being always the same, size being between 2 and 3
136     * characters (there is a check for special case length==1 and then
137     * small stringshare is applied to strings < 4), we just need to
138     * compare 2 characters of both strings.
139     */
140    const unsigned char cur_plength = bucket->lengths[i] - 1;
141    const char *cur_pstr;
142
143    if (cur_plength > plength)
144      return 1;
145    else if (cur_plength < plength)
146      return -1;
147
148    cur_pstr = bucket->strings[i] + 1;
149
150    if (cur_pstr[0] > pstr[0])
151      return 1;
152    else if (cur_pstr[0] < pstr[0])
153      return -1;
154
155    if (plength == 1)
156      return 0;
157
158    if (cur_pstr[1] > pstr[1])
159      return 1;
160    else if (cur_pstr[1] < pstr[1])
161      return -1;
162
163    return 0;
164 }
165
166 static const char *
167 _eina_stringshare_small_bucket_find(const Eina_Stringshare_Small_Bucket *bucket,
168                                     const char *str,
169                                     unsigned char length,
170                                     int *idx)
171 {
172    const char *pstr = str + 1; /* skip first letter, it's always the same */
173    unsigned char plength = length - 1;
174    int i, low, high;
175
176    if (bucket->count == 0)
177      {
178         *idx = 0;
179         return NULL;
180      }
181
182    low = 0;
183    high = bucket->count;
184
185    while (low < high)
186      {
187         int r;
188
189         i = (low + high - 1) / 2;
190
191         r = _eina_stringshare_small_cmp(bucket, i, pstr, plength);
192         if (r > 0)
193           high = i;
194         else if (r < 0)
195           low = i + 1;
196         else
197           {
198              *idx = i;
199              return bucket->strings[i];
200           }
201      }
202
203    *idx = low;
204    return NULL;
205 }
206
207 static Eina_Bool
208 _eina_stringshare_small_bucket_resize(Eina_Stringshare_Small_Bucket *bucket,
209                                       int size)
210 {
211    void *tmp;
212
213    tmp = realloc((void *)bucket->strings, size * sizeof(bucket->strings[0]));
214    if (!tmp) return 0;
215    bucket->strings = tmp;
216
217    tmp = realloc(bucket->lengths, size * sizeof(bucket->lengths[0]));
218    if (!tmp) return 0;
219    bucket->lengths = tmp;
220
221    tmp = realloc(bucket->references, size * sizeof(bucket->references[0]));
222    if (!tmp) return 0;
223    bucket->references = tmp;
224
225    bucket->size = size;
226    return 1;
227 }
228
229 static const char *
230 _eina_stringshare_small_bucket_insert_at(
231    Eina_Stringshare_Small_Bucket **p_bucket,
232    const char *str,
233    unsigned char length,
234    int idx)
235 {
236    Eina_Stringshare_Small_Bucket *bucket = *p_bucket;
237    int todo, off;
238    char *snew;
239
240    if (!bucket)
241      {
242         *p_bucket = bucket = calloc(1, sizeof(*bucket));
243         if (!bucket) return NULL;
244      }
245
246    if (bucket->count + 1 >= bucket->size)
247      {
248         int size = bucket->size + EINA_STRINGSHARE_SMALL_BUCKET_STEP;
249         if (!_eina_stringshare_small_bucket_resize(bucket, size))
250           return NULL;
251      }
252
253    snew = malloc(length + 1);
254    if (!snew) return NULL;
255
256    memcpy(snew, str, length);
257    snew[length] = '\0';
258
259    off = idx + 1;
260    todo = bucket->count - idx;
261    if (todo > 0)
262      {
263         memmove((void *)(bucket->strings + off), bucket->strings + idx,
264                 todo * sizeof(bucket->strings[0]));
265         memmove(bucket->lengths + off,           bucket->lengths + idx,
266                 todo * sizeof(bucket->lengths[0]));
267         memmove(bucket->references + off,        bucket->references + idx,
268                 todo * sizeof(bucket->references[0]));
269      }
270
271    bucket->strings[idx] = snew;
272    bucket->lengths[idx] = length;
273    bucket->references[idx] = 1;
274    bucket->count++;
275
276    return snew;
277 }
278
279 static void
280 _eina_stringshare_small_bucket_remove_at(
281    Eina_Stringshare_Small_Bucket **p_bucket,
282    int idx)
283 {
284    Eina_Stringshare_Small_Bucket *bucket = *p_bucket;
285    int todo, off;
286
287    if (bucket->references[idx] > 1)
288      {
289         bucket->references[idx]--;
290         return;
291      }
292
293    free((char *)bucket->strings[idx]);
294
295    if (bucket->count == 1)
296      {
297         free((void *)bucket->strings);
298         free(bucket->lengths);
299         free(bucket->references);
300         free(bucket);
301         *p_bucket = NULL;
302         return;
303      }
304
305    bucket->count--;
306    if (idx == bucket->count)
307      goto end;
308
309    off = idx + 1;
310    todo = bucket->count - idx;
311
312    memmove((void *)(bucket->strings + idx), bucket->strings + off,
313            todo * sizeof(bucket->strings[0]));
314    memmove(bucket->lengths + idx,           bucket->lengths + off,
315            todo * sizeof(bucket->lengths[0]));
316    memmove(bucket->references + idx,        bucket->references + off,
317            todo * sizeof(bucket->references[0]));
318
319 end:
320    if (bucket->count + EINA_STRINGSHARE_SMALL_BUCKET_STEP < bucket->size)
321      {
322         int size = bucket->size - EINA_STRINGSHARE_SMALL_BUCKET_STEP;
323         _eina_stringshare_small_bucket_resize(bucket, size);
324      }
325 }
326
327 static const char *
328 _eina_stringshare_small_add(const char *str, unsigned char length)
329 {
330    Eina_Stringshare_Small_Bucket **bucket;
331    int i;
332
333    bucket = _eina_small_share.buckets + (unsigned char)str[0];
334    if (!*bucket)
335      i = 0;
336    else
337      {
338         const char *ret;
339         ret = _eina_stringshare_small_bucket_find(*bucket, str, length, &i);
340         if (ret)
341           {
342              (*bucket)->references[i]++;
343              return ret;
344           }
345      }
346
347    return _eina_stringshare_small_bucket_insert_at(bucket, str, length, i);
348 }
349
350 static void
351 _eina_stringshare_small_del(const char *str, unsigned char length)
352 {
353    Eina_Stringshare_Small_Bucket **bucket;
354    const char *ret;
355    int i;
356
357    bucket = _eina_small_share.buckets + (unsigned char)str[0];
358    if (!*bucket)
359      goto error;
360
361    ret = _eina_stringshare_small_bucket_find(*bucket, str, length, &i);
362    if (!ret)
363      goto error;
364
365    _eina_stringshare_small_bucket_remove_at(bucket, i);
366    return;
367
368 error:
369    CRI("EEEK trying to del non-shared stringshare \"%s\"", str);
370 }
371
372 static void
373 _eina_stringshare_small_init(void)
374 {
375    eina_spinlock_new(&_mutex_small);
376    memset(&_eina_small_share, 0, sizeof(_eina_small_share));
377 }
378
379 static void
380 _eina_stringshare_small_shutdown(void)
381 {
382    Eina_Stringshare_Small_Bucket **p_bucket, **p_bucket_end;
383
384    p_bucket = _eina_small_share.buckets;
385    p_bucket_end = p_bucket + 256;
386
387    for (; p_bucket < p_bucket_end; p_bucket++)
388      {
389         Eina_Stringshare_Small_Bucket *bucket = *p_bucket;
390         char **s, **s_end;
391
392         if (!bucket)
393           continue;
394
395         s = (char **)bucket->strings;
396         s_end = s + bucket->count;
397         for (; s < s_end; s++)
398           free(*s);
399
400         free((void *)bucket->strings);
401         free(bucket->lengths);
402         free(bucket->references);
403         free(bucket);
404         *p_bucket = NULL;
405      }
406
407    eina_spinlock_free(&_mutex_small);
408 }
409
410 static void
411 _eina_stringshare_small_bucket_dump(Eina_Stringshare_Small_Bucket *bucket,
412                                     struct dumpinfo *di)
413 {
414    const char **s = bucket->strings;
415    unsigned char *l = bucket->lengths;
416    unsigned int *r = bucket->references;
417    int i;
418
419    di->used += sizeof(*bucket);
420    di->used += bucket->count * sizeof(*s);
421    di->used += bucket->count * sizeof(*l);
422    di->used += bucket->count * sizeof(*r);
423    di->unique += bucket->count;
424
425    for (i = 0; i < bucket->count; i++, s++, l++, r++)
426      {
427         int dups;
428
429         printf("DDD: %5hhu %5u '%s'\n", *l, *r, *s);
430
431         dups = (*r - 1);
432
433         di->used += *l;
434         di->saved += *l * dups;
435         di->dups += dups;
436      }
437 }
438
439 static void
440 _eina_stringshare_small_dump(struct dumpinfo *di)
441 {
442    Eina_Stringshare_Small_Bucket **p_bucket, **p_bucket_end;
443
444    p_bucket = _eina_small_share.buckets;
445    p_bucket_end = p_bucket + 256;
446
447    for (; p_bucket < p_bucket_end; p_bucket++)
448      {
449         Eina_Stringshare_Small_Bucket *bucket = *p_bucket;
450
451         if (!bucket)
452           continue;
453
454         _eina_stringshare_small_bucket_dump(bucket, di);
455      }
456 }
457
458
459 /*============================================================================*
460  *                                 Global                                     *
461  *============================================================================*/
462
463 /**
464  * @internal
465  * @brief Initialize the share_common module.
466  *
467  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
468  *
469  * This function sets up the share_common module of Eina. It is called by
470  * eina_init().
471  *
472  * @see eina_init()
473  */
474 Eina_Bool
475 eina_stringshare_init(void)
476 {
477    Eina_Bool ret;
478
479    if (_eina_share_stringshare_log_dom < 0)
480      {
481         _eina_share_stringshare_log_dom = eina_log_domain_register
482            ("eina_stringshare", EINA_LOG_COLOR_DEFAULT);
483
484         if (_eina_share_stringshare_log_dom < 0)
485           {
486              EINA_LOG_ERR("Could not register log domain: eina_stringshare");
487              return EINA_FALSE;
488           }
489      }
490
491    ret = eina_share_common_init(&stringshare_share,
492                                 EINA_MAGIC_STRINGSHARE_NODE,
493                                 EINA_MAGIC_STRINGSHARE_NODE_STR);
494    if (ret)
495      _eina_stringshare_small_init();
496    else
497      {
498         eina_log_domain_unregister(_eina_share_stringshare_log_dom);
499         _eina_share_stringshare_log_dom = -1;
500      }
501
502    return ret;
503 }
504
505 /**
506  * @internal
507  * @brief Shut down the share_common module.
508  *
509  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
510  *
511  * This function shuts down the share_common module set up by
512  * eina_share_common_init(). It is called by eina_shutdown().
513  *
514  * @see eina_shutdown()
515  */
516 Eina_Bool
517 eina_stringshare_shutdown(void)
518 {
519    Eina_Bool ret;
520    _eina_stringshare_small_shutdown();
521    ret = eina_share_common_shutdown(&stringshare_share);
522
523    if (_eina_share_stringshare_log_dom >= 0)
524      {
525         eina_log_domain_unregister(_eina_share_stringshare_log_dom);
526         _eina_share_stringshare_log_dom = -1;
527      }
528
529    return ret;
530 }
531
532 /*============================================================================*
533  *                                   API                                      *
534  *============================================================================*/
535
536 EAPI void
537 eina_stringshare_del(Eina_Stringshare *str)
538 {
539    int slen;
540
541    if (!str)
542      return;
543
544    /* special cases */
545    if (str[0] == '\0')
546      slen = 0;
547    else if (str[1] == '\0')
548      slen = 1;
549    else if (str[2] == '\0')
550      slen = 2;
551    else if (str[3] == '\0')
552      slen = 3;
553    else
554      slen = 4;  /* handled later */
555
556    if (slen < 2)
557      {
558         eina_share_common_population_del(stringshare_share, slen);
559
560         return;
561      }
562    else if (slen < 4)
563      {
564         eina_share_common_population_del(stringshare_share, slen);
565         eina_spinlock_take(&_mutex_small);
566         _eina_stringshare_small_del(str, slen);
567         eina_spinlock_release(&_mutex_small);
568
569         return;
570      }
571
572    if (!eina_share_common_del(stringshare_share, str))
573      CRI("EEEK trying to del non-shared stringshare \"%s\"", str);
574 }
575
576 EAPI Eina_Stringshare *
577 eina_stringshare_add_length(const char *str, unsigned int slen)
578 {
579    if (!str)
580      return NULL;
581    else if (slen == 0)
582      {
583         eina_share_common_population_add(stringshare_share, slen);
584
585         return "";
586      }
587    else if (slen == 1)
588      {
589         eina_share_common_population_add(stringshare_share, slen);
590
591         return (Eina_Stringshare *) _eina_stringshare_single + ((*str) << 1);
592      }
593    else if (slen < 4)
594      {
595         const char *s;
596
597         eina_share_common_population_add(stringshare_share, slen);
598         eina_spinlock_take(&_mutex_small);
599         s = _eina_stringshare_small_add(str, slen);
600         eina_spinlock_release(&_mutex_small);
601
602         return s;
603      }
604
605    return eina_share_common_add_length(stringshare_share, str, slen *
606                                        sizeof(char), sizeof(char));
607 }
608
609 EAPI Eina_Stringshare *
610 eina_stringshare_add(const char *str)
611 {
612    if (!str) return NULL;
613    return eina_stringshare_add_length(str, strlen(str));
614 }
615
616 EAPI Eina_Stringshare *
617 eina_stringshare_printf(const char *fmt, ...)
618 {
619    va_list args;
620    char *tmp = NULL;
621    const char *ret = "";
622    int len;
623
624    if (!fmt)
625      return NULL;
626
627    va_start(args, fmt);
628    len = vasprintf(&tmp, fmt, args);
629    va_end(args);
630
631    if (len < 1) goto on_error;
632
633    ret = eina_stringshare_add_length(tmp, len);
634
635  on_error:
636    free(tmp);
637    return ret;
638 }
639
640 EAPI Eina_Stringshare *
641 eina_stringshare_vprintf(const char *fmt, va_list args)
642 {
643    char *tmp = NULL;
644    const char *ret = "";
645    int len;
646
647    if (!fmt)
648      return NULL;
649
650    len = vasprintf(&tmp, fmt, args);
651
652    if (len < 1) goto on_error;
653
654    ret = eina_stringshare_add_length(tmp, len);
655
656  on_error:
657    free(tmp);
658    return ret;
659 }
660
661 EAPI Eina_Stringshare *
662 eina_stringshare_nprintf(unsigned int len, const char *fmt, ...)
663 {
664    va_list args;
665    char *tmp;
666    int size;
667
668    if (!fmt)
669      return NULL;
670
671    if (len == 0)
672      return "";
673
674    tmp = alloca(sizeof(char) * (len + 1));
675
676    va_start(args, fmt);
677    size = vsnprintf(tmp, len, fmt, args);
678    va_end(args);
679
680    if (size < 1)
681      return "";
682
683    return eina_stringshare_add_length(tmp, size);
684 }
685
686 EAPI Eina_Stringshare *
687 eina_stringshare_ref(Eina_Stringshare *str)
688 {
689    int slen;
690
691    if (!str)
692      return NULL;
693
694    /* special cases */
695    if      (str[0] == '\0')
696      slen = 0;
697    else if (str[1] == '\0')
698      slen = 1;
699    else if (str[2] == '\0')
700      slen = 2;
701    else if (str[3] == '\0')
702      slen = 3;
703    else
704      slen = 3 + (int)strlen(str + 3);
705
706    if (slen < 2)
707      {
708         eina_share_common_population_add(stringshare_share, slen);
709
710         return str;
711      }
712    else if (slen < 4)
713      {
714         const char *s;
715
716         eina_share_common_population_add(stringshare_share, slen);
717         eina_spinlock_take(&_mutex_small);
718         s = _eina_stringshare_small_add(str, slen);
719         eina_spinlock_release(&_mutex_small);
720
721         return s;
722      }
723
724    return eina_share_common_ref(stringshare_share, str);
725 }
726
727 EAPI int
728 eina_stringshare_strlen(Eina_Stringshare *str)
729 {
730    int len;
731
732    if (!str) return 0;
733
734    /* special cases */
735    if (str[0] == '\0')
736      return 0;
737
738    if (str[1] == '\0')
739      return 1;
740
741    if (str[2] == '\0')
742      return 2;
743
744    if (str[3] == '\0')
745      return 3;
746
747    len = eina_share_common_length(stringshare_share, (Eina_Stringshare *) str);
748    len = (len > 0) ? len / (int)sizeof(char) : -1;
749    return len;
750 }
751
752 EAPI void
753 eina_stringshare_dump(void)
754 {
755    eina_share_common_dump(stringshare_share,
756                           _eina_stringshare_small_dump,
757                           sizeof(_eina_stringshare_single));
758 }