git.maemo.org Git - navit-package/blob - navit/fib-1.1/fibpriv.h

   1 /*-
   2  * Copyright 1997, 1999-2003 John-Mark Gurney.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  *      $Id: fibpriv.h,v 1.1 2005-12-02 10:41:56 martin-s Exp $
  27  *
  28  */
  29
  30 #ifndef _FIBPRIV_H_
  31 #define _FIBPRIV_H_
  32
  33 struct fibheap_el;
  34
  35 /*
  36  * global heap operations
  37  */
  38 struct fibheap {
  39         int     (*fh_cmp_fnct)(void *, void *);
  40         int     fh_n;
  41         int     fh_Dl;
  42         struct  fibheap_el **fh_cons;
  43         struct  fibheap_el *fh_min;
  44         struct  fibheap_el *fh_root;
  45         void    *fh_neginf;
  46         int     fh_keys         : 1;
  47 #ifdef FH_STATS
  48         int     fh_maxn;
  49         int     fh_ninserts;
  50         int     fh_nextracts;
  51 #endif
  52 };
  53
  54 static void fh_initheap(struct fibheap *);
  55 static void fh_insertrootlist(struct fibheap *, struct fibheap_el *);
  56 static void fh_removerootlist(struct fibheap *, struct fibheap_el *);
  57 static void fh_consolidate(struct fibheap *);
  58 static void fh_heaplink(struct fibheap *h, struct fibheap_el *y,
  59                         struct fibheap_el *x);
  60 static void fh_cut(struct fibheap *, struct fibheap_el *, struct fibheap_el *);
  61 static void fh_cascading_cut(struct fibheap *, struct fibheap_el *);
  62 static struct fibheap_el *fh_extractminel(struct fibheap *);
  63 static void fh_checkcons(struct fibheap *h);
  64 static void fh_destroyheap(struct fibheap *h);
  65 static int fh_compare(struct fibheap *h, struct fibheap_el *a,
  66                         struct fibheap_el *b);
  67 static int fh_comparedata(struct fibheap *h, int key, void *data,
  68                         struct fibheap_el *b);
  69 static void fh_insertel(struct fibheap *h, struct fibheap_el *x);
  70 static void fh_deleteel(struct fibheap *h, struct fibheap_el *x);
  71
  72 /*
  73  * specific node operations
  74  */
  75 struct fibheap_el {
  76         int     fhe_degree;
  77         int     fhe_mark;
  78         struct  fibheap_el *fhe_p;
  79         struct  fibheap_el *fhe_child;
  80         struct  fibheap_el *fhe_left;
  81         struct  fibheap_el *fhe_right;
  82         int     fhe_key;
  83         void    *fhe_data;
  84 };
  85
  86 static struct fibheap_el *fhe_newelem(void);
  87 static void fhe_initelem(struct fibheap_el *);
  88 static void fhe_insertafter(struct fibheap_el *a, struct fibheap_el *b);
  89 static inline void fhe_insertbefore(struct fibheap_el *a, struct fibheap_el *b);
  90 static struct fibheap_el *fhe_remove(struct fibheap_el *a);
  91 #define fhe_destroy(x)  free((x))
  92
  93 /*
  94  * general functions
  95  */
  96 static inline int ceillog2(unsigned int a);
  97
  98 #endif /* _FIBPRIV_H_ */