Topic: STL hacks for GCC 2.6.1
Author: cabo@informatik.uni-bremen.de (Carsten Bormann)
Date: 08 Nov 1994 10:26:40 GMT Raw View
diff -P -c -C 2 ../STL/MEMO ./MEMO
*** ../STL/MEMO Thu Jan 1 01:00:00 1970
--- ./MEMO Tue Nov 8 11:12:01 1994
***************
*** 0 ****
--- 1,62 ----
+ This is a set of seriously bletcherous hacks to HP's wonderful STL
+ library. The objective is to hammer STL through GCC 2.6.1 (2.6.0
+ seems to work, too, until you run into one of its bugs) so that us
+ academic types can play with STL, not to make STL better in any way.
+
+ You need to have the STL release from butler.hpl.hp.com:stl/sharfile.Z
+ that has as its first line in the read.me:
+
+ >> This release (dated October 21, 1994) is a minor bug fix release. <<
+
+ Many of these changes make the library much less efficient. All
+ changes (except vector<bool> -- see below) are due to bugs (or
+ non-features) in GCC, not due to any problems in STL. Do not judge
+ the performance of STL (code space, data space, compile time
+ complexity, run time complexity) from these hacks -- they will be much
+ better when GCC implements more of Standard C++. May the authors of
+ STL forgive me.
+
+ The class templates generally have been hacked in the following ways:
+
+ 1) Static data members have been eliminated, generally by making them
+ non-static members or member functions (both of which generally
+ seriously impairs performance -- e.g., each rb_tree iterator now
+ carries a copy of NIL since there is no other place to put it). The
+ template list<> has suffered most.
+
+ Allocators are still static members, since I changed defalloc.h to
+ have static members only. (This makes allocators less useful, but
+ still useable.) (Note that a static member without data need not be
+ initialized.)
+
+ 2) For member functions defined outside the class template, parameters
+ of type tmpl<T>::something have been changed. In some cases, a class
+ derived from the type has been used; in some cases the function simply
+ has been made inline (again causing code bloat).
+
+ 3) A number of function templates in iterator.h have been declared
+ again for derived classes defined by templates, usually by making them
+ friend functions and using the name injection feature of GCC. I don't
+ understand the relevant sections of the WP, so I don't know if this
+ hack will cease to work in more conforming versions of GCC or become
+ unneccessary or simply STL won't work with standard C++. Some of
+ the necessary friends may still be missing...
+
+ defalloc.h has lost much of its functionality: see above.
+
+ bool.h has been made ineffective, since GCC supports bool.
+
+ Finally, bit_vector has been changed into a proper specialization of
+ vector<bool>.
+
+ demo.cc and Makefile build a small demo program for a number of
+ features of STL. This is not a test suite, so I certainly have not
+ found all my mistakes (could anyone in possession of such a test suite
+ please run it over these hacks?). Send bug reports (that follow GNU
+ bug reporting conventions) to
+
+ cabo@informatik.uni-bremen.de
+
+ Note that I generally do not have time to answer questions about STL.
+
+ Carsten Bormann
diff -P -c -C 2 ../STL/Makefile ./Makefile
*** ../STL/Makefile Thu Jan 1 01:00:00 1970
--- ./Makefile Thu Nov 3 18:00:05 1994
***************
*** 0 ****
--- 1,16 ----
+ LINK.o = $(LINK.cc)
+ CPPFLAGS=-I.
+ CXXFLAGS=-g
+ LDLIBS =
+
+ SRCS=$(wildcard *.cc)
+ CSRCS=$(wildcard *.c)
+
+ demo: $(SRCS:%.cc=%.o) $(CSRCS:%.c=%.o)
+
+ %.d: %.cc
+ echo '$@ \c'> $@.new
+ g++ $(CPPFLAGS) -M $< >>$@.new
+ mv $@.new $@
+
+ include $(SRCS:%.cc=%.d)
diff -P -c -C 2 ../STL/bool.h ./bool.h
*** ../STL/bool.h Wed Nov 2 20:11:08 1994
--- ./bool.h Tue Nov 8 09:50:57 1994
***************
*** 14,18 ****
*/
! #define bool int
! #define true 1
! #define false 0
--- 14,20 ----
*/
! // Not needed for GCC 2.6.x:
!
! // #define bool int
! // #define true 1
! // #define false 0
diff -P -c -C 2 ../STL/bvector.h ./bvector.h
*** ../STL/bvector.h Wed Nov 2 20:11:08 1994
--- ./bvector.h Tue Nov 8 10:17:04 1994
***************
*** 30,36 ****
#endif
#define __WORD_BIT (int(CHAR_BIT*sizeof(unsigned int)))
! class bit_vector {
public:
typedef Allocator<unsigned int> vector_allocator;
--- 30,42 ----
#endif
+ // We can do a specialization with GCC, so lets do it the right way.
+ // Maintain minimum patch...
+ #include <vector.h>
+ class vector<bool>;
+ typedef vector<bool> bit_vector;
+
#define __WORD_BIT (int(CHAR_BIT*sizeof(unsigned int)))
! class vector<bool> {
public:
typedef Allocator<unsigned int> vector_allocator;
***************
*** 268,281 ****
reference operator[](size_type n) { return *(begin() + n); }
const_reference operator[](size_type n) const { return *(begin() + n); }
! bit_vector() : start(iterator()), finish(iterator()), end_of_storage(0) {}
! bit_vector(size_type n, bool value = bool()) {
initialize(n);
fill(start.p, end_of_storage, value ? ~0 : 0);
}
! bit_vector(const self& x) {
initialize(x.size());
copy(x.begin(), x.end(), start);
}
! bit_vector(const_iterator first, const_iterator last) {
size_type n = 0;
distance(first, last, n);
--- 274,287 ----
reference operator[](size_type n) { return *(begin() + n); }
const_reference operator[](size_type n) const { return *(begin() + n); }
! vector() : start(iterator()), finish(iterator()), end_of_storage(0) {}
! vector(size_type n, bool value = bool()) {
initialize(n);
fill(start.p, end_of_storage, value ? ~0 : 0);
}
! vector(const self& x) {
initialize(x.size());
copy(x.begin(), x.end(), start);
}
! vector(const_iterator first, const_iterator last) {
size_type n = 0;
distance(first, last, n);
***************
*** 283,287 ****
copy(first, last, start);
}
! ~bit_vector() { static_allocator.deallocate(start.p); }
self& operator=(const self& x) {
if (&x == this) return *this;
--- 289,293 ----
copy(first, last, start);
}
! ~vector() { static_allocator.deallocate(start.p); }
self& operator=(const self& x) {
if (&x == this) return *this;
***************
*** 338,344 ****
finish = copy(last, end(), first);
}
};
! Allocator<unsigned int> bit_vector::static_allocator;
inline bool operator==(const bit_vector& x, const bit_vector& y) {
--- 344,368 ----
finish = copy(last, end(), first);
}
+ friend random_access_iterator_tag iterator_category(iterator) {
+ return random_access_iterator_tag();
+ }
+ friend difference_type* distance_type(const iterator&) {
+ return (difference_type*)(0);
+ }
+ friend bool* value_type(const iterator&) {
+ return (bool*)(0);
+ }
+ friend random_access_iterator_tag iterator_category(const_iterator) {
+ return random_access_iterator_tag();
+ }
+ friend difference_type* distance_type(const const_iterator&) {
+ return (difference_type*)(0);
+ }
+ friend bool* value_type(const const_iterator&) {
+ return (bool*)(0);
+ }
};
! // Allocator<unsigned int> bit_vector::static_allocator;
inline bool operator==(const bit_vector& x, const bit_vector& y) {
diff -P -c -C 2 ../STL/defalloc.h ./defalloc.h
*** ../STL/defalloc.h Tue Nov 8 11:14:30 1994
--- ./defalloc.h Thu Nov 3 18:31:01 1994
***************
*** 24,28 ****
#include <algobase.h>
! inline void* operator new(size_t, void* p) {return p;}
/*
--- 24,29 ----
#include <algobase.h>
! // This is already part of the GNU library...
! // inline void* operator new(size_t, void* p) {return p;}
/*
***************
*** 132,147 ****
typedef size_t size_type;
typedef ptrdiff_t difference_type;
! pointer allocate(size_type n) {
return ::allocate((difference_type)n, (pointer)0);
}
! void deallocate(pointer p) { ::deallocate(p); }
! pointer address(reference x) { return (pointer)&x; }
! const_pointer const_address(const_reference x) {
return (const_pointer)&x;
}
! size_type init_page_size() {
return max(size_type(1), size_type(4096/sizeof(T)));
}
! size_type max_size() const {
return max(size_type(1), size_type(UINT_MAX/sizeof(T)));
}
--- 133,148 ----
typedef size_t size_type;
typedef ptrdiff_t difference_type;
! static pointer allocate(size_type n) {
return ::allocate((difference_type)n, (pointer)0);
}
! static void deallocate(pointer p) { ::deallocate(p); }
! static pointer address(reference x) { return (pointer)&x; }
! static const_pointer const_address(const_reference x) {
return (const_pointer)&x;
}
! static size_type init_page_size() {
return max(size_type(1), size_type(4096/sizeof(T)));
}
! static size_type max_size() {
return max(size_type(1), size_type(UINT_MAX/sizeof(T)));
}
diff -P -c -C 2 ../STL/demo.cc ./demo.cc
*** ../STL/demo.cc Thu Jan 1 01:00:00 1970
--- ./demo.cc Tue Nov 8 10:49:02 1994
***************
*** 0 ****
--- 1,144 ----
+ #include <iostream.h>
+ #include <algo.h>
+ #include <deque.h>
+ #include <list.h>
+ #include <vector.h>
+ #include <set.h>
+ #include <map.h>
+ #include <stack.h>
+ #include <bvector.h>
+ #include <multiset.h>
+ #include <multimap.h>
+
+ template<class T>
+ struct odd: unary_function<T, bool> {
+ bool operator()(const T& x) const {
+ return x & 1;
+ }
+ };
+
+ template<class T>
+ struct bit_and: binary_function<T, T, T> {
+ T operator()(const T& x, const T& y) const {
+ return x & y;
+ }
+ };
+
+
+ int main() {
+ int i;
+ #if 0
+ copy(istream_iterator<char, ptrdiff_t>(cin),
+ istream_iterator<char, ptrdiff_t>(),
+ ostream_iterator<char>(cout));
+ #endif // geht
+
+ cout << "Testing front_inserter(deque<char>):" << endl;
+
+
+ deque<char> d;
+ copy(istream_iterator<char, ptrdiff_t>(cin),
+ istream_iterator<char, ptrdiff_t>(),
+ front_inserter(d));
+ copy(d.begin(), d.end(), ostream_iterator<char>(cout));
+ cout << endl;
+
+ cout << "Testing set<char>:" << endl;
+
+ set<char, less<char> > sc;
+ for (deque<char>::iterator di = d.begin(); di != d.end(); ++di)
+ sc.insert(*di);
+ copy(sc.begin(), sc.end(), ostream_iterator<char>(cout));
+ cout << endl;
+
+ cout << "Testing multiset<char>:" << endl;
+
+ multiset<char, less<char> > msc;
+ for (di = d.begin(); di != d.end(); di++)
+ msc.insert(*di);
+ copy(msc.begin(), msc.end(), ostream_iterator<char>(cout));
+ cout << endl;
+
+ cout << "Testing map<char, int>:" << endl;
+
+ map<char, int, less<char> > mci;
+ di = d.begin();
+ while (di != d.end())
+ mci[*di++]++;
+ for (map<char, int, less<char> >::iterator mi = mci.begin(); mi != mci.end(); ++mi)
+ cout << (*mi).first << "*" << (*mi).second << " ";
+ cout << endl;
+
+ cout << "Testing multimap<char, int>:" << endl;
+
+ multimap<char, int, less<char> > mmci;
+ for (di = d.begin(), i = 0; di != d.end(); ++di, ++i)
+ mmci.insert(pair<const char,int>(*di, i));
+ // can't use make_pair -- STL definition problem?
+ for (multimap<char, int, less<char> >::iterator mmi = mmci.begin(); mmi != mmci.end(); ++mmi)
+ cout << (*mmi).first << "*" << (*mmi).second << " ";
+ cout << endl;
+
+ cout << "Testing stack<vector<char> >:" << endl;
+
+ stack<vector<char> > st;
+ for (di = d.begin(); di != d.end(); di++)
+ st.push(*di);
+ while (!st.empty()) {
+ cout << st.top();
+ st.pop();
+ }
+ cout << endl;
+
+ cout << "Testing queue<deque<char> >:" << endl;
+
+ queue<deque<char> > qu;
+ for (di = d.begin(); di != d.end(); di++)
+ qu.push(*di);
+ while (!st.empty()) {
+ cout << qu.front();
+ qu.pop();
+ }
+ cout << endl;
+
+ cout << "Testing vector<bool>:" << endl;
+
+ vector<bool> bv(256);
+ for (di = d.begin(); di != d.end(); di++)
+ bv[(unsigned char)*di] = true;
+ for (i = 0; i < 256; i++) {
+ if (bv[i]) cout << char(i);
+ }
+ cout << endl;
+
+ cout << "Testing sort(deque<char>):" << endl;
+
+ sort(d.begin(), d.end());
+ copy(d.begin(), d.end(), ostream_iterator<char>(cout));
+ cout << endl;
+
+
+ cout << "Testing stable_partition(list<char>):" << endl;
+
+ list<char> v;
+ copy(d.begin(), d.end(), back_inserter(v));
+ list<char>::iterator p =
+ stable_partition(v.begin(), v.end(), bind2nd(modulus<char>(),2));
+
+ copy(v.begin(), p, ostream_iterator<char>(cout));
+ cout << endl;
+ copy(p, v.end(), ostream_iterator<char>(cout));
+ cout << endl;
+
+ cout << "Testing stable_partition(vector<char>):" << endl;
+
+ vector<char> vec;
+ copy(d.begin(), d.end(), back_inserter(vec));
+ vector<char>::iterator pv =
+ stable_partition(vec.begin(), vec.end(), bind2nd(modulus<char>(),2));
+
+ copy(vec.begin(), pv, ostream_iterator<char>(cout));
+ cout << endl;
+ copy(pv, vec.end(), ostream_iterator<char>(cout));
+ cout << endl;
+ }
diff -P -c -C 2 ../STL/deque.h ./deque.h
*** ../STL/deque.h Wed Nov 2 20:11:09 1994
--- ./deque.h Fri Nov 4 10:22:04 1994
***************
*** 1,3 ****
! /*
*
* Copyright (c) 1994
--- 1,3 ----
! /* -*- C++ -*-
*
* Copyright (c) 1994
***************
*** 49,53 ****
protected:
static data_allocator_type data_allocator;
! static size_type buffer_size;
static map_allocator_type map_allocator;
typedef Allocator<pointer>::pointer map_pointer;
--- 49,56 ----
protected:
static data_allocator_type data_allocator;
! // static // Too bad -- I don't like this hack very much...
! static size_type buffer_size() {
! return data_allocator.init_page_size();
! }
static map_allocator_type map_allocator;
typedef Allocator<pointer>::pointer map_pointer;
***************
*** 62,66 ****
map_pointer node;
iterator(pointer x, map_pointer y)
! : current(x), first(*y), last(*y + buffer_size), node(y) {}
public:
iterator() : current(0), first(0), last(0), node(0) {}
--- 65,69 ----
map_pointer node;
iterator(pointer x, map_pointer y)
! : current(x), first(*y), last(*y + buffer_size()), node(y) {}
public:
iterator() : current(0), first(0), last(0), node(0) {}
***************
*** 69,73 ****
return node == x.node
? current - x.current
! : difference_type(buffer_size * (node - x.node - 1) +
(current - first) + (x.last - x.current));
}
--- 72,76 ----
return node == x.node
? current - x.current
! : difference_type(buffer_size() * (node - x.node - 1) +
(current - first) + (x.last - x.current));
}
***************
*** 76,80 ****
first = *(++node);
current = first;
! last = first + buffer_size;
}
return *this;
--- 79,83 ----
first = *(++node);
current = first;
! last = first + buffer_size();
}
return *this;
***************
*** 88,92 ****
if (current == first) {
first = *(--node);
! last = first + buffer_size;
current = last;
}
--- 91,95 ----
if (current == first) {
first = *(--node);
! last = first + buffer_size();
current = last;
}
***************
*** 102,107 ****
difference_type offset = n + (current - first);
difference_type num_node_to_jump = offset >= 0
! ? offset / buffer_size
! : -((-offset + buffer_size - 1) / buffer_size);
if (num_node_to_jump == 0)
current += n;
--- 105,110 ----
difference_type offset = n + (current - first);
difference_type num_node_to_jump = offset >= 0
! ? offset / buffer_size()
! : -((-offset + buffer_size() - 1) / buffer_size());
if (num_node_to_jump == 0)
current += n;
***************
*** 109,114 ****
node = node + num_node_to_jump;
first = *node;
! last = first + buffer_size;
! current = first + (offset - num_node_to_jump * buffer_size);
}
return *this;
--- 112,117 ----
node = node + num_node_to_jump;
first = *node;
! last = first + buffer_size();
! current = first + (offset - num_node_to_jump * buffer_size());
}
return *this;
***************
*** 141,145 ****
map_pointer node;
const_iterator(pointer x, map_pointer y)
! : current(x), first(*y), last(*y + buffer_size), node(y) {}
public:
const_iterator() : current(0), first(0), last(0), node(0) {}
--- 144,148 ----
map_pointer node;
const_iterator(pointer x, map_pointer y)
! : current(x), first(*y), last(*y + buffer_size()), node(y) {}
public:
const_iterator() : current(0), first(0), last(0), node(0) {}
***************
*** 150,154 ****
return node == x.node
? current - x.current
! : difference_type(buffer_size * (node - x.node - 1) +
(current - first) + (x.last - x.current));
}
--- 153,157 ----
return node == x.node
? current - x.current
! : difference_type(buffer_size() * (node - x.node - 1) +
(current - first) + (x.last - x.current));
}
***************
*** 157,161 ****
first = *(++node);
current = first;
! last = first + buffer_size;
}
return *this;
--- 160,164 ----
first = *(++node);
current = first;
! last = first + buffer_size();
}
return *this;
***************
*** 169,173 ****
if (current == first) {
first = *(--node);
! last = first + buffer_size;
current = last;
}
--- 172,176 ----
if (current == first) {
first = *(--node);
! last = first + buffer_size();
current = last;
}
***************
*** 183,188 ****
difference_type offset = n + (current - first);
difference_type num_node_to_jump = offset >= 0
! ? offset / buffer_size
! : -((-offset + buffer_size - 1) / buffer_size);
if (num_node_to_jump == 0)
current += n;
--- 186,191 ----
difference_type offset = n + (current - first);
difference_type num_node_to_jump = offset >= 0
! ? offset / buffer_size()
! : -((-offset + buffer_size() - 1) / buffer_size());
if (num_node_to_jump == 0)
current += n;
***************
*** 190,195 ****
node = node + num_node_to_jump;
first = *node;
! last = first + buffer_size;
! current = first + (offset - num_node_to_jump * buffer_size);
}
return *this;
--- 193,198 ----
node = node + num_node_to_jump;
first = *node;
! last = first + buffer_size();
! current = first + (offset - num_node_to_jump * buffer_size());
}
return *this;
***************
*** 234,238 ****
public:
deque() : start(), finish(), length(0), map(0), map_size(0) {
! buffer_size = data_allocator.init_page_size();
}
iterator begin() { return start; }
--- 237,241 ----
public:
deque() : start(), finish(), length(0), map(0), map_size(0) {
! // buffer_size = data_allocator.init_page_size();
}
iterator begin() { return start; }
***************
*** 292,305 ****
::swap(map_size, x.map_size);
}
! iterator insert(iterator position, const T& x);
! void insert(iterator position, size_type n, const T& x);
// template <class Iterator> void insert(iterator position,
// Iterator first, Iterator last);
! void insert(iterator position, const T* first, const T* last);
! void erase(iterator position);
! void erase(iterator first, iterator last);
deque(size_type n, const T& value = T())
: start(), finish(), length(0), map(0), map_size(0) {
! buffer_size = data_allocator.init_page_size();
insert(begin(), n, value);
}
--- 295,323 ----
::swap(map_size, x.map_size);
}
! iterator insert(iterator position, const T& x) {
! return insert(deque_iterator<T>(position), x);
! }
! deque_iterator<T> insert(deque_iterator<T> position, const T& x);
! void insert(iterator position, size_type n, const T& x) {
! insert(deque_iterator<T>(position), n, x);
! }
! void insert(deque_iterator<T>(position), size_type n, const T& x);
// template <class Iterator> void insert(iterator position,
// Iterator first, Iterator last);
! void insert(iterator position, const T* first, const T* last) {
! insert(deque_iterator<T>(position), first, last);
! }
! void insert(deque_iterator<T> position, const T* first, const T* last);
! void erase(iterator position) {
! erase(deque_iterator<T>(position));
! }
! void erase(deque_iterator<T> position);
! void erase(iterator first, iterator last) {
! erase(deque_iterator<T>(first), deque_iterator<T>(last));
! }
! void erase(deque_iterator<T> first, deque_iterator<T> last);
deque(size_type n, const T& value = T())
: start(), finish(), length(0), map(0), map_size(0) {
! // buffer_size = data_allocator.init_page_size();
insert(begin(), n, value);
}
***************
*** 307,316 ****
deque(const T* first, const T* last)
: start(), finish(), length(0), map(0), map_size(0) {
! buffer_size = data_allocator.init_page_size();
copy(first, last, back_inserter(*this));
}
deque(const deque<T>& x)
: start(), finish(), length(0), map(0), map_size(0) {
! buffer_size = data_allocator.init_page_size();
copy(x.begin(), x.end(), back_inserter(*this));
}
--- 325,334 ----
deque(const T* first, const T* last)
: start(), finish(), length(0), map(0), map_size(0) {
! // buffer_size = data_allocator.init_page_size();
copy(first, last, back_inserter(*this));
}
deque(const deque<T>& x)
: start(), finish(), length(0), map(0), map_size(0) {
! // buffer_size = data_allocator.init_page_size();
copy(x.begin(), x.end(), back_inserter(*this));
}
***************
*** 326,339 ****
}
~deque();
};
! template <class T>
! deque<T>::data_allocator_type deque<T>::data_allocator;
template <class T>
! deque<T>::map_allocator_type deque<T>::map_allocator;
template <class T>
! deque<T>::size_type deque<T>::buffer_size = 0;
// should be data_allocator.init_page_size(); // Borland bug
--- 344,373 ----
}
~deque();
+ //GCC...
+ friend T* value_type(const iterator&) {
+ return (T*)(0);
+ }
};
! // Hack for GCC
template <class T>
! struct deque_iterator: deque<T>::iterator {
! deque_iterator(deque<T>::iterator i) : deque<T>::iterator(i) {}
! };
template <class T>
! inline T* value_type(const deque_iterator<T>&) {
! return (T*)(0);
! }
!
! // template <class T>
! // deque<T>::data_allocator_type deque<T>::data_allocator;
!
! // template <class T>
! // deque<T>::map_allocator_type deque<T>::map_allocator;
!
! // template <class T>
! // deque<T>::size_type deque<T>::buffer_size = 0;
// should be data_allocator.init_page_size(); // Borland bug
***************
*** 353,377 ****
template <class T>
void deque<T>::allocate_at_begin() {
! pointer p = data_allocator.allocate(buffer_size);
if (!empty()) {
if (start.node == map) {
difference_type i = finish.node - start.node;
map_size = (i + 1) * 2;
! map_pointer tmp = map_allocator.allocate(map_size);
copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
! map_allocator.deallocate(map);
map = tmp;
map[map_size / 4] = p;
! start = iterator(p + buffer_size, map + map_size / 4);
finish = iterator(finish.current, map + map_size / 4 + i + 1);
} else {
*--start.node = p;
! start = iterator(p + buffer_size, start.node);
}
} else {
! map_size = map_allocator.init_page_size();
! map = map_allocator.allocate(map_size);
map[map_size / 2] = p;
! start = iterator(p + buffer_size / 2 + 1, map + map_size / 2);
finish = start;
}
--- 387,411 ----
template <class T>
void deque<T>::allocate_at_begin() {
! pointer p = data_allocator.allocate(buffer_size());
if (!empty()) {
if (start.node == map) {
difference_type i = finish.node - start.node;
map_size = (i + 1) * 2;
! map_pointer tmp = map_allocator_type::allocate(map_size);
copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
! map_allocator_type::deallocate(map);
map = tmp;
map[map_size / 4] = p;
! start = iterator(p + buffer_size(), map + map_size / 4);
finish = iterator(finish.current, map + map_size / 4 + i + 1);
} else {
*--start.node = p;
! start = iterator(p + buffer_size(), start.node);
}
} else {
! map_size = map_allocator_type::init_page_size();
! map = map_allocator_type::allocate(map_size);
map[map_size / 2] = p;
! start = iterator(p + buffer_size() / 2 + 1, map + map_size / 2);
finish = start;
}
***************
*** 380,391 ****
template <class T>
void deque<T>::allocate_at_end() {
! pointer p = data_allocator.allocate(buffer_size);
if (!empty()) {
if (finish.node == map + map_size - 1) {
difference_type i = finish.node - start.node;
map_size = (i + 1) * 2;
! map_pointer tmp = map_allocator.allocate(map_size);
copy(start.node, finish.node + 1, tmp + map_size / 4);
! map_allocator.deallocate(map);
map = tmp;
map[map_size / 4 + i + 1] = p;
--- 414,425 ----
template <class T>
void deque<T>::allocate_at_end() {
! pointer p = data_allocator.allocate(buffer_size());
if (!empty()) {
if (finish.node == map + map_size - 1) {
difference_type i = finish.node - start.node;
map_size = (i + 1) * 2;
! map_pointer tmp = map_allocator_type::allocate(map_size);
copy(start.node, finish.node + 1, tmp + map_size / 4);
! map_allocator_type::deallocate(map);
map = tmp;
map[map_size / 4 + i + 1] = p;
***************
*** 397,404 ****
}
} else {
! map_size = map_allocator.init_page_size();
! map = map_allocator.allocate(map_size);
map[map_size / 2] = p;
! start = iterator(p + buffer_size / 2, map + map_size / 2);
finish = start;
}
--- 431,438 ----
}
} else {
! map_size = map_allocator_type::init_page_size();
! map = map_allocator_type::allocate(map_size);
map[map_size / 2] = p;
! start = iterator(p + buffer_size() / 2, map + map_size / 2);
finish = start;
}
***************
*** 411,415 ****
start = iterator();
finish = start;
! map_allocator.deallocate(map);
} else
start = iterator(*start.node, start.node);
--- 445,449 ----
start = iterator();
finish = start;
! map_allocator_type::deallocate(map);
} else
start = iterator(*start.node, start.node);
***************
*** 422,432 ****
start = iterator();
finish = start;
! map_allocator.deallocate(map);
} else
! finish = iterator(*finish.node + buffer_size, finish.node);
}
template <class T>
! deque<T>::iterator deque<T>::insert(iterator position, const T& x) {
if (position == begin()) {
push_front(x);
--- 456,468 ----
start = iterator();
finish = start;
! map_allocator_type::deallocate(map);
} else
! finish = iterator(*finish.node + buffer_size(), finish.node);
}
template <class T>
! deque_iterator<T>
! deque<T>::insert(deque_iterator<T> posn, const T& x) {
! iterator position = posn;
if (position == begin()) {
push_front(x);
***************
*** 449,453 ****
template <class T>
! void deque<T>::insert(iterator position, size_type n, const T& x) {
if (end() - position > position - begin()) {
iterator old_begin = begin();
--- 485,492 ----
template <class T>
! void deque<T>::insert(deque_iterator<T> posn,
! size_t n, // BAD HACK
! const T& x) {
! iterator position = posn;
if (end() - position > position - begin()) {
iterator old_begin = begin();
***************
*** 482,486 ****
template <class T>
! void deque<T>::insert(iterator position, const T* first, const T* last) {
size_type n = 0;
distance(first, last, n);
--- 521,526 ----
template <class T>
! void deque<T>::insert(deque_iterator<T> posn, const T* first, const T* last) {
! iterator position = posn;
size_type n = 0;
distance(first, last, n);
***************
*** 517,521 ****
template <class T>
! void deque<T>::erase(iterator position) {
if (end() - position > position - begin()) {
copy_backward(begin(), position, position + 1);
--- 557,562 ----
template <class T>
! void deque<T>::erase(deque_iterator<T> posn) {
! iterator position = posn;
if (end() - position > position - begin()) {
copy_backward(begin(), position, position + 1);
***************
*** 528,533 ****
template <class T>
! void deque<T>::erase(iterator first, iterator last) {
! difference_type n = last - first;
if (end() - last > first - begin()) {
copy_backward(begin(), first, last);
--- 569,576 ----
template <class T>
! void deque<T>::erase(deque_iterator<T> fi, deque_iterator<T> la) {
! iterator first = fi;
! iterator last = la;
! difference_type n = last - first;
if (end() - last > first - begin()) {
copy_backward(begin(), first, last);
Only in ../STL: doc.ps
Only in ../STL: docbar.ps
Only in ../STL: faralloc.h
Only in ../STL: fdeque.h
Only in ../STL: flist.h
Only in ../STL: fmap.h
Only in ../STL: fmultmap.h
Only in ../STL: fmultset.h
Only in ../STL: fset.h
Only in ../STL: hdeque.h
Only in ../STL: hlist.h
Only in ../STL: hmap.h
Only in ../STL: hmultmap.h
Only in ../STL: hmultset.h
Only in ../STL: hset.h
Only in ../STL: hugalloc.h
Only in ../STL: hvector.h
Only in ../STL: lbvector.h
Only in ../STL: ldeque.h
diff -P -c -C 2 ../STL/list.h ./list.h
*** ../STL/list.h Wed Nov 2 20:11:20 1994
--- ./list.h Fri Nov 4 21:39:39 1994
***************
*** 1,3 ****
! /*
*
* Copyright (c) 1994
--- 1,3 ----
! /* -*- C++ -*-
*
* Copyright (c) 1994
***************
*** 69,76 ****
protected:
static Allocator<list_node_buffer> buffer_allocator;
! static buffer_pointer buffer_list;
! static link_type free_list;
! static link_type next_avail;
! static link_type last;
void add_new_buffer() {
buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
--- 69,80 ----
protected:
static Allocator<list_node_buffer> buffer_allocator;
! //static
! buffer_pointer buffer_list;
! //static
! link_type free_list;
! //static
! link_type next_avail;
! //static
! link_type last;
void add_new_buffer() {
buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
***************
*** 81,85 ****
last = next_avail + buffer_size();
}
! static size_type number_of_lists;
void deallocate_buffers();
link_type get_node() {
--- 85,91 ----
last = next_avail + buffer_size();
}
! //static
! size_type number_of_lists;
! #define STUPID_LIST_FIX ,buffer_list(0),free_list(0),next_avail(0),last(0),number_of_lists(0)
void deallocate_buffers();
link_type get_node() {
***************
*** 166,170 ****
difference_type>
reverse_iterator;
! list() : length(0) {
++number_of_lists;
node = get_node();
--- 172,176 ----
difference_type>
reverse_iterator;
! list() : length(0) STUPID_LIST_FIX {
++number_of_lists;
node = get_node();
***************
*** 205,212 ****
return tmp;
}
! void insert(iterator position, const T* first, const T* last);
void insert(iterator position, const_iterator first,
! const_iterator last);
! void insert(iterator position, size_type n, const T& x);
void push_front(const T& x) { insert(begin(), x); }
void push_back(const T& x) { insert(end(), x); }
--- 211,224 ----
return tmp;
}
! void insert(iterator position, const T* first, const T* last) {
! while (first != last) insert(position, *first++);
! }
void insert(iterator position, const_iterator first,
! const_iterator last) {
! while (first != last) insert(position, *first++);
! }
! void insert(iterator position, size_type n, const T& x) {
! while (n--) insert(position, x);
! }
void push_front(const T& x) { insert(begin(), x); }
void push_back(const T& x) { insert(end(), x); }
***************
*** 218,222 ****
--length;
}
! void erase(iterator first, iterator last);
void pop_front() { erase(begin()); }
void pop_back() {
--- 230,236 ----
--length;
}
! void erase(iterator first, iterator last) {
! while (first != last) erase(first++);
! }
void pop_front() { erase(begin()); }
void pop_back() {
***************
*** 224,228 ****
erase(--tmp);
}
! list(size_type n, const T& value = T()) : length(0) {
++number_of_lists;
node = get_node();
--- 238,242 ----
erase(--tmp);
}
! list(size_type n, const T& value = T()) : length(0) STUPID_LIST_FIX {
++number_of_lists;
node = get_node();
***************
*** 231,235 ****
insert(begin(), n, value);
}
! list(const T* first, const T* last) : length(0) {
++number_of_lists;
node = get_node();
--- 245,249 ----
insert(begin(), n, value);
}
! list(const T* first, const T* last) : length(0) STUPID_LIST_FIX {
++number_of_lists;
node = get_node();
***************
*** 238,242 ****
insert(begin(), first, last);
}
! list(const list<T>& x) : length(0) {
++number_of_lists;
node = get_node();
--- 252,256 ----
insert(begin(), first, last);
}
! list(const list<T>& x) : length(0) STUPID_LIST_FIX {
++number_of_lists;
node = get_node();
***************
*** 245,248 ****
--- 259,263 ----
insert(begin(), x.begin(), x.end());
}
+ #undef STUPID_LIST_FIX
~list() {
erase(begin(), end());
***************
*** 291,319 ****
void reverse();
void sort();
};
! template <class T>
! list<T>::buffer_pointer list<T>::buffer_list = 0;
! template <class T>
! list<T>::link_type list<T>::free_list = 0;
! template <class T>
! list<T>::link_type list<T>::next_avail = 0;
! template <class T>
! list<T>::link_type list<T>::last = 0;
! template <class T>
! list<T>::size_type list<T>::number_of_lists = 0;
! template <class T>
! list<T>::list_node_allocator_type list<T>::list_node_allocator;
! template <class T>
! list<T>::value_allocator_type list<T>::value_allocator;
! template <class T>
! list<T>::buffer_allocator_type list<T>::buffer_allocator;
/*
--- 306,344 ----
void reverse();
void sort();
+ // GCC...
+ friend difference_type* distance_type(const iterator&) {
+ return (difference_type*)(0);
+ }
+ friend T* value_type(const iterator&) {
+ return (T*)(0);
+ }
+ friend bidirectional_iterator_tag iterator_category(iterator) {
+ return bidirectional_iterator_tag();
+ }
};
! //template <class T>
! //list<T>::buffer_pointer list<T>::buffer_list = 0;
! //template <class T>
! //list<T>::link_type list<T>::free_list = 0;
! //template <class T>
! //list<T>::link_type list<T>::next_avail = 0;
! //template <class T>
! //list<T>::link_type list<T>::last = 0;
! //template <class T>
! //list<T>::size_type list<T>::number_of_lists = 0;
! //template <class T>
! //list<T>::list_node_allocator_type list<T>::list_node_allocator;
! //template <class T>
! //list<T>::value_allocator_type list<T>::value_allocator;
! //template <class T>
! //list<T>::buffer_allocator_type list<T>::buffer_allocator;
/*
***************
*** 347,371 ****
next_avail = 0;
last = 0;
- }
-
- template <class T>
- void list<T>::insert(iterator position, const T* first, const T* last) {
- while (first != last) insert(position, *first++);
- }
-
- template <class T>
- void list<T>::insert(iterator position, const_iterator first,
- const_iterator last) {
- while (first != last) insert(position, *first++);
- }
-
- template <class T>
- void list<T>::insert(iterator position, size_type n, const T& x) {
- while (n--) insert(position, x);
- }
-
- template <class T>
- void list<T>::erase(iterator first, iterator last) {
- while (first != last) erase(first++);
}
--- 372,375 ----
Only in ../STL: llist.h
Only in ../STL: lmap.h
Only in ../STL: lmultmap.h
Only in ../STL: lmultset.h
Only in ../STL: lngalloc.h
Only in ../STL: lset.h
Only in ../STL: neralloc.h
Only in ../STL: nmap.h
Only in ../STL: nmultmap.h
Only in ../STL: nmultset.h
Only in ../STL: nset.h
diff -P -c -C 2 ../STL/random.cc ./random.cc
*** ../STL/random.cc Thu Jan 1 01:00:00 1970
--- ./random.cc Thu Nov 3 17:01:09 1994
***************
*** 0 ****
--- 1,60 ----
+ /*
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Hewlett-Packard Company makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ *
+ */
+
+ #include <stddef.h>
+
+ #define __SEED 161803398
+
+ class __random_generator {
+ protected:
+ unsigned long table[55];
+ size_t index1;
+ size_t index2;
+ public:
+ unsigned long operator()(unsigned long limit) {
+ index1 = (index1 + 1) % 55;
+ index2 = (index2 + 1) % 55;
+ table[index1] = table[index1] - table[index2];
+ return table[index1] % limit;
+ }
+ void seed(unsigned long j);
+ __random_generator(unsigned long j) { seed(j); }
+ };
+
+ void __random_generator::seed(unsigned long j) {
+ unsigned long k = 1;
+ table[54] = j;
+ for (size_t i = 0; i < 55; i++) {
+ size_t ii = 21 * i % 55;
+ table[ii] = k;
+ k = j - k;
+ j = table[ii];
+ }
+ for (int loop = 0; loop < 4; loop++) {
+ for (i = 0; i < 55; i++)
+ table[i] = table[i] - table[1 + (i + 30) % 55];
+ }
+ index1 = 0;
+ index2 = 31;
+ }
+
+ __random_generator rd(__SEED);
+
+ unsigned long __long_random(unsigned long limit) {
+ return rd(limit);
+ }
+
+
+
Only in ../STL: random.cpp
diff -P -c -C 2 ../STL/tempbuf.cc ./tempbuf.cc
*** ../STL/tempbuf.cc Thu Jan 1 01:00:00 1970
--- ./tempbuf.cc Thu Nov 3 17:01:09 1994
***************
*** 0 ****
--- 1,18 ----
+ /*
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Hewlett-Packard Company makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ *
+ */
+
+ #include <tempbuf.h>
+
+ char __stl_temp_buffer[__stl_buffer_size];
Only in ../STL: tempbuf.cpp
diff -P -c -C 2 ../STL/tree.h ./tree.h
*** ../STL/tree.h Wed Nov 2 20:11:27 1994
--- ./tree.h Mon Nov 7 16:00:08 1994
***************
*** 1,3 ****
! /*
*
* Copyright (c) 1994
--- 1,3 ----
! /* -*- C++ -*-
*
* Copyright (c) 1994
***************
*** 87,95 ****
typedef Allocator<rb_tree_node_buffer>::pointer buffer_pointer;
protected:
static Allocator<rb_tree_node_buffer> buffer_allocator;
! static buffer_pointer buffer_list;
! static link_type free_list;
! static link_type next_avail;
! static link_type last;
void add_new_buffer() {
buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
--- 87,100 ----
typedef Allocator<rb_tree_node_buffer>::pointer buffer_pointer;
protected:
+ #define STUPID_TREE_FIX ,buffer_list(0),free_list(0),next_avail(0),last(0),number_of_trees(0),NIL(0)
static Allocator<rb_tree_node_buffer> buffer_allocator;
! // static
! buffer_pointer buffer_list;
! // static
! link_type free_list;
! // static
! link_type next_avail;
! // static
! link_type last;
void add_new_buffer() {
buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
***************
*** 100,104 ****
last = next_avail + buffer_size();
}
! static size_type number_of_trees;
void deallocate_buffers();
link_type get_node() {
--- 105,110 ----
last = next_avail + buffer_size();
}
! // static
! size_type number_of_trees;
void deallocate_buffers();
link_type get_node() {
***************
*** 127,131 ****
//public:
Compare key_compare;
! static link_type NIL;
static link_type& left(link_type x) {
return (link_type&)((*x).left_link);
--- 133,138 ----
//public:
Compare key_compare;
! // static
! link_type NIL;
static link_type& left(link_type x) {
return (link_type&)((*x).left_link);
***************
*** 143,152 ****
static color_type& color(link_type x) {
return (color_type&)(*x).color_field; }
! static link_type minimum(link_type x) {
while (left(x) != NIL)
x = left(x);
return x;
}
! static link_type maximum(link_type x) {
while (right(x) != NIL)
x = right(x);
--- 150,161 ----
static color_type& color(link_type x) {
return (color_type&)(*x).color_field; }
! // static
! link_type minimum(link_type x) {
while (left(x) != NIL)
x = left(x);
return x;
}
! // static
! link_type maximum(link_type x) {
while (right(x) != NIL)
x = right(x);
***************
*** 167,172 ****
*/
protected:
! link_type node;
! iterator(link_type x) : node(x) {}
public:
iterator() {}
--- 176,181 ----
*/
protected:
! link_type node, NIL;
! iterator(link_type x, link_type NILarg) : node(x), NIL(NILarg) {}
public:
iterator() {}
***************
*** 229,237 ****
*/
protected:
! link_type node;
! const_iterator(link_type x) : node(x) {}
public:
const_iterator() {}
! const_iterator(const iterator& x) : node(x.node) {}
bool operator==(const const_iterator& y) const {
return node == y.node;
--- 238,246 ----
*/
protected:
! link_type node, NIL;
! const_iterator(link_type x, link_type NILarg) : node(x), NIL(NILarg) {}
public:
const_iterator() {}
! const_iterator(const iterator& x) : node(x.node), NIL(x.NIL) {}
bool operator==(const const_iterator& y) const {
return node == y.node;
***************
*** 294,298 ****
const_reverse_iterator;
private:
! iterator __insert(link_type x, link_type y, const value_type& v);
void init() {
++number_of_trees;
--- 303,307 ----
const_reverse_iterator;
private:
! rb_tree_iterator<Key, Value, KeyOfValue, Compare> __insert(void* x, void* y, const value_type& v);
void init() {
++number_of_trees;
***************
*** 316,320 ****
rb_tree(const Compare& comp = Compare(), bool always = true)
! : node_count(0) {
key_compare = comp;
insert_always = always;
--- 325,329 ----
rb_tree(const Compare& comp = Compare(), bool always = true)
! : node_count(0) STUPID_TREE_FIX {
key_compare = comp;
insert_always = always;
***************
*** 323,327 ****
rb_tree(const value_type* first, const value_type* last,
const Compare& comp = Compare(), bool always = true)
! : node_count(0) {
key_compare = comp;
insert_always = always;
--- 332,336 ----
rb_tree(const value_type* first, const value_type* last,
const Compare& comp = Compare(), bool always = true)
! : node_count(0) STUPID_TREE_FIX {
key_compare = comp;
insert_always = always;
***************
*** 330,334 ****
}
rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare>& x,
! bool always = true) : node_count(0) {
key_compare = x.key_compare;
insert_always = always;
--- 339,343 ----
}
rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare>& x,
! bool always = true) : node_count(0) STUPID_TREE_FIX {
key_compare = x.key_compare;
insert_always = always;
***************
*** 356,363 ****
Compare key_comp() const { return key_compare; }
! iterator begin() { return leftmost(); }
! const_iterator begin() const { return leftmost(); }
! iterator end() { return header; }
! const_iterator end() const { return header; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
--- 365,372 ----
Compare key_comp() const { return key_compare; }
! iterator begin() { return iterator(leftmost(), NIL); }
! const_iterator begin() const { return iterator(leftmost(), NIL); }
! iterator end() { return iterator(header, NIL); }
! const_iterator end() const { return iterator(header, NIL); }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
***************
*** 384,449 ****
typedef pair<iterator, bool> pair_iterator_bool;
// typedef done to get around compiler bug
! pair_iterator_bool insert(const value_type& x);
! iterator insert(iterator position, const value_type& x);
! void insert(iterator first, iterator last);
! void insert(const value_type* first, const value_type* last);
! void erase(iterator position);
size_type erase(const key_type& x);
! void erase(iterator first, iterator last);
void erase(const key_type* first, const key_type* last);
// set operations:
! iterator find(const key_type& x);
! const_iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
! iterator lower_bound(const key_type& x);
! const_iterator lower_bound(const key_type& x) const;
! iterator upper_bound(const key_type& x);
! const_iterator upper_bound(const key_type& x) const;
typedef pair<iterator, iterator> pair_iterator_iterator;
// typedef done to get around compiler bug
! pair_iterator_iterator equal_range(const key_type& x);
! typedef pair<const_iterator, const_iterator> pair_citerator_citerator;
// typedef done to get around compiler bug
! pair_citerator_citerator equal_range(const key_type& x) const;
! inline void rotate_left(link_type x);
! inline void rotate_right(link_type x);
};
! template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::buffer_pointer
! rb_tree<Key, Value, KeyOfValue, Compare>::buffer_list = 0;
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! rb_tree<Key, Value, KeyOfValue, Compare>::free_list = 0;
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! rb_tree<Key, Value, KeyOfValue, Compare>::next_avail = 0;
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! rb_tree<Key, Value, KeyOfValue, Compare>::last = 0;
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::size_type
! rb_tree<Key, Value, KeyOfValue, Compare>::number_of_trees = 0;
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator_type
! rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator;
template <class Key, class Value, class KeyOfValue, class Compare>
! Allocator<Value> rb_tree<Key, Value, KeyOfValue, Compare>::value_allocator;
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator_type
! rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator;
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! rb_tree<Key, Value, KeyOfValue, Compare>::NIL = 0;
template <class Key, class Value, class KeyOfValue, class Compare>
--- 393,595 ----
typedef pair<iterator, bool> pair_iterator_bool;
// typedef done to get around compiler bug
! pair_iterator_bool insert(const value_type& x) {
! return insert_hack(x);
! }
! private:
! rb_tree_pair_iterator_bool<Key, Value, KeyOfValue, Compare>
! insert_hack(const Value& v);
! public:
! iterator insert(iterator position, const value_type& x) {
! insert_hack(position, x);
! }
! private:
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! insert_hack(rb_tree_iterator<Key, Value, KeyOfValue, Compare> posn,
! const Value& v);
! public:
! void insert(iterator first, iterator last) {
! while (first != last) insert(*first++);
! }
! void insert(const value_type* first, const value_type* last){
! while (first != last) insert(*first++);
! }
! void erase(iterator position) {
! erase_hack(position);
! }
! private:
! void erase_hack(rb_tree_iterator<Key, Value, KeyOfValue, Compare> position);
! public:
size_type erase(const key_type& x);
! void erase(iterator first, iterator last) {
! while (first != last) erase(first++);
! }
void erase(const key_type* first, const key_type* last);
// set operations:
! iterator find(const key_type& x) {
! return find_hack(x);
! }
! const_iterator find(const key_type& x) const {
! return find_hack(x);
! }
! private:
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! find_hack(const key_type& x);
! rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>
! find_hack(const Key& k) const;
! public:
!
size_type count(const key_type& x) const;
! iterator lower_bound(const key_type& x) {
! return lower_bound_hack(x);
! }
! const_iterator lower_bound(const key_type& x) const {
! return lower_bound_hack(x);
! }
! iterator upper_bound(const key_type& x) {
! return upper_bound_hack(x);
! }
! const_iterator upper_bound(const key_type& x) const {
! return upper_bound_hack(x);
! }
! private:
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! lower_bound_hack(const key_type& x);
! rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>
! lower_bound_hack(const Key& k) const;
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! upper_bound_hack(const key_type& x);
! rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>
! upper_bound_hack(const Key& k) const;
! public:
typedef pair<iterator, iterator> pair_iterator_iterator;
// typedef done to get around compiler bug
! pair_iterator_iterator equal_range(const key_type& x) {
! return pair_iterator_iterator(lower_bound(x), upper_bound(x));
! }
! typedef pair<const_iterator, const_iterator> pair_citerator_citerator;
!
// typedef done to get around compiler bug
! pair_citerator_citerator equal_range(const key_type& x) const {
! return pair_citerator_citerator(lower_bound(x), upper_bound(x));
! }
! inline void rotate_left(link_type x) {
! link_type y = right(x);
! right(x) = left(y);
! if (left(y) != NIL)
! parent(left(y)) = x;
! parent(y) = parent(x);
! if (x == root())
! root() = y;
! else if (x == left(parent(x)))
! left(parent(x)) = y;
! else
! right(parent(x)) = y;
! left(y) = x;
! parent(x) = y;
! }
!
! inline void rotate_right(link_type x) {
! link_type y = left(x);
! left(x) = right(y);
! if (right(y) != NIL)
! parent(right(y)) = x;
! parent(y) = parent(x);
! if (x == root())
! root() = y;
! else if (x == right(parent(x)))
! right(parent(x)) = y;
! else
! left(parent(x)) = y;
! right(y) = x;
! parent(x) = y;
! }
! friend bidirectional_iterator_tag iterator_category(iterator) {
! return bidirectional_iterator_tag();
! }
! friend bidirectional_iterator_tag iterator_category(const_iterator) {
! return bidirectional_iterator_tag();
! }
};
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::buffer_pointer
! // rb_tree<Key, Value, KeyOfValue, Compare>::buffer_list = 0;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! // rb_tree<Key, Value, KeyOfValue, Compare>::free_list = 0;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! // rb_tree<Key, Value, KeyOfValue, Compare>::next_avail = 0;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! // rb_tree<Key, Value, KeyOfValue, Compare>::last = 0;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::size_type
! // rb_tree<Key, Value, KeyOfValue, Compare>::number_of_trees = 0;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator_type
! // rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //Allocator<Value> rb_tree<Key, Value, KeyOfValue, Compare>::value_allocator;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator_type
! // rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator;
! //
! //template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::link_type
! // rb_tree<Key, Value, KeyOfValue, Compare>::NIL = 0;
!
! // Hack for GCC
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! struct rb_tree_iterator {
! rb_tree<Key, Value, KeyOfValue, Compare>::iterator it;
! rb_tree_iterator(rb_tree<Key, Value, KeyOfValue, Compare>::iterator i) : it(i) {}
! operator rb_tree<Key, Value, KeyOfValue, Compare>::iterator() {
! return it;
! }
! };
template <class Key, class Value, class KeyOfValue, class Compare>
! inline Value* value_type(const rb_tree_iterator<Key, Value, KeyOfValue, Compare>&) {
! return (Value*)(0);
! }
template <class Key, class Value, class KeyOfValue, class Compare>
! struct rb_tree_const_iterator {
! rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator it;
! rb_tree_const_iterator(rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator i) : it(i) {}
! operator rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator() {
! return it;
! }
! };
template <class Key, class Value, class KeyOfValue, class Compare>
! inline Value* value_type(const rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>&) {
! return (Value*)(0);
! }
template <class Key, class Value, class KeyOfValue, class Compare>
! struct rb_tree_pair_iterator_bool {
! rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool it;
! rb_tree_pair_iterator_bool(rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool i) : it(i) {}
! operator rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool() {
! return it;
! }
! };
template <class Key, class Value, class KeyOfValue, class Compare>
! inline Value* value_type(rb_tree_pair_iterator_bool<Key, Value, KeyOfValue, Compare>&) {
! return (Value*)(0);
! }
template <class Key, class Value, class KeyOfValue, class Compare>
***************
*** 484,490 ****
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::iterator
rb_tree<Key, Value, KeyOfValue, Compare>::
! __insert(link_type x, link_type y, const Value& v) {
++node_count;
link_type z = get_node();
--- 630,638 ----
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::
! __insert(void* xa, void* ya, const Value& v) {
! link_type x = (link_type)xa;
! link_type y = (link_type)ya;
++node_count;
link_type z = get_node();
***************
*** 542,551 ****
}
color(root()) = black;
! return iterator(z);
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool
! rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value& v) {
link_type y = header;
link_type x = root();
--- 690,699 ----
}
color(root()) = black;
! return iterator(z, NIL);
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_pair_iterator_bool<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::insert_hack(const Value& v) {
link_type y = header;
link_type x = root();
***************
*** 559,563 ****
// value(y) and v are equivalent according to key_compare
if (!insert_always)
! return pair_iterator_bool(iterator(y), false);
if (x != NIL) {
y = minimum(x);
--- 707,711 ----
// value(y) and v are equivalent according to key_compare
if (!insert_always)
! return pair_iterator_bool(iterator(y, NIL), false);
if (x != NIL) {
y = minimum(x);
***************
*** 571,577 ****
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::insert(iterator position,
const Value& v) {
if (position == iterator(begin()))
if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
--- 719,726 ----
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::insert_hack(rb_tree_iterator<Key, Value, KeyOfValue, Compare> posn,
const Value& v) {
+ iterator position = posn;
if (position == iterator(begin()))
if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
***************
*** 599,616 ****
}
! template <class Key, class Value, class KeyOfValue, class Compare>
! void rb_tree<Key, Value, KeyOfValue, Compare>::insert(iterator first,
! iterator last) {
! while (first != last) insert(*first++);
! }
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! void rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value* first,
! const Value* last) {
! while (first != last) insert(*first++);
! }
template <class Key, class Value, class KeyOfValue, class Compare>
! void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator position) {
link_type z = position.node;
link_type y = z;
--- 748,767 ----
}
! // template <class Key, class Value, class KeyOfValue, class Compare>
! // void rb_tree<Key, Value, KeyOfValue, Compare>::insert(iterator first,
! // iterator last) {
! // while (first != last) insert(*first++);
! // }
! //
! // template <class Key, class Value, class KeyOfValue, class Compare>
! // void rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value* first,
! // const Value* last) {
! // while (first != last) insert(*first++);
! // }
template <class Key, class Value, class KeyOfValue, class Compare>
! void rb_tree<Key, Value, KeyOfValue, Compare>::erase_hack(
! rb_tree_iterator<Key, Value, KeyOfValue, Compare> posn) {
! iterator position = posn;
link_type z = position.node;
link_type y = z;
***************
*** 729,733 ****
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::size_type
rb_tree<Key, Value, KeyOfValue, Compare>::erase(const Key& x) {
pair_iterator_iterator p = equal_range(x);
--- 880,885 ----
template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::size_type
! size_t
rb_tree<Key, Value, KeyOfValue, Compare>::erase(const Key& x) {
pair_iterator_iterator p = equal_range(x);
***************
*** 738,746 ****
}
! template <class Key, class Value, class KeyOfValue, class Compare>
! void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator first,
! iterator last) {
! while (first != last) erase(first++);
! }
template <class Key, class Value, class KeyOfValue, class Compare>
--- 890,898 ----
}
! // template <class Key, class Value, class KeyOfValue, class Compare>
! // void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator first,
! // iterator last) {
! // while (first != last) erase(first++);
! // }
template <class Key, class Value, class KeyOfValue, class Compare>
***************
*** 751,756 ****
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::find(const Key& k) {
link_type x = root();
while (x != NIL) {
--- 903,908 ----
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::find_hack(const Key& k) {
link_type x = root();
while (x != NIL) {
***************
*** 760,764 ****
x = right(x);
else
! return iterator(x);
}
return end();
--- 912,916 ----
x = right(x);
else
! return iterator(x, NIL);
}
return end();
***************
*** 766,771 ****
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::find(const Key& k) const {
link_type x = root();
while (x != NIL) {
--- 918,923 ----
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::find_hack(const Key& k) const {
link_type x = root();
while (x != NIL) {
***************
*** 775,779 ****
x = right(x);
else
! return const_iterator(x);
}
return end();
--- 927,931 ----
x = right(x);
else
! return const_iterator(x, NIL);
}
return end();
***************
*** 781,785 ****
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::size_type
rb_tree<Key, Value, KeyOfValue, Compare>::count(const Key& k) const {
pair<const_iterator, const_iterator> p = equal_range(k);
--- 933,938 ----
template <class Key, class Value, class KeyOfValue, class Compare>
! //rb_tree<Key, Value, KeyOfValue, Compare>::size_type
! size_t
rb_tree<Key, Value, KeyOfValue, Compare>::count(const Key& k) const {
pair<const_iterator, const_iterator> p = equal_range(k);
***************
*** 790,795 ****
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound(const Key& k) {
link_type y = header;
link_type x = root();
--- 943,948 ----
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound_hack(const Key& k) {
link_type y = header;
link_type x = root();
***************
*** 802,813 ****
}
if (y == header || !key_compare(key(y), k))
! return iterator(y);
! iterator j = iterator(y);
return ++j;
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound(const Key& k) const {
link_type y = header;
link_type x = root();
--- 955,966 ----
}
if (y == header || !key_compare(key(y), k))
! return iterator(y, NIL);
! iterator j = iterator(y, NIL);
return ++j;
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound_hack(const Key& k) const {
link_type y = header;
link_type x = root();
***************
*** 820,831 ****
}
if (y == header || !key_compare(key(y), k))
! return const_iterator(y);
! const_iterator j = const_iterator(y);
return ++j;
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound(const Key& k) {
link_type y = header;
link_type x = root();
--- 973,984 ----
}
if (y == header || !key_compare(key(y), k))
! return const_iterator(y, NIL);
! const_iterator j = const_iterator(y, NIL);
return ++j;
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_iterator<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound_hack(const Key& k) {
link_type y = header;
link_type x = root();
***************
*** 838,849 ****
}
if (y == header || key_compare(k, key(y)))
! return iterator(y);
! iterator j = iterator(y);
return ++j;
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound(const Key& k) const {
link_type y = header;
link_type x = root();
--- 991,1002 ----
}
if (y == header || key_compare(k, key(y)))
! return iterator(y, NIL);
! iterator j = iterator(y, NIL);
return ++j;
}
template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound_hack(const Key& k) const {
link_type y = header;
link_type x = root();
***************
*** 856,911 ****
}
if (y == header || key_compare(k, key(y)))
! return const_iterator(y);
! const_iterator j = const_iterator(y);
return ++j;
}
! template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_iterator
! rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) {
! return pair_iterator_iterator(lower_bound(k), upper_bound(k));
! }
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! rb_tree<Key, Value, KeyOfValue, Compare>::pair_citerator_citerator
! rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) const {
! return pair_citerator_citerator(lower_bound(k), upper_bound(k));
! }
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! inline void
! rb_tree<Key, Value, KeyOfValue, Compare>::rotate_left(link_type x) {
! link_type y = right(x);
! right(x) = left(y);
! if (left(y) != NIL)
! parent(left(y)) = x;
! parent(y) = parent(x);
! if (x == root())
! root() = y;
! else if (x == left(parent(x)))
! left(parent(x)) = y;
! else
! right(parent(x)) = y;
! left(y) = x;
! parent(x) = y;
! }
!
! template <class Key, class Value, class KeyOfValue, class Compare>
! inline void
! rb_tree<Key, Value, KeyOfValue, Compare>::rotate_right(link_type x) {
! link_type y = left(x);
! left(x) = right(y);
! if (right(y) != NIL)
! parent(right(y)) = x;
! parent(y) = parent(x);
! if (x == root())
! root() = y;
! else if (x == right(parent(x)))
! right(parent(x)) = y;
! else
! left(parent(x)) = y;
! right(y) = x;
! parent(x) = y;
! }
#endif
--- 1009,1028 ----
}
if (y == header || key_compare(k, key(y)))
! return const_iterator(y, NIL);
! const_iterator j = const_iterator(y, NIL);
return ++j;
}
! // template <class Key, class Value, class KeyOfValue, class Compare>
! // rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_iterator
! // rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) {
! // return pair_iterator_iterator(lower_bound(k), upper_bound(k));
! // }
! //
! // template <class Key, class Value, class KeyOfValue, class Compare>
! // rb_tree<Key, Value, KeyOfValue, Compare>::pair_citerator_citerator
! // rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) const {
! // return pair_citerator_citerator(lower_bound(k), upper_bound(k));
! // }
#endif
diff -P -c -C 2 ../STL/vector.h ./vector.h
*** ../STL/vector.h Wed Nov 2 20:11:27 1994
--- ./vector.h Fri Nov 4 10:53:50 1994
***************
*** 1,3 ****
! /*
*
* Copyright (c) 1994
--- 1,3 ----
! /* -*- C++ -*-
*
* Copyright (c) 1994
***************
*** 52,56 ****
iterator finish;
iterator end_of_storage;
! void insert_aux(iterator position, const T& x);
public:
iterator begin() { return start; }
--- 52,59 ----
iterator finish;
iterator end_of_storage;
! void insert_aux(iterator position, const T& x) {
! insert_aux(vector_iterator<T>(position), x);
! }
! void insert_aux(vector_iterator<T> position, const T& x);
public:
iterator begin() { return start; }
***************
*** 131,136 ****
}
void insert (iterator position, const_iterator first,
! const_iterator last);
! void insert (iterator position, size_type n, const T& x);
void pop_back() { destroy(--finish); }
void erase(iterator position) {
--- 134,148 ----
}
void insert (iterator position, const_iterator first,
! const_iterator last) {
! insert(vector_iterator<T>(position),
! vector_const_iterator<T>(first),
! vector_const_iterator<T>(last));
! }
! void insert (vector_iterator<T> position, vector_const_iterator<T> first,
! vector_const_iterator<T> last);
! void insert (iterator position, size_type n, const T& x) {
! insert(vector_iterator<T>(position), n, x);
! }
! void insert (vector_iterator<T> position, size_type n, const T& x);
void pop_back() { destroy(--finish); }
void erase(iterator position) {
***************
*** 145,151 ****
--- 157,197 ----
finish = finish - (last - first);
}
+ friend T* value_type(const iterator&) {
+ return (T*)(0);
+ }
+ };
+
+ // Hack for GCC
+
+ template <class T>
+ struct vector_iterator {
+ vector<T>::iterator it;
+ vector_iterator(vector<T>::iterator i) : it(i) {}
+ operator vector<T>::iterator() {
+ return it;
+ }
+ };
+
+ template <class T>
+ inline T* value_type(const vector_iterator<T>&) {
+ return (T*)(0);
+ }
+
+
+ template <class T>
+ struct vector_const_iterator {
+ vector<T>::const_iterator it;
+ vector_const_iterator(vector<T>::const_iterator i) : it(i) {}
+ operator vector<T>::const_iterator() {
+ return it;
+ }
};
template <class T>
+ inline T* value_type(const vector_const_iterator<T>&) {
+ return (T*)(0);
+ }
+
+ template <class T>
inline bool operator==(const vector<T>& x, const vector<T>& y) {
return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
***************
*** 158,163 ****
! template <class T>
! vector<T>::vector_allocator vector<T>::static_allocator;
--- 204,209 ----
! // template <class T>
! // vector<T>::vector_allocator vector<T>::static_allocator;
***************
*** 183,187 ****
template <class T>
! void vector<T>::insert_aux(iterator position, const T& x) {
if (finish != end_of_storage) {
construct(finish, *(finish - 1));
--- 229,234 ----
template <class T>
! void vector<T>::insert_aux(vector_iterator<T> posn, const T& x) {
! iterator position = posn;
if (finish != end_of_storage) {
construct(finish, *(finish - 1));
***************
*** 205,209 ****
template <class T>
! void vector<T>::insert(iterator position, size_type n, const T& x) {
if (n == 0) return;
if (end_of_storage - finish >= n) {
--- 252,259 ----
template <class T>
! void vector<T>::insert(vector_iterator<T> posn,
! size_t n,
! const T& x) {
! iterator position = posn;
if (n == 0) return;
if (end_of_storage - finish >= n) {
***************
*** 233,239 ****
template <class T>
! void vector<T>::insert(iterator position,
! const_iterator first,
! const_iterator last) {
if (first == last) return;
size_type n = 0;
--- 283,293 ----
template <class T>
! void vector<T>::insert(vector_iterator<T> posn,
! vector_const_iterator<T> fi,
! vector_const_iterator<T> la) {
! iterator position = posn;
! const_iterator first = fi;
! const_iterator last = la;
!
if (first == last) return;
size_type n = 0;
***************
*** 268,274 ****
#endif
-
-
-
-
-
--- 322,323 ----