ucw/doc/mempool.txt

   1 Memory pools
   2 ============
   3
   4 You can use them for efficient allocation of large amount of small
   5 memory blocks. You can use them to allocate many blocks and free them
   6 all at once. They allow storing and restoring state of what is
   7 allocated, growing and shrinking the last block and other tricks.
   8
   9 * <<defs,Definitions>>
  10 * <<basic,Basic manipulation>>
  11 * <<alloc,Allocation routines>>
  12 * <<gbuf,Growing buffers>>
  13 * <<store,Storing and restoring state>>
  14 * <<string,String operations>>
  15 * <<format,Formatted output>>
  16 * <<examples,Examples>>
  17   - <<ex_trie,String trie>>
  18   - <<ex_try,Action which may fail>>
  19   - <<ex_stdin,Load all data from stdin>>
  20
  21 !!ucw/mempool.h
  22
  23 [[examples]]
  24 Examples
  25 --------
  26
  27 You can find few examples of mempools use. But their actual use is
  28 limited only by your fantasy.
  29
  30 [[ex_trie]]
  31 String trie
  32 ~~~~~~~~~~~
  33
  34 There are two advantages for a trie to use a mempool. One, it has less
  35 overhead than malloc (with the cost you can not free the blocks one by
  36 one as you allocated them). Second is freeing the whole trie, you do
  37 not need to walk trough it and free each node, you just
  38 <<mp_flush(),flush>> the whole mempool.
  39
  40   struct trie_node {
  41     struct trie_node *subs[256];
  42     bool present;
  43   };
  44
  45   struct trie {
  46     struct trie_node root;
  47     struct mempool *pool;
  48   };
  49
  50   struct trie *trie_new(void) {
  51     struct mempool *pool = mn_new(4096);
  52     struct trie *result = mp_alloc_zero(pool, sizeof(*result));
  53     result->pool = pool;
  54     return result;
  55   }
  56
  57   void trie_insert_internal(struct trie_node *where, struct mempool *pool, const char *string) {
  58     if(*string) {
  59       if(!where->subs[*string])
  60         where->subs[*string] = mp_alloc_zero(pool, sizeof(*where->subs[*string]));
  61       trie_insert_internal(where->subs[*string], pool, string + 1);
  62     } else {
  63       where->present = 1;
  64     }
  65   }
  66
  67   void trie_insert(struct trie *trie, const char *string) {
  68     trie_insert_internal(&trie->root, trie->pool, string);
  69   }
  70
  71   void trie_delete(struct trie *trie) {
  72     mp_delete(trie->pool);      //Free everything, including the trie structure
  73   }
  74
  75 [[ex_try]]
  76 Action which may fail
  77 ~~~~~~~~~~~~~~~~~~~~~
  78
  79 Imagine a situation where you want to load information from few files.
  80 Loading of each file consists of list of actions, each can allocate
  81 some memory and each can fail. If an action fails, the whole file is
  82 considered invalid, you want to ignore that file and keep loading the
  83 others.
  84
  85 The problem with memory is you want to return the already allocated
  86 amount for the file which failed. You can use <<store,storing>> of
  87 mempool state.
  88
  89   void load_file(struct mempool *pool, const char *file) {
  90     struct mempool_state state;
  91     mp_save(pool, &state);              // Store the current state
  92     struct file_data *data = mp_alloc_zero(pool, sizeof(*data));
  93     if(!(
  94         file_open(file, data, pool) &&  // Load the file
  95         header_load(data, pool) &&
  96         part1_load(data, pool) &&
  97         part2_load(data, pool) &&
  98         file_close(data) &&
  99         data_link(data, pool)))         // Link the loaded data into global state
 100       mp_restore(pool, &state);         // Failed -> return all used memory
 101   }
 102
 103 [[ex_stdin]]
 104 Load all data from stdin
 105 ~~~~~~~~~~~~~~~~~~~~~~~~
 106
 107 You may want to load all data from stdin into a memory buffer. But
 108 there is the problem you do not know how many of them there is. You
 109 may use mempool and it's <<gbuf,growing buffer>> feature.
 110
 111 This example uses libucw's own IO system, <<fastbuf:,fastbufs>>.
 112
 113   void *stdin_data(struct mempool *pool) {
 114     struct fastbuf *fb = bopen_fd(0, NULL);     // Read from stdin
 115     uint amount;
 116     char *ptr = mp_start(pool, 1024);
 117     while(amount = bread(fb, ptr, 1024)) {      // Read a block
 118       ptr += amount;                            // Move after it
 119       ptr = mp_spread(pool, ptr, 1024);         // Get space for the next block
 120     }
 121     bclose(fb);
 122     return mp_end(pool, ptr);
 123   }