path: root/src-diclib/alloc.c

/*
 * 構造体アロケータ
 * Funded by IPA未踏ソフトウェア創造事業 2001 8/15
 *
 * $Id: alloc.c,v 1.12 2002/05/15 11:21:10 yusuke Exp $
 *
 * Copyright (C) 2005 YOSHIDA Yuichi
 * Copyright (C) 2000-2005 TABATA Yusuke, UGAWA Tomoharu
 * Copyright (C) 2002, 2005 NIIBE Yutaka
 *
 * dtor: destructor
 * 
 * ページ中のフリーなchunkは単方向リストに継がれている
 *
 */
/*
  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <anthy/alloc.h>
#include <anthy/logger.h>

/**/
#define PAGE_MAGIC 0x12345678
#define PAGE_SIZE 2048

/* ページ使用量の合計、デバッグの時等に用いる */
static int nr_pages;

/* page内のオブジェクトを表すオブジェクト */
struct chunk {
  void *storage[1];
};
#define CHUNK_HEADER_SIZE ((size_t)&((struct chunk *)0)->storage)
/* CPUもしくは、OSの種類によって要求されるアライメント */
#define CHUNK_ALIGN (sizeof(double))

/*
 * pageのstorage中には 
 * max_obj = (PAGE_SIZE - PAGE_HEADER_SIZE) / (size + CHUNK_HEADER_SIZE)個の
 * スロットがある。そのうちuse_count個のスロットがfree_listにつながっている、
 * もしくは使用中である。
 */
struct page {
  int magic;
  struct page *prev, *next;
};


#define PAGE_HEADER_SIZE (sizeof(struct page))
#define PAGE_AVAIL(p) ((unsigned char*)p + sizeof(struct page))
#define PAGE_STORAGE(a, p) (((unsigned char *)p) + (a->storage_offset))
#define PAGE_CHUNK(a, p, i) (struct chunk*)(&PAGE_STORAGE(a, p)[((a->size) + CHUNK_HEADER_SIZE) * (i)])


/**/
struct allocator_priv {
  /* 構造体のサイズ */
  int size;
  /* ページ内に入れることができるオブジェクトの数 */
  int max_num;
  /* 
     実際のデータが格納され始める場所のオフセット 
     ページ中のこれより手前には対応する場所のデータが使われているかどうかを0/1で表す
     ビットマップがある
   */
  int storage_offset;
  /* このallocatorが使用しているページのリスト */
  struct page page_list;
  /* allocatorのリスト */
  struct allocator_priv *next;
  /* sfreeした際に呼ばれる */
  void (*dtor)(void *);
};

static struct allocator_priv *allocator_list;

static int bit_test(unsigned char* bits, int pos)
{
  /*
     bit_getとほぼ同じだがbit != 0の時に0以外を返すことしか保証しない
   */
  return bits[pos >> 3] & (1 << (7 - (pos & 0x7)));
}


static int bit_set(unsigned char* bits, int pos, int bit)
{
  unsigned char filter = 1 << (7 - (pos & 0x7));
  if (bit == 0) {
    return bits[pos >> 3] &= ~filter;
  } else {
    return bits[pos >> 3] |= filter;
  }
}


static struct chunk *
get_chunk_address(void *s)
{
  return (struct chunk *)
    ((unsigned long)s - CHUNK_HEADER_SIZE);
}

static struct page *
alloc_page(struct allocator_priv *ator)
{
  struct page *p;
  unsigned char* avail;
    
  p = malloc(PAGE_SIZE);
  if (!p) {
    return NULL;
  }

  p->magic = PAGE_MAGIC;
  avail = PAGE_AVAIL(p);
  memset(avail, 0, (ator->max_num >> 3) + 1);
  return p;
}

static struct chunk *
get_chunk_from_page(allocator a, struct page *p)
{
  int i;

  int num = a->max_num;
  unsigned char* avail = PAGE_AVAIL(p);

  for (i = 0; i < num; ++i) {
    if (bit_test(avail, i) == 0) {
      bit_set(avail, i, 1);
      return PAGE_CHUNK(a, p, i);
    }
  }
  return NULL;  
}

static int
roundup_align(int num)
{
  num = num + (CHUNK_ALIGN - 1);
  num /= CHUNK_ALIGN;
  num *= CHUNK_ALIGN;
  return num;
}

