Add section on irep_idt and dstringt

Owen Jones · Owen Jones · commit 01dc76b4529d · 2018-05-25T08:44:39.000+01:00
diff --git a/src/util/README.md b/src/util/README.md
@@ -3,7 +3,7 @@
 
 # Folder util
 
-\author Martin Brain
+\author Martin Brain, Owen Jones
 
 \section data_structures Data Structures
 
@@ -82,6 +82,19 @@ recurse on the expression on either side.
 [^2]: Unless `USE_STD_STRING` is set, this is actually
 a `dstring` and thus an integer which is a reference into a string table
 
+\subsection irep_idt Irep_idt and Dstringt
+
+Inside `irept`s, strings are stored as `irep_idt`s, or `irep_namet`s for
+keys to `named_sub` or `comments`. If `USE_STD_STRING` is set then both 
+`irep_idt` and `irep_namet` are `typedef`ed to `std::string`, but by default 
+it is not set and they are `typedef`ed to `dstringt`. `dstringt` has one 
+field, an unsigned integer which is an index into a static table of strings. 
+This makes it expensive to create a new string (because you have to look 
+through the whole table to see if it is already there, and add it if it 
+isn't) but very cheap to compare strings (just compare the two integers). It 
+also means that when you have lots of copies of the same string you only have
+to store the whole string once, which saves space.
+
 \dot
 digraph G {
   node [shape=box];
