text: /*
   * Author: Garrett Barboza <garrett.barboza@kapricasecurity.com>
   *
   * Copyright (c) 2014 Kaprica Security, Inc.
   *
   * Permission is hereby granted, free of charge, to any person obtaining a copy
   * of this software and associated documentation files (the "Software"), to deal
   * in the Software without restriction, including without limitation the rights
   * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   * copies of the Software, and to permit persons to whom the Software is
   * furnished to do so, subject to the following conditions:
   *
   * The above copyright notice and this permission notice shall be included in
   * all copies or substantial portions of the Software.
   *
   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
   * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
   * THE SOFTWARE.
   *
   */
  
  #include "libcgc.h"
  #include "cgc_malloc.h"
  #include "cgc_stdlib.h"
  
  cgc_size_t size_class_limits[NUM_FREE_LISTS] = {
    2, 3, 4, 8,
    16, 24, 32, 48,
    64, 96, 128, 192,
    256, 384, 512, 768,
    1024, 1536, 2048, 3072,
    4096, 6144, 8192, 12288,
    16384, 24576, 32768, 49152,
    65536, 98304, 131072, INT32_MAX
  };
  
  struct blk_t *cgc_free_lists[NUM_FREE_LISTS] = {0};
  
  static void cgc_remove_from_blist(struct blk_t *blk)
  {
    if (blk->prev)
      blk->prev->next = blk->next;
  
    if (blk->next)
      blk->next->prev = blk->prev;
  }
  
  int cgc_get_size_class(cgc_size_t size)
  {
    int i;
    for (i = 0; i < NUM_FREE_LISTS && size > size_class_limits[i]; i++);
    return i;
  }
  
  
  void cgc_insert_into_flist(struct blk_t *blk)
  {
    int sc_i = cgc_get_size_class(blk->size);
    blk->free = 1;
  
    if (cgc_free_lists[sc_i] == NULL) {
      cgc_free_lists[sc_i] = blk;
      return;
    }
  
    blk->fsucc = cgc_free_lists[sc_i];
    cgc_free_lists[sc_i]->fpred = blk;
    cgc_free_lists[sc_i] = blk;
    blk->fpred = NULL;
  }
  
  void cgc_remove_from_flist(struct blk_t *blk)
  {
    int sc_i = cgc_get_size_class(blk->size);
  
    if (blk->fpred)
      blk->fpred->fsucc = blk->fsucc;
  
    if (blk->fsucc)
      blk->fsucc->fpred = blk->fpred;
  
    if (cgc_free_lists[sc_i] == blk)
      cgc_free_lists[sc_i] = blk->fsucc;
  
    blk->fsucc = NULL;
    blk->fpred = NULL;
    blk->free = 0;
  }
  
  void cgc_coalesce(struct blk_t *blk)
  {
    /* prev and next are free */
    if (blk->prev && blk->prev->free && blk->next && blk->next->free) {
      cgc_remove_from_flist(blk->prev);
      cgc_remove_from_flist(blk->next);
      cgc_remove_from_flist(blk);
  
      blk->prev->size += blk->size;
      blk->prev->size += blk->next->size;
      cgc_insert_into_flist(blk->prev);
  
      cgc_remove_from_blist(blk->next);
      cgc_remove_from_blist(blk);
    /* Just prev is free */
    } else if (blk->prev && blk->prev->free && blk->next && !blk->next->free) {
      cgc_remove_from_flist(blk->prev);
      cgc_remove_from_flist(blk);
  
      blk->prev->size += blk->size;
      cgc_insert_into_flist(blk->prev);
  
      cgc_remove_from_blist(blk);
    /* Just next is free */
    } else if (blk->prev && !blk->prev->free && blk->next && blk->next->free) {
      cgc_remove_from_flist(blk->next);
      cgc_remove_from_flist(blk);
  
      blk->size += blk->next->size;
      cgc_insert_into_flist(blk);
  
      cgc_remove_from_blist(blk->next);
    }
  }
  