From: Martin Hansson Date: January 13 2011 12:48pm Subject: bzr commit into mysql-trunk-bugfixing branch (martin.hansson:3263) List-Archive: http://lists.mysql.com/commits/128650 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============0431390619==" --===============0431390619== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #At file:///data0/martin/bzrroot/refactoring-Bitmap_set/n-mr-o-t/ based on revid:tor.didriksen@stripped 3263 Martin Hansson 2011-01-13 The Bitmap_set class. The class hides the bitmaps that represent sets frequently used in our source code behind an STL-like container interface. The benefits are safer type checks, less boilerplate code, an optimized iterator and a familiar and consistent interface. added: sql/sql_set.h unittest/gunit/sql_set-t.cc modified: unittest/gunit/CMakeLists.txt === added file 'sql/sql_set.h' --- a/sql/sql_set.h 1970-01-01 00:00:00 +0000 +++ b/sql/sql_set.h 2011-01-13 12:48:09 +0000 @@ -0,0 +1,140 @@ +#ifndef INCLUDES_MYSQL_SQL_SET_H +#define INCLUDES_MYSQL_SQL_SET_H +/* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ + +#include "sql_bitmap.h" +#include "my_global.h" + +template class Bitmap_set_iterator; +template class Bitmap_set_reverse_iterator; + +/** + A set implemented as a bitmap. Due to this implementation, operations that + normally are quite expensive, typically having O(n log n) complexity, are + extremely cheap. A set consists of a bitmap and mechanisms for lookup in + both directions. + + - In order to find an element of class T given its bit index, a lookup + array of pointers is employed. + + - In order to find the bit representing an element of type T, a pointer to + a bitmap member is employed. + + The n:th bit in the bitmap represents the member at position n in the + lookup array, where the first member has position 0. A set consisting of + this element is represented by the bitmap 1. + + For obvious reasons, it cannot be allowed to perform a set operation on two + sets that have different lookup arrays, even if they are of the same + type. Attempts at such operations will result in failed assertions. + */ +template class Bitmap_set +{ + +private: + ulonglong m_map; + T*const* const m_lookup_array; + const ulonglong T::*m_map_member; + +protected: + inline ulonglong get_map(const T& t) const { return t.*m_map_member; } + inline T* lookup(uint bit) const { return m_lookup_array[bit]; } + +public: + + /** + Creates a set from the given bitmap. + + @param The bitmap for initializing the set. + + @param lookup_array Pointer to an array of pointers for looking up + elements given a bit index. + + @param map_member Pointer (offset) to the member of T that holds a bitmap + representing the set of that element. + */ + Bitmap_set(ulonglong map, T*const* lookup_array, const ulonglong T::*map_member) : + m_map(map), m_lookup_array(lookup_array), m_map_member(map_member) {} + + inline bool is_empty() const { return m_map == 0; } + inline bool contains(const T *t) const { return ((get_map(*t)) & m_map) != 0; } + + /** + Adds the new element to the set. + + @retval false If the element was already in the set. + @retval true If the element was not in the set prior to insertion. + */ + inline bool add(T *t) + { + bool was_there= contains(t); + m_map|= get_map(*t); + return !was_there; + } + + /** + Removes the element from the set. + + @retval true If the element was in the set prior to removal. + @retval false If the element was not in the set. + */ + inline bool remove(T *t) { + bool was_there= contains(t); + m_map&= ~get_map(*t); + return was_there; + } + + Bitmap_set set_union(const Bitmap_set& other) const + { + DBUG_ASSERT(m_lookup_array == other.m_lookup_array); + return Bitmap_set(m_map | other.m_map, m_lookup_array, m_map_member); + } + + Bitmap_set set_intersection(const Bitmap_set& other) const + { + DBUG_ASSERT(m_lookup_array == other.m_lookup_array); + return Bitmap_set(m_map & other.m_map, m_lookup_array, m_map_member); + } + + friend class Bitmap_set_iterator; + friend class Bitmap_set_reverse_iterator; +}; + + +template class Bitmap_set_iterator { +private: + const Bitmap_set& m_set; + Table_map_iterator m_it; + +public: + Bitmap_set_iterator(const Bitmap_set& set) : + m_set(set), m_it(m_set.m_map) {} + + /** + Returns the next element in the set, or NULL if there are no more elements. + + @retval NULL If all elements have been iterated through. + @retval element If there was at least one element left. + */ + inline T* operator++(int) { + uint next_bit= m_it.next_bit(); + if (next_bit == Table_map_iterator::BITMAP_END) + return NULL; + return m_set.lookup(next_bit); + } +}; + +#endif // INCLUDES_MYSQL_SQL_SET_H === modified file 'unittest/gunit/CMakeLists.txt' --- a/unittest/gunit/CMakeLists.txt 2010-12-17 09:41:21 +0000 +++ b/unittest/gunit/CMakeLists.txt 2011-01-13 12:48:09 +0000 @@ -214,6 +214,7 @@ SET(TESTS mdl_mytap my_regex sql_list + sql_set thread_utils ) === added file 'unittest/gunit/sql_set-t.cc' --- a/unittest/gunit/sql_set-t.cc 1970-01-01 00:00:00 +0000 +++ b/unittest/gunit/sql_set-t.cc 2011-01-13 12:48:09 +0000 @@ -0,0 +1,136 @@ +#include "my_config.h" +#include + +#include "sql_set.h" + + +namespace { + + class A { + public: + const ulonglong map; + A(ulonglong map_arg) : map(map_arg) {} + }; + + class Sql_set_test : public ::testing::Test { + + public: + static const uint SET_SIZE= sizeof(ulonglong) * 8; + A *a_store[SET_SIZE]; + + Sql_set_test() { + for (uint i= 0; i < SET_SIZE; i++) + a_store[i]= new A(1 << i); + } + + ~Sql_set_test() { + for (uint i= 0; i < SET_SIZE; i++) + delete a_store[i]; + } + + }; + + TEST_F(Sql_set_test, self_test) + { + for (uint i= 0; i < SET_SIZE; i++) + { + // Test the map member + EXPECT_EQ(a_store[i]->map, 1 << i); + } + } + + TEST_F(Sql_set_test, add) + { + Bitmap_set as(0, a_store, &A::map); + EXPECT_TRUE(as.add(a_store[4])); + EXPECT_TRUE(as.contains(a_store[4])); + EXPECT_FALSE(as.add(a_store[4])); + } + + TEST_F(Sql_set_test, remove) + { + Bitmap_set as(1 << 5, a_store, &A::map); + EXPECT_TRUE(as.remove(a_store[5])); + EXPECT_FALSE(as.contains(a_store[5])); + EXPECT_FALSE(as.remove(a_store[5])); + } + + TEST_F(Sql_set_test, contains) + { + const Bitmap_set bs(1, a_store, &A::map); + EXPECT_TRUE(bs.contains(a_store[0])); + } + + TEST_F(Sql_set_test, set_union) + { + const Bitmap_set set_x(1 | 4 | 16, a_store, &A::map); + const Bitmap_set set_y(4 | 32 | 128, a_store, &A::map); + + const Bitmap_set the_union= set_x.set_union(set_y); + + EXPECT_TRUE (the_union.contains(a_store[0])); + EXPECT_FALSE(the_union.contains(a_store[1])); + EXPECT_TRUE (the_union.contains(a_store[2])); + EXPECT_FALSE(the_union.contains(a_store[3])); + EXPECT_TRUE (the_union.contains(a_store[4])); + EXPECT_TRUE (the_union.contains(a_store[5])); + EXPECT_FALSE(the_union.contains(a_store[6])); + EXPECT_TRUE (the_union.contains(a_store[7])); + EXPECT_FALSE(the_union.contains(a_store[8])); + EXPECT_FALSE(the_union.contains(a_store[9])); + } + + TEST_F(Sql_set_test, set_intersection) + { + const Bitmap_set x(1 | 4 | 16, a_store, &A::map); + const Bitmap_set y(4 | 32 | 128, a_store, &A::map); + + const Bitmap_set z= x.set_intersection(y); + + EXPECT_FALSE(z.contains(a_store[0])); + EXPECT_FALSE(z.contains(a_store[1])); + EXPECT_TRUE (z.contains(a_store[2])); + EXPECT_FALSE(z.contains(a_store[3])); + EXPECT_FALSE(z.contains(a_store[4])); + EXPECT_FALSE(z.contains(a_store[5])); + EXPECT_FALSE(z.contains(a_store[6])); + EXPECT_FALSE(z.contains(a_store[7])); + EXPECT_FALSE(z.contains(a_store[8])); + EXPECT_FALSE(z.contains(a_store[9])); + } + + TEST_F(Sql_set_test, singleton_iterator) + { + const Bitmap_set as(1, a_store, &A::map); + Bitmap_set_iterator it(as); + EXPECT_EQ(a_store[0], it++); + EXPECT_EQ((A*)NULL, it++); + + const Bitmap_set a2(2, a_store, &A::map); + Bitmap_set_iterator it2(a2); + EXPECT_EQ(it2++, a_store[1]); + EXPECT_EQ(it2++, (A*)NULL); + + const Bitmap_set as3(1ULL << (SET_SIZE - 1), a_store, &A::map); + Bitmap_set_iterator it3(as3); + EXPECT_EQ(a_store[SET_SIZE - 1], it3++); + EXPECT_EQ((A*)NULL, it++); + + } + + TEST_F(Sql_set_test, iterator) + { + const Bitmap_set x(1 | 4 | 16 | 32 | 128, a_store, &A::map); + + Bitmap_set_iterator it(x); + + EXPECT_EQ(a_store[0], it++); + EXPECT_EQ(a_store[2], it++); + EXPECT_EQ(a_store[4], it++); + EXPECT_EQ(a_store[5], it++); + EXPECT_EQ(a_store[7], it++); + EXPECT_EQ((A*)NULL, it++); + } + + +} --===============0431390619== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/martin.hansson@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: martin.hansson@stripped\ # mdn35tjkt4vyfky5 # target_branch: file:///data0/martin/bzrroot/refactoring-\ # Bitmap_set/n-mr-o-t/ # testament_sha1: bff237bc0a5d6f77d874c0a89d71e0637aa1ed90 # timestamp: 2011-01-13 13:48:14 +0100 # base_revision_id: tor.didriksen@stripped\ # od5w1gwdldjesjuk # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWbrBPiEAB7XfgHQQeX///3/n /vq/////YBC+8b7d7y+ok++973ndeuc2toG+Pe0PsZ0NPh7evWqKCj2H3vDkffc5QDrDFCBomCp5 T8CJpqPR6kaNNA0ANHqAAaABKEATQBJip4U2UeiHqM1PSNqBoAAA0DQNAJNJhDEiPIyT01AAGjIb UaAAAABJqSamg0k8QKeKNqeEjammjNJiAAAAA00CJSE00m1TQ9TGpp6IaaaDRkABpoDEwgDRoEiQ QEamTNE0yEbUajE0nplM00m1HqDRoB6TRiWZCCI4dTmiEyDXB1akrj/aSUmjrUq2dOt/E+l/OI9T 1cOvLK21qFlMBslCFMkUBYDW2qUtVFVstYpWDXLaYQ3KPMG9+sx/dM8xDExftPuoK/bpr0PHrtjh szry0bduAClVZ3XHmq+3G1tYnCJfI+JEBMrwbtytaE5kwCD2cVtcAB4sR0S65dlVOsG1rpwzkbNs RtqkIW22ETYJCoJpCIkJJzRkKIgoM2OaxCpuZKBYDEkjFHJmwBTVwqVzZvuzaXiSMu27wvputhWN uZPw6FRVMSfah+iGMcc+3V/iXlPSlBUjbakjonITfCsbKLKQz1TnxRm8iiqLIejSLuD96XBr4IyQ ggHhzUBnqi3vS76xB9KAZuMvBvwZ0IVRqEthcyDool+2Oy2C6I7xnkfMcHPbNnkMGwIg9A6teH8q 8Pxq1p2X+C8anvSeAodmNIoZ1o4jxyu4KLGS8TtgTewBHmc7IG831V0QzM6sz1DGq1P7nfGEUiqt m+KnXBwxDq520eEsuI/F5kxwuJUyDhQBnRxQy4pQJsWYHhMJ+b1mKRZuNLZurGE1WOyW+DJSPXlh otmpuiG5zMqbCLGi6IVFuxX0NnCkAYOqpJq4VFwk68/EcsGQnoG3MxKtfG5U13PNEqaVm/xpexNc dToruoz5PFVvNN9ymnPs/pexuMTxs6/NNN+hlgipv2GzVaz44zivIz+4LwahLxGCuZTJRM7mZ3HV bwu8XPFGR6wVtx6mQ3unBaM7yDAS3mFTzMRvORtCizLBVRorggZ1a603Bipim+RSVBZjbVU6mVOB dLVdbPoNrk7rMQyYmt+UphNdq9i+dnzLssAxGCM1pxB5dDjNXfvbxPh80+ff05EwYGQqs8wFaClr qaSPkVqqLjgLv4WCieIR85XtAG/XDGcwQCRHjPciswKoKX/EJctOo9WWV/1RqY6GpfMr+c3K+1QW szMGZh0J79iSgOZFZ7TF11dVCHMaa9ezglCyUSM2DLJUn+CQu6Kbnxg6PXMhprJh13cehCKthpwV 4/GURkSv9aDf7Z9jfEJImlI+j2uS0K4SvxLzUgaRAOO/rjEkOz5UTPxEF9cownslydmlnuDMBiMQ iq51TEWJlASbm4BFr2Vu4Zg8gdh0jCHH5TTJCeOrzAhr7uQ2CvbJy6hnbpuYIaFanZulCaE4ZWSt kYmX477+BhLyTP6cKpRqqpoRVeAML6tPfsGMgoQkFGKQjkDwjk1AJbkdkb7qD0xAMIiWK0aMtYbM nyRxPC4kkFUgafXY5E1MJSKn/TyiLg/ic7kXK9H4ouwxNR9XzY3Nh8FeiJQtY+mFREoNdByzkiIw T/KAdRyeTUmQrQRHHWMImU6PNoSFSIByUS98YR0M7CJN5YijriidiGR142IbskmvEvLi5lYXJTta GCg2XmS/MLK4hbfKOc03qW0s0Sa0hTIIsAbEELWWjtkNlFLaUIQPOckLeeBCse7KAbC/HgpSgtDm AUBAhjDmNZ1asBjYNgIecKhZhoGxwHLnM8pMhB3+HL6RS4kbJzlREflry7BAw3Qw0OtiKF17tOQb BQRsN4UPz2lxxEbjyl+feVmG5UZqw+aTQ6PAPbVRusINnxhUvjv3CTLZGTiYhcitctFRyLuLum8Y gcShlVMnIXBiQqXFxhx4zxVU8BoYHbzcH7BQ2rrqhqkSnh0Nids7s4JgINBNNxGdjYqHOXPgOy+u 2l+hAxkXFPW4G6L8RDBRJbdWkrEhp0Kaa7iOgZjjUruzNhSGCuMy++zJ5jq8PeiE5zXmx1q7JbRR DeOB8HILJYhMSEuejqB9/eHeoMCVI2w8cBJI5kIk2Dq+NxFiSEjWVHmPLTujmhkXrFrCBeNYRWFA 8rJNh5PeYjfw51Zfn7m9q23NJ2KQtYVELw3dvcdcdgIEIsAy7WJXjQ4vZ+cY09YdFTMgZ2+gcnHh u2OXl5jPwGXWIEJNDa4Tq4A4BhBBDe9E5rgQ9F8r4n8TBJ6R5VVZJQZagEahLZQu3AdCkIwEf1aE r7UCxQsRqj/Lqpu0dKmn08a2IUXBLskAyoGJ+42h0phl7TquW6tx+StPUDk8t/KR+YCOUVaL0LpF +E6T6ZQPQI5FlNqAtkdK8fwxByEexY4lISGHH9LQJNvGFkNI5iPFAG+emDQIdOCFMBoDEQxFi4Nt FFrVwjkV9FEuqzay8BE9x3qelLsBA4zLyekcnlTm2s3qiOaUssQ6pB+aZslBzeH25T5D6ozXkBMz 1GixgnuFtDe0OKaNZ5pQj6G2hXSuoYtaNAg0INQFRg9WGsslEo0VaI2DwCDHigFoRwqQNR2ouMzg OAq7uY0nVN01MxapYk2kL4uPy+GBvNRnsH9wBb8R0LDHObqK3NCXhwPjRMX9/GXFMILiwV/YEsKI rX98g65T90kiV4QNiEJlz78/nSoNQPIUy3RUlI8GeQq8NUBwSbkGHjSU4pVhIbiaMzTXTTXPshwI LgYB6uk+Y7l5sPwJHfwx/3XWeU4FkjjrQtp1TBtn7IAh2HxQQj7B+18XwMoMRSRnRniZ63z5Br8h 3lwSMwjEkeVazj2wvPtuuDqlqlPAslKSD6wZMAsTh4Ky9XLTTiaakypApA2iYFSJjHEwGuUBA1uD XCkdfn6j6aPySNvaoLUWodx2l1iWzZU5mJuD38EaTAOwt/P1R2l2ndM3g/EEsHreg6l6F0iFQdyt O8vXs5maa1mHsAroKGMoq7AeYz68KT9u6qFAo3ir6KThJQdCqOqqOUR6RVhCy1Z0L6XvtGgORC9r qxsiIqpMnep6OHlfEloe4ULznNDJCqbJIH4FooiBZMjERjZELCwVXL2YQKD7Suqj9VpdMkJae7u8 QnU+IDwdIZBs31LXmOjDBj0YXOt9VtZ5/sg7kL2Mxw0HAS2ZCBo/dqC0fp3LFl4dR5NvuW0O/uTU m8mhhSxKnXqlizhDnSacWcicFhOmx0DTCVlJlVGKYm0FUrIJXxtZiNOc1K+casR/TzrpZ6SI0llw q64QExWlArEywcpAOgqVnJFqUdGzDwMjfB73JigHEODtJ/T49GRiHZ1HIFOqFauTd5Z4pomdN5ew h4Dx5aPJ+RnDYna5IY43ZKK/5J4IKMVxL8SWtL6sPufyWEKvnYGnBfXn7Tx92e6dc6nySV2VXYA1 Idy5EE9oZFFCKAuqhWSX62KvXBYORSC4xOKVFNoZY4XuXGXkIGEMOf7Qnv7uCXn9AStqXc6Ypo9f 3x22FhbASQc+70y6idiwQ7YEQkYI02HIVCKpWZ+q5eu2Ou4DGQj3iezslhOKW6+jXp0s5BWU0Qqq oKDhMvWeBv2ZbWmDNtgsMCwfGhfYMGN6nA0FhKNQyJnTpmTBtBvLLyxB7xAOuT4ea8s8XeoVHkUN SNoia8hnrOt3QZmwXXsttD2CJiDpEWhGTiGQQQQYe+RrDSFYJjGCL0lzRsLdavpoTSTV41mZw8EK 8alKM5xMoBLn3dKU6moxX5Oe2xNWTJTYC0Ox4xe6lId7j2nqGnWmm/Ah5PjTkw3AHEiNKyH0DCG/ KRJMPeSIm8S6/W2ybIShlOaR7pzKKIdIId0oCaQD9J6Qat+S9a0J9gjUGM3cwaUCCVm0jnG7Z6Ll aKUwYJEVYuUu6Xe0ZEXEmUYZaNNlUZqqaQSJm85jWFTMwvZJihkyGEg9ZDtL2hiDCVOjTpzwUzFF Ik7puaMGTO1VVM81+q1e4iwQREDdiSaEwpkbnWzp8+7QuMhGZBVSs4SiSVYWMFAWFBI/EliCRYDm GfHjQEyBnv6lDTvh07iDNX5BjJCcufhSGcgHtQDMgZC6F8XnxQqUlKutZjQLDBCpFalDGJ23WhDp 91+1TH5GSiPNgTRpaF+iSYrDaQIFZua1yTPVMNOq0V/u++mvIrs6J5C2LuOSGNtIYxB9ownZATBM EiLdi8ITRaWBpMn9EBV+udA6GKi2s0S7USPAaxjLCpSbG5E8+k1eMaXryCa8tDoWDoSkZGtdQsKK JEyQqRFUn3sIVL+wI8vJuuEEA0YncM8vYoKISGQyEkGePa6u47OyR4DuvQQvg660QfQ2fbBDfYL9 Rx40DBYD0FcDlX0hoOTPMZo7TDeI/m9FixNEHOzJAMDe4BMwtI7iSlCFlSk4bZOANGpGDI7mGdGI 60a06phKWEi30IgSXpxxpUUWSJqEUU7iznBvisp0FTJDEhYIocYzdskQFHh8NWYISPO1CDSFksZ5 yNTZga6JqnGN5fVNs4Uxw3gm6u3HXVmeBXtM0JmRciSkgb0pSBsGmNI7sCMugXQIFMWNJu3SRxlK rSV4zOV84sXy2VlSQ1G+tk3BBQZaMq4iTHOcTpC1A1DOlS4171m2VrZmuIovmGB2VLsNPqKF5dVD 4Rhu3kgvZbDR1iHISHk7wvU0BAmkEAlUZQJOmpwV0VKT+fDmGOFii8Ag0NFpmC8xuoLPXLK6ghGY hyEy0GE3/G+nlpLr6S85yBZam7CzYmUacfARWgJGhIs3WpXg0EgEqrdBFSthg5lONJEljCJH11hA bFd3qt9ZhrNU/Ymjno3og0n+vVdfwDvn9i1VdQq2YTJcRLkeKTQFKHakOZ8sM+Us85tLBVzOSgIO lnBvqTMaVxmLmWnYfIImeJYq8X4tdCxhE8yPg83uUhF2hcwMUEYBaxPLcTaRcemhxqk7VVwLFQMY EziIg6zM6TWIvtDRZgInGXBLaRM+Rgu5oFa1/1SVhRLJaqsjav/F3JFOFCQusE+IQA== --===============0431390619==--