From: Martin Hansson Date: January 13 2011 1:00pm Subject: bzr commit into mysql-trunk-bugfixing branch (martin.hansson:3263) List-Archive: http://lists.mysql.com/commits/128651 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============0826472067==" --===============0826472067== 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 13:00:39 +0000 @@ -0,0 +1,138 @@ +#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; + +/** + 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; +}; + + +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 13:00:39 +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 13:00:39 +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++); + } + + +} --===============0826472067== 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\ # vn5nchn6ur82prcg # target_branch: file:///data0/martin/bzrroot/refactoring-\ # Bitmap_set/n-mr-o-t/ # testament_sha1: 67ac2ce02511b0b32f8c5508c79d7a1da50979bb # timestamp: 2011-01-13 14:00:42 +0100 # base_revision_id: tor.didriksen@stripped\ # od5w1gwdldjesjuk # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWSJulPUAB6rfgHQQeX///3/n /vq/////YBCfee7u3T2ope9bt996+vIquK3d7lsX3m4Jp92rmO7uzZ0ZVI7aTQ1VHRYSSEaaEyNB iAUxMU2kzTKDI02iNNMgGQZAlCJpgRoRU81PU1NijTI9TGjQEANAAAAGmiaCU8JpkKaeJHqPSaAG gAyADQAAAk1IgiYKn6noFNMnlMT1NDEyMRoGg0aAAAEUpqIPTUADQ0AAAANAAA0AAAkSCAjRMEni ZFPKan5FP1E09qm0j0nqNqDQaGymGo211jEIV3V8WgesU2LlJE2vzhuHu+SJenhNe9/61/YJ0dvf 2+Xbs2W6zULKXGyUIUyRQFgNdaqUtVFVvtYpWDXrWl4cFHsBu/OZfqmcyBISPtHIoC/Tav7O7Y0o ZJk6lF98AASFVsrg5le+WD7iwZKUqYsgZ1219/zYPGg6sGKXeDC6YFw2nwq4yzVU6wa2ujDZI1vX rqkIWu2ETYJCoJpCEkJJ6sZCiIKDNzjYhU3slAoDEZmTJCz7JwduoSIN4cktl/ahk0uvIGR3cpiA o7V7+wUJFwnwoPkgujdfw4Q4DpH9SgKRrxpIb05BND1RrMemSszWL7aFrC3NHpPVuMef/d0B9M1C QwwUkHsaM0eH4Q/iJTlYHfiqufvTaGJ2t3lV6g6b4W1de3kwmxiuCslTWYOe2jPMMmyII9A6duX+ FeH3zasar+xYaXlxeAouV1jODtPuHJLDZO2C4il0RR7QFehpbEa4fVnVSSalV6hnNZn9RtDCCQbR 8FO7g4Yw6eZtXhjfgPzeaXg6jLeNqgQdXE4NuSiKQTODmoF/OLUqFuiEt/lNHNRmj103gUZDz8sY RuoxdVLmhSq1EyK2qLK2G5jOGkMgBBrrWjOGVs0nbl7hlmgqPMceeCM1nfdKrMHoq1DLVOHhSzEV z2PZnvkz8Xiq3ni+imvNuf0PY3mZ4WdbRNeTUyWoU0Yhbyap7t04nOsO0BYAtBLgFpZSMhCaXJOB ru2u8cHjO97Al2B5sFL4UimrS8hACWuArehEdboXwcZawSsO3aCCrX2rNyFJwnuxTFzGV389cHKk 6EnaStnoNjk7rMQyYmunKUwmua8l87PFcrAMRgxrWnIHj0eLOau7jbwvf45592nWS7A1iqzxgVyR ejfJI+5PlpU1wPN+agyz2Fv2J/aB2cq2rMMG0TInJFZgVQUt6hKLLpOfG9vXCZnqbFok/xi5X1qO sqkEkOqPjvrKIcolvIRhhZXNTQbLNunZKLSYMM5AZZKk/gkLrim58YNHqmQ01kw4XcdCEVbDPgry MkppcEp9pCrXpYsRWCSUlkbNeJNs2os9DO3UCykx4dfObUiGjotrp2k2u6o2WX1d0MlVmI7YbTaJ me+kzFgXwEi5uUINZlbsGYOsOo6BhDh75rdTKOjSw8S1Gbmo69x6BGiG7FxG1sGhZnnWVoHTfU+T mdNfNkgXmEkz/29Uo1VU0IqvAL4cWn2rBlIOIo1BlGXSLoPHvBm9bKminCxaSYnS5GvNHTxHwIbe gQwvOMuRNILEgae/hcyZRXCMSwJlx8v4lQ/md1yLVgj8EX2E/X44Tmj7FaiJQtY8oVESguoPaUUk 4JfpMHKYQ8eUoJ6ZCTzSZ3iUqYF0IjLUKSrfTCbTe8RdMJdhKI2QnVZSvCi458sL1cVFSoHZxnHX 0ZR6w1qjaaslsTGsd6ln1tTpTpT8jMWSI4g2IIWgzm+LpjZVSvGgcQU6yFV6s8C1LeYCL3dGZmnS UiDhDlWrjftmNIyvz2p8hGiGJpuOdOJuuORgWx+Rv+IyZRa1xLUKerhmLGOhsinPUbLlfU0i4NAq u9iteFPyvHGJVvH3tYO7tq1cCh6azlCTs+FB+wmhhuM6FJneEIJN1FosFHpId3OQfCgxxO06d6oY hcsWMyJvuIdrOUVzZMDcdfHldQJEr3QumkMTRiwxqSzreGCbtsE5hDePoUzMSZvU9gsJvXZnszkx hI5HGrTVpSIWi7z5rhs+qRF05p0kcwXHGF9+RqKYPVx3CtVovnOXu+hEIxivHhLZXb1rBEPMSCdJ IdjqFoqWcrpXB/b1h62EDeg8K+miSR5UybYeC0ORU+N9SeWeHd9eXFjsfQc0RDWS4MkXL6UzN0L9 fUUnsoqgZLfP+O+MhzHK5iKYeMZA9HX51zDmsBBCwtXVnV8ELHH70DNxBdqVkCp2IH3f5tu8/4/j 8TKp0/IMGN7Pm/uc6hrGhDBmf8lwoAj8qY0sPepsXxHvbbbSUBlpARpEtdC7cBoZCVBLEIs9og0I 0EMz92so5ZnAmwsGhaaEyU7SzsBggKV/Iohoahsimxkr55HxVB5AZ7W4bpHxAR1RVovQtQvhOk9U oHmEdRZTYgLZGpfJ7sQchHkscSkJDDj/60CTbxhZDEdyDsgDpnngzCHTehTAaAxEMRYt7bRRdCuE dRXwzJYx0sUgIhecqhYlvBB9bL0ew8vc70/dCHrnn9MY3Ri7LE+ehgszR4vx5T4D0xnxQBBqTSio hQhB5giSD0cf3vJc8jQz4ZlReqJcl4SgSUJLAY+bOxdqFSoSVCYk+4gRnpQMgZnIIdid9SrKke01 Dl7R03VuMTdQy7idInSZkhe9nfH76jAx0m3WP7QC77x0LVtk6Cs2oS79576Ji19hcUvguLBX9QSw oitfdIN8p/ukkSvBBkxAseXQvhe2DhB6iGpdcJQx67UiKIwgN6Tcgw7AU4pVhIbiYbTPXPTon1Q4 ALgYB9Go6/E3nwPm8cGU+/xKajeM7OroQtpvoDbPrgCHYe9BCPYP6n1NrLXFYno1TMcrGfYXGTtO blIUgxwDqfYQOhSM3Fyx00yDHhERNnmnrHiJQhBLzJiABMj3flAsSmyuuw68g88EKQ744yQYaiaY gnZoKFYhc5PNvVxJzE36YcFQihER1JzVUJaNE5xLwsNp6NiLTvBwJfLrdxKrcYGsG5AfU2dshsXU pA7B0ayq+9zM3trOId9FdgoZ4wV2Q8zjxylHqpNCQSbnn+8o0sYSpepXtSYpqrgRi74lTNdmnjcE JGaML6YpJmWBZ2fC3thOdW/SOO/mK8pxNJnRWr1IIWFk6SDOshM3JGA5tycipF1LdanslbSM9YzP fv8i6d4fVy8/Hxj9DRv0Qwdv0XTvz330NN73HIhfQxVTWaxLRYIGHn3TMfByzUmkOfq3eacA7m2c SbE0MKWJU9nilizeHrpNOTOZOFhOmx0jELZYXMZWqJFkqlZBK+NjRjOalfONOIv+rPc6ftGhQ6XC SXEGIL7CAmI6WLpGLQVKzki1KNGvDwMjpg9rkxQDiHB7TtKPx3Sz6DMHh6fSWBJ5ZkSzb9X0r9aw VymSr4DvUj5fwMQ0U7FoqUpLJGh+Y/QqgQVBgWZB6/shck/y1+xumgco9TAW1r7NXmNu5eI5Vlbt Sd0ud0gNSG3AiCd0ZFFCKBOfAxtJ5EmPXosHURMrIuMTilRTaGWuF7Fxl8pAwhh2/xCGHHWl4OoH 0Ty5pq0yOz3O4RIlDgeg5uPzv1kIqpDUOEOSKkWRNwph06UdXXJdlDtkgIpCbvi6MqeJyS3b6den SznFZTRCqqgoOM2+I6jm4beNiDNlgsMCwfGhfYMGN6XA0FhKNIyJmrPMmDaXSWXliD+AAOuT3+i8 s7O1QqPIoaUSXcbNJxWLG82E47RiDhAgC1VmUYYYYl8rjMKhCCYxgi0F2hpLclfTBNJNXjWs1Q8E K8alKNU4mUAl289KU6mksb9vKWhmGLShyAkjvewb4shh3btJwL8zL6a0PJ9dOLDcAcCIzrIegYUv cKtEPnLFXdRo071S6VJSYdqQ+K9zCVThRTotQXgA947wMz6tM3wjuDis5oMlCCVdZHbG3V6blaKy 0IVhVwXs6+yXgaCsiyGQQ6KzpSq0pvwmJj4zKr1MWGFkmSGpkLyDziPQI+grNFoNChdmGHqEXohl kEMYuZrcF2TQ1VVNE29lrDARYIIiBwyJNCXpkcDuM7XwcNC5SEZqCqlZhKJJVhYwUBaIBJ+xkhDE 2gnCz8vFhixZ+PdlJdpPPNCx6PrOV1V4e7vbNaBdVDMgNRczM0tDSCSQ4l2UxQFCrJISUkgxE7br Qh0/rfsUx+dkoj0YEEWMkf8kmFE0jhAo3srnpjyQCzNQKn0+6a60x4br7ScJ0HYgisgiQPoEL5UF wiQhFutd8JotLAzmT9UBV+U6LQxUWxmaX7xHWiZ4DNdbtWRhdFsX5eBv7QydMgmzVodCwdCUjI1s qFhRRImpCpLEKKGHpYQqYdQx8N+qggYBbgItMi5VkQEEJDIZCSDdm63V3nPnI7x3XoIXudcUQeTZ 7YIb5i4cJheqRqzsq3z+UMhuY6jUjgVYCOLZIqsyOOaNqAYWDgEzC0jrJKUCMqUnDbJ1Dj1xMnFK MnSJp5onk8biL5li5QkKNcfVXnItz2FrCqZ5GMpBuq7LbhrQsimIVR5q2y1qoDHs8Yk0MEnzcJA4 YSZItXmcLRMzQLBbh0VMFpWxlk84LojyszRZnuK++YkMUXUSUkDZa1gUGIyHRxFZaBaBApixpN25 yOMpVaSvGbZXzixeFlZUkNRzY5XaKMBMxMWqsje9XpC1A1DNKmA19MnLGUquNpBSo0HhCo0X/QUL y6qHvjDd0kgvTOklEg7HQGiXklEZAoJMBMJZw3NFcalJ/Pf3LDCxReJQYtFpsBeg20Fs0yyuoIRs EOQmWgwm/5X089Jb9Red0gWWluws1plGnFJiEYpFdtiVwNKQCVVtgipWwvcym+kiSwhBx6oMgGyS 6EhODw0Lv7EVDptyIMZH6dcp8A6H+taauoVbMJkuAlxPPJoClOoQ+SQ6HfDO8t9BtLBV3HJQEGtn BvesaVxoLtLRiOZI9awVwvwayWEIntI+x7XuvIl7CWwZamC7S7T0KfM1PnbQ58cH1tAycw9QkKcD qNSMApCQg9rcETcM876hOlgTNr/qkq9EslqqyNq/8XckU4UJAibpT1A= --===============0826472067==--