thodg/libgit2/src/pool.c

• Show log

  Commit

• Hash : da3b391c
  Author :
  Date : 2012-04-18T10:57:08
  

  Convert revwalk to use git_pool This removes the custom paged allocator from revwalk and replaces it with a `git_pool`.

Download

• src/pool.c

• #include "pool.h"
  #ifndef GIT_WIN32
  #include <unistd.h>
  #endif
  
  struct git_pool_page {
  	git_pool_page *next;
  	uint32_t size;
  	uint32_t avail;
  	char data[GIT_FLEX_ARRAY];
  };
  
  #define GIT_POOL_MIN_USABLE	4
  #define GIT_POOL_MIN_PAGESZ	2 * sizeof(void*)
  
  static void *pool_alloc_page(git_pool *pool, uint32_t size);
  static void pool_insert_page(git_pool *pool, git_pool_page *page);
  
  int git_pool_init(
  	git_pool *pool, uint32_t item_size, uint32_t items_per_page)
  {
  	assert(pool);
  
  	if (!item_size)
  		item_size = 1;
  	/* round up item_size for decent object alignment */
  	if (item_size > 4)
  		item_size = (item_size + 7) & ~7;
  	else if (item_size == 3)
  		item_size = 4;
  
  	if (!items_per_page)
  		items_per_page = git_pool__suggest_items_per_page(item_size);
  	if (item_size * items_per_page < GIT_POOL_MIN_PAGESZ)
  		items_per_page = (GIT_POOL_MIN_PAGESZ + item_size - 1) / item_size;
  
  	memset(pool, 0, sizeof(git_pool));
  	pool->item_size = item_size;
  	pool->page_size = item_size * items_per_page;
  
  	return 0;
  }
  
  void git_pool_clear(git_pool *pool)
  {
  	git_pool_page *scan, *next;
  
  	for (scan = pool->open; scan != NULL; scan = next) {
  		next = scan->next;
  		git__free(scan);
  	}
  	pool->open = NULL;
  
  	for (scan = pool->full; scan != NULL; scan = next) {
  		next = scan->next;
  		git__free(scan);
  	}
  	pool->full = NULL;
  
  	pool->free_list = NULL;
  
  	pool->items = 0;
  
  	pool->has_string_alloc     = 0;
  	pool->has_multi_item_alloc = 0;
  	pool->has_large_page_alloc = 0;
  }
  
  void git_pool_swap(git_pool *a, git_pool *b)
  {
  	git_pool temp;
  
  	if (a == b)
  		return;
  
  	memcpy(&temp, a, sizeof(temp));
  	memcpy(a, b, sizeof(temp));
  	memcpy(b, &temp, sizeof(temp));
  }
  
  static void pool_insert_page(git_pool *pool, git_pool_page *page)
  {
  	git_pool_page *scan;
  
  	/* If there are no open pages or this page has the most open space,
  	 * insert it at the beginning of the list.  This is the common case.
  	 */
  	if (pool->open == NULL || pool->open->avail < page->avail) {
  		page->next = pool->open;
  		pool->open = page;
  		return;
  	}
  
  	/* Otherwise insert into sorted position. */
  	for (scan = pool->open;
  		 scan->next && scan->next->avail > page->avail;
  		 scan = scan->next);
  	page->next = scan->next;
  	scan->next = page;
  }
  
  static void *pool_alloc_page(git_pool *pool, uint32_t size)
  {
  	git_pool_page *page;
  	uint32_t alloc_size;
  
  	if (size <= pool->page_size)
  		alloc_size = pool->page_size;
  	else {
  		alloc_size = size;
  		pool->has_large_page_alloc = 1;
  	}
  
  	page = git__calloc(1, alloc_size + sizeof(git_pool_page));
  	if (!page)
  		return NULL;
  
  	page->size  = alloc_size;
  	page->avail = alloc_size - size;
  
  	if (page->avail > 0)
  		pool_insert_page(pool, page);
  	else {
  		page->next = pool->full;
  		pool->full = page;
  	}
  
  	pool->items++;
  
  	return page->data;
  }
  
  GIT_INLINE(void) pool_remove_page(
  	git_pool *pool, git_pool_page *page, git_pool_page *prev)
  {
  	if (prev == NULL)
  		pool->open = page->next;
  	else
  		prev->next = page->next;
  }
  
  void *git_pool_malloc(git_pool *pool, uint32_t items)
  {
  	git_pool_page *scan = pool->open, *prev;
  	uint32_t size = items * pool->item_size;
  	void *ptr = NULL;
  
  	pool->has_string_alloc = 0;
  	if (items > 1)
  		pool->has_multi_item_alloc = 1;
  	else if (pool->free_list != NULL) {
  		ptr = pool->free_list;
  		pool->free_list = *((void **)pool->free_list);
  		return ptr;
  	}
  
  	/* just add a block if there is no open one to accomodate this */
  	if (size >= pool->page_size || !scan || scan->avail < size)
  		return pool_alloc_page(pool, size);
  
  	pool->items++;
  
  	/* find smallest block in free list with space */
  	for (scan = pool->open, prev = NULL;
  		 scan->next && scan->next->avail >= size;
  		 prev = scan, scan = scan->next);
  
  	/* allocate space from the block */
  	ptr = &scan->data[scan->size - scan->avail];
  	scan->avail -= size;
  
  	/* move to full list if there is almost no space left */
  	if (scan->avail < pool->item_size || scan->avail < GIT_POOL_MIN_USABLE) {
  		pool_remove_page(pool, scan, prev);
  		scan->next = pool->full;
  		pool->full = scan;
  	}
  	/* reorder list if block is now smaller than the one after it */
  	else if (scan->next != NULL && scan->next->avail > scan->avail) {
  		pool_remove_page(pool, scan, prev);
  		pool_insert_page(pool, scan);
  	}
  
  	return ptr;
  }
  
  char *git_pool_strndup(git_pool *pool, const char *str, size_t n)
  {
  	void *ptr = NULL;
  
  	assert(pool && str && pool->item_size == sizeof(char));
  
  	if ((ptr = git_pool_malloc(pool, n + 1)) != NULL) {
  		memcpy(ptr, str, n);
  		*(((char *)ptr) + n) = '\0';
  	}
  	pool->has_string_alloc = 1;
  
  	return ptr;
  }
  
  char *git_pool_strdup(git_pool *pool, const char *str)
  {
  	assert(pool && str && pool->item_size == sizeof(char));
  
  	return git_pool_strndup(pool, str, strlen(str));
  }
  
  char *git_pool_strcat(git_pool *pool, const char *a, const char *b)
  {
  	void *ptr;
  	size_t len_a, len_b;
  
  	assert(pool && a && b && pool->item_size == sizeof(char));
  
  	len_a = a ? strlen(a) : 0;
  	len_b = b ? strlen(b) : 0;
  
  	if ((ptr = git_pool_malloc(pool, len_a + len_b + 1)) != NULL) {
  		if (len_a)
  			memcpy(ptr, a, len_a);
  		if (len_b)
  			memcpy(((char *)ptr) + len_a, b, len_b);
  		*(((char *)ptr) + len_a + len_b) = '\0';
  	}
  	pool->has_string_alloc = 1;
  
  	return ptr;
  }
  
  void git_pool_free(git_pool *pool, void *ptr)
  {
  	assert(pool && ptr && pool->item_size >= sizeof(void*));
  
  	*((void **)ptr) = pool->free_list;
  	pool->free_list = ptr;
  }
  
  uint32_t git_pool__open_pages(git_pool *pool)
  {
  	uint32_t ct = 0;
  	git_pool_page *scan;
  	for (scan = pool->open; scan != NULL; scan = scan->next) ct++;
  	return ct;
  }
  
  uint32_t git_pool__full_pages(git_pool *pool)
  {
  	uint32_t ct = 0;
  	git_pool_page *scan;
  	for (scan = pool->full; scan != NULL; scan = scan->next) ct++;
  	return ct;
  }
  
  bool git_pool__ptr_in_pool(git_pool *pool, void *ptr)
  {
  	git_pool_page *scan;
  	for (scan = pool->open; scan != NULL; scan = scan->next)
  		if ( ((void *)scan->data) <= ptr &&
  			(((void *)scan->data) + scan->size) > ptr)
  			return true;
  	for (scan = pool->full; scan != NULL; scan = scan->next)
  		if ( ((void *)scan->data) <= ptr &&
  			(((void *)scan->data) + scan->size) > ptr)
  			return true;
  	return false;
  }
  
  uint32_t git_pool__system_page_size(void)
  {
  	static uint32_t size = 0;
  
  	if (!size) {
  #ifdef GIT_WIN32
  		SYSTEM_INFO info;
  		GetSystemInfo(&info);
  		size = (uint32_t)info.dwPageSize;
  #else
  		size = (uint32_t)sysconf(_SC_PAGE_SIZE);
  #endif
  
  		size -= 2 * sizeof(void *); /* allow space for malloc overhead */
  	}
  
  	return size;
  }
  
  uint32_t git_pool__suggest_items_per_page(uint32_t item_size)
  {
  	uint32_t page_bytes =
  		git_pool__system_page_size() - sizeof(git_pool_page);
  	return page_bytes / item_size;
  }
  
  

Download