Graphviz  2.41.20170921.2350
PriorityQueue.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 #include "LinkedList.h"
15 #include "PriorityQueue.h"
16 #include "memory.h"
17 #include "logic.h"
18 #include "assert.h"
19 #include "arith.h"
20 
21 #define MALLOC gmalloc
22 #define REALLOC grealloc
23 #define FREE free
24 #define MEMCPY memcpy
25 
26 
27 PriorityQueue PriorityQueue_new(int n, int ngain){
28  PriorityQueue q;
29  int i;
30  q = N_GNEW(1,struct PriorityQueue_struct);
31  q->count = 0;
32  q->n = n;
33  q->ngain = ngain;
34  q->gain_max = -1;/* no entries yet */
35  q->buckets = N_GNEW((ngain+1),DoubleLinkedList);
36  for (i = 0; i < ngain+1; i++) (q->buckets)[i] = NULL;
37 
38  q->where = N_GNEW((n+1),DoubleLinkedList);
39  for (i = 0; i < n+1; i++) (q->where)[i] = NULL;
40 
41  q->gain = N_GNEW((n+1),int);
42  for (i = 0; i < n+1; i++) (q->gain)[i] = -999;
43  return q;
44 
45 }
46 
48  int i;
49 
50  if (q){
51  if (q->buckets){
52  for (i = 0; i < q->ngain+1; i++) DoubleLinkedList_delete((q->buckets)[i], free);
53  FREE(q->buckets);
54  }
55 
56  if (q->where){
57  FREE(q->where);
58  }
59 
60  FREE(q->gain);
61  FREE(q);
62  }
63 }
64 
67  int *data, gainold;
68 
69  assert(q);
70  assert(gain <= q->ngain);
71 
72 
73  if (!(q->where)[i]){
74  /* this entry is no in the queue yet, so this is a new addition */
75 
76  (q->count)++;
77  if (gain > q->gain_max) q->gain_max = gain;
78  q->gain[i] = gain;
79 
80  data = N_GNEW(1,int);
81  data[0] = i;
82  if ((l = (q->buckets)[gain])){
83  (q->buckets)[gain] = (q->where)[i] = DoubleLinkedList_prepend(l, data);
84  } else {
85  (q->buckets)[gain] = (q->where)[i] = DoubleLinkedList_new(data);
86  }
87 
88  } else {
89  /* update gain for an exisiting entry */
90  l = q->where[i];
91  gainold = q->gain[i];
92  q->where[i] = NULL;
93  (q->count)--;
94  DoubleLinkedList_delete_element(l, free, &((q->buckets)[gainold]));
95  return PriorityQueue_push(q, i, gain);
96  }
97  return q;
98 }
99 
100 int PriorityQueue_pop(PriorityQueue q, int *i, int *gain){
101  int gain_max;
103  int *data;
104 
105  if (!q || q->count <= 0) return 0;
106  *gain = gain_max = q->gain_max;
107  (q->count)--;
108  l = (q->buckets)[gain_max];
109  data = (int*) DoubleLinkedList_get_data(l);
110  *i = data[0];
111 
112  DoubleLinkedList_delete_element(l, free, &((q->buckets)[gain_max]));
113  if (!(q->buckets)[gain_max]){/* the bin that contain the best gain is empty now after poping */
114  while (gain_max >= 0 && !(q->buckets)[gain_max]) gain_max--;
115  q->gain_max = gain_max;
116  }
117  q->where[*i] = NULL;
118  q->gain[*i] = -999;
119  return 1;
120 }
121 
122 
123 
124 
126  return q->gain[i];
127 }
128 
130  /* remove an entry from the queue. If error, return 0. */
131  int gain, gain_max;
133 
134  if (!q || q->count <= 0) return 0;
135  gain = q->gain[i];
136  (q->count)--;
137  l = (q->where)[i];
138 
139  DoubleLinkedList_delete_element(l, free, &((q->buckets)[gain]));
140 
141  if (gain == (gain_max = q->gain_max) && !(q->buckets)[gain_max]){/* the bin that contain the best gain is empty now after poping */
142  while (gain_max >= 0 && !(q->buckets)[gain_max]) gain_max--;
143  q->gain_max = gain_max;
144  }
145  q->where[i] = NULL;
146  q->gain[i] = -999;
147  return 1;
148 }
149 
150 /*
151 
152 main(){
153  int i, gain;
154 
155 
156  PriorityQueue q;
157  q = PriorityQueue_new(10,100);
158  PriorityQueue_push(q, 3, 1);
159  PriorityQueue_push(q, 2, 2);
160  PriorityQueue_push(q, 4, 2);
161  PriorityQueue_push(q, 5, 2);
162  PriorityQueue_push(q, 1, 100);
163  PriorityQueue_push(q, 2, 1);
164  while (PriorityQueue_pop(q, &i, &gain)){
165  printf("i = %d gain = %d\n", i, gain);
166  }
167 
168  printf("=========\n");
169  PriorityQueue_push(q, 3, 1);
170  PriorityQueue_push(q, 2, 2);
171  PriorityQueue_push(q, 4, 2);
172  PriorityQueue_push(q, 5, 2);
173  PriorityQueue_push(q, 1, 100);
174  PriorityQueue_push(q, 2, 1);
175  PriorityQueue_push(q, 2, 100);
176  while (PriorityQueue_pop(q, &i, &gain)){
177  printf("i = %d gain = %d\n", i, gain);
178  }
179 
180 
181  printf("====after removing 3 and 2 =====\n");
182  PriorityQueue_push(q, 3, 1);
183  PriorityQueue_push(q, 2, 2);
184  PriorityQueue_push(q, 4, 2);
185  PriorityQueue_push(q, 5, 2);
186  PriorityQueue_push(q, 1, 100);
187  PriorityQueue_push(q, 2, 1);
188  PriorityQueue_push(q, 2, 100);
189  PriorityQueue_remove(q, 3);
190  PriorityQueue_remove(q, 2);
191  while (PriorityQueue_pop(q, &i, &gain)){
192  printf("i = %d gain = %d\n", i, gain);
193  }
194  PriorityQueue_delete(q);
195 
196 }
197 
198 */
void DoubleLinkedList_delete(DoubleLinkedList head, void(*linklist_deallocator)(void *))
Definition: LinkedList.c:93
#define FREE
Definition: PriorityQueue.c:23
void DoubleLinkedList_delete_element(DoubleLinkedList l, void(*linklist_deallocator)(void *), DoubleLinkedList *head)
Definition: LinkedList.c:134
PriorityQueue PriorityQueue_push(PriorityQueue q, int i, int gain)
Definition: PriorityQueue.c:65
#define assert(x)
Definition: cghdr.h:47
int PriorityQueue_remove(PriorityQueue q, int i)
DoubleLinkedList DoubleLinkedList_new(void *data)
Definition: LinkedList.c:84
DoubleLinkedList DoubleLinkedList_prepend(DoubleLinkedList l, void *data)
Definition: LinkedList.c:107
DoubleLinkedList * buckets
Definition: PriorityQueue.h:18
DoubleLinkedList * where
Definition: PriorityQueue.h:21
PriorityQueue PriorityQueue_new(int n, int ngain)
Definition: PriorityQueue.c:27
#define NULL
Definition: logic.h:39
int PriorityQueue_pop(PriorityQueue q, int *i, int *gain)
void PriorityQueue_delete(PriorityQueue q)
Definition: PriorityQueue.c:47
int PriorityQueue_get_gain(PriorityQueue q, int i)
#define N_GNEW(n, t)
Definition: agxbuf.c:20
Definition: legal.c:60
void * DoubleLinkedList_get_data(DoubleLinkedList l)
Definition: LinkedList.c:116