diff options
Diffstat (limited to 'doc/html/EASTL Maintenance.html')
| -rw-r--r-- | doc/html/EASTL Maintenance.html | 292 |
1 files changed, 0 insertions, 292 deletions
diff --git a/doc/html/EASTL Maintenance.html b/doc/html/EASTL Maintenance.html deleted file mode 100644 index aaca955..0000000 --- a/doc/html/EASTL Maintenance.html +++ /dev/null @@ -1,292 +0,0 @@ -<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> -<html> -<head> - <title>EASTL Maintenance</title> - <meta content="text/html; charset=us-ascii" http-equiv="content-type"> - <meta name="author" content="Paul Pedriana"> - <meta name="description" content="Information for the EASTL maintainer."> - <link type="text/css" rel="stylesheet" href="EASTLDoc.css"> -</head> -<body> - -<h1>EASTL Maintenance</h1> -<h2><span style="font-style: italic;"><a name="Introduction" id="Introduction"></a></span>Introduction</h2> -<p>The purpose of this document is to provide some necessary background for anybody who might do work on EASTL. Writing - generic templated systems like EASTL can be surprisingly tricky. There are numerous details of the C++ language that - you need to understand which don't usually come into play during the day-to-day C++ coding that many people do. It is - easy to make a change to some function that seems proper and works for your test case but either violates the design - expectations or simply breaks under other circumstances.<br> - <br> - It may be useful to start with an example. Here we provide an implementation of the count algorithm which is seems -simple enough. Except it is wrong and while it will compile in some cases it won't compile in others:</p> -<pre class="code-example">template <class InputIterator, class T> -int count(InputIterator first, InputIterator last, const T& value) -{ - int result = 0; - - for(; first < last; ++first){ - if(*first == value) - ++result; - } - - return result; - } </pre> -<p>The problem is with the comparison 'first < last'. The count algorithm takes an InputIterator and operator< is -not guaranteed to exist for any given InputIterator (and indeed while operator< exists for vector::iterator, it -doesn't exist for list::iterator). The comparison in the above algorithm must instead be implemented as 'first != -last'. If we were working with a RandomAccessIterator then 'first < last' would be valid.</p> -<p>In the following sections we cover various topics of interest regarding the development and maintentance of EASTL. - Unfortunately, this document can't cover every aspect of EASTL maintenance issues, but at least it should give you a -sense of the kinds of issues.</p> - -<h2> <a name="Language_Standard" id="Language_Standard"></a>C++ Language Standard</h2> -<p>First and foremost, you need to be familiar with the C++ standard. In particular, the sections of the standard related - to containers, algorithms, and iterators are of prime significance. We'll talk about some of this in more detail below. - Similarly, a strong understanding of the basic data types is required. What is the difference between ptrdiff_t and -intptr_t; unsigned int and size_t; char and signed char?</p> -<p>In addition to the C++ language standard, you'll want to be familiar with the C++ Defect Report. This is a continuously - updated document which lists flaws in the original C++ language specification and the current thinking as the -resolutions of those flaws. You will notice various references to the Defect Report in EASTL source code.</p> -<p>Additionally, you will want to be familiar with the C++ Technical Report 1 (as of this writing there is only one). This - document is the evolving addendum to the C++ standard based on both the Defect Report and based on desired additions to -the C++ language and standard library.</p> -<p>Additionally, you will probably want to have some familiarity with Boost. It also helps to keep an eye on - comp.std.c++ Usenet discussions. However, watch out for what people say on Usenet. They tend to defend GCC, Unix, std - STL, and C++ to a sometimes unreasonable degree. Many discussions ignore performance implications and -concentrate only on correctness and sometimes academic correctness above usability.</p> -<h2> <a name="Langauge_Use" id="Langauge_Use"></a>Language Use</h2> -<p>Macros are (almost) not allowed in EASTL. A prime directive of EASTL is to be easier to read by users and most of - the time macros are an impedence to this. So we avoid macros at all costs, even if it ends up making our development - and maintenance more difficult. That being said, you will notice that the EASTL config.h file uses macros to control - various options. This is an exception to the rule; when we talk about not using macros, we mean with the EASTL -implementation itself.</p> -<p>EASTL assumes a compliant and intelligent C++ compiler, and thus all language facilities are usable. However, we -nevertheless choose to stay away from some language functionality. The primary language features we avoid are:</p> -<ul> - <li>RTTI (run-time-type-identification) (this is deemed too costly)</li> -<li>Template export (few compilers support this)</li> -<li>Exception specifications (most compilers ignore them)</li> -</ul> -<p>Use of per-platform or per-compiler code should be avoided when possible but where there is a significant advantage to - be gained it can and indeed should be used. An example of this is the GCC __builtin_expect feature, which allows the - user to give the compiler a hint about whether an expression is true or false. This allows for the generation of code -that executes faster due to more intelligent branch prediction.</p> -<h2> <a name="Prime_Directives" id="Prime_Directives"></a>Prime Directives</h2> -<p>The -implementation of EASTL is guided foremost by the following directives which are listed in order of importance.</p> -<ol> -<li>Efficiency (speed and memory usage)</li> -<li>Correctness (doesn't have bugs)</li> -<li>Portability (works on all required platforms with minimal specialized code)</li> -<li>Readability (code is legible and comments are present and useful)</li> -</ol> -<p>Note that unlike commercial STL implementations which must put correctness above all, we put a higher value on - efficiency. As a result, some functionality may have some usage limitation that is not present in other similar systems -but which allows for more efficient operation, especially on the platforms of significance to us.</p> -<p>Portability is significant, but not critical. Yes, EASTL must compile and run on all platforms that we will ship games - for. But we don't take that to mean under all compilers that could be conceivably used for such platforms. For example, - Microsoft VC6 can be used to compile Windows programs, but VC6's C++ support is too weak for EASTL and so you simply -cannot use EASTL under VC6.</p> -<p>Readability is something that EASTL achieves better than many other templated libraries, particularly Microsoft STL and - STLPort. We make every attempt to make EASTL code clean and sensible. Sometimes our need to provide optimizations - (particularly related to type_traits and iterator types) results in less simple code, but efficiency happens to be our -prime directive and so it overrides all other considerations.</p> - -<h2> <a name="Coding_Conventions" id="Coding_Conventions"></a>Coding Conventions</h2> -<p>Here we provide a list of coding conventions to follow when maintaining or adding to EASTL, starting with the three -language use items from above:</p> -<ul> -<li>No RTTI use.</li> -<li>No use of exception specifications (e.g. appending the 'throw' declarator to a function).</li> -<li>No use of exception handling itself except where explicitly required by the implementation (e.g. vector::at).</li> -<li>Exception use needs to savvy to EASTL_EXCEPTIONS_ENABLED.</li> -<li>No use of macros (outside of config.h). Macros make things more difficult for the user.</li> -<li>No use of static or global variables.</li> -<li>No use of global new, delete, malloc, or free. All memory must be user-specifyable via an Allocator parameter -(default-specified or explicitly specified).</li> -<li>Containers use protected member data and functions as opposed to private. This is because doing so allows -subclasses to extend the container without the creation of intermediary functions. Recall from our <a href="#Prime_Directives">prime directives</a> above that performance and simplicity overrule all.</li> -<li>No use of multithreading primitives. </li> -<li>No use of the export keyword.</li> -<li>We don't have a rule about C-style casts vs. C++ static_cast<>, etc. We would always use static_cast except -that debuggers can't evaluate them and so in practice they can get in the way of debugging and tracing. However, if the -cast is one that users don't tend to need to view in a debugger, C++ casts are preferred.</li> -<li>No external library dependencies whatsoever, including standard STL. EASTL is dependent on only EABase and the -C++ compiler. </li> -<li>All code must be const-correct. This isn't just for readability -- compilation can fail unless const-ness is used -correctly everywhere. </li> -<li>Algorithms do not refer to containers; they refer only to iterators.</li> -<li>Algorithms in general do not allocate memory. If such a situation arises, there should be a version of the -algorithm which allows the user to provide the allocator.</li> -<li>No inferior implementations. No facility should be added to EASTL unless it is of professional -quality.</li> -<li>The maintainer should emulate the EASTL style of code layout, regardless of the maintainer's personal preferences. -When in Rome, do as the Romans do. EASTL uses 4 spaces for indents, which is how the large majority of code within EA -is written.</li> -<li>No major changes should be done without consulting a peer group.</li> -</ul> - -<h2><a name="Compiler_Issues" id="Compiler_Issues"></a>Compiler Issues</h2> -<p>Historically, templates are the feature of C++ that has given C++ compilers the most fits. We are still working with - compilers that don't completely and properly support templates. Luckily, most compilers are now good enough to handle -what EASTL requires. Nevertheless, there are precautions we must take.</p> -<p>It turns out that the biggest problem in writing portable EASTL code is that VC++ allows you to make illegal statements - which are not allowed by other compilers. For example, VC++ will allow you to neglect using the typename keyword in -template references, whereas GCC (especially 3.4+) requires it.</p> -<p>In order to feel comfortable that your EASTL code is C++ correct and is portable, you must do at least these two -things:</p> -<ul> -<li>Test under at least VS2005, GCC 3.4+, GCC 4.4+, EDG, and clang. </li> -<li>Test all functions that you write, as compilers will often skip the compilation of a template function if it isn't -used.</li> -</ul> -<p>The two biggest issues to watch out for are 'typename' and a concept called "dependent names". In both cases VC++ will - accept non-conforming syntax whereas most other compilers will not. Whenever you reference a templated type (and not a templated - value) in a template, you need to prefix it by 'typename'. Whenever your class function refers to a base class member (data or - function), you need to refer to it by "this->", "base_type::", or by placing a "using" statement in your class to -declare that you will be referencing the given base class member.</p> - -<h2> <a name="Iterator_Issues" id="Iterator_Issues"></a>Iterator Issues</h2> -<p>The most important thing to understand about iterators is the concept of iterator types and their designated - properties. In particular, we need to understand the difference between InputIterator, ForwardIterator, - BidirectionalIterator, RandomAccessIterator, and OutputIterator. These differences dictate both how we implement our - algorithms and how we implement our optimizations. Please read the C++ standard for a reasonably well-implemented - description of these iterator types.</p> -<p>Here's an example from EASTL/algorithm.h which demonstrates how we use iterator types to optimize the reverse algorithm -based on the kind of iterator passed to it:</p> -<pre class="code-example">template <class BidirectionalIterator> -inline void reverse_impl(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag)<br>{ - for(; (first != last) && (first != --last); ++first) <span class="code-example-comment">// We are not allowed to use operator <, <=, >, >= with</span> - iter_swap(first, last); <span class="code-example-comment">// a generic (bidirectional or otherwise) iterator.</span> -}<br> - -template <typename RandomAccessIterator> -inline void reverse_impl(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) -{ - for(; first < --last; ++first) <span class="code-example-comment">// With a random access iterator, we can use operator < to more efficiently implement</span> - iter_swap(first, last); <span class="code-example-comment">// this algorithm. A generic iterator doesn't necessarily have an operator < defined.</span> -}<br><br> -template <class BidirectionalIterator> -inline void reverse(BidirectionalIterator first, BidirectionalIterator last) -{ - typedef typename iterator_traits<BidirectionalIterator>::iterator_category IC; - reverse_impl(first, last, IC()); -}</pre> - -<h2> <a name="Exception_Handling" id="Exception_Handling"></a>Exception Handling</h2> -<p>You will notice that EASTL uses try/catch in some places (particularly in containers) and uses - the EASTL_EXCEPTIONS_ENABLED define. For starters, any EASTL code that uses try/catch should always be wrapped - within #if EASTL_EXCEPTIONS_ENABLED (note: #if, not #ifdef).</p> -<p>This is simple enough, but what you may be wondering is how it is that EASTL decides to use try/catch for some sections - of code and not for others. EASTL follows the C++ standard library conventions with respect to exception handling, and - you will see similar exception handling in standard STL. The code that you need to wrap in try/catch is code that can - throw a C++ exception (not to be confused with CPU exception) and needs to have something unwound (or fixed) as a - result. The important thing is that the container be in a valid state after encountering such exceptions. In general -the kinds of things that require such try/catch are:</p> -<ul> -<li>Memory allocation failures (which throw exceptions)</li> -<li>Constructor exceptions</li> -</ul> -<p>Take a look at the cases in EASTL where try/catch is used and see what it is doing.</p> -<h2> <a name="Type_Traits" id="Type_Traits"></a>Type Traits </h2> -<p>EASTL provides a facility called type_traits which is very similar to the type_traits being proposed by the C++ TR1 - (see above). type_traits are useful because they tell you about properties of types at compile time. This allows you to - do things such as assert that a data type is scalar or that a data type is const. The way we put them to use in EASTL - is to take advantage of them to implement different pathways for functions based on types. For example, we can copy a - contiguous array of scalars much faster via memcpy than we can via a for loop, though we could not safely employ the - for loop for a non-trivial C++ class.</p> -<p>As mentioned in the GeneralOptimizations section below, EASTL should take advantage of type_traits information to the -extent possible to achive maximum effiiciency.</p> -<h2> <a name="General_Optimizations" id="General_Optimizations"></a>General -Optimizations</h2> -<p>One of the primary goals of EASTL is to achieve the highest possible efficiency. In cases where EASTL functionality - overlaps standard C++ STL functionality, standard STL implementations provided by compiler vendors are a benchmark upon - which EASTL strives to beat. Indeed EASTL is more efficient than all other current STL implementations (with some - exception in the case of some Metrowerks STL facilities). Here we list some of the things to look for when considering - optimization of EASTL code These items can be considered general optimization suggestions for any code, but this -particular list applies to EASTL:</p> -<ul> -<li>Take advantage of type_traits to the extent possible (e.g. to use memcpy to move data instead of a for loop when -possible).</li> -<li>Take advantage of iterator types to the extent possible.</li> -<li>Take advantage of the compiler's expectation that if statements are expected to evaluate as true and for loop -conditions are expected to evaluate as false.</li> -<li>Make inline-friendly code. This often means avoiding temporaries to the extent possible.</li> -<li>Minimize branching (i.e. minimize 'if' statements). Where branching is used, make it so that 'if' statements -execute as true.</li> -<li>Use EASTL_LIKELY/EASTL_UNLIKELY to give branch hints to the compiler when you are confident it will be -beneficial.</li> -<li>Use restricted pointers (EABase's EA_RESTRICT or various compiler-specific versions of __restrict).</li> -<li>Compare unsigned values to < max instead of comparing signed values to >= 0 && < max.</li> -<li>Employ power of 2 integer math instead of math with any kind of integer.</li> -<li>Use template specialization where possible to implement improved functionality.</li> -<li>Avoid function calls when the call does something trivial. This improves debug build speed (which matters) and -sometimes release build speed as well, though sometimes makes the code intent less clear. A comment next to the code -saying what call it is replacing makes the intent clear without sacrificing performance.</li> -</ul> -<h2><a name="Unit_Tests" id="Unit_Tests"></a>Unit Tests</h2> -<p>Writing robust templated containers and algorithms is difficult or impossible without a heavy unit test suite in place. - EASTL has a pretty extensive set of unit tests for all containers and algorithms. While the successful automated unit - testing of shipping application programs may be a difficult thing to pull off, unit testing of libraries such as this - is of huge importance and cannot be understated. </p> -<ul> -<li>When making a new unit test, start by copying one of the existing unit tests and follow its conventions.</li> -<li>Test containers of both scalars and classes.</li> -<li>Test algorithms on both container iterators (e.g. vector.begin()) and pointer iterators (e.g. int*).</li> -<li>Make sure that algorithm or container member functions which take iterators work with the type of iterator they -claim to (InputIterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator). </li> -<li>Test for const-correctness. If a user is allowed to modify something that is supposed to be const, silent errors -can go undetected.</li> -<li>Make sure that unit tests cover all functions and all pathways of the tested code. This means that in writing the -unit test you need to look at the source code to understand all the pathways.</li> -<li>Consider using a random number generator (one is provided in the test library) to do 'monkey' testing whereby -unexpected input is given to a module being tested. When doing so, make sure you seed the generator in a way that -problems can be reproduced.</li> -<li>While we avoid macros in EASTL user code, macros to assist in unit tests aren't considered a problem. However, -consider that a number of macros could be replaced by templated functions and thus be easier to work with.</li> -<li>Unit tests don't need to be efficient; feel free to take up all the CPU power and time you need to test a module -sufficiently.</li> -<li>EASTL containers are not thread-safe, by design. Thus there is no need to do multithreading tests as long as you -stay away from the usage of static and global variables.</li> -<li>Unit tests must succeed with no memory leaks and of course no memory corruption. The heap system should be -configured to test for this, and heap validation functions are available to the unit tests while in the middle of -runs.</li> -</ul> - -<h2><a name="Things_to_Keep_in_Mind" id="Things_to_Keep_in_Mind"></a>Things to Keep in Mind</h2> -<ul> -<li>When referring to EASTL functions and types from EASTL code, make sure to preface the type with the EASTL -namespace. If you don't do this you can get collisions due to the compiler not knowing if it should use the EASTL -namespace or the namespace of the templated type for the function or type.</li> -<li>Newly constructed empty containers do no memory allocation. Some STL and other container libraries allocate an -initial node from the class memory allocator. EASTL containers by design never do this. If a container needs an -initial node, that node should be made part of the container itself or be a static empty node object.</li> -<li>Empty containers (new or otherwise) contain no constructed objects, including those that might be in an 'end' node. -Similarly, no user object (e.g. of type T) should be constructed unless required by the design and unless documented in -the cotainer/algorithm contract. </li> -<li>When creating a new container class, it's best to copy from an existing similar class to the extent possible. This -helps keep the library consistent and resolves subtle problems that can happen in the construction of containers.</li> -<li>Be very careful about tweaking the code. It's easy to think (for example) that a > could be switch to a >= -where instead it is a big deal. Just about every line of code in EASTL has been thought through and has a purpose. Unit -tests may or may not currently test every bit of EASTL, so you can't necessarily rely on them to give you 100% -confidence in changes. If you are not sure about something, contact the original author and he will tell you for -sure.</li> -<li>Algorithm templates always work with iterators and not containers. A given container may of course implement an -optimized form or an algorithm itself.</li> -<li>Make sure everything is heavily unit tested. If somebody finds a bug, fix the bug and make a unit test to make sure -the bug doesn't happen again.</li> -<li>It's easy to get iterator categories confused or forgotten while implementing algorithms and containers.</li> -<li>Watch out for the strictness of GCC 3.4+. There is a bit of syntax — especially related to templates — that other -compilers accept but GCC 3.4+ will not.</li> -<li>Don't forget to update the config.h EASTL_VERSION define before publishing.</li> -<li>The vector and string classes define iterator to be T*. We want to always leave this so — at least in release -builds — as this gives some algorithms an advantage that optimizers cannot get around.</li> -</ul> -<hr style="width: 100%; height: 2px;"> -<br> -<br> -<br> -<br> -<br> -</body> -</html> |