ucw/doc/generic.txt

   1 Generic data structures and algorithms
   2 ======================================
   3
   4 The C preprocessor is a very powerful tool. One handy way to use it
   5 can be generating generic data structures and algorithms. Here you can
   6 find some conventions that are used in all such generic structures in
   7 libUCW, and also hints for use of these structures.
   8
   9 - <<idea,General idea>>
  10 - <<use,How to use them>>
  11 - <<implement,How it is implemented>>
  12 - Modules with generics
  13   * <<growbuf:gbuf,`gbuf.h`>>
  14   * <<sort:,Sorting>>
  15   * <<binheap:,`binheap.h`>>
  16   * <<hashtable:,`hashtable.h`>>
  17
  18 // TODO The module list
  19
  20 [[idea]]
  21 General idea
  22 ------------
  23
  24 The idea is simple. If you have some code, you can customize it a
  25 little by preprocessor macros. You can change constants, data types it
  26 operates on, whole expressions, or you can compile parts of the code
  27 conditionally. You can generate new function names using macros.
  28
  29 So if you provide few macros for data types, function names and
  30 parameters and include some code using them, it gets modified by it
  31 and a code for a specific data type is created. Then you can provide
  32 new macros and include it again, to get another version of the code,
  33 with different function names and types.
  34
  35 [[use]]
  36 How to use them
  37 ---------------
  38
  39 The use is best explained with an example, so we will suppose there
  40 is a header file `array.h`, which contains a generic array data type
  41 and an indexing function, which returns a pointer to n'th element.
  42
  43 To get an array of integers, we need to provide macro for used data
  44 type and macro that will provide prefixes for identifier names. Then
  45 we include the file. Then we could get another array with unsigned
  46 integers, so we will do the same:
  47
  48   #define ARRAY_TYPE int
  49   #define ARRAY_PREFIX(name) intarray_##name
  50   #include <array.h>
  51
  52   #define ARRAY_TYPE uns
  53   #define ARRAY_PREFIX(name) unsarray_##name
  54   #include <array.h>
  55
  56 This will generate the data types (presumably `intarray_t` and
  57 `unsarray_t`) and the index functions (`intarray_index` and
  58 `unsarray_index`). We can use them like anything else.
  59
  60 Maybe the `ARRAY_PREFIX` deserves some attention. When the header file
  61 wants to generate an identifier, it uses this macro with
  62 some name. Then the macro takes the name, adds a prefix to it and
  63 returns the new identifier, so `ARRAY_PREFIX(t)` will generate
  64 `intarray_t` in the first case and `unsarray_t` in the second. This
  65 allows having more than one instance of the same data structure or
  66 algorithm, because it generates different identifiers for them.
  67
  68 A similar macro is needed for every generic header in libUCW.
  69
  70 [[implement]]
  71 How it is implemented
  72 ---------------------
  73
  74 For those who want to write their own or are just interested, how it
  75 works, here is the `array.h` header and some description to it.
  76
  77   #define ARRAY_A_TYPE ARRAY_PREFIX(t)
  78   typedef ARRAY_TYPE *ARRAY_A_TYPE
  79
  80   static ARRAY_TYPE *ARRAY_PREFIX(index)(ARRAY_A_TYPE array, uns index)
  81   {
  82     return array + index;
  83   }
  84
  85   #undef ARRAY_A_TYPE
  86   #undef ARRAY_TYPE
  87   #undef ARRAY_PREFIX
  88
  89 There are few things that are worth noticing. The first two lines
  90 define the data type. The macro (`ARRAY_A_TYPE`) is only for
  91 convenience inside the header, since such type names can be used quite
  92 often inside the header (if it is large).
  93
  94 Then there is the function with its name generated (do not get scared
  95 by the double parenthesis, ones will be eaten by the macro, the second
  96 ones are real function parameters). The function is static, since more
  97 than one `.c` file might want to use the same header with the same
  98 prefix -- each one generates it's own instance.
  99
 100 And the end just undefines all the macros, so user may define them
 101 again and get another instance of the data structure.
 102
 103 Also note it is not protected against multiple inclusion in the usual
 104 way (eg. `#ifndef ARRAY_H` ...), since multiple inclusion is desired
 105 -- it generates multiple versions of the data structure.