priority.c

Go to the documentation of this file.
00001 /****************************************************************************/
00002 /*                                                                          */
00003 /*  This file is part of QSopt_ex.                                          */
00004 /*                                                                          */
00005 /*  (c) Copyright 2006 by David Applegate, William Cook, Sanjeeb Dash,      */
00006 /*  and Daniel Espinoza                                                     */
00007 /*                                                                          */
00008 /*  Sanjeeb Dash ownership of copyright in QSopt_ex is derived from his     */
00009 /*  copyright in QSopt.                                                     */
00010 /*                                                                          */
00011 /*  This code may be used under the terms of the GNU General Public License */
00012 /*  (Version 2.1 or later) as published by the Free Software Foundation.    */
00013 /*                                                                          */
00014 /*  Alternatively, use is granted for research purposes only.               */
00015 /*                                                                          */
00016 /*  It is your choice of which of these two licenses you are operating      */
00017 /*  under.                                                                  */
00018 /*                                                                          */
00019 /*  We make no guarantees about the correctness or usefulness of this code. */
00020 /*                                                                          */
00021 /****************************************************************************/
00022 
00023 /* RCSINFO $Id: priority.c,v 1.2 2003/11/05 16:47:22 meven Exp $ */
00024 /****************************************************************************/
00025 /*                                                                          */
00026 /*  This file is part of CONCORDE                                           */
00027 /*                                                                          */
00028 /*  (c) Copyright 1995--1999 by David Applegate, Robert Bixby,              */
00029 /*  Vasek Chvatal, and William Cook                                         */
00030 /*                                                                          */
00031 /*  Permission is granted for academic research use.  For other uses,       */
00032 /*  contact the authors for licensing options.                              */
00033 /*                                                                          */
00034 /*  Use at your own risk.  We make no guarantees about the                  */
00035 /*  correctness or usefulness of this code.                                 */
00036 /*                                                                          */
00037 /****************************************************************************/
00038 
00039 /****************************************************************************/
00040 /*                                                                          */
00041 /*                      PRIORITY QUEUE ROUTINES                             */
00042 /*                                                                          */
00043 /*                                                                          */
00044 /*                              TSP CODE                                    */
00045 /*  Written by:  Applegate, Bixby, Chvatal, and Cook                        */
00046 /*  Date: March 3, 1997                                                     */
00047 /*        March 13, 2002 - Cook Modified for QS)                            */
00048 /*  Reference: R.E. Tarjan, Data Structures and Network Algorithms          */
00049 /*                                                                          */
00050 /*    EXPORTED FUNCTIONS:                                                   */
00051 /*                                                                          */
00052 /*  int ILLutil_priority_init (ILLpriority *pri, int k)                     */
00053 /*    -h should point to a ILLpriority struct.                              */
00054 /*    -k an initial allocation for the priority queue.                      */
00055 /*                                                                          */
00056 /*  void ILLutil_priority_free (ILLpriority *pri)                           */
00057 /*    -frees the spaces allocated for the ILLpriority queue.                */
00058 /*                                                                          */
00059 /*  void ILLutil_priority_findmin (ILLpriority *pri, double *keyval         */
00060 /*      void **en)                                                          */
00061 /*    -en the entry with least key value (NULL if no entries in heap).      */
00062 /*    -if (keyval != NULL), *keyval will be the minimum key value.          */
00063 /*                                                                          */
00064 /*  int ILLutil_priority_insert (ILLpriority *pri, void *data,              */
00065 /*      double keyval, int *handle)                                         */
00066 /*    -adds (data, keyval) to h.                                            */
00067 /*    -handle returns a handle (>= 0) to use when deleting or changing the  */
00068 /*     entry                                                                */
00069 /*                                                                          */
00070 /*  void ILLutil_priority_delete (ILLpriority *pri, int handle)             */
00071 /*    -deletes an entry from the queue.  handle is the value returned by    */
00072 /*     ILLutil_priority_insert.                                             */
00073 /*                                                                          */
00074 /*  void ILLutil_priority_deletemin (ILLpriority *pri, double *keyval,      */
00075 /*       void **en)                                                         */
00076 /*    -like ILLutil_priority_findmin, but also deletes the entry.           */
00077 /*                                                                          */
00078 /*  void ILLutil_priority_changekey (ILLpriority *pri, int handle,          */
00079 /*      double newkey)                                                      */
00080 /*    -changes the key of an entry in the queue.  handle is the value       */
00081 /*     returned by ILLutil_priority_insert.                                 */
00082 /*                                                                          */
00083 /****************************************************************************/
00084 
00085 /****************************************************************************/
00086 /*                                                                          */
00087 /*  NOTES:                                                                  */
00088 /*      These priority queue routines use the ILLdheap routines to maintain */
00089 /*  the priority queue.                                                     */
00090 /*                                                                          */
00091 /****************************************************************************/
00092 
00093 #include "qs_config.h"
00094 #include "machdefs.h"
00095 #include "priority.h"
00096 #include "allocrus.h"
00097 #include "except.h"
00098 #ifdef USEDMALLOC
00099 #include "dmalloc.h"
00100 #endif
00101 
00102 
00103 int ILLutil_priority_init (
00104   ILLpriority * pri,
00105   int k)
00106 {
00107   int i;
00108   int list;
00109   int rval = 0;
00110 
00111   pri->space = k;
00112   ILL_SAFE_MALLOC (pri->pri_info, k, union ILLpri_data);
00113 
00114   rval = ILLutil_dheap_init (&pri->heap, k);
00115   ILL_CLEANUP_IF (rval);
00116 
00117   list = -1;
00118   for (i = k - 1; i >= 0; i--)
00119   {
00120     pri->pri_info[i].next = list;
00121     list = i;
00122   }
00123   pri->freelist = list;
00124 
00125 CLEANUP:
00126 
00127   if (rval)
00128   {
00129     ILL_IFFREE (pri->pri_info, union ILLpri_data);
00130   }
00131   return rval;
00132 }
00133 
00134 void ILLutil_priority_free (
00135   ILLpriority * pri)
00136 {
00137   ILLutil_dheap_free (&pri->heap);
00138   ILL_IFFREE (pri->pri_info, union ILLpri_data);
00139 
00140   pri->space = 0;
00141 }
00142 
00143 void ILLutil_priority_findmin (
00144   ILLpriority * pri,
00145   EGlpNum_t * keyval,
00146   void **en)
00147 {
00148   int handle;
00149 
00150   ILLutil_dheap_findmin (&pri->heap, &handle);
00151 
00152   if (handle < 0)
00153   {
00154     *en = (void *) NULL;
00155   }
00156   else
00157   {
00158     if (keyval)
00159       EGlpNumCopy (*keyval, pri->heap.key[handle]);
00160     *en = pri->pri_info[handle].data;
00161   }
00162 }
00163 
00164 int ILLutil_priority_insert (
00165   ILLpriority * pri,
00166   void *data,
00167   EGlpNum_t * keyval,
00168   int *handle)
00169 {
00170   int newsize;
00171   int i;
00172   int list;
00173   int rval = 0;
00174 
00175   if (pri->freelist == -1)
00176   {
00177     /* Change from 1.3 * pri->space to avoid a warning */
00178     newsize = pri->space + (pri->space / 3);
00179     if (newsize < pri->space + 1000)
00180       newsize = pri->space + 1000;
00181     rval = ILLutil_dheap_resize (&pri->heap, newsize);
00182     ILL_CLEANUP_IF (rval);
00183 
00184     pri->pri_info =
00185       EGrealloc (pri->pri_info, sizeof (union ILLpri_data) * newsize);
00186     //rval = ILLutil_reallocrus_count ((void **) &pri->pri_info, newsize,
00187     //                                 sizeof (union ILLpri_data));
00188     //ILL_CLEANUP_IF (rval);
00189 
00190     list = -1;
00191     for (i = newsize - 1; i >= pri->space; i--)
00192     {
00193       pri->pri_info[i].next = list;
00194       list = i;
00195     }
00196     pri->space = newsize;
00197     pri->freelist = list;
00198   }
00199 
00200   i = pri->freelist;
00201   pri->freelist = pri->pri_info[i].next;
00202   pri->pri_info[i].data = data;
00203   EGlpNumCopy (pri->heap.key[i], *keyval);
00204   rval = ILLutil_dheap_insert (&pri->heap, i);
00205   ILL_CLEANUP_IF (rval);
00206 
00207   if (handle)
00208     *handle = i;
00209 
00210 CLEANUP:
00211 
00212   return rval;
00213 }
00214 
00215 void ILLutil_priority_delete (
00216   ILLpriority * pri,
00217   int handle)
00218 {
00219   ILLutil_dheap_delete (&pri->heap, handle);
00220   pri->pri_info[handle].next = pri->freelist;
00221   pri->freelist = handle;
00222 }
00223 
00224 void ILLutil_priority_deletemin (
00225   ILLpriority * pri,
00226   EGlpNum_t * keyval,
00227   void **en)
00228 {
00229   int handle;
00230   void *data;
00231 
00232   ILLutil_dheap_deletemin (&pri->heap, &handle);
00233 
00234   if (handle < 0)
00235   {
00236     *en = (void *) NULL;
00237   }
00238   else
00239   {
00240     if (keyval)
00241       EGlpNumCopy (*keyval, pri->heap.key[handle]);
00242     data = pri->pri_info[handle].data;
00243     pri->pri_info[handle].next = pri->freelist;
00244     pri->freelist = handle;
00245     *en = data;
00246   }
00247 }
00248 
00249 void ILLutil_priority_changekey (
00250   ILLpriority * pri,
00251   int handle,
00252   EGlpNum_t * newkey)
00253 {
00254   ILLutil_dheap_changekey (&pri->heap, handle, newkey);
00255 }

Generated on Thu Mar 29 09:32:32 2012 for QSopt_ex by  doxygen 1.4.7