THESE/codes/graphe/GCmex1.9/block.h

   1 /* block.h */\r
   2 /*\r
   3     Copyright 2001 Vladimir Kolmogorov (vnk@cs.cornell.edu), Yuri Boykov (yuri@csd.uwo.ca).\r
   4 \r
   5     This program is free software; you can redistribute it and/or modify\r
   6     it under the terms of the GNU General Public License as published by\r
   7     the Free Software Foundation; either version 2 of the License, or\r
   8     (at your option) any later version.\r
   9 \r
  10     This program is distributed in the hope that it will be useful,\r
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13     GNU General Public License for more details.\r
  14 \r
  15     You should have received a copy of the GNU General Public License\r
  16     along with this program; if not, write to the Free Software\r
  17     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  18 */\r
  19 \r
  20 \r
  21 /*\r
  22         Template classes Block and DBlock\r
  23         Implement adding and deleting items of the same type in blocks.\r
  24 \r
  25         If there there are many items then using Block or DBlock\r
  26         is more efficient than using 'new' and 'delete' both in terms\r
  27         of memory and time since\r
  28         (1) On some systems there is some minimum amount of memory\r
  29             that 'new' can allocate (e.g., 64), so if items are\r
  30             small that a lot of memory is wasted.\r
  31         (2) 'new' and 'delete' are designed for items of varying size.\r
  32             If all items has the same size, then an algorithm for\r
  33             adding and deleting can be made more efficient.\r
  34         (3) All Block and DBlock functions are inline, so there are\r
  35             no extra function calls.\r
  36 \r
  37         Differences between Block and DBlock:\r
  38         (1) DBlock allows both adding and deleting items,\r
  39             whereas Block allows only adding items.\r
  40         (2) Block has an additional operation of scanning\r
  41             items added so far (in the order in which they were added).\r
  42         (3) Block allows to allocate several consecutive\r
  43             items at a time, whereas DBlock can add only a single item.\r
  44 \r
  45         Note that no constructors or destructors are called for items.\r
  46 \r
  47         Example usage for items of type 'MyType':\r
  48 \r
  49         ///////////////////////////////////////////////////\r
  50         #include "block.h"\r
  51         #define BLOCK_SIZE 1024\r
  52         typedef struct { int a, b; } MyType;\r
  53         MyType *ptr, *array[10000];\r
  54 \r
  55         ...\r
  56 \r
  57         Block<MyType> *block = new Block<MyType>(BLOCK_SIZE);\r
  58 \r
  59         // adding items\r
  60         for (int i=0; i<sizeof(array); i++)\r
  61         {\r
  62                 ptr = block -> New();\r
  63                 ptr -> a = ptr -> b = rand();\r
  64         }\r
  65 \r
  66         // reading items\r
  67         for (ptr=block->ScanFirst(); ptr; ptr=block->ScanNext())\r
  68         {\r
  69                 printf("%d %d\n", ptr->a, ptr->b);\r
  70         }\r
  71 \r
  72         delete block;\r
  73 \r
  74         ...\r
  75 \r
  76         DBlock<MyType> *dblock = new DBlock<MyType>(BLOCK_SIZE);\r
  77         \r
  78         // adding items\r
  79         for (int i=0; i<sizeof(array); i++)\r
  80         {\r
  81                 array[i] = dblock -> New();\r
  82         }\r
  83 \r
  84         // deleting items\r
  85         for (int i=0; i<sizeof(array); i+=2)\r
  86         {\r
  87                 dblock -> Delete(array[i]);\r
  88         }\r
  89 \r
  90         // adding items\r
  91         for (int i=0; i<sizeof(array); i++)\r
  92         {\r
  93                 array[i] = dblock -> New();\r
  94         }\r
  95 \r
  96         delete dblock;\r
  97 \r
  98         ///////////////////////////////////////////////////\r
  99 \r
 100         Note that DBlock deletes items by marking them as\r
 101         empty (i.e., by adding them to the list of free items),\r
 102         so that this memory could be used for subsequently\r
 103         added items. Thus, at each moment the memory allocated\r
 104         is determined by the maximum number of items allocated\r
 105         simultaneously at earlier moments. All memory is\r
 106         deallocated only when the destructor is called.\r
 107 */\r
 108 \r
 109 #ifndef __BLOCK_H__\r
 110 #define __BLOCK_H__\r
 111 \r
 112 #include <stdlib.h>\r
 113 \r
 114 /***********************************************************************/\r
 115 /***********************************************************************/\r
 116 /***********************************************************************/\r
 117 \r
 118 template <class Type> class Block\r
 119 {\r
 120 public:\r
 121         /* Constructor. Arguments are the block size and\r
 122            (optionally) the pointer to the function which\r
 123            will be called if allocation failed; the message\r
 124            passed to this function is "Not enough memory!" */\r
 125         Block(int size, void (*err_function)(const char *) = NULL) { first = last = NULL; block_size = size; error_function = err_function; }\r
 126 \r
 127         /* Destructor. Deallocates all items added so far */\r
 128         ~Block() { while (first) { block *next = first -> next; delete first; first = next; } }\r
 129 \r
 130         /* Allocates 'num' consecutive items; returns pointer\r
 131            to the first item. 'num' cannot be greater than the\r
 132            block size since items must fit in one block */\r
 133         Type *New(int num = 1)\r
 134         {\r
 135                 Type *t;\r
 136 \r
 137                 if (!last || last->current + num > last->last)\r
 138                 {\r
 139                         if (last && last->next) last = last -> next;\r
 140                         else\r
 141                         {\r
 142                                 block *next = (block *) new char [sizeof(block) + (block_size-1)*sizeof(Type)];\r
 143                                 if (!next) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }\r
 144                                 if (last) last -> next = next;\r
 145                                 else first = next;\r
 146                                 last = next;\r
 147                                 last -> current = & ( last -> data[0] );\r
 148                                 last -> last = last -> current + block_size;\r
 149                                 last -> next = NULL;\r
 150                         }\r
 151                 }\r
 152 \r
 153                 t = last -> current;\r
 154                 last -> current += num;\r
 155                 return t;\r
 156         }\r
 157 \r
 158         /* Returns the first item (or NULL, if no items were added) */\r
 159         Type *ScanFirst()\r
 160         {\r
 161                 scan_current_block = first;\r
 162                 if (!scan_current_block) return NULL;\r
 163                 scan_current_data = & ( scan_current_block -> data[0] );\r
 164                 return scan_current_data ++;\r
 165         }\r
 166 \r
 167         /* Returns the next item (or NULL, if all items have been read)\r
 168            Can be called only if previous ScanFirst() or ScanNext()\r
 169            call returned not NULL. */\r
 170         Type *ScanNext()\r
 171         {\r
 172                 if (scan_current_data >= scan_current_block -> current)\r
 173                 {\r
 174                         scan_current_block = scan_current_block -> next;\r
 175                         if (!scan_current_block) return NULL;\r
 176                         scan_current_data = & ( scan_current_block -> data[0] );\r
 177                 }\r
 178                 return scan_current_data ++;\r
 179         }\r
 180 \r
 181         /* Marks all elements as empty */\r
 182         void Reset()\r
 183         {\r
 184                 block *b;\r
 185                 if (!first) return;\r
 186                 for (b=first; ; b=b->next)\r
 187                 {\r
 188                         b -> current = & ( b -> data[0] );\r
 189                         if (b == last) break;\r
 190                 }\r
 191                 last = first;\r
 192         }\r
 193 \r
 194 /***********************************************************************/\r
 195 \r
 196 private:\r
 197 \r
 198         typedef struct block_st\r
 199         {\r
 200                 Type                                    *current, *last;\r
 201                 struct block_st                 *next;\r
 202                 Type                                    data[1];\r
 203         } block;\r
 204 \r
 205         int             block_size;\r
 206         block   *first;\r
 207         block   *last;\r
 208 \r
 209         block   *scan_current_block;\r
 210         Type    *scan_current_data;\r
 211 \r
 212         void    (*error_function)(const char *);\r
 213 };\r
 214 \r
 215 /***********************************************************************/\r
 216 /***********************************************************************/\r
 217 /***********************************************************************/\r
 218 \r
 219 template <class Type> class DBlock\r
 220 {\r
 221 public:\r
 222         /* Constructor. Arguments are the block size and\r
 223            (optionally) the pointer to the function which\r
 224            will be called if allocation failed; the message\r
 225            passed to this function is "Not enough memory!" */\r
 226         DBlock(int size, void (*err_function)(const char *) = NULL) { first = NULL; first_free = NULL; block_size = size; error_function = err_function; }\r
 227 \r
 228         /* Destructor. Deallocates all items added so far */\r
 229         ~DBlock() { while (first) { block *next = first -> next; delete first; first = next; } }\r
 230 \r
 231         /* Allocates one item */\r
 232         Type *New()\r
 233         {\r
 234                 block_item *item;\r
 235 \r
 236                 if (!first_free)\r
 237                 {\r
 238                         block *next = first;\r
 239                         first = (block *) new char [sizeof(block) + (block_size-1)*sizeof(block_item)];\r
 240                         if (!first) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }\r
 241                         first_free = & (first -> data[0] );\r
 242                         for (item=first_free; item<first_free+block_size-1; item++)\r
 243                                 item -> next_free = item + 1;\r
 244                         item -> next_free = NULL;\r
 245                         first -> next = next;\r
 246                 }\r
 247 \r
 248                 item = first_free;\r
 249                 first_free = item -> next_free;\r
 250                 return (Type *) item;\r
 251         }\r
 252 \r
 253         /* Deletes an item allocated previously */\r
 254         void Delete(Type *t)\r
 255         {\r
 256                 ((block_item *) t) -> next_free = first_free;\r
 257                 first_free = (block_item *) t;\r
 258         }\r
 259 \r
 260 /***********************************************************************/\r
 261 \r
 262 private:\r
 263 \r
 264         typedef union block_item_st\r
 265         {\r
 266                 Type                    t;\r
 267                 block_item_st   *next_free;\r
 268         } block_item;\r
 269 \r
 270         typedef struct block_st\r
 271         {\r
 272                 struct block_st                 *next;\r
 273                 block_item                              data[1];\r
 274         } block;\r
 275 \r
 276         int                     block_size;\r
 277         block           *first;\r
 278         block_item      *first_free;\r
 279 \r
 280         void    (*error_function)(const char *);\r
 281 };\r
 282 \r
 283 \r
 284 #endif\r
 285 \r