priority_queue.h

Go to the documentation of this file.

/*

  Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.

  This program is free software; you can redistribute it and/or modify it
  under the terms of version 2 of the GNU General Public License as
  published by the Free Software Foundation.

  This program is distributed in the hope that it would be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

  Further, this software is distributed without any warranty that it is
  free of the rightful claim of any third person regarding infringement 
  or the like.  Any license provided herein, whether implied or 
  otherwise, applies only to this software file.  Patent licenses, if 
  any, provided herein do not apply to combinations of this program with 
  other software, or any other product whatsoever.  

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

  Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
  Mountain View, CA 94043, or:

  http://www.sgi.com

  For further information regarding this notice, see:

  http://oss.sgi.com/projects/GenInfo/NoticeExplan

*/


#ifndef prq_INCLUDED
#define prq_INCLUDED
#ifdef __cplusplus
extern "C" {
#endif

#ifdef _KEEP_RCS_ID
#ifndef PRQ_RCS_ID
#define PRQ_RCS_ID
#endif
#endif

#include "defs.h"

struct mem_pool;

typedef BOOL  (*PRQ_COMPARISON_FUNCTION) (void*,void*);
typedef INT32 (*PRQ_GET_INDEX_FUNCTION)(void*);
typedef void (*PRQ_SET_INDEX_FUNCTION)(void*,INT);
typedef void (*PRQ_ELEMENT_PRINT_FUNCTION)(void*);

typedef struct prq {
    PRQ_COMPARISON_FUNCTION comparison_fn;
                    /*  Function used to compare keys.
                     */
    struct mem_pool* mem_pool;
                    /* Where to [re]allocate
                     */
    INT32 size;
                    /*  Number of elements in the heap.
                     */
    INT32 allocated_size;
                    /*  Number of elements 'heap_vector' can hold.
                     */

    INT32 expansion_factor;
                    /*  Amount to grow heap.
                     */

    PRQ_GET_INDEX_FUNCTION get_index_fn;
    PRQ_SET_INDEX_FUNCTION set_index_fn;
                    /*  Functions to get/set the index of a heap element.
                     */

    void** heap_vector;
                    /*  The vector used to hold the heap elements.  It is
                     *  dynamically allocated.  It is a standard C 0-origin
                     *  vector.  Access utilities are used to map the 1-origin
                     *  indexing used by the heap algorithms onto the 0-origin
                     *  'heap_vector'.
                     */
} PRQ;


extern void
PRQ_Initialize(
    PRQ*                    prq,
    PRQ_COMPARISON_FUNCTION comparison_fn,
    PRQ_GET_INDEX_FUNCTION  get_fn,
    PRQ_SET_INDEX_FUNCTION  set_fn,
    MEM_POOL*               pool,
    INT32                   initial_size,
    INT32                   expansion_factor
);

extern void*
PRQ_Delete_Top(
    PRQ*    prq
);

extern void*
PRQ_Top(
    PRQ*    prq
);

extern void
PRQ_Insert(
    PRQ*    prq,
    void*   element
);

extern void
PRQ_Remove(
    PRQ*    prq,
    void*   element
);

extern void
PRQ_Reset(
    PRQ*    prq
);

extern INT32
PRQ_Size(
    PRQ*    prq
);

extern void*
PRQ_Ith(
    PRQ*    prq,
    INT32   i
);


/* Look Ma, no templates!
 */

/* Generate the names used in the typesafe interface and invoke the low
 * level interface generation macro:
 */
#define TYPE_PRQ(base_type,prq_type)                                    \
    _TYPE_PRQ(base_type,                                                \
              prq_type,                                                 \
              prq_type##_COMPARISON_FUNCTION,                           \
              prq_type##_GET_INDEX_FUNCTION,                            \
              prq_type##_SET_INDEX_FUNCTION,                            \
              prq_type##_Initialize,                                    \
              prq_type##_Delete_Top,                                    \
              prq_type##_Top,                                           \
              prq_type##_Insert,                                        \
              prq_type##_Remove,                                        \
              prq_type##_Reset,                                         \
              prq_type##_Size,                                          \
              prq_type##_Ith)


/* Actually generate the typesafe interface:
 */
#define _TYPE_PRQ(base_type,                                            \
                  prq_type,                                             \
                  comparison_function_type,                             \
                  get_index_function_type,                              \
                  set_index_function_type,                              \
                  initialize_function_name,                             \
                  delete_top_function_name,                             \
                  top_function_name,                                    \
                  insert_function_name,                                 \
                  remove_function_name,                                 \
                  reset_function_name,                                  \
                  size_function_name,                                   \
                  ith_function_name)                                    \
                                                                        \
typedef PRQ prq_type;                                                   \
                                                                        \
typedef INT (*comparison_function_type)(base_type*,base_type*);         \
typedef INT32 (*get_index_function_type)(base_type*);                   \
typedef void (*set_index_function_type)(base_type*,INT32);              \
                                                                        \
/*REFERENCED*/                                                          \
inline base_type*                                                       \
delete_top_function_name(                                               \
  prq_type* prq                                                         \
)                                                                       \
{                                                                       \
  return (base_type*) PRQ_Delete_Top((PRQ*) prq);                       \
}                                                                       \
                                                                        \
/*REFERENCED*/                                                          \
inline base_type*                                                       \
top_function_name(                                                      \
  prq_type* prq                                                         \
)                                                                       \
{                                                                       \
  return (base_type*) PRQ_Top((PRQ*) prq);                              \
}                                                                       \
                                                                        \
/*REFERENCED*/                                                          \
inline void                                                             \
insert_function_name(                                                   \
  prq_type*    prq,                                                     \
  base_type*   element                                                  \
)                                                                       \
{                                                                       \
  PRQ_Insert((PRQ*)prq,(void*)element);                                 \
}                                                                       \
                                                                        \
/*REFERENCED*/                                                          \
inline void                                                             \
remove_function_name(                                                   \
  prq_type*   prq,                                                      \
  base_type*  element                                                   \
)                                                                       \
{                                                                       \
  PRQ_Remove((PRQ*)prq,(void*)element);                                 \
}                                                                       \
                                                                        \
/*REFERENCED*/                                                          \
inline void                                                             \
reset_function_name(                                                    \
  prq_type* prq                                                         \
)                                                                       \
{                                                                       \
  PRQ_Reset((PRQ*)prq);                                                 \
}                                                                       \
                                                                        \
/*REFERENCED*/                                                          \
inline INT32                                                            \
size_function_name(                                                     \
  prq_type*   prq                                                       \
)                                                                       \
{                                                                       \
  return PRQ_Size((PRQ*)prq);                                           \
}                                                                       \
                                                                        \
/*REFERENCED*/                                                          \
inline base_type*                                                       \
ith_function_name(                                                      \
  prq_type* prq,                                                        \
  INT32     i                                                           \
)                                                                       \
{                                                                       \
  return (base_type*)PRQ_Ith((PRQ*)prq,i);                              \
}                                                                       \
                                                                        \
/*REFERENCED*/                                                          \
inline void                                                             \
initialize_function_name(                                               \
  prq_type*                 prq,                                        \
  comparison_function_type  comparison_fn,                              \
  get_index_function_type   get_index,                                  \
  set_index_function_type   set_index,                                  \
  MEM_POOL*                 pool,                                       \
  INT32                     initial_size,                               \
  INT32                     expansion_factor                            \
)                                                                       \
{                                                                       \
  PRQ_Initialize((PRQ*)prq,(PRQ_COMPARISON_FUNCTION)comparison_fn,      \
                           (PRQ_GET_INDEX_FUNCTION)get_index,           \
                           (PRQ_SET_INDEX_FUNCTION)set_index,           \
                           pool,                                        \
                           initial_size,                                \
                           expansion_factor);                           \
}


#ifdef __cplusplus
}
#endif
#endif