[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