apps/plugins/pdbox/dbestfit-3.3/bmalloc.c

   1 /*****************************************************************************
   2  *
   3  * Big (best-fit) Memory Allocation
   4  *
   5  * Author:  Daniel Stenberg
   6  * Date:    March 5, 1997
   7  * Version: 2.0
   8  * Email:   Daniel.Stenberg@sth.frontec.se
   9  *
  10  *
  11  * Read 'thoughts' for theories and details in implementation.
  12  *
  13  * Routines meant to replace the most low level functions of an Operting
  14  * System
  15  *
  16  * v2.0
  17  * - Made all size-routines get moved out from this file. This way, the size
  18  *   functions can much more easily get replaced.
  19  * - Improved how new memory blocks get added to the size-sorted list. When
  20  *   not adding new pools, there should never ever be any list traversing
  21  *   since all information is dynamically gathered.
  22  *
  23  ****************************************************************************/
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27
  28 #include "bysize.h"
  29
  30 #ifndef TRUE
  31 #define TRUE 1
  32 #endif
  33 #ifndef FALSE
  34 #define FALSE 0
  35 #endif
  36
  37 /* #define DEBUG */
  38
  39 #define BMEM_ALIGN 64 /* resolution */
  40
  41 #define BMEMERR_TOOSMALL -1
  42
  43 /* this struct will be stored in all CHUNKS and AREAS */
  44 struct BlockInfo {
  45   struct BlockInfo *lower;  /* previous block in memory (lower address) */
  46   struct BlockInfo *higher; /* next block in memory (higher address) */
  47   unsigned long info;       /* 31 bits size: 1 bit free boolean */
  48 #define INFO_FREE 1
  49 #define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */
  50
  51   /* FREE+SIZE Could be written to use ordinary bitfields if using a smart
  52      (like gcc) compiler in a manner like:
  53      int size:31;
  54      int free:1;
  55
  56      The 'higher' pointer COULD be removed completely if the size is used as
  57      an index to the higher one. This would then REQUIRE the entire memory
  58      pool to be contiguous and it needs a 'terminating' "node" or an extra
  59      flag that informs about the end of the list.
  60      */
  61 };
  62
  63 /* the BLOCK list should be sorted in a lower to higher address order */
  64 struct BlockInfo *blockHead=NULL; /* nothing from the start */
  65
  66 void print_lists(void);
  67
  68
  69 /***********************************************************************
  70  *
  71  * remove_block()
  72  *
  73  * Remove the block from the address-sorted list.
  74  *
  75  ***********************************************************************/
  76
  77 void remove_block(struct BlockInfo *block)
  78 {
  79   if(block->lower)
  80     block->lower->higher = block->higher;
  81   else
  82     blockHead = block->higher;
  83   if(block->higher)
  84     block->higher->lower = block->lower;
  85 }
  86
  87 /****************************************************************************
  88  *
  89  * add_blocktolists()
  90  *
  91  * Adds the specified block at the specified place in the address-sorted
  92  * list and at the appropriate place in the size-sorted.
  93  *
  94  ***************************************************************************/
  95 void add_blocktolists(struct BlockInfo *block,
  96                       struct BlockInfo *newblock,
  97                       size_t newsize)
  98 {
  99   struct BlockInfo *temp; /* temporary storage variable */
 100   if(block) {
 101     /* `block' is now a lower address than 'newblock' */
 102
 103     /*
 104      * Check if the new CHUNK is wall-to-wall with the lower addressed
 105      * one (if *that* is free)
 106      */
 107     if(block->info&INFO_FREE) {
 108       if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) {
 109         /* yes sir, this is our lower address neighbour, enlarge that one
 110            pick it out from the list and recursively add that chunk and
 111            then we escape */
 112
 113         /* remove from size-sorted list: */
 114         remove_chunksize((char*)block+sizeof(struct BlockInfo));
 115
 116         block->info += newsize; /* newsize is an even number and thus the FREE
 117                                    bit is untouched */
 118
 119         remove_block(block); /* unlink the block address-wise */
 120
 121         /* recursively check our lower friend(s) */
 122         add_blocktolists(block->lower, block, block->info&INFO_SIZE);
 123         return;
 124       }
 125     }
 126
 127     temp = block->higher;
 128
 129     block->higher = newblock;
 130     newblock->lower = block;
 131     newblock->higher = temp;
 132     if(newblock->higher)
 133         newblock->higher->lower = newblock;
 134   }
 135   else {
 136     /* this block should preceed the heading one */
 137     temp = blockHead;
 138
 139     /* check if this is our higher addressed neighbour */
 140     if((char *)newblock + newsize == (char *)temp) {
 141
 142       /* yes, we are wall-to-wall with the higher CHUNK */
 143       if(temp->info&INFO_FREE) {
 144         /* and the neighbour is even free, remove that one and enlarge
 145            ourselves, call add_pool() recursively and then escape */
 146
 147         remove_block(temp); /* unlink 'temp' from list */
 148
 149         /* remove from size-sorted list: */
 150         remove_chunksize((char*)temp+sizeof(struct BlockInfo) );
 151
 152         /* add the upper block's size on ourselves */
 153         newsize += temp->info&INFO_SIZE;
 154
 155         /* add the new, bigger block */
 156         add_blocktolists(block, newblock, newsize);
 157         return;
 158       }
 159     }
 160
 161     blockHead = newblock;
 162     newblock->higher = temp;
 163     newblock->lower  = NULL; /* there is no lower one */
 164     if(newblock->higher)
 165         newblock->higher->lower = newblock;
 166   }
 167
 168   newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the
 169                                            FREE bit */
 170   insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize);
 171 }
 172
 173 /***********************************************************************
 174  *
 175  * findblockbyaddr()
 176  *
 177  * Find the block that is just before the input block in memory. Returns NULL
 178  * if none is.
 179  *
 180  ***********************************************************************/
 181
 182 static struct BlockInfo *findblockbyaddr(struct BlockInfo *block)
 183 {
 184   struct BlockInfo *test = blockHead;
 185   struct BlockInfo *lower = NULL;
 186
 187   while(test && (test < block)) {
 188     lower = test;
 189     test = test->higher;
 190   }
 191   return lower;
 192 }
 193
 194 /***********************************************************************
 195  *
 196  * add_pool()
 197  *
 198  * This function should be the absolutely first function to call. It sets up
 199  * the memory bounds of the [first] CHUNK(s). It should be possible to call
 200  * this function several times to add more CHUNKs to the pool of free
 201  * memory. This allows the bmalloc system to deal with a non-contigous memory
 202  * area.
 203  *
 204  * Returns non-zero if an error occured. The memory was not added then.
 205  *
 206  ***********************************************************************/
 207
 208 int add_pool(void *start,
 209              size_t size)
 210 {
 211   struct BlockInfo *newblock = (struct BlockInfo *)start;
 212   struct BlockInfo *block;
 213
 214   if(size < BMEM_ALIGN)
 215     return BMEMERR_TOOSMALL;
 216
 217   block = findblockbyaddr( newblock );
 218   /* `block' is now a lower address than 'newblock' or NULL */
 219
 220   if(size&1)
 221     size--; /* only add even sizes */
 222
 223   add_blocktolists(block, newblock, size);
 224
 225   return 0;
 226 }
 227
 228
 229 #ifdef DEBUG
 230 static void bmalloc_failed(size_t size)
 231 {
 232   printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
 233   print_lists();
 234 }
 235 #else
 236 #define bmalloc_failed(x)
 237 #endif
 238
 239 void print_lists()
 240 {
 241   struct BlockInfo *block = blockHead;
 242 #if 1
 243   printf("List of BLOCKS (in address order):\n");
 244   while(block) {
 245     printf("  START %p END %p SIZE %ld FLAG %s\n",
 246            (char *)block,
 247            (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE,
 248            (block->info&INFO_FREE)?"free":"used");
 249     block = block->higher;
 250   }
 251   printf("End of BLOCKS:\n");
 252 #endif
 253   print_sizes();
 254 }
 255
 256 void *bmalloc(size_t size)
 257 {
 258   void *mem;
 259
 260 #ifdef DEBUG
 261   {
 262     static int count=0;
 263     int realsize = size + sizeof(struct BlockInfo);
 264     if(realsize%4096)
 265       realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
 266     printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
 267   }
 268 #endif
 269
 270   size += sizeof(struct BlockInfo); /* add memory for our header */
 271
 272   if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
 273                              changed if the BLOCKSIZE is not 2^X ! */
 274     size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
 275
 276   /* get a CHUNK from the list with this size */
 277   mem = obtainbysize ( size );
 278   if(mem) {
 279     /* the memory block we have got is the "best-fit" and it is already
 280        un-linked from the free list */
 281
 282     /* now do the math to get the proper block pointer */
 283     struct BlockInfo *block= (struct BlockInfo *)
 284       ((char *)mem - sizeof(struct BlockInfo));
 285
 286     block->info &= ~INFO_FREE;
 287     /* not free anymore */
 288
 289     if( size != (block->info&INFO_SIZE)) {
 290       /* split this chunk into two pieces and return the one that fits us */
 291       size_t othersize = (block->info&INFO_SIZE) - size;
 292
 293       if(othersize > BMEM_ALIGN) {
 294         /* prevent losing small pieces of memory due to weird alignments
 295            of the memory pool */
 296
 297         block->info = size;  /* set new size (leave FREE bit cleared) */
 298
 299         /* Add the new chunk to the lists: */
 300         add_blocktolists(block,
 301                          (struct BlockInfo *)((char *)block + size),
 302                          othersize );
 303       }
 304     }
 305
 306     /* Return the memory our parent may use: */
 307     return (char *)block+sizeof(struct BlockInfo);
 308   }
 309   else {
 310     bmalloc_failed(size);
 311     return NULL; /* can't find any memory, fail hard */
 312   }
 313   return NULL;
 314 }
 315
 316 void bfree(void *ptr)
 317 {
 318   struct BlockInfo *block = (struct BlockInfo *)
 319     ((char *)ptr - sizeof(struct BlockInfo));
 320   size_t size;
 321
 322   /* setup our initial higher and lower pointers */
 323   struct BlockInfo *lower = block->lower;
 324   struct BlockInfo *higher = block->higher;
 325
 326 #ifdef DEBUG
 327   static int freecount=0;
 328   printf("%d bfree(%p)\n", freecount++, ptr);
 329 #endif
 330
 331   /* bind together lower addressed FREE CHUNKS */
 332   if(lower && (lower->info&INFO_FREE) &&
 333      ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
 334     size = block->info&INFO_SIZE;      /* original size */
 335
 336     /* remove from size-link: */
 337     remove_chunksize((char *)lower+sizeof(struct BlockInfo));
 338
 339     remove_block(block);              /* unlink from address list */
 340     block = lower;                    /* new base area pointer */
 341     block->info += size;              /* append the new size (the FREE bit
 342                                          will remain untouched) */
 343
 344     lower = lower->lower;             /* new lower pointer */
 345   }
 346   /* bind together higher addressed FREE CHUNKS */
 347   if(higher && (higher->info&INFO_FREE) &&
 348      ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) {
 349     /* append higher size, the FREE bit won't be affected */
 350     block->info += (higher->info&INFO_SIZE);
 351
 352     /* unlink from size list: */
 353     remove_chunksize((char *)higher+sizeof(struct BlockInfo));
 354     remove_block(higher);             /* unlink from address list */
 355     higher = higher->higher;          /* the new higher link */
 356     block->higher = higher;           /* new higher link */
 357   }
 358   block->info |= INFO_FREE;   /* consider this FREE! */
 359
 360   block->lower = lower;
 361   block->higher = higher;
 362
 363   insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE);
 364
 365 #ifdef DEBUG
 366   print_lists();
 367 #endif
 368
 369 }
 370
 371 /*****************************************************************************
 372  *
 373  * Big (best-fit) Memory Allocation
 374  *
 375  * Author:  Daniel Stenberg
 376  * Date:    March 5, 1997
 377  * Version: 2.0
 378  * Email:   Daniel.Stenberg@sth.frontec.se
 379  *
 380  *
 381  * Read 'thoughts' for theories and details in implementation.
 382  *
 383  * Routines meant to replace the most low level functions of an Operting
 384  * System
 385  *
 386  * v2.0
 387  * - Made all size-routines get moved out from this file. This way, the size
 388  *   functions can much more easily get replaced.
 389  * - Improved how new memory blocks get added to the size-sorted list. When
 390  *   not adding new pools, there should never ever be any list traversing
 391  *   since all information is dynamically gathered.
 392  *
 393  ****************************************************************************/
 394
 395 #include <stdio.h>
 396 #include <stdlib.h>
 397
 398 #include "bysize.h"
 399
 400 #ifndef TRUE
 401 #define TRUE 1
 402 #endif
 403 #ifndef FALSE
 404 #define FALSE 0
 405 #endif
 406
 407 /* #define DEBUG */
 408
 409 #define BMEM_ALIGN 64 /* resolution */
 410
 411 #define BMEMERR_TOOSMALL -1
 412
 413 /* this struct will be stored in all CHUNKS and AREAS */
 414 struct BlockInfo {
 415   struct BlockInfo *lower;  /* previous block in memory (lower address) */
 416   struct BlockInfo *higher; /* next block in memory (higher address) */
 417   unsigned long info;       /* 31 bits size: 1 bit free boolean */
 418 #define INFO_FREE 1
 419 #define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */
 420
 421   /* FREE+SIZE Could be written to use ordinary bitfields if using a smart
 422      (like gcc) compiler in a manner like:
 423      int size:31;
 424      int free:1;
 425
 426      The 'higher' pointer COULD be removed completely if the size is used as
 427      an index to the higher one. This would then REQUIRE the entire memory
 428      pool to be contiguous and it needs a 'terminating' "node" or an extra
 429      flag that informs about the end of the list.
 430      */
 431 };
 432
 433 /* the BLOCK list should be sorted in a lower to higher address order */
 434 struct BlockInfo *blockHead=NULL; /* nothing from the start */
 435
 436 void print_lists(void);
 437
 438
 439 /***********************************************************************
 440  *
 441  * remove_block()
 442  *
 443  * Remove the block from the address-sorted list.
 444  *
 445  ***********************************************************************/
 446
 447 void remove_block(struct BlockInfo *block)
 448 {
 449   if(block->lower)
 450     block->lower->higher = block->higher;
 451   else
 452     blockHead = block->higher;
 453   if(block->higher)
 454     block->higher->lower = block->lower;
 455 }
 456
 457 /****************************************************************************
 458  *
 459  * add_blocktolists()
 460  *
 461  * Adds the specified block at the specified place in the address-sorted
 462  * list and at the appropriate place in the size-sorted.
 463  *
 464  ***************************************************************************/
 465 void add_blocktolists(struct BlockInfo *block,
 466                       struct BlockInfo *newblock,
 467                       size_t newsize)
 468 {
 469   struct BlockInfo *temp; /* temporary storage variable */
 470   if(block) {
 471     /* `block' is now a lower address than 'newblock' */
 472
 473     /*
 474      * Check if the new CHUNK is wall-to-wall with the lower addressed
 475      * one (if *that* is free)
 476      */
 477     if(block->info&INFO_FREE) {
 478       if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) {
 479         /* yes sir, this is our lower address neighbour, enlarge that one
 480            pick it out from the list and recursively add that chunk and
 481            then we escape */
 482
 483         /* remove from size-sorted list: */
 484         remove_chunksize((char*)block+sizeof(struct BlockInfo));
 485
 486         block->info += newsize; /* newsize is an even number and thus the FREE
 487                                    bit is untouched */
 488
 489         remove_block(block); /* unlink the block address-wise */
 490
 491         /* recursively check our lower friend(s) */
 492         add_blocktolists(block->lower, block, block->info&INFO_SIZE);
 493         return;
 494       }
 495     }
 496
 497     temp = block->higher;
 498
 499     block->higher = newblock;
 500     newblock->lower = block;
 501     newblock->higher = temp;
 502     if(newblock->higher)
 503         newblock->higher->lower = newblock;
 504   }
 505   else {
 506     /* this block should preceed the heading one */
 507     temp = blockHead;
 508
 509     /* check if this is our higher addressed neighbour */
 510     if((char *)newblock + newsize == (char *)temp) {
 511
 512       /* yes, we are wall-to-wall with the higher CHUNK */
 513       if(temp->info&INFO_FREE) {
 514         /* and the neighbour is even free, remove that one and enlarge
 515            ourselves, call add_pool() recursively and then escape */
 516
 517         remove_block(temp); /* unlink 'temp' from list */
 518
 519         /* remove from size-sorted list: */
 520         remove_chunksize((char*)temp+sizeof(struct BlockInfo) );
 521
 522         /* add the upper block's size on ourselves */
 523         newsize += temp->info&INFO_SIZE;
 524
 525         /* add the new, bigger block */
 526         add_blocktolists(block, newblock, newsize);
 527         return;
 528       }
 529     }
 530
 531     blockHead = newblock;
 532     newblock->higher = temp;
 533     newblock->lower  = NULL; /* there is no lower one */
 534     if(newblock->higher)
 535         newblock->higher->lower = newblock;
 536   }
 537
 538   newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the
 539                                            FREE bit */
 540   insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize);
 541 }
 542
 543 /***********************************************************************
 544  *
 545  * findblockbyaddr()
 546  *
 547  * Find the block that is just before the input block in memory. Returns NULL
 548  * if none is.
 549  *
 550  ***********************************************************************/
 551
 552 static struct BlockInfo *findblockbyaddr(struct BlockInfo *block)
 553 {
 554   struct BlockInfo *test = blockHead;
 555   struct BlockInfo *lower = NULL;
 556
 557   while(test && (test < block)) {
 558     lower = test;
 559     test = test->higher;
 560   }
 561   return lower;
 562 }
 563
 564 /***********************************************************************
 565  *
 566  * add_pool()
 567  *
 568  * This function should be the absolutely first function to call. It sets up
 569  * the memory bounds of the [first] CHUNK(s). It should be possible to call
 570  * this function several times to add more CHUNKs to the pool of free
 571  * memory. This allows the bmalloc system to deal with a non-contigous memory
 572  * area.
 573  *
 574  * Returns non-zero if an error occured. The memory was not added then.
 575  *
 576  ***********************************************************************/
 577
 578 int add_pool(void *start,
 579              size_t size)
 580 {
 581   struct BlockInfo *newblock = (struct BlockInfo *)start;
 582   struct BlockInfo *block;
 583
 584   if(size < BMEM_ALIGN)
 585     return BMEMERR_TOOSMALL;
 586
 587   block = findblockbyaddr( newblock );
 588   /* `block' is now a lower address than 'newblock' or NULL */
 589
 590   if(size&1)
 591     size--; /* only add even sizes */
 592
 593   add_blocktolists(block, newblock, size);
 594
 595   return 0;
 596 }
 597
 598
 599 #ifdef DEBUG
 600 static void bmalloc_failed(size_t size)
 601 {
 602   printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
 603   print_lists();
 604 }
 605 #else
 606 #define bmalloc_failed(x)
 607 #endif
 608
 609 void print_lists()
 610 {
 611   struct BlockInfo *block = blockHead;
 612 #if 1
 613   printf("List of BLOCKS (in address order):\n");
 614   while(block) {
 615     printf("  START %p END %p SIZE %ld FLAG %s\n",
 616            (char *)block,
 617            (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE,
 618            (block->info&INFO_FREE)?"free":"used");
 619     block = block->higher;
 620   }
 621   printf("End of BLOCKS:\n");
 622 #endif
 623   print_sizes();
 624 }
 625
 626 void *bmalloc(size_t size)
 627 {
 628   void *mem;
 629
 630 #ifdef DEBUG
 631   {
 632     static int count=0;
 633     int realsize = size + sizeof(struct BlockInfo);
 634     if(realsize%4096)
 635       realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
 636     printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
 637   }
 638 #endif
 639
 640   size += sizeof(struct BlockInfo); /* add memory for our header */
 641
 642   if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
 643                              changed if the BLOCKSIZE is not 2^X ! */
 644     size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
 645
 646   /* get a CHUNK from the list with this size */
 647   mem = obtainbysize ( size );
 648   if(mem) {
 649     /* the memory block we have got is the "best-fit" and it is already
 650        un-linked from the free list */
 651
 652     /* now do the math to get the proper block pointer */
 653     struct BlockInfo *block= (struct BlockInfo *)
 654       ((char *)mem - sizeof(struct BlockInfo));
 655
 656     block->info &= ~INFO_FREE;
 657     /* not free anymore */
 658
 659     if( size != (block->info&INFO_SIZE)) {
 660       /* split this chunk into two pieces and return the one that fits us */
 661       size_t othersize = (block->info&INFO_SIZE) - size;
 662
 663       if(othersize > BMEM_ALIGN) {
 664         /* prevent losing small pieces of memory due to weird alignments
 665            of the memory pool */
 666
 667         block->info = size;  /* set new size (leave FREE bit cleared) */
 668
 669         /* Add the new chunk to the lists: */
 670         add_blocktolists(block,
 671                          (struct BlockInfo *)((char *)block + size),
 672                          othersize );
 673       }
 674     }
 675
 676     /* Return the memory our parent may use: */
 677     return (char *)block+sizeof(struct BlockInfo);
 678   }
 679   else {
 680     bmalloc_failed(size);
 681     return NULL; /* can't find any memory, fail hard */
 682   }
 683   return NULL;
 684 }
 685
 686 void bfree(void *ptr)
 687 {
 688   struct BlockInfo *block = (struct BlockInfo *)
 689     ((char *)ptr - sizeof(struct BlockInfo));
 690   size_t size;
 691
 692   /* setup our initial higher and lower pointers */
 693   struct BlockInfo *lower = block->lower;
 694   struct BlockInfo *higher = block->higher;
 695
 696 #ifdef DEBUG
 697   static int freecount=0;
 698   printf("%d bfree(%p)\n", freecount++, ptr);
 699 #endif
 700
 701   /* bind together lower addressed FREE CHUNKS */
 702   if(lower && (lower->info&INFO_FREE) &&
 703      ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
 704     size = block->info&INFO_SIZE;      /* original size */
 705
 706     /* remove from size-link: */
 707     remove_chunksize((char *)lower+sizeof(struct BlockInfo));
 708
 709     remove_block(block);              /* unlink from address list */
 710     block = lower;                    /* new base area pointer */
 711     block->info += size;              /* append the new size (the FREE bit
 712                                          will remain untouched) */
 713
 714     lower = lower->lower;             /* new lower pointer */
 715   }
 716   /* bind together higher addressed FREE CHUNKS */
 717   if(higher && (higher->info&INFO_FREE) &&
 718      ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) {
 719     /* append higher size, the FREE bit won't be affected */
 720     block->info += (higher->info&INFO_SIZE);
 721
 722     /* unlink from size list: */
 723     remove_chunksize((char *)higher+sizeof(struct BlockInfo));
 724     remove_block(higher);             /* unlink from address list */
 725     higher = higher->higher;          /* the new higher link */
 726     block->higher = higher;           /* new higher link */
 727   }
 728   block->info |= INFO_FREE;   /* consider this FREE! */
 729
 730   block->lower = lower;
 731   block->higher = higher;
 732
 733   insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE);
 734
 735 #ifdef DEBUG
 736   print_lists();
 737 #endif
 738
 739 }
 740