From d709f30132d02d0665d28b7fdd6d3935206b7c23 Mon Sep 17 00:00:00 2001 From: tasn Date: Tue, 27 Jul 2010 08:55:23 +0000 Subject: [PATCH] Eina: Add Eina_UStringshare and Eina_Binshare. Also modified Eina_Stringshare to share most of the code with the two above. Added Magics for Eina_UStrbuf as well as for UStringshare/Binshare. git-svn-id: http://svn.enlightenment.org/svn/e/trunk/eina@50533 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- AUTHORS | 1 + src/include/Eina.h | 3 + src/include/Makefile.am | 3 + src/include/eina_binshare.h | 85 ++++ src/include/eina_inline_stringshare.x | 2 + src/include/eina_inline_ustringshare.x | 92 ++++ src/include/eina_private.h | 13 +- src/include/eina_ustringshare.h | 89 ++++ src/lib/Makefile.am | 3 + src/lib/eina_binshare.c | 212 ++++++++ src/lib/eina_main.c | 9 +- src/lib/eina_share_common.c | 863 +++++++++++++++++++++++++++++++ src/lib/eina_share_common.h | 93 ++++ src/lib/eina_stringshare.c | 898 ++++----------------------------- src/lib/eina_ustringshare.c | 242 +++++++++ 15 files changed, 1797 insertions(+), 811 deletions(-) create mode 100644 src/include/eina_binshare.h create mode 100644 src/include/eina_inline_ustringshare.x create mode 100644 src/include/eina_ustringshare.h create mode 100644 src/lib/eina_binshare.c create mode 100644 src/lib/eina_share_common.c create mode 100644 src/lib/eina_share_common.h create mode 100644 src/lib/eina_ustringshare.c diff --git a/AUTHORS b/AUTHORS index 223a257..8666800 100644 --- a/AUTHORS +++ b/AUTHORS @@ -14,3 +14,4 @@ Raphael Kubo da Costa Gustavo Chaves Fabiano Fidêncio Brett Nash +Tom Hacohen diff --git a/src/include/Eina.h b/src/include/Eina.h index 32071aa..2cc7f5d 100644 --- a/src/include/Eina.h +++ b/src/include/Eina.h @@ -15,6 +15,7 @@ * Raphael Kubo da Costa * Tilman Sauerbeck * Vincent "caro" Torri + * Tom Hacohen * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -135,7 +136,9 @@ extern "C" { #include "eina_error.h" #include "eina_log.h" #include "eina_array.h" +#include "eina_binshare.h" #include "eina_stringshare.h" +#include "eina_ustringshare.h" #include "eina_magic.h" #include "eina_counter.h" #include "eina_rbtree.h" diff --git a/src/include/Makefile.am b/src/include/Makefile.am index bb3b4b0..52eed11 100644 --- a/src/include/Makefile.am +++ b/src/include/Makefile.am @@ -25,7 +25,10 @@ eina_counter.h \ eina_inline_array.x \ eina_magic.h \ eina_stringshare.h \ +eina_binshare.h \ +eina_ustringshare.h \ eina_inline_stringshare.x \ +eina_inline_ustringshare.x \ eina_inline_list.x \ eina_accessor.h \ eina_convert.h \ diff --git a/src/include/eina_binshare.h b/src/include/eina_binshare.h new file mode 100644 index 0000000..3d67f39 --- /dev/null +++ b/src/include/eina_binshare.h @@ -0,0 +1,85 @@ +/* EINA - EFL data type library + * Copyright (C) 2002-2008 Carsten Haitzler, Jorge Luis Zapata Muga, Cedric Bail + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + * + * This file incorporates work covered by the following copyright and + * permission notice: + * + * Copyright (C) 2008 Peter Wehrfritz + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its Copyright notices. In addition publicly + * documented acknowledgment must be given that this software has been used if no + * source code of this software is made available publicly. This includes + * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing + * documents or any documentation provided with any product containing this + * software. This License does not apply to any software that links to the + * libraries provided by this software (statically or dynamically), but only to + * the software provided. + * + * Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice + * and it's intent. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef EINA_BINSHARE_H_ +#define EINA_BINSHARE_H_ + +#include "eina_types.h" + +/** + * @addtogroup Eina_Data_Types_Group Data Types + * + * @{ + */ + +/** + * @defgroup Eina_Binshare_Group Binary Share + * + * @{ + */ + +EAPI Eina_Bool eina_binshare_init(void); +EAPI Eina_Bool eina_binshare_shutdown(void); +EAPI const char *eina_binshare_add_length(const char *str, unsigned int slen) EINA_WARN_UNUSED_RESULT; +EAPI const char *eina_binshare_add(const char *str) EINA_WARN_UNUSED_RESULT; +EAPI const char *eina_binshare_ref(const char *str); +EAPI void eina_binshare_del(const char *str); +EAPI int eina_binshare_length(const char *str) EINA_CONST EINA_WARN_UNUSED_RESULT; +EAPI void eina_binshare_dump(void); + +/** + * @} + */ + +/** + * @} + */ + +#endif /* EINA_STRINGSHARE_H_ */ diff --git a/src/include/eina_inline_stringshare.x b/src/include/eina_inline_stringshare.x index 438218b..bfd7677 100644 --- a/src/include/eina_inline_stringshare.x +++ b/src/include/eina_inline_stringshare.x @@ -19,6 +19,8 @@ #ifndef EINA_STRINGSHARE_INLINE_H_ #define EINA_STRINGSHARE_INLINE_H_ +#include +#include "eina_stringshare.h" /** * @addtogroup Eina_Stringshare_Group Stringshare * diff --git a/src/include/eina_inline_ustringshare.x b/src/include/eina_inline_ustringshare.x new file mode 100644 index 0000000..80cca75 --- /dev/null +++ b/src/include/eina_inline_ustringshare.x @@ -0,0 +1,92 @@ +/* EINA - EFL data type library + * Copyright (C) 2002-2008 Gustavo Sverzut Barbieri + Tom Hacohen + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + */ + +#ifndef EINA_USTRINGSHARE_INLINE_H_ +#define EINA_USTRINGSHARE_INLINE_H_ + +#include "eina_unicode.h" +#include "eina_ustringshare.h" +/** + * @addtogroup Eina_UStringshare_Group UStringshare + * + * @{ + */ + +/** + * Replace the previously stringshared pointer with new content. + * + * The string pointed by @a p_str should be previously stringshared or + * @c NULL and it will be eina_ustringshare_del(). The new string will + * be passed to eina_ustringshare_add() and then assigned to @c *p_str. + * + * @param p_str pointer to the stringhare to be replaced. Must not be + * @c NULL, but @c *p_str may be @c NULL as it is a valid + * stringshare handle. + * @param news new string to be stringshared, may be @c NULL. + * + * @return #EINA_TRUE if the strings were different and thus replaced, + * #EINA_FALSE if the strings were the same after shared. + */ +static inline Eina_Bool +eina_ustringshare_replace(const Eina_Unicode **p_str, const Eina_Unicode *news) +{ + if (*p_str == news) return EINA_FALSE; + + news = eina_ustringshare_add(news); + eina_ustringshare_del(*p_str); + if (*p_str == news) + return EINA_FALSE; + *p_str = news; + return EINA_TRUE; +} + +/** + * Replace the previously stringshared pointer with a new content. + * + * The string pointed by @a p_str should be previously stringshared or + * @c NULL and it will be eina_ustringshare_del(). The new string will + * be passed to eina_ustringshare_add_length() and then assigned to @c *p_str. + * + * @param p_str pointer to the stringhare to be replaced. Must not be + * @c NULL, but @c *p_str may be @c NULL as it is a valid + * stringshare handle. + * @param news new string to be stringshared, may be @c NULL. + * @param slen The string size (<= strlen(str)). + * + * @return #EINA_TRUE if the strings were different and thus replaced, + * #EINA_FALSE if the strings were the same after shared. + */ +static inline Eina_Bool +eina_ustringshare_replace_length(const Eina_Unicode **p_str, const Eina_Unicode *news, unsigned int slen) +{ + if (*p_str == news) return EINA_FALSE; + + news = eina_ustringshare_add_length(news, slen); + eina_ustringshare_del(*p_str); + if (*p_str == news) + return EINA_FALSE; + *p_str = news; + return EINA_TRUE; +} + +/** + * @} + */ + +#endif /* EINA_USTRINGSHARE_INLINE_H_ */ diff --git a/src/include/eina_private.h b/src/include/eina_private.h index 8e05bf6..06b7a6f 100644 --- a/src/include/eina_private.h +++ b/src/include/eina_private.h @@ -52,9 +52,11 @@ #define EINA_LOG_COLOR_DEFAULT "\033[36m" /* eina magic types */ -#define EINA_MAGIC_STRINGSHARE 0x98761234 -#define EINA_MAGIC_STRINGSHARE_NODE 0x98761235 -#define EINA_MAGIC_STRINGSHARE_HEAD 0x98761236 +#define EINA_MAGIC_SHARE 0x98761234 +#define EINA_MAGIC_SHARE_HEAD 0x98761235 +#define EINA_MAGIC_STRINGSHARE_NODE 0x98761254 +#define EINA_MAGIC_USTRINGSHARE_NODE 0x98761255 +#define EINA_MAGIC_BINSHARE_NODE 0x98761256 #define EINA_MAGIC_LIST 0x98761237 #define EINA_MAGIC_LIST_ITERATOR 0x98761238 @@ -81,6 +83,7 @@ #define EINA_MAGIC_MATRIXSPARSE_CELL_ACCESSOR 0x98761249 #define EINA_MAGIC_STRBUF 0x98761250 +#define EINA_MAGIC_USTRBUF 0x98761257 #define EINA_MAGIC_QUADTREE 0x98761251 #define EINA_MAGIC_QUADTREE_ROOT 0x98761252 @@ -121,8 +124,8 @@ } while(0); #ifdef EFL_HAVE_THREADS -void eina_stringshare_threads_init(void); -void eina_stringshare_threads_shutdown(void); +void eina_share_common_threads_init(void); +void eina_share_common_threads_shutdown(void); void eina_log_threads_init(void); void eina_log_threads_shutdown(void); #endif diff --git a/src/include/eina_ustringshare.h b/src/include/eina_ustringshare.h new file mode 100644 index 0000000..ef8df5f --- /dev/null +++ b/src/include/eina_ustringshare.h @@ -0,0 +1,89 @@ +/* EINA - EFL data type library + * Copyright (C) 2002-2008 Carsten Haitzler, Jorge Luis Zapata Muga, Cedric Bail + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + * + * This file incorporates work covered by the following copyright and + * permission notice: + * + * Copyright (C) 2008 Peter Wehrfritz + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its Copyright notices. In addition publicly + * documented acknowledgment must be given that this software has been used if no + * source code of this software is made available publicly. This includes + * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing + * documents or any documentation provided with any product containing this + * software. This License does not apply to any software that links to the + * libraries provided by this software (statically or dynamically), but only to + * the software provided. + * + * Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice + * and it's intent. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef EINA_USTRINGSHARE_H_ +#define EINA_USTRINGSHARE_H_ + +#include "eina_types.h" +#include "eina_unicode.h" + +/** + * @addtogroup Eina_Data_Types_Group Data Types + * + * @{ + */ + +/** + * @defgroup Eina_UStringshare_Group Unicode Stringshare + * + * @{ + */ + +EAPI const Eina_Unicode *eina_ustringshare_add_length(const Eina_Unicode *str, unsigned int slen) EINA_WARN_UNUSED_RESULT; +EAPI const Eina_Unicode *eina_ustringshare_add(const Eina_Unicode *str) EINA_WARN_UNUSED_RESULT; +EAPI const Eina_Unicode *eina_ustringshare_ref(const Eina_Unicode *str); +EAPI void eina_ustringshare_del(const Eina_Unicode *str); +EAPI int eina_ustringshare_strlen(const Eina_Unicode *str) EINA_CONST EINA_WARN_UNUSED_RESULT; +EAPI void eina_ustringshare_dump(void); + +static inline Eina_Bool eina_ustringshare_replace(const Eina_Unicode **p_str, const Eina_Unicode *news) EINA_ARG_NONNULL(1); +static inline Eina_Bool eina_ustringshare_replace_length(const Eina_Unicode **p_str, const Eina_Unicode *news, unsigned int slen) EINA_ARG_NONNULL(1); + +#include "eina_inline_ustringshare.x" + +/** + * @} + */ + +/** + * @} + */ + +#endif /* EINA_STRINGSHARE_H_ */ diff --git a/src/lib/Makefile.am b/src/lib/Makefile.am index 7628e7f..740a3d4 100644 --- a/src/lib/Makefile.am +++ b/src/lib/Makefile.am @@ -32,7 +32,10 @@ eina_fp.c \ eina_rbtree.c \ eina_benchmark.c \ eina_rectangle.c \ +eina_share_common.c \ +eina_binshare.c \ eina_stringshare.c \ +eina_ustringshare.c \ eina_cpu.c \ eina_tiler.c \ eina_hamster.c \ diff --git a/src/lib/eina_binshare.c b/src/lib/eina_binshare.c new file mode 100644 index 0000000..c7d2884 --- /dev/null +++ b/src/lib/eina_binshare.c @@ -0,0 +1,212 @@ +/* + * vim:ts=8:sw=3:sts=8:noexpandtab:cino=>5n-3f0^-2{2 + */ +/* EINA - EFL data type library + * Copyright (C) 2002-2008 Carsten Haitzler, + * Jorge Luis Zapata Muga, + * Cedric Bail, + * Gustavo Sverzut Barbieri + * Tom Hacohen + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + + */ + /** + * @page tutorial_binshare_page Binary Share Tutorial + * + * Should call eina_binshare_init() before usage and eina_binshare_shutdown() after. + * to be written... + * + */ + +#include "eina_share_common.h" +#include "eina_unicode.h" +#include "eina_private.h" + +/* The actual share */ +static Eina_Share *share; +static const char EINA_MAGIC_BINSHARE_NODE_STR[] = "Eina Binshare Node"; + +/*============================================================================* + * Global * + *============================================================================*/ + +/** + * @internal + * @brief Initialize the share_common module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function sets up the share_common module of Eina. It is called by + * eina_init(). + * + * @see eina_init() + */ +EAPI Eina_Bool +eina_binshare_init(void) +{ + return eina_share_common_init(&share, EINA_MAGIC_BINSHARE_NODE, EINA_MAGIC_BINSHARE_NODE_STR); +} + +/** + * @internal + * @brief Shut down the share_common module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function shuts down the share_common module set up by + * eina_share_common_init(). It is called by eina_shutdown(). + * + * @see eina_shutdown() + */ +EAPI Eina_Bool +eina_binshare_shutdown(void) +{ + Eina_Bool ret; + ret = eina_share_common_shutdown(&share); + return ret; +} + +/*============================================================================* + * API * + *============================================================================*/ +/** + * @addtogroup Eina_Binshare_Group Binary Share + * + * These functions allow you to store one copy of a string, and use it + * throughout your program. + * + * This is a method to reduce the number of duplicated strings kept in + * memory. It's pretty common for the same strings to be dynamically + * allocated repeatedly between applications and libraries, especially in + * circumstances where you could have multiple copies of a structure that + * allocates the string. So rather than duplicating and freeing these + * strings, you request a read-only pointer to an existing string and + * only incur the overhead of a hash lookup. + * + * It sounds like micro-optimizing, but profiling has shown this can have + * a significant impact as you scale the number of copies up. It improves + * string creation/destruction speed, reduces memory use and decreases + * memory fragmentation, so a win all-around. + * + * For more information, you can look at the @ref tutorial_binshare_page. + * + * @{ + */ + +/** + * @brief Note that the given string has lost an instance. + * + * @param str string The given string. + * + * This function decreases the reference counter associated to @p str + * if it exists. If that counter reaches 0, the memory associated to + * @p str is freed. If @p str is NULL, the function returns + * immediatly. + * + * Note that if the given pointer is not shared or NULL, bad things + * will happen, likely a segmentation fault. + */ +EAPI void +eina_binshare_del(const char *str, unsigned int slen) +{ + if (!str) + return; + eina_share_common_del(share,(const char *) str, slen); +} + +/** + * @brief Retrieve an instance of a string for use in a program. + * + * @param str The binary string to retrieve an instance of. + * @param slen The byte size + * @return A pointer to an instance of the string on success. + * @c NULL on failure. + * + * This function retrieves an instance of @p str. If @p str is + * @c NULL, then @c NULL is returned. If @p str is already stored, it + * is just returned and its reference counter is increased. Otherwise + * it is added to the strings to be searched and a duplicated string + * of @p str is returned. + * + * This function does not check string size, but uses the + * exact given size. This can be used to share_common part of a larger + * buffer or substring. + * + * @see eina_binshare_add() + */ +EAPI const char * +eina_binshare_add_length(const char *str, unsigned int slen) +{ + return (const char *) eina_share_common_add_length(share,(const char *) str, (slen + 1) * sizeof(char), 0); +} + +/** + * Increment references of the given shared string. + * + * @param str The shared string. + * @return A pointer to an instance of the string on success. + * @c NULL on failure. + * + * This is similar to eina_share_common_add(), but it's faster since it will + * avoid lookups if possible, but on the down side it requires the parameter + * to be shared before, in other words, it must be the return of a previous + * eina_binshare_add(). + * + * There is no unref since this is the work of eina_binshare_del(). + */ +EAPI const char * +eina_binshare_ref(const char *str) +{ + if (!str) + { + return (const char *) eina_share_common_ref(share, (const char *) str); + } + return (const char *) eina_share_common_ref(share, (const char *) str); +} + +/** + * @brief Note that the given string @b must be shared. + * + * @param str the shared string to know the length. It is safe to + * give NULL, in that case -1 is returned. + * + * This function is a cheap way to known the length of a shared + * string. Note that if the given pointer is not shared, bad + * things will happen, likely a segmentation fault. If in doubt, try + * strlen(). + */ +EAPI int +eina_binshare_length(const char *str) +{ + return eina_share_common_length(share, (const char *) str); +} + +/** + * @brief Dump the contents of the share_common. + * + * This function dumps all strings in the share_common to stdout with a + * DDD: prefix per line and a memory usage summary. + */ +EAPI void +eina_binshare_dump(void) +{ + eina_share_common_dump(share, NULL, 0); +} + +/** + * @} + */ + diff --git a/src/lib/eina_main.c b/src/lib/eina_main.c index fefae7d..d1c62dc 100644 --- a/src/lib/eina_main.c +++ b/src/lib/eina_main.c @@ -40,6 +40,7 @@ #include "eina_log.h" #include "eina_hash.h" #include "eina_stringshare.h" +#include "eina_ustringshare.h" #include "eina_list.h" #include "eina_matrixsparse.h" #include "eina_array.h" @@ -110,6 +111,7 @@ S(module); S(mempool); S(list); S(stringshare); +S(ustringshare); S(matrixsparse); S(convert); S(counter); @@ -139,6 +141,7 @@ static const struct eina_desc_setup _eina_desc_setup[] = { S(mempool), S(list), S(stringshare), + S(ustringshare), S(matrixsparse), S(convert), S(counter), @@ -288,13 +291,13 @@ eina_threads_init(void) ++_eina_main_thread_count; ret = _eina_main_thread_count; - if(_eina_main_thread_count > 1) + if(_eina_main_thread_count > 1) { UNLOCK(); return ret; } - eina_stringshare_threads_init(); + eina_share_common_threads_init(); eina_log_threads_init(); _threads_activated = EINA_TRUE; @@ -332,7 +335,7 @@ eina_threads_shutdown(void) return ret; } - eina_stringshare_threads_shutdown(); + eina_share_common_threads_shutdown(); eina_log_threads_shutdown(); _threads_activated = EINA_FALSE; diff --git a/src/lib/eina_share_common.c b/src/lib/eina_share_common.c new file mode 100644 index 0000000..0af95ca --- /dev/null +++ b/src/lib/eina_share_common.c @@ -0,0 +1,863 @@ +/* + * vim:ts=8:sw=3:sts=8:noexpandtab:cino=>5n-3f0^-2{2 + */ +/* EINA - EFL data type library + * Copyright (C) 2002,2003,2004,2005,2006,2007,2008,2010 + * Carsten Haitzler, + * Jorge Luis Zapata Muga, + * Cedric Bail, + * Gustavo Sverzut Barbieri + * Tom Hacohen + * Brett Nash + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + * + * This file incorporates work covered by the following copyright and + * permission notice: + * + * Copyright (C) 2008 Peter Wehrfritz + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its Copyright notices. In addition publicly + * documented acknowledgment must be given that this software has been used if no + * source code of this software is made available publicly. This includes + * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing + * documents or any documentation provided with any product containing this + * software. This License does not apply to any software that links to the + * libraries provided by this software (statically or dynamically), but only to + * the software provided. + * + * Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice + * and it's intent. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include +#include +#include +#include + +#ifdef EFL_HAVE_POSIX_THREADS +# include +#endif + +#ifdef HAVE_EVIL +# include +#endif + +#include "eina_config.h" +#include "eina_private.h" +#include "eina_hash.h" +#include "eina_rbtree.h" +#include "eina_error.h" + +/* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ +#include "eina_safety_checks.h" +#include "eina_share_common.h" + +/*============================================================================* + * Local * + *============================================================================*/ + +/** + * @cond LOCAL + */ + +#define EINA_SHARE_COMMON_BUCKETS 256 +#define EINA_SHARE_COMMON_MASK 0xFF + +static const char EINA_MAGIC_SHARE_STR[] = "Eina Share"; +static const char EINA_MAGIC_SHARE_HEAD_STR[] = "Eina Share Head"; + + +#define EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(d, unlock, ...) \ + do { \ + if (!EINA_MAGIC_CHECK((d), EINA_MAGIC_SHARE_HEAD)) \ + { \ + EINA_MAGIC_FAIL((d), EINA_MAGIC_SHARE_HEAD); \ + unlock; \ + return __VA_ARGS__; \ + } \ + } while (0) + +#define EINA_MAGIC_CHECK_SHARE_COMMON_NODE(d, _node_magic, unlock) \ + do { \ + if (!EINA_MAGIC_CHECK((d), _node_magic)) \ + { \ + unlock; \ + EINA_MAGIC_FAIL((d), _node_magic); \ + } \ + } while (0) + +#ifdef EINA_SHARE_USAGE +typedef struct _Eina_Share_Common_Population Eina_Share_Common_Population; +#endif + +typedef struct _Eina_Share_Common Eina_Share_Common; +typedef struct _Eina_Share_Common_Node Eina_Share_Common_Node; +typedef struct _Eina_Share_Common_Head Eina_Share_Common_Head; + +int _eina_share_common_log_dom = -1; + +struct _Eina_Share +{ + Eina_Share_Common *share; + Eina_Magic node_magic; +#ifdef EINA_SHARE_COMMON_USAGE + Eina_Share_Common_Population population; + int max_node_population; +#endif +}; + +struct _Eina_Share_Common +{ + Eina_Share_Common_Head *buckets[EINA_SHARE_COMMON_BUCKETS]; + + EINA_MAGIC +}; + +struct _Eina_Share_Common_Node +{ + Eina_Share_Common_Node *next; + + EINA_MAGIC + + unsigned int length; + unsigned int references; + char str[]; +}; + +struct _Eina_Share_Common_Head +{ + EINA_RBTREE; + EINA_MAGIC + + int hash; + +#ifdef EINA_SHARE_COMMON_USAGE + int population; +#endif + + Eina_Share_Common_Node *head; + Eina_Share_Common_Node builtin_node; +}; + +#ifdef EFL_HAVE_THREADS +Eina_Bool _share_common_threads_activated = EINA_FALSE; + +# ifdef EFL_HAVE_POSIX_THREADS +static pthread_mutex_t _mutex_big = PTHREAD_MUTEX_INITIALIZER; +# define SHARE_COMMON_LOCK_BIG() if(_share_common_threads_activated) pthread_mutex_lock(&_mutex_big) +# define SHARE_COMMON_UNLOCK_BIG() if(_share_common_threads_activated) pthread_mutex_unlock(&_mutex_big) +# else /* EFL_HAVE_WIN32_THREADS */ +static HANDLE _mutex_big = NULL; +# define SHARE_COMMON_LOCK_BIG() if(_share_common_threads_activated) WaitForSingleObject(_mutex_big, INFINITE) +# define SHARE_COMMON_UNLOCK_BIG() if(_share_common_threads_activated) ReleaseMutex(_mutex_big) + +# endif /* EFL_HAVE_WIN32_THREADS */ +#else /* EFL_HAVE_THREADS */ +# define SHARE_COMMON_LOCK_BIG() do {} while (0) +# define SHARE_COMMON_UNLOCK_BIG() do {} while (0) +#endif + +#ifdef EINA_SHARE_COMMON_USAGE +struct _Eina_Share_Common_Population +{ + int count; + int max; +}; + +static Eina_Share_Common_Population population = { 0, 0 }; + +static Eina_Share_Common_Population population_group[4] = + { + { 0, 0 }, + { 0, 0 }, + { 0, 0 }, + { 0, 0 } + }; + +static void +_eina_share_common_population_init(Eina_Share *share) +{ + unsigned int i; + + for (i = 0; i < sizeof (share->population_group) / sizeof (share->population_group[0]); ++i) + { + share->population_group[i].count = 0; + share->population_group[i].max = 0; + } +} + +static void +_eina_share_common_population_shutdown(Eina_Share *share) +{ + unsigned int i; + + share->max_node_population = 0; + share->population.count = 0; + share->population.max = 0; + + for (i = 0; i < sizeof (share->population_group) / sizeof (share->population_group[0]); ++i) + { + share->population_group[i].count = 0; + share->population_group[i].max = 0; + } +} + +static void +_eina_share_common_population_stats(Eina_Share *share) +{ + unsigned int i; + + fprintf(stderr, "eina share_common statistic:\n"); + fprintf(stderr, " * maximum shared strings : %i\n", share->population.max); + fprintf(stderr, " * maximum shared strings per node : %i\n", share->max_node_population); + + for (i = 0; i < sizeof (share->population_group) / sizeof (share->population_group[0]); ++i) + fprintf(stderr, "DDD: %i strings of length %i, max strings: %i\n", share->population_group[i].count, i, share->population_group[i].max); +} + +void +eina_share_common_population_add(Eina_Share *share, int slen) +{ + SHARE_COMMON_LOCK_BIG(); + + share->population.count++; + if (share->population.count > share->population.max) + share->population.max = share->population.count; + + if (slen < 4) + { + share->population_group[slen].count++; + if (share->population_group[slen].count > share->population_group[slen].max) + share->population_group[slen].max = share->population_group[slen].count; + } + + SHARE_COMMON_UNLOCK_BIG(); +} + +void +eina_share_common_population_del(Eina_Share *share, int slen) +{ + SHARE_COMMON_LOCK_BIG(); + + share->population.count--; + if (slen < 4) + share->population_group[slen].count--; + + SHARE_COMMON_UNLOCK_BIG(); +} + +static void +_eina_share_common_population_head_init(Eina_Share *share, Eina_Share_Common_Head *head) +{ + head->population = 1; +} + +static void +_eina_share_common_population_head_add(Eina_Share *share, Eina_Share_Common_Head *head) +{ + head->population++; + if (head->population > share->max_node_population) + share->max_node_population = head->population; +} + +static void +_eina_share_common_population_head_del(Eina_Share *share, Eina_Share_Common_Head *head) +{ + head->population--; +} + +#else /* EINA_SHARE_COMMON_USAGE undefined */ + +static void _eina_share_common_population_init(__UNUSED__ Eina_Share *share) {} +static void _eina_share_common_population_shutdown(__UNUSED__ Eina_Share *share) {} +static void _eina_share_common_population_stats(__UNUSED__ Eina_Share *share) {} +void eina_share_common_population_add(__UNUSED__ Eina_Share *share, __UNUSED__ int slen) {} +void eina_share_common_population_del(__UNUSED__ Eina_Share *share, __UNUSED__ int slen) {} +static void _eina_share_common_population_head_init(__UNUSED__ Eina_Share *share, __UNUSED__ Eina_Share_Common_Head *head) {} +static void _eina_share_common_population_head_add(__UNUSED__ Eina_Share *share, __UNUSED__ Eina_Share_Common_Head *head) {} +static void _eina_share_common_population_head_del(__UNUSED__ Eina_Share *share, __UNUSED__ Eina_Share_Common_Head *head) {} +#endif + +static int +_eina_share_common_cmp(const Eina_Share_Common_Head *ed, const int *hash, __UNUSED__ int length, __UNUSED__ void *data) +{ + EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, , 0); + + return ed->hash - *hash; +} + +static Eina_Rbtree_Direction +_eina_share_common_node(const Eina_Share_Common_Head *left, const Eina_Share_Common_Head *right, __UNUSED__ void *data) +{ + EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(left, , 0); + EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(right, , 0); + + if (left->hash - right->hash < 0) + return EINA_RBTREE_LEFT; + return EINA_RBTREE_RIGHT; +} + +static void +_eina_share_common_head_free(Eina_Share_Common_Head *ed, __UNUSED__ void *data) +{ + EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, ); + + while (ed->head) + { + Eina_Share_Common_Node *el = ed->head; + + ed->head = ed->head->next; + if (el != &ed->builtin_node) + MAGIC_FREE(el); + } + MAGIC_FREE(ed); +} + +static void +_eina_share_common_node_init(Eina_Share_Common_Node *node, const char *str, int slen, unsigned int null_size, Eina_Magic node_magic) +{ + EINA_MAGIC_SET(node, node_magic); + node->references = 1; + node->length = slen; + memcpy(node->str, str, slen); + memset(node->str + slen, 0, null_size); /* Nullify the null */ +} + +static Eina_Share_Common_Head * +_eina_share_common_head_alloc(int slen) +{ + Eina_Share_Common_Head *head; + const size_t head_size = offsetof(Eina_Share_Common_Head, builtin_node.str); + + head = malloc(head_size + slen); + if (!head) + eina_error_set(EINA_ERROR_OUT_OF_MEMORY); + + return head; +} + +static const char * +_eina_share_common_add_head(Eina_Share *share, Eina_Share_Common_Head **p_bucket, int hash, const char *str, unsigned int slen, unsigned int null_size) +{ + Eina_Rbtree **p_tree = (Eina_Rbtree **)p_bucket; + Eina_Share_Common_Head *head; + + head = _eina_share_common_head_alloc(slen + null_size); + if (!head) + return NULL; + + EINA_MAGIC_SET(head, EINA_MAGIC_SHARE_HEAD); + head->hash = hash; + head->head = &head->builtin_node; + _eina_share_common_node_init(head->head, str, slen, null_size, share->node_magic); + head->head->next = NULL; + + _eina_share_common_population_head_init(share, head); + + *p_tree = eina_rbtree_inline_insert + (*p_tree, EINA_RBTREE_GET(head), + EINA_RBTREE_CMP_NODE_CB(_eina_share_common_node), NULL); + + return head->head->str; +} + +static void +_eina_share_common_del_head(Eina_Share_Common_Head **p_bucket, Eina_Share_Common_Head *head) +{ + Eina_Rbtree **p_tree = (Eina_Rbtree **)p_bucket; + + *p_tree = eina_rbtree_inline_remove + (*p_tree, EINA_RBTREE_GET(head), + EINA_RBTREE_CMP_NODE_CB(_eina_share_common_node), NULL); + + MAGIC_FREE(head); +} + + +static inline Eina_Bool +_eina_share_common_node_eq(const Eina_Share_Common_Node *node, const char *str, unsigned int slen) +{ + return ((node->length == slen) && + (memcmp(node->str, str, slen) == 0)); +} + +static Eina_Share_Common_Node * +_eina_share_common_head_find(Eina_Share_Common_Head *head, const char *str, unsigned int slen) +{ + Eina_Share_Common_Node *node, *prev; + + node = head->head; + if (_eina_share_common_node_eq(node, str, slen)) + return node; + + prev = node; + node = node->next; + for (; node != NULL; prev = node, node = node->next) + if (_eina_share_common_node_eq(node, str, slen)) + { + /* promote node, make hot items be at the beginning */ + prev->next = node->next; + node->next = head->head; + head->head = node; + return node; + } + + return NULL; +} + +static Eina_Bool +_eina_share_common_head_remove_node(Eina_Share_Common_Head *head, const Eina_Share_Common_Node *node) +{ + Eina_Share_Common_Node *cur, *prev; + + if (head->head == node) + { + head->head = node->next; + return 1; + } + + prev = head->head; + cur = head->head->next; + for (; cur != NULL; prev = cur, cur = cur->next) + if (cur == node) + { + prev->next = cur->next; + return 1; + } + + return 0; +} + +static Eina_Share_Common_Head * +_eina_share_common_find_hash(Eina_Share_Common_Head *bucket, int hash) +{ + return (Eina_Share_Common_Head*) eina_rbtree_inline_lookup + (EINA_RBTREE_GET(bucket), &hash, 0, + EINA_RBTREE_CMP_KEY_CB(_eina_share_common_cmp), NULL); +} + +static Eina_Share_Common_Node * +_eina_share_common_node_alloc(unsigned int slen, unsigned int null_size) +{ + Eina_Share_Common_Node *node; + const size_t node_size = offsetof(Eina_Share_Common_Node, str); + + node = malloc(node_size + slen + null_size); + if (!node) + eina_error_set(EINA_ERROR_OUT_OF_MEMORY); + + return node; +} + +static Eina_Share_Common_Node * +_eina_share_common_node_from_str(const char *str, Eina_Magic node_magic) +{ + Eina_Share_Common_Node *node; + const size_t offset = offsetof(Eina_Share_Common_Node, str); + + node = (Eina_Share_Common_Node *)(str - offset); + EINA_MAGIC_CHECK_SHARE_COMMON_NODE(node, node_magic, ); + return node; +} + +static Eina_Bool +eina_iterator_array_check(const Eina_Rbtree *rbtree __UNUSED__, Eina_Share_Common_Head *head, struct dumpinfo *fdata) +{ + Eina_Share_Common_Node *node; + + SHARE_COMMON_LOCK_BIG(); + + fdata->used += sizeof(Eina_Share_Common_Head); + for (node = head->head; node; node = node->next) + { + printf("DDD: %5i %5i ", node->length, node->references); + printf("'%s'\n", ((char *)node) + sizeof(Eina_Share_Common_Node)); + fdata->used += sizeof(Eina_Share_Common_Node); + fdata->used += node->length; + fdata->saved += (node->references - 1) * node->length; + fdata->dups += node->references - 1; + fdata->unique++; + } + + SHARE_COMMON_UNLOCK_BIG(); + + return EINA_TRUE; +} + +/** + * @endcond + */ + + +/*============================================================================* + * Global * + *============================================================================*/ + +/** + * @internal + * @brief Initialize the share_common module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function sets up the share_common module of Eina. It is called by + * eina_init(). + * + * @see eina_init() + */ +Eina_Bool +eina_share_common_init(Eina_Share **_share, Eina_Magic node_magic, const char *node_magic_STR) +{ + Eina_Share *share; + share = *_share = calloc(sizeof(Eina_Share), 1); + if (!share) + return EINA_FALSE; + if (_eina_share_common_log_dom < 0) /*Only register if not already */ + _eina_share_common_log_dom = eina_log_domain_register("eina_share", EINA_LOG_COLOR_DEFAULT); + if (_eina_share_common_log_dom < 0) + { + EINA_LOG_ERR("Could not register log domain: eina_share_common"); + return EINA_FALSE; + } + + share->share = calloc(1, sizeof(Eina_Share_Common)); + if (!share->share) + { + if (_eina_share_common_log_dom > 0) + { + eina_log_domain_unregister(_eina_share_common_log_dom); + _eina_share_common_log_dom = -1; + } + return EINA_FALSE; + } + share->node_magic = node_magic; +#define EMS(n) eina_magic_string_static_set(n, n##_STR) + EMS(EINA_MAGIC_SHARE); + EMS(EINA_MAGIC_SHARE_HEAD); + EMS(node_magic); +#undef EMS + EINA_MAGIC_SET(share->share, EINA_MAGIC_SHARE); + + _eina_share_common_population_init(share); + return EINA_TRUE; +} + +/** + * @internal + * @brief Shut down the share_common module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function shuts down the share_common module set up by + * eina_share_common_init(). It is called by eina_shutdown(). + * + * @see eina_shutdown() + */ +Eina_Bool +eina_share_common_shutdown(Eina_Share **_share) +{ + unsigned int i; + Eina_Share *share = *_share; + + SHARE_COMMON_LOCK_BIG(); + + _eina_share_common_population_stats(share); + + /* remove any string still in the table */ + for (i = 0; i < EINA_SHARE_COMMON_BUCKETS; i++) + { + eina_rbtree_delete(EINA_RBTREE_GET(share->share->buckets[i]), EINA_RBTREE_FREE_CB(_eina_share_common_head_free), NULL); + share->share->buckets[i] = NULL; + } + MAGIC_FREE(share->share); + + _eina_share_common_population_shutdown(share); + if (_eina_share_common_log_dom > 0) /* Only free if necessary */ + { + eina_log_domain_unregister(_eina_share_common_log_dom); + _eina_share_common_log_dom = -1; + } + + SHARE_COMMON_UNLOCK_BIG(); + + free(*_share); + *_share = NULL; + return EINA_TRUE; +} + +#ifdef EFL_HAVE_THREADS + +/** + * @internal + * @brief Activate the share_common mutexs. + * + * This function activate the mutexs in the eina share_common module. It is called by + * eina_thread_init(). + * + * @see eina_thread_init() + */ +void +eina_share_common_threads_init(void) +{ + _share_common_threads_activated = EINA_TRUE; +} + +/** + * @internal + * @brief Shut down the share_common mutexs. + * + * This function shuts down the mutexs in the share_common module. + * It is called by eina_thread_shutdown(). + * + * @see eina_thread_shutdown() + */ +void +eina_share_common_threads_shutdown(void) +{ + _share_common_threads_activated = EINA_FALSE; +} + +#endif + +/*============================================================================* + * API * + *============================================================================*/ + +/** + * @cond LOCAL + */ + +const char * +eina_share_common_add_length(Eina_Share *share, const char *str, unsigned int slen, unsigned int null_size) +{ + Eina_Share_Common_Head **p_bucket, *ed; + Eina_Share_Common_Node *el; + int hash_num, hash; + + DBG("str=%p (%.*s), slen=%u", str, slen, str ? str : "", slen); + if (!str) return NULL; + + eina_share_common_population_add(share, slen); + + if (slen <= 0) + return NULL; + + hash = eina_hash_superfast(str, slen); + hash_num = hash & 0xFF; + hash = (hash >> 8) & EINA_SHARE_COMMON_MASK; + + SHARE_COMMON_LOCK_BIG(); + p_bucket = share->share->buckets + hash_num; + + ed = _eina_share_common_find_hash(*p_bucket, hash); + if (!ed) + { + const char *s = _eina_share_common_add_head(share, p_bucket, hash, str, slen, null_size); + SHARE_COMMON_UNLOCK_BIG(); + return s; + } + + EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, SHARE_COMMON_UNLOCK_BIG(), NULL); + + el = _eina_share_common_head_find(ed, str, slen); + if (el) + { + EINA_MAGIC_CHECK_SHARE_COMMON_NODE(el, share->node_magic, SHARE_COMMON_UNLOCK_BIG()); + el->references++; + SHARE_COMMON_UNLOCK_BIG(); + return el->str; + } + + el = _eina_share_common_node_alloc(slen, null_size); + if (!el) + { + SHARE_COMMON_UNLOCK_BIG(); + return NULL; + } + + _eina_share_common_node_init(el, str, slen, null_size, share->node_magic); + el->next = ed->head; + ed->head = el; + _eina_share_common_population_head_add(share, ed); + + SHARE_COMMON_UNLOCK_BIG(); + + return el->str; +} + +const char * +eina_share_common_ref(Eina_Share *share, const char *str) +{ + Eina_Share_Common_Node *node; + + DBG("str=%p (%s)", str, str ? str : ""); + if (!str) return NULL; + + SHARE_COMMON_LOCK_BIG(); + node = _eina_share_common_node_from_str(str, share->node_magic); + node->references++; + DBG("str=%p (%s) refs=%u", str, str, node->references); + + SHARE_COMMON_UNLOCK_BIG(); + + eina_share_common_population_add(share, node->length); + + return str; +} + + +void +eina_share_common_del(Eina_Share *share, const char *str, int slen) +{ + Eina_Share_Common_Head *ed; + Eina_Share_Common_Head **p_bucket; + Eina_Share_Common_Node *node; + int hash_num, hash; + + DBG("str=%p (%s)", str, str ? str : ""); + if (!str) return; + + eina_share_common_population_del(share, slen); + + SHARE_COMMON_LOCK_BIG(); + + node = _eina_share_common_node_from_str(str, share->node_magic); + if (node->references > 1) + { + node->references--; + DBG("str=%p (%s) refs=%u", str, str, node->references); + SHARE_COMMON_UNLOCK_BIG(); + return; + } + + DBG("str=%p (%s) refs=0, delete.", str, str); + node->references = 0; + slen = node->length; + + hash = eina_hash_superfast(str, slen); + hash_num = hash & 0xFF; + hash = (hash >> 8) & EINA_SHARE_COMMON_MASK; + + p_bucket = share->share->buckets + hash_num; + ed = _eina_share_common_find_hash(*p_bucket, hash); + if (!ed) + goto on_error; + + EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, SHARE_COMMON_UNLOCK_BIG()); + + if (!_eina_share_common_head_remove_node(ed, node)) + goto on_error; + + if (node != &ed->builtin_node) + MAGIC_FREE(node); + + if (!ed->head) + _eina_share_common_del_head(p_bucket, ed); + else + _eina_share_common_population_head_del(share, ed); + + SHARE_COMMON_UNLOCK_BIG(); + + return; + + on_error: + SHARE_COMMON_UNLOCK_BIG(); + /* possible segfault happened before here, but... */ + CRITICAL("EEEK trying to del non-shared share_common \"%s\"", str); +} + +int +eina_share_common_length(__UNUSED__ Eina_Share *share, const char *str) +{ + const Eina_Share_Common_Node *node; + + if (!str) + return -1; + + node = _eina_share_common_node_from_str(str, share->node_magic); + return node->length; +} + +void +eina_share_common_dump(Eina_Share *share, void (* additional_dump)(struct dumpinfo *), int used) +{ + Eina_Iterator *it; + unsigned int i; + struct dumpinfo di; + + if (!share) return; + di.used = used; + di.saved = 0; + di.dups = 0; + di.unique = 0; + printf("DDD: len ref string\n"); + printf("DDD:-------------------\n"); + + SHARE_COMMON_LOCK_BIG(); + for (i = 0; i < EINA_SHARE_COMMON_BUCKETS; i++) + { + if (!share->share->buckets[i]) continue; +// printf("DDD: BUCKET # %i (HEAD=%i, NODE=%i)\n", i, +// sizeof(Eina_Share_Common_Head), sizeof(Eina_Share_Common_Node)); + it = eina_rbtree_iterator_prefix((Eina_Rbtree *)share->share->buckets[i]); + eina_iterator_foreach(it, EINA_EACH(eina_iterator_array_check), &di); + eina_iterator_free(it); + } + if (additional_dump) + additional_dump(&di); +#ifdef EINA_SHARE_COMMON_USAGE + /* One character strings are not counted in the hash. */ + di.saved += share->population_group[0].count * sizeof(char); + di.saved += share->population_group[1].count * sizeof(char) * 2; +#endif + printf("DDD:-------------------\n"); + printf("DDD: usage (bytes) = %i, saved = %i (%3.0f%%)\n", + di.used, di.saved, di.used ? (di.saved * 100.0 / di.used) : 0.0); + printf("DDD: unique: %d, duplicates: %d (%3.0f%%)\n", + di.unique, di.dups, di.unique ? (di.dups * 100.0 / di.unique) : 0.0); + +#ifdef EINA_SHARE_COMMON_USAGE + printf("DDD: Allocated strings: %i\n", share->population.count); + printf("DDD: Max allocated strings: %i\n", share->population.max); + + for (i = 0; i < sizeof (share->population_group) / sizeof (share->population_group[0]); ++i) + fprintf(stderr, "DDD: %i strings of length %i, max strings: %i\n", share->population_group[i].count, i, share->population_group[i].max); +#endif + + SHARE_COMMON_UNLOCK_BIG(); +} + +/** + * @endcond + */ diff --git a/src/lib/eina_share_common.h b/src/lib/eina_share_common.h new file mode 100644 index 0000000..738814a --- /dev/null +++ b/src/lib/eina_share_common.h @@ -0,0 +1,93 @@ +/* EINA - EFL data type library + * Copyright (C) 2002-2008 Carsten Haitzler, Jorge Luis Zapata Muga, Cedric Bail + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + * + * This file incorporates work covered by the following copyright and + * permission notice: + * + * Copyright (C) 2008 Peter Wehrfritz + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its Copyright notices. In addition publicly + * documented acknowledgment must be given that this software has been used if no + * source code of this software is made available publicly. This includes + * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing + * documents or any documentation provided with any product containing this + * software. This License does not apply to any software that links to the + * libraries provided by this software (statically or dynamically), but only to + * the software provided. + * + * Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice + * and it's intent. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef EINA_SHARE_COMMON_H_ +#define EINA_SHARE_COMMON_H_ + +#include "eina_types.h" +#include "eina_magic.h" + +typedef struct _Eina_Share Eina_Share; + +struct dumpinfo +{ + int used, saved, dups, unique; +}; + +Eina_Bool eina_share_common_init(Eina_Share **share, Eina_Magic node_magic, const char *node_magic_STR); +Eina_Bool eina_share_common_shutdown(Eina_Share **share); +const char *eina_share_common_add_length(Eina_Share *share, const char *str, unsigned int slen, unsigned int null_size) EINA_WARN_UNUSED_RESULT; +const char *eina_share_common_ref(Eina_Share *share, const char *str); +void eina_share_common_del(Eina_Share *share, const char *str, int slen); +int eina_share_common_length(Eina_Share *share, const char *str) EINA_CONST EINA_WARN_UNUSED_RESULT; +void eina_share_common_dump(Eina_Share *share, void (* additional_dump)(struct dumpinfo *), int used); + + +/* Population functions */ +void eina_share_common_population_add(Eina_Share *share, int slen); +void eina_share_common_population_del(Eina_Share *share, int slen); + +/* Share logging */ +#ifdef CRITICAL +#undef CRITICAL +#endif +#define CRITICAL(...) EINA_LOG_DOM_CRIT(_eina_share_common_log_dom, __VA_ARGS__) + +#ifdef ERR +#undef ERR +#endif +#define ERR(...) EINA_LOG_DOM_ERR(_eina_share_common_log_dom, __VA_ARGS__) + +#ifdef DBG +#undef DBG +#endif +#define DBG(...) EINA_LOG_DOM_DBG(_eina_share_common_log_dom, __VA_ARGS__) +extern int _eina_share_common_log_dom; +#endif /* EINA_STRINGSHARE_H_ */ diff --git a/src/lib/eina_stringshare.c b/src/lib/eina_stringshare.c index baaef21..04a9916 100644 --- a/src/lib/eina_stringshare.c +++ b/src/lib/eina_stringshare.c @@ -7,6 +7,7 @@ * Jorge Luis Zapata Muga, * Cedric Bail, * Gustavo Sverzut Barbieri + * Tom Hacohen * Brett Nash * * This library is free software; you can redistribute it and/or @@ -22,43 +23,10 @@ * You should have received a copy of the GNU Lesser General Public * License along with this library; * if not, see . - * - * This file incorporates work covered by the following copyright and - * permission notice: - * - * Copyright (C) 2008 Peter Wehrfritz - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to - * deal in the Software without restriction, including without limitation the - * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or - * sell copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies of the Software and its Copyright notices. In addition publicly - * documented acknowledgment must be given that this software has been used if no - * source code of this software is made available publicly. This includes - * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing - * documents or any documentation provided with any product containing this - * software. This License does not apply to any software that links to the - * libraries provided by this software (statically or dynamically), but only to - * the software provided. - * - * Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice - * and it's intent. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER - * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN - * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ - +*/ -/** - * @page tutorial_stringshare_page Stringshare Tutorial + /** + * @page tutorial_ustringshare_page UStringshare Tutorial * * to be written... * @@ -72,7 +40,6 @@ #include #include #include -#include #ifdef EFL_HAVE_POSIX_THREADS # include @@ -90,129 +57,31 @@ /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ #include "eina_safety_checks.h" -#include "eina_stringshare.h" - -/*============================================================================* - * Local * - *============================================================================*/ +#include "eina_share_common.h" -/** - * @cond LOCAL - */ - -#define EINA_STRINGSHARE_BUCKETS 256 -#define EINA_STRINGSHARE_MASK 0xFF - -static const char EINA_MAGIC_STRINGSHARE_STR[] = "Eina Stringshare"; -static const char EINA_MAGIC_STRINGSHARE_HEAD_STR[] = "Eina Stringshare Head"; +/* The actual share */ +static Eina_Share *share; static const char EINA_MAGIC_STRINGSHARE_NODE_STR[] = "Eina Stringshare Node"; - -#define EINA_MAGIC_CHECK_STRINGSHARE_HEAD(d, unlock, ...) \ - do { \ - if (!EINA_MAGIC_CHECK((d), EINA_MAGIC_STRINGSHARE_HEAD)) \ - { \ - EINA_MAGIC_FAIL((d), EINA_MAGIC_STRINGSHARE_HEAD); \ - unlock; \ - return __VA_ARGS__; \ - } \ - } while (0) - -#define EINA_MAGIC_CHECK_STRINGSHARE_NODE(d, unlock) \ - do { \ - if (!EINA_MAGIC_CHECK((d), EINA_MAGIC_STRINGSHARE_NODE)) \ - { \ - unlock; \ - EINA_MAGIC_FAIL((d), EINA_MAGIC_STRINGSHARE_NODE); \ - } \ - } while (0) - -typedef struct _Eina_Stringshare Eina_Stringshare; -typedef struct _Eina_Stringshare_Node Eina_Stringshare_Node; -typedef struct _Eina_Stringshare_Head Eina_Stringshare_Head; - -struct _Eina_Stringshare -{ - Eina_Stringshare_Head *buckets[EINA_STRINGSHARE_BUCKETS]; - - EINA_MAGIC -}; - -struct _Eina_Stringshare_Node -{ - Eina_Stringshare_Node *next; - - EINA_MAGIC - - unsigned int length; - unsigned int references; - char str[]; -}; - -struct _Eina_Stringshare_Head -{ - EINA_RBTREE; - EINA_MAGIC - - int hash; - -#ifdef EINA_STRINGSHARE_USAGE - int population; -#endif - - Eina_Stringshare_Node *head; - Eina_Stringshare_Node builtin_node; -}; - -static Eina_Stringshare *share = NULL; -static int _eina_stringshare_log_dom = -1; - -#ifdef CRITICAL -#undef CRITICAL -#endif -#define CRITICAL(...) EINA_LOG_DOM_CRIT(_eina_stringshare_log_dom, __VA_ARGS__) - -#ifdef ERR -#undef ERR -#endif -#define ERR(...) EINA_LOG_DOM_ERR(_eina_stringshare_log_dom, __VA_ARGS__) - -#ifdef DBG -#undef DBG -#endif -#define DBG(...) EINA_LOG_DOM_DBG(_eina_stringshare_log_dom, __VA_ARGS__) - - - #ifdef EFL_HAVE_THREADS -static Eina_Bool _stringshare_threads_activated = EINA_FALSE; +extern Eina_Bool _share_common_threads_activated; # ifdef EFL_HAVE_POSIX_THREADS -/* string < 4 */ static pthread_mutex_t _mutex_small = PTHREAD_MUTEX_INITIALIZER; -/* string >= 4 */ -static pthread_mutex_t _mutex_big = PTHREAD_MUTEX_INITIALIZER; -# define STRINGSHARE_LOCK_SMALL() if(_stringshare_threads_activated) pthread_mutex_lock(&_mutex_small) -# define STRINGSHARE_UNLOCK_SMALL() if(_stringshare_threads_activated) pthread_mutex_unlock(&_mutex_small) -# define STRINGSHARE_LOCK_BIG() if(_stringshare_threads_activated) pthread_mutex_lock(&_mutex_big) -# define STRINGSHARE_UNLOCK_BIG() if(_stringshare_threads_activated) pthread_mutex_unlock(&_mutex_big) +# define STRINGSHARE_LOCK_SMALL() if(_share_common_threads_activated) pthread_mutex_lock(&_mutex_small) +# define STRINGSHARE_UNLOCK_SMALL() if(_share_common_threads_activated) pthread_mutex_unlock(&_mutex_small) # else /* EFL_HAVE_WIN32_THREADS */ static HANDLE _mutex_small = NULL; -static HANDLE _mutex_big = NULL; -# define STRINGSHARE_LOCK_SMALL() if(_stringshare_threads_activated) WaitForSingleObject(_mutex_small, INFINITE) -# define STRINGSHARE_UNLOCK_SMALL() if(_stringshare_threads_activated) ReleaseMutex(_mutex_small) -# define STRINGSHARE_LOCK_BIG() if(_stringshare_threads_activated) WaitForSingleObject(_mutex_big, INFINITE) -# define STRINGSHARE_UNLOCK_BIG() if(_stringshare_threads_activated) ReleaseMutex(_mutex_big) +# define STRINGSHARE_LOCK_SMALL() if(_share_common_threads_activated) WaitForSingleObject(_mutex_small, INFINITE) +# define STRINGSHARE_UNLOCK_SMALL() if(_share_common_threads_activated) ReleaseMutex(_mutex_small) # endif /* EFL_HAVE_WIN32_THREADS */ #else /* EFL_HAVE_THREADS */ # define STRINGSHARE_LOCK_SMALL() do {} while (0) # define STRINGSHARE_UNLOCK_SMALL() do {} while (0) -# define STRINGSHARE_LOCK_BIG() do {} while (0) -# define STRINGSHARE_UNLOCK_BIG() do {} while (0) #endif - +/* Stringshare optimizations */ static const unsigned char _eina_stringshare_single[512] = { 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, 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, @@ -254,171 +123,6 @@ struct _Eina_Stringshare_Small #define EINA_STRINGSHARE_SMALL_BUCKET_STEP 8 static Eina_Stringshare_Small _eina_small_share; - -#ifdef EINA_STRINGSHARE_USAGE -typedef struct _Eina_Stringshare_Population Eina_Stringshare_Population; -struct _Eina_Stringshare_Population -{ - int count; - int max; -}; - -static Eina_Stringshare_Population population = { 0, 0 }; - -static Eina_Stringshare_Population population_group[4] = - { - { 0, 0 }, - { 0, 0 }, - { 0, 0 }, - { 0, 0 } - }; - -static int max_node_population = 0; - - -static void -_eina_stringshare_population_init(void) -{ - unsigned int i; - - for (i = 0; i < sizeof (population_group) / sizeof (population_group[0]); ++i) - { - population_group[i].count = 0; - population_group[i].max = 0; - } -} - -static void -_eina_stringshare_population_shutdown(void) -{ - unsigned int i; - - max_node_population = 0; - population.count = 0; - population.max = 0; - - for (i = 0; i < sizeof (population_group) / sizeof (population_group[0]); ++i) - { - population_group[i].count = 0; - population_group[i].max = 0; - } -} - -static void -_eina_stringshare_population_stats(void) -{ - unsigned int i; - - fprintf(stderr, "eina stringshare statistic:\n"); - fprintf(stderr, " * maximum shared strings : %i\n", population.max); - fprintf(stderr, " * maximum shared strings per node : %i\n", max_node_population); - - for (i = 0; i < sizeof (population_group) / sizeof (population_group[0]); ++i) - fprintf(stderr, "DDD: %i strings of length %i, max strings: %i\n", population_group[i].count, i, population_group[i].max); -} - -static void -_eina_stringshare_population_add(int slen) -{ - STRINGSHARE_LOCK_SMALL(); - STRINGSHARE_LOCK_BIG(); - - population.count++; - if (population.count > population.max) - population.max = population.count; - - if (slen < 4) - { - population_group[slen].count++; - if (population_group[slen].count > population_group[slen].max) - population_group[slen].max = population_group[slen].count; - } - - STRINGSHARE_UNLOCK_BIG(); - STRINGSHARE_UNLOCK_SMALL(); -} - -static void -_eina_stringshare_population_del(int slen) -{ - STRINGSHARE_LOCK_SMALL(); - STRINGSHARE_LOCK_BIG(); - - population.count--; - if (slen < 4) - population_group[slen].count--; - - STRINGSHARE_UNLOCK_BIG(); - STRINGSHARE_UNLOCK_SMALL(); -} - -static void -_eina_stringshare_population_head_init(Eina_Stringshare_Head *head) -{ - head->population = 1; -} - -static void -_eina_stringshare_population_head_add(Eina_Stringshare_Head *head) -{ - head->population++; - if (head->population > max_node_population) - max_node_population = head->population; -} - -static void -_eina_stringshare_population_head_del(Eina_Stringshare_Head *head) -{ - head->population--; -} - -#else /* EINA_STRINGSHARE_USAGE undefined */ - -static void _eina_stringshare_population_init(void) {} -static void _eina_stringshare_population_shutdown(void) {} -static void _eina_stringshare_population_stats(void) {} -static void _eina_stringshare_population_add(__UNUSED__ int slen) {} -static void _eina_stringshare_population_del(__UNUSED__ int slen) {} -static void _eina_stringshare_population_head_init(__UNUSED__ Eina_Stringshare_Head *head) {} -static void _eina_stringshare_population_head_add(__UNUSED__ Eina_Stringshare_Head *head) {} -static void _eina_stringshare_population_head_del(__UNUSED__ Eina_Stringshare_Head *head) {} -#endif - -static int -_eina_stringshare_cmp(const Eina_Stringshare_Head *ed, const int *hash, __UNUSED__ int length, __UNUSED__ void *data) -{ - EINA_MAGIC_CHECK_STRINGSHARE_HEAD(ed, , 0); - - return ed->hash - *hash; -} - -static Eina_Rbtree_Direction -_eina_stringshare_node(const Eina_Stringshare_Head *left, const Eina_Stringshare_Head *right, __UNUSED__ void *data) -{ - EINA_MAGIC_CHECK_STRINGSHARE_HEAD(left, , 0); - EINA_MAGIC_CHECK_STRINGSHARE_HEAD(right, , 0); - - if (left->hash - right->hash < 0) - return EINA_RBTREE_LEFT; - return EINA_RBTREE_RIGHT; -} - -static void -_eina_stringshare_head_free(Eina_Stringshare_Head *ed, __UNUSED__ void *data) -{ - EINA_MAGIC_CHECK_STRINGSHARE_HEAD(ed, ); - - while (ed->head) - { - Eina_Stringshare_Node *el = ed->head; - - ed->head = ed->head->next; - if (el != &ed->builtin_node) - MAGIC_FREE(el); - } - MAGIC_FREE(ed); -} - static inline int _eina_stringshare_small_cmp(const Eina_Stringshare_Small_Bucket *bucket, int i, const char *pstr, unsigned char plength) { @@ -711,158 +415,6 @@ _eina_stringshare_small_shutdown(void) } static void -_eina_stringshare_node_init(Eina_Stringshare_Node *node, const char *str, int slen) -{ - EINA_MAGIC_SET(node, EINA_MAGIC_STRINGSHARE_NODE); - node->references = 1; - node->length = slen; - memcpy(node->str, str, slen); - node->str[slen] = '\0'; -} - -static Eina_Stringshare_Head * -_eina_stringshare_head_alloc(int slen) -{ - Eina_Stringshare_Head *head; - const size_t head_size = offsetof(Eina_Stringshare_Head, builtin_node.str); - - head = malloc(head_size + slen + 1); - if (!head) - eina_error_set(EINA_ERROR_OUT_OF_MEMORY); - - return head; -} - -static const char * -_eina_stringshare_add_head(Eina_Stringshare_Head **p_bucket, int hash, const char *str, int slen) -{ - Eina_Rbtree **p_tree = (Eina_Rbtree **)p_bucket; - Eina_Stringshare_Head *head; - - head = _eina_stringshare_head_alloc(slen); - if (!head) - return NULL; - - EINA_MAGIC_SET(head, EINA_MAGIC_STRINGSHARE_HEAD); - head->hash = hash; - head->head = &head->builtin_node; - _eina_stringshare_node_init(head->head, str, slen); - head->head->next = NULL; - - _eina_stringshare_population_head_init(head); - - *p_tree = eina_rbtree_inline_insert - (*p_tree, EINA_RBTREE_GET(head), - EINA_RBTREE_CMP_NODE_CB(_eina_stringshare_node), NULL); - - return head->head->str; -} - -static void -_eina_stringshare_del_head(Eina_Stringshare_Head **p_bucket, Eina_Stringshare_Head *head) -{ - Eina_Rbtree **p_tree = (Eina_Rbtree **)p_bucket; - - *p_tree = eina_rbtree_inline_remove - (*p_tree, EINA_RBTREE_GET(head), - EINA_RBTREE_CMP_NODE_CB(_eina_stringshare_node), NULL); - - MAGIC_FREE(head); -} - - -static inline Eina_Bool -_eina_stringshare_node_eq(const Eina_Stringshare_Node *node, const char *str, unsigned int slen) -{ - return ((node->length == slen) && - (memcmp(node->str, str, slen) == 0)); -} - -static Eina_Stringshare_Node * -_eina_stringshare_head_find(Eina_Stringshare_Head *head, const char *str, unsigned int slen) -{ - Eina_Stringshare_Node *node, *prev; - - node = head->head; - if (_eina_stringshare_node_eq(node, str, slen)) - return node; - - prev = node; - node = node->next; - for (; node != NULL; prev = node, node = node->next) - if (_eina_stringshare_node_eq(node, str, slen)) - { - /* promote node, make hot items be at the beginning */ - prev->next = node->next; - node->next = head->head; - head->head = node; - return node; - } - - return NULL; -} - -static Eina_Bool -_eina_stringshare_head_remove_node(Eina_Stringshare_Head *head, const Eina_Stringshare_Node *node) -{ - Eina_Stringshare_Node *cur, *prev; - - if (head->head == node) - { - head->head = node->next; - return 1; - } - - prev = head->head; - cur = head->head->next; - for (; cur != NULL; prev = cur, cur = cur->next) - if (cur == node) - { - prev->next = cur->next; - return 1; - } - - return 0; -} - -static Eina_Stringshare_Head * -_eina_stringshare_find_hash(Eina_Stringshare_Head *bucket, int hash) -{ - return (Eina_Stringshare_Head*) eina_rbtree_inline_lookup - (EINA_RBTREE_GET(bucket), &hash, 0, - EINA_RBTREE_CMP_KEY_CB(_eina_stringshare_cmp), NULL); -} - -static Eina_Stringshare_Node * -_eina_stringshare_node_alloc(int slen) -{ - Eina_Stringshare_Node *node; - const size_t node_size = offsetof(Eina_Stringshare_Node, str); - - node = malloc(node_size + slen + 1); - if (!node) - eina_error_set(EINA_ERROR_OUT_OF_MEMORY); - - return node; -} - -static Eina_Stringshare_Node * -_eina_stringshare_node_from_str(const char *str) -{ - Eina_Stringshare_Node *node; - const size_t offset = offsetof(Eina_Stringshare_Node, str); - - node = (Eina_Stringshare_Node *)(str - offset); - EINA_MAGIC_CHECK_STRINGSHARE_NODE(node, ); - return node; -} - -struct dumpinfo -{ - int used, saved, dups, unique; -}; - -static void _eina_stringshare_small_bucket_dump(Eina_Stringshare_Small_Bucket *bucket, struct dumpinfo *di) { const char **s = bucket->strings; @@ -912,36 +464,6 @@ _eina_stringshare_small_dump(struct dumpinfo *di) } } -static Eina_Bool -eina_iterator_array_check(const Eina_Rbtree *rbtree __UNUSED__, Eina_Stringshare_Head *head, struct dumpinfo *fdata) -{ - Eina_Stringshare_Node *node; - - STRINGSHARE_LOCK_SMALL(); - STRINGSHARE_LOCK_BIG(); - - fdata->used += sizeof(Eina_Stringshare_Head); - for (node = head->head; node; node = node->next) - { - printf("DDD: %5i %5i ", node->length, node->references); - printf("'%s'\n", ((char *)node) + sizeof(Eina_Stringshare_Node)); - fdata->used += sizeof(Eina_Stringshare_Node); - fdata->used += node->length; - fdata->saved += (node->references - 1) * node->length; - fdata->dups += node->references - 1; - fdata->unique++; - } - - STRINGSHARE_UNLOCK_BIG(); - STRINGSHARE_UNLOCK_SMALL(); - - return EINA_TRUE; -} - -/** - * @endcond - */ - /*============================================================================* * Global * @@ -949,11 +471,11 @@ eina_iterator_array_check(const Eina_Rbtree *rbtree __UNUSED__, Eina_Stringshare /** * @internal - * @brief Initialize the stringshare module. + * @brief Initialize the share_common module. * * @return #EINA_TRUE on success, #EINA_FALSE on failure. * - * This function sets up the stringshare module of Eina. It is called by + * This function sets up the share_common module of Eina. It is called by * eina_init(). * * @see eina_init() @@ -961,108 +483,35 @@ eina_iterator_array_check(const Eina_Rbtree *rbtree __UNUSED__, Eina_Stringshare Eina_Bool eina_stringshare_init(void) { - _eina_stringshare_log_dom = eina_log_domain_register("eina_stringshare", EINA_LOG_COLOR_DEFAULT); - if (_eina_stringshare_log_dom < 0) + Eina_Bool ret; + ret = eina_share_common_init(&share, EINA_MAGIC_STRINGSHARE_NODE, EINA_MAGIC_STRINGSHARE_NODE_STR); + if (ret) { - EINA_LOG_ERR("Could not register log domain: eina_stringshare"); - return EINA_FALSE; + _eina_stringshare_small_init(); } - - share = calloc(1, sizeof(Eina_Stringshare)); - if (!share) - { - eina_log_domain_unregister(_eina_stringshare_log_dom); - _eina_stringshare_log_dom = -1; - return EINA_FALSE; - } - -#define EMS(n) eina_magic_string_static_set(n, n##_STR) - EMS(EINA_MAGIC_STRINGSHARE); - EMS(EINA_MAGIC_STRINGSHARE_HEAD); - EMS(EINA_MAGIC_STRINGSHARE_NODE); -#undef EMS - EINA_MAGIC_SET(share, EINA_MAGIC_STRINGSHARE); - - _eina_stringshare_small_init(); - _eina_stringshare_population_init(); - return EINA_TRUE; + return ret; } /** * @internal - * @brief Shut down the stringshare module. + * @brief Shut down the share_common module. * * @return #EINA_TRUE on success, #EINA_FALSE on failure. * - * This function shuts down the stringshare module set up by - * eina_stringshare_init(). It is called by eina_shutdown(). + * This function shuts down the share_common module set up by + * eina_share_common_init(). It is called by eina_shutdown(). * * @see eina_shutdown() */ Eina_Bool eina_stringshare_shutdown(void) { - unsigned int i; - - STRINGSHARE_LOCK_SMALL(); - STRINGSHARE_LOCK_BIG(); - - _eina_stringshare_population_stats(); - - /* remove any string still in the table */ - for (i = 0; i < EINA_STRINGSHARE_BUCKETS; i++) - { - eina_rbtree_delete(EINA_RBTREE_GET(share->buckets[i]), EINA_RBTREE_FREE_CB(_eina_stringshare_head_free), NULL); - share->buckets[i] = NULL; - } - MAGIC_FREE(share); - - _eina_stringshare_population_shutdown(); + Eina_Bool ret; _eina_stringshare_small_shutdown(); - eina_log_domain_unregister(_eina_stringshare_log_dom); - _eina_stringshare_log_dom = -1; - - STRINGSHARE_UNLOCK_BIG(); - STRINGSHARE_UNLOCK_SMALL(); - - - return EINA_TRUE; -} - -#ifdef EFL_HAVE_THREADS - -/** - * @internal - * @brief Activate the stringshare mutexs. - * - * This function activate the mutexs in the eina stringshare module. It is called by - * eina_thread_init(). - * - * @see eina_thread_init() - */ -void -eina_stringshare_threads_init(void) -{ - _stringshare_threads_activated = EINA_TRUE; -} - -/** - * @internal - * @brief Shut down the stringshare mutexs. - * - * This function shuts down the mutexs in the stringshare module. - * It is called by eina_thread_shutdown(). - * - * @see eina_thread_shutdown() - */ -void -eina_stringshare_threads_shutdown(void) -{ - _stringshare_threads_activated = EINA_FALSE; + ret = eina_share_common_shutdown(&share); + return ret; } -#endif - /*============================================================================* * API * *============================================================================*/ @@ -1092,6 +541,48 @@ eina_stringshare_threads_shutdown(void) */ /** + * @brief Note that the given string has lost an instance. + * + * @param str string The given string. + * + * This function decreases the reference counter associated to @p str + * if it exists. If that counter reaches 0, the memory associated to + * @p str is freed. If @p str is NULL, the function returns + * immediatly. + * + * Note that if the given pointer is not shared or NULL, bad things + * will happen, likely a segmentation fault. + */ +EAPI void +eina_stringshare_del(const char *str) +{ + int slen; + if (!str) + return; + + /* special cases */ + if (str[0] == '\0') slen = 0; + else if (str[1] == '\0') slen = 1; + else if (str[2] == '\0') slen = 2; + else if (str[3] == '\0') slen = 3; + else slen = 4; /* handled later */ + + if (slen < 2) + return; + else if (slen < 4) + { + eina_share_common_population_del(share, slen); + STRINGSHARE_LOCK_SMALL(); + _eina_stringshare_small_del(str, slen); + STRINGSHARE_UNLOCK_SMALL(); + return; + } + slen = strlen(str); + slen = (int) (slen * sizeof(char)); + eina_share_common_del(share, str, slen); +} + +/** * @brief Retrieve an instance of a string for use in a program. * * @param str The string to retrieve an instance of. @@ -1106,78 +597,28 @@ eina_stringshare_threads_shutdown(void) * of @p str is returned. * * This function does not check string size, but uses the - * exact given size. This can be used to stringshare part of a larger + * exact given size. This can be used to share_common part of a larger * buffer or substring. * - * @see eina_stringshare_add() + * @see eina_share_common_add() */ EAPI const char * eina_stringshare_add_length(const char *str, unsigned int slen) { - Eina_Stringshare_Head **p_bucket, *ed; - Eina_Stringshare_Node *el; - int hash_num, hash; - - DBG("str=%p (%.*s), slen=%u", str, slen, str ? str : "", slen); - if (!str) return NULL; - - _eina_stringshare_population_add(slen); - if (slen <= 0) return ""; else if (slen == 1) return (const char *)_eina_stringshare_single + ((*str) << 1); else if (slen < 4) { - const char *s; - - STRINGSHARE_LOCK_SMALL(); - s = _eina_stringshare_small_add(str, slen); - STRINGSHARE_UNLOCK_SMALL(); - return s; - } - - hash = eina_hash_superfast(str, slen); - hash_num = hash & 0xFF; - hash = (hash >> 8) & EINA_STRINGSHARE_MASK; - - STRINGSHARE_LOCK_BIG(); - p_bucket = share->buckets + hash_num; - - ed = _eina_stringshare_find_hash(*p_bucket, hash); - if (!ed) - { - const char *s = _eina_stringshare_add_head(p_bucket, hash, str, slen); - STRINGSHARE_UNLOCK_BIG(); - return s; - } - - EINA_MAGIC_CHECK_STRINGSHARE_HEAD(ed, STRINGSHARE_UNLOCK_BIG(), NULL); - - el = _eina_stringshare_head_find(ed, str, slen); - if (el) - { - EINA_MAGIC_CHECK_STRINGSHARE_NODE(el, STRINGSHARE_UNLOCK_BIG()); - el->references++; - STRINGSHARE_UNLOCK_BIG(); - return el->str; - } + const char *s; - el = _eina_stringshare_node_alloc(slen); - if (!el) - { - STRINGSHARE_UNLOCK_BIG(); - return NULL; + STRINGSHARE_LOCK_SMALL(); + s = _eina_stringshare_small_add(str, slen); + STRINGSHARE_UNLOCK_SMALL(); + return s; } - - _eina_stringshare_node_init(el, str, slen); - el->next = ed->head; - ed->head = el; - _eina_stringshare_population_head_add(ed); - - STRINGSHARE_UNLOCK_BIG(); - - return el->str; + return eina_share_common_add_length(share, str, slen * sizeof(char), sizeof(char)); } /** @@ -1203,7 +644,6 @@ EAPI const char * eina_stringshare_add(const char *str) { int slen; - if (!str) return NULL; if (str[0] == '\0') slen = 0; @@ -1211,7 +651,7 @@ eina_stringshare_add(const char *str) else if (str[2] == '\0') slen = 2; else if (str[3] == '\0') slen = 3; else slen = 3 + (int)strlen(str + 3); - + return eina_stringshare_add_length(str, slen); } @@ -1347,39 +787,39 @@ eina_stringshare_nprintf(unsigned int len, const char *fmt, ...) * @return A pointer to an instance of the string on success. * @c NULL on failure. * - * This is similar to eina_stringshare_add(), but it's faster since it will + * This is similar to eina_share_common_add(), but it's faster since it will * avoid lookups if possible, but on the down side it requires the parameter * to be shared before, in other words, it must be the return of a previous - * eina_stringshare_add(). + * eina_share_common_add(). * - * There is no unref since this is the work of eina_stringshare_del(). + * There is no unref since this is the work of eina_share_common_del(). */ EAPI const char * eina_stringshare_ref(const char *str) { - Eina_Stringshare_Node *node; int slen; - - DBG("str=%p (%s)", str, str ? str : ""); - if (!str) return NULL; + if (!str) + { + return eina_share_common_ref(share, str); + } /* special cases */ if (str[0] == '\0') slen = 0; else if (str[1] == '\0') slen = 1; else if (str[2] == '\0') slen = 2; else if (str[3] == '\0') slen = 3; - else slen = 4; /* handled later */ + else slen = 3 + (int)strlen(str + 3); if (slen < 2) { - _eina_stringshare_population_add(slen); + eina_share_common_population_add(share, slen); return str; } else if (slen < 4) { const char *s; - _eina_stringshare_population_add(slen); + eina_share_common_population_add(share, slen); STRINGSHARE_LOCK_SMALL(); s = _eina_stringshare_small_add(str, slen); @@ -1388,107 +828,7 @@ eina_stringshare_ref(const char *str) return s; } - STRINGSHARE_LOCK_BIG(); - node = _eina_stringshare_node_from_str(str); - node->references++; - DBG("str=%p (%s) refs=%u", str, str, node->references); - - STRINGSHARE_UNLOCK_BIG(); - - _eina_stringshare_population_add(node->length); - - return str; -} - - -/** - * @brief Note that the given string has lost an instance. - * - * @param str string The given string. - * - * This function decreases the reference counter associated to @p str - * if it exists. If that counter reaches 0, the memory associated to - * @p str is freed. If @p str is NULL, the function returns - * immediatly. - * - * Note that if the given pointer is not shared or NULL, bad things - * will happen, likely a segmentation fault. - */ -EAPI void -eina_stringshare_del(const char *str) -{ - Eina_Stringshare_Head *ed; - Eina_Stringshare_Head **p_bucket; - Eina_Stringshare_Node *node; - int hash_num, slen, hash; - - DBG("str=%p (%s)", str, str ? str : ""); - if (!str) return; - - /* special cases */ - if (str[0] == '\0') slen = 0; - else if (str[1] == '\0') slen = 1; - else if (str[2] == '\0') slen = 2; - else if (str[3] == '\0') slen = 3; - else slen = 4; /* handled later */ - - _eina_stringshare_population_del(slen); - - if (slen < 2) - return; - else if (slen < 4) - { - STRINGSHARE_LOCK_SMALL(); - _eina_stringshare_small_del(str, slen); - STRINGSHARE_UNLOCK_SMALL(); - return; - } - - STRINGSHARE_LOCK_BIG(); - - node = _eina_stringshare_node_from_str(str); - if (node->references > 1) - { - node->references--; - DBG("str=%p (%s) refs=%u", str, str, node->references); - STRINGSHARE_UNLOCK_BIG(); - return; - } - - DBG("str=%p (%s) refs=0, delete.", str, str); - node->references = 0; - slen = node->length; - - hash = eina_hash_superfast(str, slen); - hash_num = hash & 0xFF; - hash = (hash >> 8) & EINA_STRINGSHARE_MASK; - - p_bucket = share->buckets + hash_num; - ed = _eina_stringshare_find_hash(*p_bucket, hash); - if (!ed) - goto on_error; - - EINA_MAGIC_CHECK_STRINGSHARE_HEAD(ed, STRINGSHARE_UNLOCK_BIG()); - - if (!_eina_stringshare_head_remove_node(ed, node)) - goto on_error; - - if (node != &ed->builtin_node) - MAGIC_FREE(node); - - if (!ed->head) - _eina_stringshare_del_head(p_bucket, ed); - else - _eina_stringshare_population_head_del(ed); - - STRINGSHARE_UNLOCK_BIG(); - - return; - - on_error: - STRINGSHARE_UNLOCK_BIG(); - /* possible segfault happened before here, but... */ - CRITICAL("EEEK trying to del non-shared stringshare \"%s\"", str); + return eina_share_common_ref(share, str); } /** @@ -1505,76 +845,28 @@ eina_stringshare_del(const char *str) EAPI int eina_stringshare_strlen(const char *str) { - const Eina_Stringshare_Node *node; - - if (!str) - return -1; - + int len; /* special cases */ if (str[0] == '\0') return 0; if (str[1] == '\0') return 1; if (str[2] == '\0') return 2; if (str[3] == '\0') return 3; - node = _eina_stringshare_node_from_str(str); - return node->length; + len = eina_share_common_length(share, (const char *) str); + len = (len > 0) ? len / (int) sizeof(char) : -1; + return len; } /** - * @brief Dump the contents of the stringshare. + * @brief Dump the contents of the share_common. * - * This function dumps all strings in the stringshare to stdout with a + * This function dumps all strings in the share_common to stdout with a * DDD: prefix per line and a memory usage summary. */ EAPI void eina_stringshare_dump(void) { - Eina_Iterator *it; - unsigned int i; - struct dumpinfo di; - - if (!share) return; - di.used = sizeof (_eina_stringshare_single); - di.saved = 0; - di.dups = 0; - di.unique = 0; - printf("DDD: len ref string\n"); - printf("DDD:-------------------\n"); - - STRINGSHARE_LOCK_SMALL(); - _eina_stringshare_small_dump(&di); - STRINGSHARE_UNLOCK_SMALL(); - - STRINGSHARE_LOCK_BIG(); - for (i = 0; i < EINA_STRINGSHARE_BUCKETS; i++) - { - if (!share->buckets[i]) continue; -// printf("DDD: BUCKET # %i (HEAD=%i, NODE=%i)\n", i, -// sizeof(Eina_Stringshare_Head), sizeof(Eina_Stringshare_Node)); - it = eina_rbtree_iterator_prefix((Eina_Rbtree *)share->buckets[i]); - eina_iterator_foreach(it, EINA_EACH(eina_iterator_array_check), &di); - eina_iterator_free(it); - } -#ifdef EINA_STRINGSHARE_USAGE - /* One character strings are not counted in the hash. */ - di.saved += population_group[0].count * sizeof(char); - di.saved += population_group[1].count * sizeof(char) * 2; -#endif - printf("DDD:-------------------\n"); - printf("DDD: usage (bytes) = %i, saved = %i (%3.0f%%)\n", - di.used, di.saved, di.used ? (di.saved * 100.0 / di.used) : 0.0); - printf("DDD: unique: %d, duplicates: %d (%3.0f%%)\n", - di.unique, di.dups, di.unique ? (di.dups * 100.0 / di.unique) : 0.0); - -#ifdef EINA_STRINGSHARE_USAGE - printf("DDD: Allocated strings: %i\n", population.count); - printf("DDD: Max allocated strings: %i\n", population.max); - - for (i = 0; i < sizeof (population_group) / sizeof (population_group[0]); ++i) - fprintf(stderr, "DDD: %i strings of length %i, max strings: %i\n", population_group[i].count, i, population_group[i].max); -#endif - - STRINGSHARE_UNLOCK_BIG(); + eina_share_common_dump(share, _eina_stringshare_small_dump, sizeof(_eina_stringshare_single)); } /** diff --git a/src/lib/eina_ustringshare.c b/src/lib/eina_ustringshare.c new file mode 100644 index 0000000..76df3e3 --- /dev/null +++ b/src/lib/eina_ustringshare.c @@ -0,0 +1,242 @@ +/* + * vim:ts=8:sw=3:sts=8:noexpandtab:cino=>5n-3f0^-2{2 + */ +/* EINA - EFL data type library + * Copyright (C) 2002-2008 Carsten Haitzler, + * Jorge Luis Zapata Muga, + * Cedric Bail, + * Gustavo Sverzut Barbieri + * Tom Hacohen + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + + */ + /** + * @page tutorial_ustringshare_page UStringshare Tutorial + * + * to be written... + * + */ + +#include "eina_share_common.h" +#include "eina_unicode.h" +#include "eina_private.h" + +/* The actual share */ +static Eina_Share *share; +static const char EINA_MAGIC_USTRINGSHARE_NODE_STR[] = "Eina UStringshare Node"; + +/*============================================================================* + * Global * + *============================================================================*/ + +/** + * @internal + * @brief Initialize the share_common module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function sets up the share_common module of Eina. It is called by + * eina_init(). + * + * @see eina_init() + */ +Eina_Bool +eina_ustringshare_init(void) +{ + return eina_share_common_init(&share, EINA_MAGIC_USTRINGSHARE_NODE, EINA_MAGIC_USTRINGSHARE_NODE_STR); +} + +/** + * @internal + * @brief Shut down the share_common module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function shuts down the share_common module set up by + * eina_share_common_init(). It is called by eina_shutdown(). + * + * @see eina_shutdown() + */ +Eina_Bool +eina_ustringshare_shutdown(void) +{ + Eina_Bool ret; + ret = eina_share_common_shutdown(&share); + return ret; +} + +/*============================================================================* + * API * + *============================================================================*/ +/** + * @addtogroup Eina_UStringshare_Group Unicode Stringshare + * + * These functions allow you to store one copy of a string, and use it + * throughout your program. + * + * This is a method to reduce the number of duplicated strings kept in + * memory. It's pretty common for the same strings to be dynamically + * allocated repeatedly between applications and libraries, especially in + * circumstances where you could have multiple copies of a structure that + * allocates the string. So rather than duplicating and freeing these + * strings, you request a read-only pointer to an existing string and + * only incur the overhead of a hash lookup. + * + * It sounds like micro-optimizing, but profiling has shown this can have + * a significant impact as you scale the number of copies up. It improves + * string creation/destruction speed, reduces memory use and decreases + * memory fragmentation, so a win all-around. + * + * For more information, you can look at the @ref tutorial_ustringshare_page. + * + * @{ + */ + +/** + * @brief Note that the given string has lost an instance. + * + * @param str string The given string. + * + * This function decreases the reference counter associated to @p str + * if it exists. If that counter reaches 0, the memory associated to + * @p str is freed. If @p str is NULL, the function returns + * immediatly. + * + * Note that if the given pointer is not shared or NULL, bad things + * will happen, likely a segmentation fault. + */ +EAPI void +eina_ustringshare_del(const Eina_Unicode *str) +{ + int slen; + if (!str) + return; + slen = eina_unicode_strlen(str); + slen = (int) (slen * sizeof(Eina_Unicode)); + eina_share_common_del(share,(const char *) str, slen); +} + +/** + * @brief Retrieve an instance of a string for use in a program. + * + * @param str The string to retrieve an instance of. + * @param slen The string size (<= strlen(str)). + * @return A pointer to an instance of the string on success. + * @c NULL on failure. + * + * This function retrieves an instance of @p str. If @p str is + * @c NULL, then @c NULL is returned. If @p str is already stored, it + * is just returned and its reference counter is increased. Otherwise + * it is added to the strings to be searched and a duplicated string + * of @p str is returned. + * + * This function does not check string size, but uses the + * exact given size. This can be used to share_common part of a larger + * buffer or substring. + * + * @see eina_ustringshare_add() + */ +EAPI const Eina_Unicode * +eina_ustringshare_add_length(const Eina_Unicode *str, unsigned int slen) +{ + return (const Eina_Unicode *) eina_share_common_add_length(share,(const char *) str, slen * sizeof(Eina_Unicode), sizeof(Eina_Unicode)); +} + +/** + * @brief Retrieve an instance of a string for use in a program. + * + * @param str The NULL terminated string to retrieve an instance of. + * @return A pointer to an instance of the string on success. + * @c NULL on failure. + * + * This function retrieves an instance of @p str. If @p str is + * @c NULL, then @c NULL is returned. If @p str is already stored, it + * is just returned and its reference counter is increased. Otherwise + * it is added to the strings to be searched and a duplicated string + * of @p str is returned. + * + * The string @p str must be NULL terminated ('@\0') and its full + * length will be used. To use part of the string or non-null + * terminated, use eina_stringshare_add_length() instead. + * + * @see eina_ustringshare_add_length() + */ +EAPI const Eina_Unicode * +eina_ustringshare_add(const Eina_Unicode *str) +{ + int slen = (str) ? (int) eina_unicode_strlen(str) : -1; + return eina_ustringshare_add_length(str, slen); +} + +/** + * Increment references of the given shared string. + * + * @param str The shared string. + * @return A pointer to an instance of the string on success. + * @c NULL on failure. + * + * This is similar to eina_share_common_add(), but it's faster since it will + * avoid lookups if possible, but on the down side it requires the parameter + * to be shared before, in other words, it must be the return of a previous + * eina_ustringshare_add(). + * + * There is no unref since this is the work of eina_ustringshare_del(). + */ +EAPI const Eina_Unicode * +eina_ustringshare_ref(const Eina_Unicode *str) +{ + if (!str) + { + return (Eina_Unicode *) eina_share_common_ref(share, (const char *) str); + } + return (const Eina_Unicode *) eina_share_common_ref(share, (const char *) str); +} + +/** + * @brief Note that the given string @b must be shared. + * + * @param str the shared string to know the length. It is safe to + * give NULL, in that case -1 is returned. + * + * This function is a cheap way to known the length of a shared + * string. Note that if the given pointer is not shared, bad + * things will happen, likely a segmentation fault. If in doubt, try + * strlen(). + */ +EAPI int +eina_ustringshare_strlen(const Eina_Unicode *str) +{ + int len = eina_share_common_length(share, (const char *) str); + len = (len > 0) ? len / (int) sizeof(Eina_Unicode) : -1; + return len; +} + +/** + * @brief Dump the contents of the share_common. + * + * This function dumps all strings in the share_common to stdout with a + * DDD: prefix per line and a memory usage summary. + */ +EAPI void +eina_ustringshare_dump(void) +{ + eina_share_common_dump(share, NULL, 0); +} + +/** + * @} + */ + -- 2.7.4