Re: [gnugo-devel] Arraybound checking on Tru64 not working anymore

[Paul Pogonyshev]

Gunnar wrote:
> Teun wrote:
> > I was trying to run 3.5.3 with arraybound checking on
> > Tru64. It won't run however since it already chokes on
> > this assignment in readconnect.c
> >
> > > struct heap_entry **heap = conn->heap - 1
>
> If somebody wonders why there is a problem with this, you should read
> http://www.eskimo.com/~scs/C-faq/q6.17.html
>
> > The attached patch fixes this, but perhaps someone
> > has a more elegant fix for this issue.
>
> I guess Paul (who wrote the code), should decide how to solve it.

Here is a patch.  It also modifies the code in `owl.c', which has a
similarly implemented heap (with the difference that there's no heap
pushing, only heap building from array).  There are no unexpected
results or differences in node counters in the first batch, so i
assume the patch works just fine.

I eliminated auxilary `heap' pointers completely.  `conn->heap' and
`list->pattern_heap' are used now.

Paul



Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.188
diff -u -p -r1.188 owl.c
--- engine/owl.c        14 Jan 2004 22:21:27 -0000      1.188
+++ engine/owl.c        19 Jan 2004 21:24:40 -0000
@@ -3526,7 +3526,6 @@ pattern_list_build_heap(struct matched_p
 {
   int k;
   int limit;
-  struct matched_pattern_data **heap;
 
   list->pattern_heap = malloc(list->counter
                              * sizeof(struct matched_pattern_data*));
@@ -3539,28 +3538,28 @@ pattern_list_build_heap(struct matched_p
     list->pattern_heap[k] = &list->pattern_list[k];
   }
 
-  heap = list->pattern_heap - 1;
   list->heap_num_patterns = list->counter;
   limit = list->heap_num_patterns / 2;
 
-  for (k = limit; k >= 1; k--) {
+  for (k = limit; --k >= 0;) {
     int parent;
     int child;
-    struct matched_pattern_data *pattern_data = heap[k];
+    struct matched_pattern_data *pattern_data = list->pattern_heap[k];
 
-    for (parent = k; parent <= limit; parent = child) {
-      child = 2 * parent;
-      if (child < list->heap_num_patterns
-         && BETTER_PATTERN(heap[child + 1], heap[child]))
+    for (parent = k; parent < limit; parent = child) {
+      child = 2 * parent + 1;
+      if (child + 1 < list->heap_num_patterns
+         && BETTER_PATTERN(list->pattern_heap[child + 1],
+                           list->pattern_heap[child]))
        child++;
 
-      if (BETTER_PATTERN(pattern_data, heap[child]))
+      if (BETTER_PATTERN(pattern_data, list->pattern_heap[child]))
        break;
 
-      heap[parent] = heap[child];
+      list->pattern_heap[parent] = list->pattern_heap[child];
     }
 
-    heap[parent] = pattern_data;
+    list->pattern_heap[parent] = pattern_data;
   }
 }
 
@@ -3573,23 +3572,24 @@ pattern_list_get_next_pattern(struct mat
 {
   int parent;
   int child;
-  struct matched_pattern_data **heap = list->pattern_heap - 1;
 
-  list->next_pattern = heap[1];
+  list->next_pattern = list->pattern_heap[0];
 
-  for (parent = 1; 2 * parent < list->heap_num_patterns; parent = child) {
-    child = 2 * parent;
-    if (BETTER_PATTERN(heap[child + 1], heap[child]))
+  list->heap_num_patterns--;
+  for (parent = 0; 2 * parent + 1 < list->heap_num_patterns; parent = child) {
+    child = 2 * parent + 1;
+    if (BETTER_PATTERN(list->pattern_heap[child + 1],
+                      list->pattern_heap[child]))
       child++;
 
-    if (BETTER_PATTERN(heap[list->heap_num_patterns], heap[child]))
+    if (BETTER_PATTERN(list->pattern_heap[list->heap_num_patterns],
+                      list->pattern_heap[child]))
       break;
 
-    heap[parent] = heap[child];
+    list->pattern_heap[parent] = list->pattern_heap[child];
   }
 
-  heap[parent] = heap[list->heap_num_patterns];
-  list->heap_num_patterns--;
+  list->pattern_heap[parent] = list->pattern_heap[list->heap_num_patterns];
 }
 
 
Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.62
diff -u -p -r1.62 readconnect.c
--- engine/readconnect.c        16 Jan 2004 12:43:25 -0000      1.62
+++ engine/readconnect.c        19 Jan 2004 21:24:49 -0000
@@ -3077,7 +3077,6 @@ push_connection_heap_entry(struct connec
   int k;
   int parent;
   struct heap_entry *new_entry = &conn->heap_data[conn->heap_data_size];
-  struct heap_entry **heap = conn->heap - 1;
 
   gg_assert(conn->heap_data_size < 4 * BOARDMAX);
   gg_assert(conn->heap_size < BOARDMAX);
@@ -3090,17 +3089,16 @@ push_connection_heap_entry(struct connec
 
   /* And insert it into the heap. */
   conn->heap_data_size++;
-  conn->heap_size++;
 
-  for (k = conn->heap_size; k > 1; k = parent) {
-    parent = k / 2;
-    if (heap[parent]->distance <= distance)
+  for (k = conn->heap_size++; k > 0; k = parent) {
+    parent = (k - 1) / 2;
+    if (conn->heap[parent]->distance <= distance)
       break;
 
-    heap[k] = heap[parent];
+    conn->heap[k] = conn->heap[parent];
   }
 
-  heap[k] = new_entry;
+  conn->heap[k] = new_entry;
 }
 
 
@@ -3109,20 +3107,19 @@ pop_connection_heap_entry(struct connect
 {
   int k;
   int child;
-  struct heap_entry **heap = conn->heap - 1;
 
-  for (k = 1; 2 * k < conn->heap_size; k = child) {
-    child = 2 * k;
-    if (heap[child]->distance > heap[child + 1]->distance)
+  conn->heap_size--;
+  for (k = 0; 2 * k + 1 < conn->heap_size; k = child) {
+    child = 2 * k + 1;
+    if (conn->heap[child]->distance > conn->heap[child + 1]->distance)
       child++;
-    if (heap[child]->distance >= heap[conn->heap_size]->distance)
+    if (conn->heap[child]->distance >= conn->heap[conn->heap_size]->distance)
       break;
 
-    heap[k] = heap[child];
+    conn->heap[k] = conn->heap[child];
   }
 
-  heap[k] = heap[conn->heap_size];
-  conn->heap_size--;
+  conn->heap[k] = conn->heap[conn->heap_size];
 }