Référence du fichier fixed_heap.c

gestion de tas d'éléments à taille fixe. Plus de détails...

#include "fixed_heap.h"
#include <stdlib.h>
#include <assert.h>

Graphe des dépendances par inclusion de fixed_heap.c:

Aller au code source de ce fichier.

Structures de données
struct	fheap_t

Définitions de type
typedef struct fheap_t	fheap_t

Fonctions
static fheap_t	_newheap (size_t nmem, size_t size)
static void	_moreheap (fheap_t *h)
static void	_push (size_t *stack, size_t *head, size_t value)
static size_t	_pop (size_t *stack, size_t *head)
static int	_empty (size_t head)
size_t	fheapCreate (size_t nmem, size_t size)
	créé un tas de nmem éléments de taille size et retourne son id (<>0). Plus de détails...
size_t	fheapPut (size_t heap_id, void *element)
	insert, en copiant le contenu, un élément dans le tas et retourne son id (<>0). Plus de détails...
void *	fheapGet (size_t heap_id, size_t element_id)
	récupère un élément du tas et retourne le pointeur vers la donnée. Attention, cette fonction n'efface pas la donnée du tas. Plus de détails...
void	fheapDelete (size_t heap_id, size_t element_id)
	libère une donnée du tas (étiquette une donnée du tas comme espace libre). Plus de détails...
void	fheapDestroy (size_t heap_id)
	libère l'ensemble du tas et sa mémoire. Plus de détails...
void	fheapClean (void)
	libère tous les tas créés par cette bibliothèque. Plus de détails...

Variables
static fheap_t	_heap = { 16, sizeof _heap, NULL, NULL, 0 }

Description détaillée

gestion de tas d'éléments à taille fixe.

Auteur

Farès BELHADJ amsi@.nosp@m.ai.u.nosp@m.niv-p.nosp@m.aris.nosp@m.8.fr

Date

November 30, 2016

Définition dans le fichier fixed_heap.c.

Documentation des définitions de type

fheap_t

typedef struct fheap_t fheap_t

Documentation des fonctions

_empty()

static int _empty ( size_t  head )

inlinestatic

                                      {
  return head == 0;
}

Référencé par fheapCreate(), et fheapPut().

_moreheap()

static void _moreheap ( fheap_t *  h )

static

                                   {
  size_t i, onmem = h->nmem;
  h->nmem <<= 1;
  h->heap = realloc(h->heap, h->nmem * h->size * sizeof *(h->heap));
  assert(h->heap);
  memset(&(h->heap[(h->nmem >> 1) * h->size]), 0, (h->nmem >> 1) * h->size);
  h->stack = realloc(h->stack, h->nmem * sizeof *(h->stack));
  assert(h->stack);
  h->head = 0;
  for(i = onmem; i < h->nmem; ++i)
    _push(h->stack, &(h->head), onmem + h->nmem - 1 - i);
}

Références _push(), fheap_t::head, fheap_t::heap, fheap_t::nmem, fheap_t::size, et fheap_t::stack.

Référencé par fheapCreate(), et fheapPut().

_newheap()

static fheap_t _newheap ( size_t  nmem, size_t  size  )

static

                                                  {
  size_t i;
  fheap_t h;
  h.nmem = nmem;
  h.size = size;
  h.heap = calloc(nmem, size * sizeof *(h.heap));
  assert(h.heap);
  h.stack = malloc(nmem * sizeof *(h.stack));
  assert(h.stack);
  h.head = 0;
  for(i = 0; i < nmem; ++i)
    _push(h.stack, &(h.head), nmem - 1 - i);
  return h;
}

Références _push(), fheap_t::head, fheap_t::heap, fheap_t::nmem, fheap_t::size, et fheap_t::stack.

Référencé par fheapCreate().

_pop()

static size_t _pop ( size_t *  stack, size_t *  head  )

inlinestatic

                                                         {
  return stack[--(*head)] + 1;
}

Référencé par fheapCreate(), et fheapPut().

_push()

static void _push ( size_t *  stack, size_t *  head, size_t  value  )

inlinestatic

                                                                      {
  stack[(*head)++] = value;
}

Référencé par _moreheap(), _newheap(), fheapDelete(), et fheapDestroy().

fheapClean()

void fheapClean

(

void

)

