Référence du fichier bin_tree.c

Fonctions de gestion d'arbres binaires. Plus de détails...

#include "bin_tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

Aller au code source de ce fichier.

Fonctions
pair_t	btInsert (bin_tree_t **tree, void *data, int(*compar)(const void *newData, const void *nodeData))
pair_t	btFind (bin_tree_t **tree, const void *data, int(*compar)(const void *newData, const void *nodeData))
bin_tree_t **	btFirst (bin_tree_t **ptr)
bin_tree_t **	btLast (bin_tree_t **ptr)
void	btDelete (bin_tree_t **ptr, void(*freeData)(void *))
bin_tree_t **	btNext (bin_tree_t **ptr)
void	btFree (bin_tree_t **tree, void(*freeData)(void *))
void	btForAll (bin_tree_t *ptr, void(*todo)(void *, void **), void **ldata)

Description détaillée

Fonctions de gestion d'arbres binaires.

Auteur

Fares BELHADJ amsi@.nosp@m.ai.u.nosp@m.niv-p.nosp@m.aris.nosp@m.8.fr

Date

January 16, 2006 - June 01, 2010

Définition dans le fichier bin_tree.c.

Documentation des fonctions

btDelete()

void btDelete	(	bin_tree_t **	ptr,
		void(*)(void *)	freeData
	)

                                                           {
  bin_tree_t * todelete = *ptr, ** ptr2 = ptr, * lrc;
  if(todelete->lc) {
    *ptr = todelete->lc;
    (*ptr)->next = todelete->next;
    lrc = (*ptr)->lc;
    while(lrc) {
      lrc->next = ptr;
      lrc = lrc->rc;
    }
    while((*ptr2)->rc) {
      (*ptr2)->rc->next = todelete->next;
      ptr2 = &((*ptr2)->rc);
    }
    (*ptr2)->rc = todelete->rc;
    if(todelete->rc) {
      lrc = todelete->rc->lc;
      while(lrc) {
    lrc->next = &((*ptr2)->rc);
    lrc = lrc->rc;
      }
    }
  } else {
    *ptr = todelete->rc;
    if(todelete->rc) {
      lrc = todelete->rc->lc;
      while(lrc) {
        lrc->next = ptr;
        lrc = lrc->rc;
      }
    }
  }
  if(freeData)
    freeData(todelete->data);
  free(todelete);
}

Références bin_tree_t::data, bin_tree_t::lc, bin_tree_t::next, et bin_tree_t::rc.

Référencé par gl4duDeleteMatrix().

btFind()

pair_t btFind	(	bin_tree_t **	tree,
		const void *	data,
		int(*)(const void *newData, const void *nodeData)	compar
	)

                                                                                                                 {
  pair_t res = {(void **)tree, -1};
  while(*((bin_tree_t **)res.ptr)) {
    if((res.compResult = compar(data, (*((bin_tree_t **)res.ptr))->data)) < 0)
      res.ptr = (void **)&((*((bin_tree_t **)res.ptr))->lc);
    else if(res.compResult > 0)
      res.ptr = (void **)&((*((bin_tree_t **)res.ptr))->rc);
    else
      return res;
  }
  return res;
}

Références pair_t::compResult, et pair_t::ptr.

Référencé par findMatrix(), gl4duGenMatrix(), gl4duIsMatrix(), gl4duwBindWindow(), gl4duwCreateWindow(), et manageEvents().

btFirst()

bin_tree_t** btFirst

(

bin_tree_t **

ptr

)

                                         {
  bin_tree_t ** f = ptr;
  while(*ptr) {
    f = ptr;
    ptr = &((*ptr)->lc);
  }
  return f;
}

Référencé par btNext().

btForAll()

void btForAll	(	bin_tree_t *	ptr,
		void(*)(void *, void **)	todo,
		void **	ldata
	)

                                                                              {
  if(ptr->lc)
    btForAll(ptr->lc, todo, ldata);
  todo(ptr->data, ldata);
  if(ptr->rc)
    btForAll(ptr->rc, todo, ldata);
}

Références btForAll(), bin_tree_t::data, bin_tree_t::lc, et bin_tree_t::rc.

Référencé par btForAll(), gl4duSendMatrices(), et gl4duwMainLoop().

btFree()

void btFree	(	bin_tree_t **	tree,
		void(*)(void *)	freeData
	)

                                                          {
  if(!(*tree)) return;
  if((*tree)->lc) btFree(&((*tree)->lc), freeData);
  if((*tree)->rc) btFree(&((*tree)->rc), freeData);
  freeData((*tree)->data);
  free(*tree);
  (*tree) = NULL;
}

Référencé par gl4duClean(), et quit().

btInsert()

pair_t btInsert	(	bin_tree_t **	tree,
		void *	data,
		int(*)(const void *newData, const void *nodeData)	compar
	)

                                                                                                             {
  bin_tree_t ** next = *tree ? (*tree)->next : NULL /* correspond au parent du dernier fils gauche */;
  pair_t res = {(void **)tree, -1};
  while(*((bin_tree_t **)res.ptr)) {
    if((res.compResult = compar(data, (*((bin_tree_t **)res.ptr))->data)) < 0) {
      next = (bin_tree_t **)res.ptr;
      res.ptr = (void **)&((*((bin_tree_t **)res.ptr))->lc);
    } else if(res.compResult > 0) {
      res.ptr = (void **)&((*((bin_tree_t **)res.ptr))->rc);
    } else
      return res;
  }
  (*((bin_tree_t **)res.ptr)) = calloc(1, sizeof (bin_tree_t));
  assert(*res.ptr);
  (*((bin_tree_t **)res.ptr))->data = data;
  (*((bin_tree_t **)res.ptr))->next = next;
  return res;
}

Références pair_t::compResult, bin_tree_t::next, et pair_t::ptr.

Référencé par gl4duGenMatrix(), et gl4duwCreateWindow().

btLast()

bin_tree_t** btLast

(

bin_tree_t **

ptr

)

                                        {
  bin_tree_t ** l = ptr;
  while(*ptr) {
    l = ptr;
    ptr = &((*ptr)->rc);
  }
  return l;
}

btNext()

bin_tree_t** btNext

(

bin_tree_t **

ptr

)

                                        {
  return (*ptr)->rc ? btFirst(&((*ptr)->rc)) : (*ptr)->next;
}

Références btFirst(), bin_tree_t::next, et bin_tree_t::rc.