Merge "Cleanup the ASTL makefiles."
diff --git a/include/list b/include/list
index d6583d2..a2fdc9b 100644
--- a/include/list
+++ b/include/list
@@ -171,10 +171,10 @@
void clear();
// Element access.
- reference front() { return *begin(); }
- const_reference front() const { return *begin(); }
- reference back() { return *(end()--); }
- const_reference back() const { return *(end()--); }
+ reference front() { return *iterator(mHead.mNext); }
+ const_reference front() const { return *iterator(mHead.mNext); }
+ reference back() { return *iterator(mHead.mPrev); }
+ const_reference back() const { return *iterator(mHead.mPrev); }
// Iterators.
iterator begin() { return iterator(mHead.mNext); }
@@ -187,6 +187,13 @@
void push_front(const value_type& elt) { insert(begin(), elt); }
void push_back(const value_type& elt) { insert(end(), elt); }
+ // Removes first element. Invalidated the iterators/references to begin.
+ void pop_front() { eraseAtPos(iterator(mHead.mNext)); }
+
+ // Removes last element. Invalidated the iterators/references to
+ // the last element.
+ void pop_back() { eraseAtPos(iterator(mHead.mPrev)); }
+
bool empty() const { return mLength == 0; }
// @eturn the number of elements in the list.
@@ -201,12 +208,28 @@
// @return an iterator that points to the inserted element.
iterator insert(iterator pos, const value_type& elt);
+ // Remove the element pointed by the iterator. Constant in time,
+ // calls once to _T's destructor.
+ // @param pos Iterator pointing to the elt to be removed.
+ // @return An iterator pointing to the next elt or end().
+ iterator erase(iterator position);
+
+ // Remove a range of elements [first, last)
+ // @param first Iterator pointing to the first element to be removed.
+ // @param last Iterator pointing to one past the last element to be removed.
+ // @return An iterator pointing to the elt next to 'last' or end().
+ iterator erase(iterator first, iterator last);
+
private:
void init() {
mHead.mNext = &mHead;
mHead.mPrev = &mHead;
mLength = 0;
}
+
+ // Erase, don't return anything.
+ void eraseAtPos(iterator pos);
+
size_type mLength;
// mHead does not contain any data, it represents end().
android::ListNodeBase mHead;
@@ -238,6 +261,32 @@
}
}
+template<typename _T>
+typename list<_T>::iterator list<_T>::erase(iterator pos) {
+ iterator res = iterator(pos.mNode->mNext);
+ eraseAtPos(pos);
+ return res;
+}
+
+template<typename _T>
+typename list<_T>::iterator list<_T>::erase(iterator first, iterator last) {
+ while (first != last) {
+ first = erase(first); // erase returns an iterator to the next elt.
+ }
+ return last;
+}
+
+template<typename _T>
+void list<_T>::eraseAtPos(iterator pos) {
+ if (pos.mNode != &mHead) {
+ pos.mNode->unhook();
+ android::ListNode<_T>* node =
+ static_cast<android::ListNode<_T>*>(pos.mNode);
+ delete node;
+ --mLength;
+ }
+}
+
} // namespace std
#endif // ANDROID_ASTL_LIST__
diff --git a/include/string b/include/string
index 428d1db..9f9d146 100644
--- a/include/string
+++ b/include/string
@@ -30,6 +30,7 @@
#ifndef ANDROID_ASTL_STRING__
#define ANDROID_ASTL_STRING__
+#include <algorithm>
#include <cstddef>
#include <iterator>
#include <char_traits.h>
@@ -161,6 +162,9 @@
string& append(const value_type *str, size_type pos, size_type n);
string& append(const string& str);
+ template<typename _InputIterator>
+ string& append(_InputIterator first, _InputIterator last);
+
// Comparison.
// @return 0 if this==other, < 0 if this < other and > 0 if this > other.
// Don't assume the values are -1, 0, 1
@@ -325,6 +329,37 @@
// I/O
ostream& operator<<(ostream& os, const string& str);
+
+// Specialization of append(iterator, iterator) using string iterators
+// (const and non const).
+template<>
+string& string::append<__wrapper_iterator<const char *,string> >(
+ __wrapper_iterator<const char *,string> first,
+ __wrapper_iterator<const char *,string> last);
+template<>
+string& string::append<__wrapper_iterator<char *,string> >(
+ __wrapper_iterator<char *,string> first,
+ __wrapper_iterator<char *,string> last);
+
+// append(iterator,iterator) default implementation.
+template<typename _InputIterator>
+string& string::append(_InputIterator first, _InputIterator last) {
+ size_type dist = std::distance(first, last);
+ size_type new_len = mLength + dist;
+ if (new_len <= mLength) {
+ return *this; // 0 / overflow
+ }
+ reserve(new_len);
+ if (new_len > mCapacity) {
+ return *this; // memory allocation failed.
+ }
+ std::copy(first, last, mData + mLength);
+ mLength = new_len;
+ mData[mLength] = '\0';
+ return *this;
+}
+
+
} // namespace std
#endif // ANDROID_ASTL_STRING__
diff --git a/include/vector b/include/vector
index 051da1d..b17cc70 100644
--- a/include/vector
+++ b/include/vector
@@ -132,6 +132,13 @@
// @return A reference to the element.
reference operator[](size_type index) { return *(mBegin + index); }
+ // 'at' is similar to operator[] except that it does check bounds.
+ const_reference at(const size_type index) const
+ { return index < mLength ? *( mBegin + index) : sDummy; }
+
+ reference at(const size_type index)
+ { return index < mLength ? *( mBegin + index) : sDummy; }
+
iterator begin() { return iterator(mBegin); }
iterator end() { return iterator(mBegin + mLength); }
@@ -217,6 +224,7 @@
pointer mBegin;
size_type mCapacity;
size_type mLength;
+ static value_type sDummy; // at() doen't throw exception and returns mDummy.
static const size_type kExponentialFactor = 2;
static const size_type kExponentialLimit = 256;
static const size_type kLinearIncrement = 256;
@@ -234,6 +242,7 @@
//
// Invariant: mLength <= mCapacity <= max_size()
+
template<typename _T>
vector<_T>::vector()
:mBegin(NULL), mCapacity(0), mLength(0) { }
@@ -490,6 +499,9 @@
free(mBegin);
}
+// Dummy element returned when at() is out of bound.
+template<typename _T> _T vector<_T>::sDummy;
+
} // namespace std
#endif // ANDROID_ASTL_VECTOR__
diff --git a/src/string.cpp b/src/string.cpp
index 5c04c8e..930e77d 100644
--- a/src/string.cpp
+++ b/src/string.cpp
@@ -337,6 +337,22 @@
return *this;
}
+// Specialization to append from other strings' iterators.
+template<>
+string& string::append<__wrapper_iterator<const char *,string> >(
+ __wrapper_iterator<const char *,string> first,
+ __wrapper_iterator<const char *,string> last) {
+ Append(&*first, std::distance(first, last));
+ return *this;
+}
+template<>
+string& string::append<__wrapper_iterator<char *,string> >(
+ __wrapper_iterator<char *,string> first,
+ __wrapper_iterator<char *,string> last) {
+ Append(&*first, std::distance(first, last));
+ return *this;
+}
+
void string::push_back(const char c)
{
// Check we don't overflow.
diff --git a/tests/test_list.cpp b/tests/test_list.cpp
index 6cb9634..b017a29 100644
--- a/tests/test_list.cpp
+++ b/tests/test_list.cpp
@@ -115,6 +115,71 @@
return true;
}
+bool testErase() {
+ list<int> l;
+ for (int i = 0; i < 100; ++i) {
+ l.push_back(i);
+ }
+
+ // Deleting the first element.
+ list<int>::iterator val = l.erase(l.begin());
+ EXPECT_TRUE(l.size() == 99);
+ EXPECT_TRUE(*val == 1);
+
+ // Deleting the last should be a no op.
+ l.erase(l.end());
+ EXPECT_TRUE(l.size() == 99);
+
+ // Empty bay removing the last element;
+ while (l.size() > 0) {
+ val = l.erase(--l.end());
+ }
+
+ EXPECT_TRUE(l.size() == 0);
+ EXPECT_TRUE(val == l.end());
+
+ return true;
+}
+
+bool testEraseRange() {
+ list<int> l;
+ for (int i = 0; i < 100; ++i) {
+ l.push_back(i);
+ }
+ l.erase(l.begin(), l.end());
+ EXPECT_TRUE(l.size() == 0);
+ return true;
+}
+
+bool testPushPop() {
+ list<int> l;
+
+ l.push_front(10);
+ EXPECT_TRUE(l.front() == 10);
+ l.push_back(100);
+ EXPECT_TRUE(l.back() == 100);
+
+ l.push_front(1);
+ EXPECT_TRUE(l.front() == 1);
+ l.push_back(1000);
+ EXPECT_TRUE(l.back() == 1000);
+
+ l.pop_front();
+ EXPECT_TRUE(l.front() == 10);
+ l.pop_back();
+ EXPECT_TRUE(l.back() == 100);
+ l.pop_front();
+ EXPECT_TRUE(l.front() == 100);
+ EXPECT_TRUE(l.back() == 100);
+ l.pop_back();
+ EXPECT_TRUE(l.empty());
+ // all these are noops
+ l.pop_back();
+ l.pop_front();
+ l.pop_back();
+ return true;
+}
+
} // namespace android
int main(int argc, char **argv)
@@ -123,5 +188,8 @@
FAIL_UNLESS(testSize);
FAIL_UNLESS(testClear);
FAIL_UNLESS(testIterator);
+ FAIL_UNLESS(testErase);
+ FAIL_UNLESS(testEraseRange);
+ FAIL_UNLESS(testPushPop);
return kPassed;
}
diff --git a/tests/test_string.cpp b/tests/test_string.cpp
index 0a9c1cc..f5c3d1a 100644
--- a/tests/test_string.cpp
+++ b/tests/test_string.cpp
@@ -34,6 +34,7 @@
#include <climits>
#include <cstring>
#include <algorithm>
+#include <list>
#include "common.h"
@@ -386,6 +387,42 @@
str12.append(dummy, kMaxSizeT);
EXPECT_TRUE(str12 == "original");
+ // Append iterator.
+ {
+ string str1("once upon ");
+ const string str2("a time");
+
+ str1.append(str2.begin(), str2.end());
+ EXPECT_TRUE(str1.size() == 16);
+ EXPECT_TRUE(str1 == "once upon a time");
+ }
+ {
+ string str1("once upon ");
+ string str2("a time");
+
+ str1.append(str2.begin(), str2.begin());
+ EXPECT_TRUE(str1.size() == 10);
+ EXPECT_TRUE(str1 == "once upon ");
+ }
+ {
+ string str1;
+ string str2("hello");
+
+ str1.append(str2.begin(), str2.end());
+ EXPECT_TRUE(str1.size() == 5);
+ EXPECT_TRUE(str1 == "hello");
+ }
+ {
+ string str1("hello ");
+ std::list<char> list1;
+ list1.push_back('w');
+ list1.push_back('o');
+ list1.push_back('r');
+ list1.push_back('l');
+ list1.push_back('d');
+ str1.append(list1.begin(), list1.end());
+ EXPECT_TRUE(str1 == "hello world");
+ }
return true;
}
diff --git a/tests/test_vector.cpp b/tests/test_vector.cpp
index 8b85b97..95de15e 100644
--- a/tests/test_vector.cpp
+++ b/tests/test_vector.cpp
@@ -641,6 +641,14 @@
return true;
}
+// Valgrind should not barf when we access element out of bound.
+bool testAt() {
+ vector<int> vec;
+
+ vec.at(1000) = 0xdeadbeef;
+ EXPECT_TRUE(vec.at(1000) == 0xdeadbeef);
+ return true;
+}
} // namespace android
int main(int argc, char **argv)
@@ -659,5 +667,6 @@
FAIL_UNLESS(testCtorDtorForNonPod);
FAIL_UNLESS(testEraseElt);
FAIL_UNLESS(testEraseRange);
+ FAIL_UNLESS(testAt);
return kPassed;
}