libère tous les tas créés par cette bibliothèque.

                      {
  size_t i;
  fheap_t * h;
  if(!_heap.heap) return;
  for(i = 0; i < _heap.nmem; i++) {
    h = &(((fheap_t * )_heap.heap)[i]);
    if(h->heap)
      fheapDestroy(i + 1);
  }
  free(_heap.heap);
  _heap.heap = NULL;
  free(_heap.stack);
  _heap.stack = NULL;
  _heap.head = 0;
  _heap.size = 16;
}

Références _heap, fheapDestroy(), fheap_t::head, fheap_t::heap, fheap_t::nmem, fheap_t::size, et fheap_t::stack.

Référencé par fheapCreate().

fheapCreate()

size_t fheapCreate	(	size_t	nmem,
		size_t	size
	)

créé un tas de nmem éléments de taille size et retourne son id (<>0).

Paramètres

nmem	nombre initial d'éléments dans le tas.
size	taille, en octets, d'éléments du tas.

Renvoie

identifiant du tas créé (différent de 0).

                                             {
  fheap_t * h;
  size_t heap_id;
  static int ft = 1;
  if(_heap.heap == NULL) {
    _heap = _newheap(_heap.nmem, _heap.size);
    if(ft) gl4duAtExit(fheapClean);
    ft = 0;
  }
  heap_id = _pop(_heap.stack, &(_heap.head));
  if(_empty(_heap.head))
    _moreheap(&_heap);
  h = &(((fheap_t * )_heap.heap)[heap_id - 1]);
  *h =_newheap(nmem, size);
  return heap_id;
}

Références _empty(), _heap, _moreheap(), _newheap(), _pop(), fheapClean(), gl4duAtExit(), fheap_t::head, fheap_t::heap, fheap_t::nmem, fheap_t::size, et fheap_t::stack.

fheapDelete()

void fheapDelete	(	size_t	heap_id,
		size_t	element_id
	)

libère une donnée du tas (étiquette une donnée du tas comme espace libre).

Paramètres

heap_id	identifiant du tas duquel la donnée est libérée.
element_id	identifiant de la donnée à libérer.

                                                    {
  fheap_t * h = &(((fheap_t * )_heap.heap)[heap_id - 1]);
  _push(h->stack, &(h->head), --element_id);
}

Références _heap, _push(), fheap_t::head, fheap_t::heap, et fheap_t::stack.

fheapDestroy()

void fheapDestroy

(

size_t

heap_id

)

libère l'ensemble du tas et sa mémoire.

Paramètres

heap_id

identifiant du tas à libérer.

                                  {
  fheap_t * h = &(((fheap_t * )_heap.heap)[heap_id - 1]);
  free(h->heap); 
  h->heap = NULL;
  free(h->stack);
  h->stack = NULL;
  _push(_heap.stack, &(_heap.head), heap_id - 1);
}

Références _heap, _push(), fheap_t::head, fheap_t::heap, et fheap_t::stack.

Référencé par fheapClean().

fheapGet()

void* fheapGet	(	size_t	heap_id,
		size_t	element_id
	)

récupère un élément du tas et retourne le pointeur vers la donnée. Attention, cette fonction n'efface pas la donnée du tas.

Paramètres

heap_id	identifiant du tas duquel est extraite la donnée.
element_id	identifiant de la donnée à extraire.

Renvoie

pointeur vers la donnée extraite.

                                                   {
  fheap_t * h = &(((fheap_t * )_heap.heap)[heap_id - 1]);
  return &(h->heap[--element_id * h->size]);
}

Références _heap, fheap_t::heap, et fheap_t::size.

fheapPut()

size_t fheapPut	(	size_t	heap_id,
		void *	element
	)

insert, en copiant le contenu, un élément dans le tas et retourne son id (<>0).

Paramètres

heap_id	identifiant du tas dans lequel se passe l'insertion.
element	pointeur vers la donnée à insérer (copier).

Renvoie

identifiant de l'élément inséré dans le tas (différent de 0).

                                                {
  fheap_t * h = &(((fheap_t * )_heap.heap)[heap_id - 1]);
  size_t element_id = _pop(h->stack, &(h->head));
  if(_empty(h->head))
    _moreheap(h);
  memcpy(&(h->heap[(element_id - 1) * h->size]), element, h->size);
  return element_id;
}

Références _empty(), _heap, _moreheap(), _pop(), fheap_t::head, fheap_t::heap, fheap_t::size, et fheap_t::stack.

Documentation des variables

_heap

fheap_t _heap = { 16, sizeof _heap, NULL, NULL, 0 }

static

Référencé par fheapClean(), fheapCreate(), fheapDelete(), fheapDestroy(), fheapGet(), et fheapPut().