[uClibc-cvs] CVS uClibc++/include
CVS User gkajmowi
gkajmowi at codepoet.org
Fri Sep 17 02:47:52 UTC 2004
Update of /var/cvs/uClibc++/include
In directory nail:/tmp/cvs-serv30023/include
Modified Files:
algorithm deque fstream list map memory set string
Log Message:
-Added code for all algorithms
-Fixed map/set code to prevent infinite loops. Oops.
-Fixed list code to prevent most memory leaks. 1 still remains, but unknown location
-stlport v 1.00 test suite now compiles, links and runs. Some issues remain
-Fix deque constructor using the wrong end_pointer value
-Added erase capability to vector
-Changed multimap::find to point to first matching element instead of any matching element
-Added more tests to test suite based upon problems from stlport test suite
--- /var/cvs/uClibc++/include/algorithm 2004/09/12 02:20:32 1.7
+++ /var/cvs/uClibc++/include/algorithm 2004/09/17 02:47:50 1.8
@@ -142,11 +142,12 @@
ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last)
{
+ ForwardIterator temp;
while(first != last){
- ForwardIterator temp(first);
+ temp = first;
++temp;
if(*temp == *first){
- break;
+ return first;
}
++first;
}
@@ -157,11 +158,12 @@
ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
{
+ ForwardIterator temp;
while(first != last){
- ForwardIterator temp(first);
+ temp = first;
++temp;
if( pred(*temp, *first)){
- break;
+ return first;
}
++first;
}
@@ -266,7 +268,7 @@
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
- while(first1 != last1){
+/* while(first1 != last1){
ForwardIterator1 temp1(first1);
ForwardIterator2 temp2(first2);
while(temp2 != last2 && temp1 != last1){
@@ -279,8 +281,12 @@
return first1;
}
}
+ ++first1;
}
return last1;
+*/
+ equal_to<typename iterator_traits<ForwardIterator1>::value_type> c;
+ return search(first1, last1, first2, last2, c);
}
@@ -303,6 +309,7 @@
return first1;
}
}
+ ++first1;
}
return last1;
}
@@ -520,7 +527,7 @@
while(n != 0){
*first = value;
--n;
- --first;
+ ++first;
}
}
@@ -894,7 +901,7 @@
RandomAccessIterator result_first, RandomAccessIterator result_last)
{
less<typename iterator_traits<RandomAccessIterator>::value_type> c;
- partial_sort_copy(first, last, result_first, result_last, c);
+ return partial_sort_copy(first, last, result_first, result_last, c);
}
template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
@@ -902,8 +909,9 @@
RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp)
{
size_t output_size = last-first;
- if(result_last - result_first < output_size){
- output_size = result_last - result_first;
+ size_t temp_size = result_last - result_first;
+ if(temp_size < output_size){
+ output_size = temp_size;
}
RandomAccessIterator middle = first;
first += output_size;
@@ -911,6 +919,7 @@
for(size_t i =0; i < output_size; ++i){
result_first[i] = first[i];
}
+ return (result_first + output_size);
}
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
@@ -1033,7 +1042,7 @@
pair<ForwardIterator, ForwardIterator> retval;
retval.first = lower_bound(first, last, value, comp);
//Reuse retval.first in order to (possibly) save a few comparisons
- retval.second = lower_bound(retval.first, last, value, comp);
+ retval.second = upper_bound(retval.first, last, value, comp);
return retval;
}
@@ -1050,7 +1059,7 @@
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp)
{
- if(last - first == 0){
+ if( distance(first, last) == 0){
return false;
}
@@ -1529,7 +1538,7 @@
InputIterator2 first2, InputIterator2 last2)
{
less<typename iterator_traits<InputIterator1>::value_type> c;
- return lexicographical_compare(first1, last1, first2, last2);
+ return lexicographical_compare(first1, last1, first2, last2, c);
}
template<class InputIterator1, class InputIterator2, class Compare>
@@ -1550,10 +1559,141 @@
}
// _lib.alg.permutation.generators_, permutations
- template<class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
- template<class BidirectionalIterator, class Compare> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
- template<class BidirectionalIterator> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
- template<class BidirectionalIterator, class Compare> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
+ template<class BidirectionalIterator>
+ bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
+ {
+ less<typename iterator_traits<BidirectionalIterator>::value_type> c;
+ return next_permutation(first, last, c);
+ }
+
+ template<class BidirectionalIterator, class Compare>
+ bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
+ {
+ if(first == last){
+ return false; // No data
+ }
+ BidirectionalIterator i = last;
+ --i;
+ if(i == first){
+ return false; //Only one element
+ }
+ BidirectionalIterator ii = i;
+ --ii;
+ //If the last two items are in order, swap them and call it done
+ if( comp(*ii, *i) ){
+ iter_swap(ii, i);
+ return true;
+ }
+
+
+/* temp = i;
+ --temp;
+ while( comp(*i, *temp) && first < i){
+ --i;
+ --temp;
+ }
+
+ BidirectionalIterator j = last;
+
+ --j;
+
+ --i;
+ --j;
+ while( comp(*j, *i) && first < j){
+ --j;
+ }
+
+ iter_swap(i, j);
+
+ ++i;
+ ++i;
+
+ j = last;
+
+ --i;
+ while(i < j && first < j && i < last){
+ --j;
+ iter_swap(i, j);
+ ++i;
+ }*/
+
+ //This part of the algorithm copied from G++ header files ver. 3.4.2
+ i = last;
+ --i;
+ for(;;){
+ ii = i;
+ --i;
+ if ( comp(*i, *ii) ){
+ BidirectionalIterator j = last;
+ --j;
+ while ( !comp(*i, *j)){
+ --j;
+ }
+ iter_swap(i, j);
+ reverse(ii, last);
+ return true;
+ }
+ if (i == first){
+ reverse(first, last);
+ return false;
+ }
+ }
+
+
+ }
+
+ template<class BidirectionalIterator>
+ bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)
+ {
+ less<typename iterator_traits<BidirectionalIterator>::value_type> c;
+ return prev_permutation(first, last, c);
+ }
+
+ template<class BidirectionalIterator, class Compare>
+ bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
+ {
+ if(first == last){
+ return false; // No data
+ }
+ BidirectionalIterator i = last;
+ --i;
+ if(i == first){
+ return false; //Only one element
+ }
+ BidirectionalIterator ii = i;
+ --ii;
+ //If the last two items are in reverse order, swap them and call it done
+ if( comp(*i, *ii) ){
+ iter_swap(ii, i);
+ return true;
+ }
+
+ //Copied from GNU GCC header files version 3.4.2
+ i = last;
+ --i;
+
+// BidirectionalIterator ii;
+
+ for(;;){
+ ii = i;
+ --i;
+ if ( comp(*ii, *i)){
+ BidirectionalIterator j = last;
+ --j;
+ while ( !comp(*j, *i)){
+ --j;
+ }
+ iter_swap(i, j);
+ reverse(ii, last);
+ return true;
+ }
+ if (i == first){
+ reverse(first, last);
+ return false;
+ }
+ }
+
+ }
}
--- /var/cvs/uClibc++/include/deque 2004/09/10 04:27:17 1.7
+++ /var/cvs/uClibc++/include/deque 2004/09/17 02:47:50 1.8
@@ -290,7 +290,7 @@
data_size = x.elements + __UCLIBCXX_STL_BUFFER_SIZE__;
data = a.allocate(data_size);
first_element = (data_size - x.elements) / 2;
- last_element = first_element + 1;
+ last_element = first_element;
for(size_type i=0; i < x.elements; ++i){
push_back(x[i]);
}
@@ -560,7 +560,6 @@
erase(typename deque<T, Allocator>::iterator first, typename deque<T, Allocator>::iterator last)
{
//Shift backwards
- printf("First element number: %i\nSecond element number: %i\n", first.element, last.element);
size_type num_move = last.element - first.element;
if( first.element > (elements - last.element) ){
for(size_type i = last.element; i < elements ; ++i){
--- /var/cvs/uClibc++/include/fstream 2004/09/08 14:27:06 1.5
+++ /var/cvs/uClibc++/include/fstream 2004/09/17 02:47:50 1.6
@@ -220,6 +220,16 @@
return traits::not_eof(c);
}
size_t r = basic_streambuf<charT,traits>::pptr() - basic_streambuf<charT,traits>::pbase();
+
+ if( r == 0 && traits::eq_int_type(c,traits::eof()) ){
+ return traits::not_eof(c);
+ }else if (r == 0 ){
+ if(fputc(c, fp) == EOF){
+ return traits::eof();
+ }
+ return c;
+ }
+
size_t s = r;
char_type *buffer = 0;
--- /var/cvs/uClibc++/include/list 2004/09/12 02:20:32 1.4
+++ /var/cvs/uClibc++/include/list 2004/09/17 02:47:50 1.5
@@ -158,7 +158,7 @@
}
T & operator*(){
- return *current->val;
+ return *(current->val);
}
T * operator->(){
return current->val;
@@ -256,12 +256,19 @@
{
list_start = new node();
list_end = list_start;
+
+ iterator i = x.begin();
+ while(i != x.end()){
+ push_back( *i);
+ ++i;
+ }
}
template<class T, class Allocator> list<T, Allocator>::~list(){
while(elements > 0){
pop_front();
}
+ delete list_start->val;
delete list_start;
list_start = 0;
list_end = 0;
@@ -377,6 +384,7 @@
template<class T, class Allocator> void list<T, Allocator>::pop_front(){
if(elements > 0){
list_start = list_start->next;
+ delete list_start->previous->val;
delete list_start->previous;
list_start->previous = 0;
--elements;
@@ -386,8 +394,8 @@
template<class T, class Allocator> void list<T, Allocator>::push_back(const T& x){
if(elements == 0){
//The list is completely empty
- list_end->previous = new node(x);
- list_start = list_end->previous;
+ list_start = new node(x);
+ list_end->previous = list_start;
list_start->previous = 0;
list_start->next = list_end;
elements = 1;
@@ -411,6 +419,7 @@
temp->previous->next = temp->next;
list_end->previous = temp->previous;
}
+ delete temp->val;
delete temp;
--elements;
}
@@ -421,13 +430,13 @@
list<T, Allocator>::insert(iterator position, const T& x)
{
node * temp = new node(x);
- if(list_start == 0 && position == begin()){ //Deal with empty situation
+/* if(list_start == 0 && position == begin()){ //Deal with empty situation
list_start = temp;
list_end = temp;
++elements;
return begin();
}else{
- temp->previous = position.link_struct()->previous;
+*/ temp->previous = position.link_struct()->previous;
temp->next = position.link_struct();
if(position.link_struct()->previous !=0){
position.link_struct()->previous->next = temp;
@@ -436,10 +445,10 @@
++elements;
--position;
return position;
- }
+/* }
//This should never happen
return position;
- }
+*/ }
template<class T, class Allocator> void list<T, Allocator>::insert(iterator position, size_type n, const T& x){
for(typename list<T, Allocator>::size_type i = 0; i < n; ++i){
@@ -458,17 +467,18 @@
template<class T, class Allocator> typename list<T, Allocator>::iterator
list<T, Allocator>::erase(iterator position)
{
- if(position.link_struct() != list_end){
+ if(position != end() ){
node * temp = position.link_struct();
if(temp == list_start){
+ position = end();
temp->next->previous = 0;
list_start = temp->next;
- position = end();
}else{
+ --position;
temp->next->previous = temp->previous;
temp->previous->next = temp->next;
- --position;
}
+ delete temp->val;
delete temp;
--elements;
}
@@ -477,6 +487,7 @@
template<class T, class Allocator> typename list<T, Allocator>::iterator
list<T, Allocator>::erase(iterator position, iterator last)
{
+ iterator temp = position;
while(position !=last){
position = erase(position);
++position;
@@ -574,9 +585,13 @@
return;
}
-
- i.link_struct()->previous->next = i.link_struct()->next;
- i.link_struct()->next->previous = i.link_struct()->previous;
+ if( i.link_struct()->previous != 0){
+ i.link_struct()->previous->next = i.link_struct()->next;
+ i.link_struct()->next->previous = i.link_struct()->previous;
+ }else{
+ i.link_struct()->next->previous = 0;
+ x.list_start = i.link_struct()->next;
+ }
i.link_struct()->previous = position.link_struct()->previous;
position.link_struct()->previous->next = i.link_struct();
@@ -601,7 +616,7 @@
temp = first;
++first;
splice(position, x, temp);
- }
+ }
}
--- /var/cvs/uClibc++/include/map 2004/09/08 14:27:06 1.4
+++ /var/cvs/uClibc++/include/map 2004/09/17 02:47:50 1.5
@@ -495,6 +495,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
@@ -685,6 +686,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
@@ -932,6 +934,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
@@ -1117,6 +1120,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
@@ -1163,10 +1167,21 @@
iterator retval = ifind(x);
+ if(retval == end()){
+ return retval;
+ }
+
if( c(x, retval->first) || c(retval->first, x) ){
return end();
}
+ while( retval.element > 0 && !c(retval->first, x) && !c(x, retval->first) ){
+ --retval;
+ }
+ if( c(retval->first, x)){
+ ++retval;
+ }
+
return retval;
}
@@ -1180,10 +1195,22 @@
}
const_iterator retval = ifind(x);
+ if(retval == end()){
+ return retval;
+ }
+
if( c(x, retval->first) || c(retval->first, x) ){
return end();
}
+ while( retval.element > 0 && !c(retval->first, x) && !c(x, retval->first) ){
+ --retval;
+ }
+ if( c(retval->first, x)){
+ ++retval;
+ }
+
+
return retval;
}
@@ -1205,9 +1232,8 @@
typename multimap<Key, T, Compare, Allocator>::iterator
multimap<Key, T, Compare, Allocator>::lower_bound(const key_type& x)
{
- //FIXME - linear search - can we do any better?
typename multimap<Key, T, Compare, Allocator>::iterator i = find(x);
- if(i == end()){
+/* if(i == end()){
return i;
}
while( i.element > 0 && !c(i->first, x) && !c(x, i->first) ){
@@ -1216,7 +1242,7 @@
if( c(i->first, x)){
++i;
}
- return i;
+*/ return i;
}
template <class Key, class T, class Compare, class Allocator>
@@ -1225,7 +1251,7 @@
{
//FIXME - linear search - can we do any better?
typename multimap<Key, T, Compare, Allocator>::const_iterator i = find(x);
- if(i == end()){
+/* if(i == end()){
return i;
}
while( i.element >0 && !c(i->first, x) && !c(x, i->first) ){
@@ -1234,14 +1260,19 @@
if( c(i->first, x)){
++i;
}
- return i;
+*/ return i;
}
template <class Key, class T, class Compare, class Allocator>
typename multimap<Key, T, Compare, Allocator>::iterator
multimap<Key, T, Compare, Allocator>::upper_bound(const key_type& x)
{
- typename multimap<Key, T, Compare, Allocator>::iterator i = find(x);
+ typename multimap<Key, T, Compare, Allocator>::iterator i = ifind(x);
+
+ if( c(x, i->first) || c(i->first, x) ){
+ return end();
+ }
+
if(i != end()){
++i;
}
@@ -1252,7 +1283,12 @@
typename multimap<Key, T, Compare, Allocator>::const_iterator
multimap<Key, T, Compare, Allocator>::upper_bound(const key_type& x) const
{
- typename multimap<Key, T, Compare, Allocator>::const_iterator i = find(x);
+ typename multimap<Key, T, Compare, Allocator>::const_iterator i = ifind(x);
+
+ if( c(x, i->first) || c(i->first, x) ){
+ return end();
+ }
+
if(i != end()){
++i;
}
--- /var/cvs/uClibc++/include/memory 2004/09/08 14:27:06 1.4
+++ /var/cvs/uClibc++/include/memory 2004/09/17 02:47:51 1.5
@@ -22,6 +22,7 @@
#include <cstdlib>
#include <iterator_base>
#include <utility>
+#include <cstdio>
#ifndef HEADER_STD_MEMORY
#define HEADER_STD_MEMORY 1
--- /var/cvs/uClibc++/include/set 2004/09/08 14:27:06 1.2
+++ /var/cvs/uClibc++/include/set 2004/09/17 02:47:51 1.3
@@ -487,6 +487,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
@@ -662,6 +663,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
@@ -908,6 +910,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
@@ -1093,6 +1096,7 @@
{
while(first !=last){
insert(*first);
+ ++first;
}
}
--- /var/cvs/uClibc++/include/string 2004/09/08 14:27:06 1.5
+++ /var/cvs/uClibc++/include/string 2004/09/17 02:47:51 1.6
@@ -340,8 +340,37 @@
return *this;
}
-// iterator erase(iterator position);
-// iterator erase(iterator first, iterator last);
+ iterator erase(iterator position){
+ if(position == end()){
+ return position;
+ }
+
+ ++position;
+
+ iterator temp = position;
+
+ while(position != end()){
+ *(position-1) = *position;
+ ++position;
+ }
+ --vector<Ch, A>::elements;
+ return temp;
+ }
+
+ iterator erase(iterator first, iterator last){
+ size_t count = last - first;
+
+ iterator temp = last;
+
+ while(last != end()){
+ *(last - count) = *last;
+ ++last;
+ }
+
+ vector<Ch, A>::elements-= count;
+
+ return temp;
+ }
// basic_string& replace(size_type pos1, size_type n1, const basic_string& str);
More information about the uClibc-cvs
mailing list