DisOrder 3.0

[disorder] / lib / heap.h

diff --git a/lib/heap.h b/lib/heap.h
index 56821bf0b820fb0b70499281d27f27aa879630b9..6f9bcab7c1e6fd6866178fb950bc6ef2bd080870 100644 (file)
--- a/lib/heap.h
+++ b/lib/heap.h
@@ -1,6 +1,6 @@
 /*
  * This file is part of DisOrder.
- * Copyright (C) 2007 Richard Kettlewell
+ * Copyright (C) 2007, 2008 Richard Kettlewell
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -85,53 +85,60 @@
   }                                                                     \
                                                                         \
   static inline NAME##_element NAME##_first(struct NAME *heap) {        \
-    assert(heap->nvec > 0);                                             \
+    assert(heap->nvec > 0 && "_first");                                 \
     return heap->vec[0];                                                \
   }                                                                     \
                                                                         \
-  static void NAME##_insert(struct NAME *heap, NAME##_element elt) {    \
-    int n = heap->nvec;                                                 \
-    NAME##_append(heap, elt);                                           \
-    while(n > 0) {                                                      \
-      const int p = (n-1)/2;                                            \
-      if(!LT(heap->vec[n],heap->vec[p]))                                \
-        break;                                                          \
-      else {                                                            \
-        const NAME##_element t = heap->vec[n];                          \
-        heap->vec[n] = heap->vec[p];                                    \
-        heap->vec[p] = t;                                               \
-        n = p;                                                          \
-      }                                                                 \
-    }                                                                   \
-  }                                                                     \
-                                                                        \
-  static NAME##_element NAME##_remove(struct NAME *heap) {              \
-    int n = 0;                                                          \
-    NAME##_element r;                                                   \
-                                                                        \
-    assert(heap->nvec > 0);                                             \
-    r = heap->vec[0];                                                   \
-    heap->vec[0] = heap->vec[--heap->nvec];                             \
-    while(2 * n + 1 < heap->nvec) {                                     \
-      int a = 2 * n + 1;                                                \
-      int b = 2 * n + 2;                                                \
-                                                                        \
-      if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {             \
-        ++a;                                                            \
-        --b;                                                            \
-      }                                                                 \
-      if(LT(heap->vec[a], heap->vec[n])) {                              \
-        const NAME##_element t = heap->vec[n];                          \
-        heap->vec[n] = heap->vec[a];                                    \
-        heap->vec[a] = t;                                               \
-        n = a;                                                          \
-      } else                                                            \
-        break;                                                          \
-    }                                                                   \
-    return r;                                                           \
-  }                                                                     \
+  void NAME##_insert(struct NAME *heap, NAME##_element elt);            \
+  NAME##_element NAME##_remove(struct NAME *heap);                      \
                                                                         \
   struct heap_swallow_semicolon
+
+/** @brief External-linkage definitions for @ref HEAP_TYPE */
+#define HEAP_DEFINE(NAME, ETYPE, LT)                            \
+  void NAME##_insert(struct NAME *heap, NAME##_element elt) {   \
+    int n = heap->nvec;                                         \
+    NAME##_append(heap, elt);                                   \
+    while(n > 0) {                                              \
+      const int p = (n-1)/2;                                    \
+      if(!LT(heap->vec[n],heap->vec[p]))                        \
+        break;                                                  \
+      else {                                                    \
+        const NAME##_element t = heap->vec[n];                  \
+        heap->vec[n] = heap->vec[p];                            \
+        heap->vec[p] = t;                                       \
+        n = p;                                                  \
+      }                                                         \
+    }                                                           \
+  }                                                             \
+                                                                \
+  NAME##_element NAME##_remove(struct NAME *heap) {             \
+    int n = 0;                                                  \
+    NAME##_element r;                                           \
+                                                                \
+    assert(heap->nvec > 0 && "_remove");                        \
+    r = heap->vec[0];                                           \
+    heap->vec[0] = heap->vec[--heap->nvec];                     \
+    while(2 * n + 1 < heap->nvec) {                             \
+      int a = 2 * n + 1;                                        \
+      int b = 2 * n + 2;                                        \
+                                                                \
+      if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {     \
+        ++a;                                                    \
+        --b;                                                    \
+      }                                                         \
+      if(LT(heap->vec[a], heap->vec[n])) {                      \
+        const NAME##_element t = heap->vec[n];                  \
+        heap->vec[n] = heap->vec[a];                            \
+        heap->vec[a] = t;                                       \
+        n = a;                                                  \
+      } else                                                    \
+        break;                                                  \
+    }                                                           \
+    return r;                                                   \
+  }                                                             \
+                                                                \
+  struct heap_swallow_semicolon                                 \
   
 
 #endif /* PQUEUE_H */