static int
calc_max_num(int size)
{
  int area, bits;
  /* ビット数で計算
   * 厳密な最適解ではない
   */
  area = (PAGE_SIZE - PAGE_HEADER_SIZE - CHUNK_ALIGN) * 8;
  bits = (size + CHUNK_HEADER_SIZE) * 8 + 1;
  return (int)(area / bits);
}

allocator
anthy_create_allocator(int size, void (*dtor)(void *))
{
  allocator a;
size=roundup_align(size);
  if (size > (int)(PAGE_SIZE - PAGE_HEADER_SIZE - CHUNK_HEADER_SIZE)) {
    anthy_log(0, "Fatal error: too big allocator is requested.\n");
    exit(1);
  }
  a = malloc(sizeof(*a));
  if (!a) {
    anthy_log(0, "Fatal error: Failed to allocate memory.\n");
    exit(1);
  }
  a->size = size;
  a->max_num = calc_max_num(size); 
  a->storage_offset = roundup_align(sizeof(struct page) + a->max_num / 8 + 1);
  /*printf("size=%d max_num=%d offset=%d area=%d\n", size, a->max_num, a->storage_offset, size*a->max_num + a->storage_offset);*/
  a->dtor = dtor;
  a->page_list.next = &a->page_list;
  a->page_list.prev = &a->page_list;
  a->next = allocator_list;
  allocator_list = a;
  return a;
}

static void
anthy_free_allocator_internal(allocator a)
{
  struct page *p, *p_next;

  /* 各ページのメモリを解放する */
  for (p = a->page_list.next; p != &a->page_list; p = p_next) {
    unsigned char* avail = PAGE_AVAIL(p);
    int i;

    p_next = p->next;
    if (a->dtor) {
      for (i = 0; i < a->max_num; i++) {
	if (bit_test(avail, i)) {
	  struct chunk *c;

	  bit_set(avail, i, 0);
	  c = PAGE_CHUNK(a, p, i);
	  a->dtor(c->storage);
	}
      }
    }
    free(p);
    nr_pages--;
  }
  free(a);
}

void
anthy_free_allocator(allocator a)
{
  allocator a0, *a_prev_p;

  /* リストからaの前の要素を見付ける */
  a_prev_p = &allocator_list;
  for (a0 = allocator_list; a0; a0 = a0->next) {
    if (a == a0)
      break;
    else
      a_prev_p = &a0->next;
  }
  /* aをリストから外す */
  *a_prev_p = a->next;

  anthy_free_allocator_internal(a);
}

void *
anthy_smalloc(allocator a)
{
  struct page *p;
  struct chunk *c;

  /* 空いてるページをさがす */
  for (p = a->page_list.next; p != &a->page_list; p = p->next) {
    c = get_chunk_from_page(a, p);
    if (c) {
      return c->storage;
    }
  }
  /* ページを作って、リンクする */
  p = alloc_page(a);
  if (!p) {
    anthy_log(0, "Fatal error: Failed to allocate memory.\n");
    return NULL;
  }
  nr_pages++;

  p->next = a->page_list.next;
  p->prev = &a->page_list;
  a->page_list.next->prev = p;
  a->page_list.next = p;
  /* やり直す */
  return anthy_smalloc(a);
}

void
anthy_sfree(allocator a, void *ptr)
{
  struct chunk *c = get_chunk_address(ptr);
  struct page *p;
  int index;
  /* ポインタの含まれるページを探す */
  for (p = a->page_list.next; p != &a->page_list; p = p->next) {
    if ((unsigned long)p < (unsigned long)c &&
	(unsigned long)c < (unsigned long)p + PAGE_SIZE) {
      break;
    }
  }

  /* sanity check */
  if (!p || p->magic != PAGE_MAGIC) {
    anthy_log(0, "sfree()ing Invalid Object\n");
    abort();
  }

  /* ページ中の何番目のオブジェクトかを求める */
  index = ((unsigned long)c - (unsigned long)PAGE_STORAGE(a, p)) /
    (a->size + CHUNK_HEADER_SIZE);  
  bit_set(PAGE_AVAIL(p), index, 0);

  /* デストラクタを呼ぶ */
  if (a->dtor) {
    a->dtor(ptr);
  }
}

void
anthy_quit_allocator(void)
{
  allocator a, a_next;
  for (a = allocator_list; a; a = a_next) {
    a_next = a->next;
    anthy_free_allocator_internal(a);
  }
  allocator_list = NULL;
}