nsz Git - libfirm/blob - bucket.c

   1 #include "adt/array.h"
   2
   3 #include "bucket.h"
   4 #include "pbqp_edge_t.h"
   5 #include "pbqp_node.h"
   6 #include "pbqp_node_t.h"
   7
   8 int edge_bucket_contains(pbqp_edge_bucket bucket, pbqp_edge *edge)
   9 {
  10         assert(edge);
  11
  12         return edge->bucket_index < edge_bucket_get_length(bucket)
  13                         && bucket[edge->bucket_index] == edge;
  14 }
  15
  16 void edge_bucket_free(pbqp_edge_bucket *bucket)
  17 {
  18         DEL_ARR_F(*bucket);
  19         *bucket = NULL;
  20 }
  21
  22 unsigned edge_bucket_get_length(pbqp_edge_bucket bucket)
  23 {
  24         return ARR_LEN(bucket);
  25 }
  26
  27 void edge_bucket_init(pbqp_edge_bucket *bucket)
  28 {
  29         *bucket = NEW_ARR_F(pbqp_edge *, 0);
  30 }
  31
  32 void edge_bucket_insert(pbqp_edge_bucket *bucket, pbqp_edge *edge)
  33 {
  34         edge->bucket_index = edge_bucket_get_length(*bucket);
  35         ARR_APP1(pbqp_edge *, *bucket, edge);
  36 }
  37
  38 pbqp_edge *edge_bucket_pop(pbqp_edge_bucket *bucket)
  39 {
  40         unsigned   bucket_len = edge_bucket_get_length(*bucket);
  41         pbqp_edge *edge;
  42
  43         assert(bucket_len > 0);
  44
  45         edge = (*bucket)[bucket_len - 1];
  46
  47         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
  48         edge->bucket_index = UINT_MAX;
  49
  50         return edge;
  51 }
  52
  53 void node_bucket_shrink(pbqp_node_bucket *bucket, unsigned len)
  54 {
  55         ARR_SHRINKLEN(*bucket, len);
  56 }
  57
  58 int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node)
  59 {
  60         assert(node);
  61
  62         return node->bucket_index < node_bucket_get_length(bucket)
  63                         && bucket[node->bucket_index] == node;
  64 }
  65
  66 void node_bucket_copy(pbqp_node_bucket *dst, pbqp_node_bucket src)
  67 {
  68         unsigned src_index;
  69         unsigned src_length = node_bucket_get_length(src);
  70
  71         for (src_index = 0; src_index < src_length; ++src_index) {
  72                 node_bucket_insert(dst, src[src_index]);
  73         }
  74 }
  75
  76 void node_bucket_free(pbqp_node_bucket *bucket)
  77 {
  78         DEL_ARR_F(*bucket);
  79         *bucket = NULL;
  80 }
  81
  82 unsigned node_bucket_get_length(pbqp_node_bucket bucket)
  83 {
  84         return ARR_LEN(bucket);
  85 }
  86
  87 void node_bucket_init(pbqp_node_bucket *bucket)
  88 {
  89         *bucket = NEW_ARR_F(pbqp_node *, 0);
  90 }
  91
  92 void node_bucket_insert(pbqp_node_bucket *bucket, pbqp_node *node)
  93 {
  94         node->bucket_index = node_bucket_get_length(*bucket);
  95         ARR_APP1(pbqp_node *, *bucket, node);
  96 }
  97
  98 pbqp_node *node_bucket_pop(pbqp_node_bucket *bucket)
  99 {
 100         unsigned   bucket_len = node_bucket_get_length(*bucket);
 101         pbqp_node *node;
 102
 103         assert(bucket_len > 0);
 104
 105         node = (*bucket)[bucket_len - 1];
 106         assert(node);
 107
 108         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 109         node->bucket_index = UINT_MAX;
 110
 111         return node;
 112 }
 113
 114 void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node)
 115 {
 116         unsigned   bucket_len = node_bucket_get_length(*bucket);
 117         unsigned   node_index;
 118         pbqp_node *other;
 119
 120         assert(node);
 121         assert(node_bucket_contains(*bucket, node));
 122         assert(bucket_len > 0);
 123
 124         node_index            = node->bucket_index;
 125         other                 = (*bucket)[bucket_len - 1];
 126         other->bucket_index   = node_index;
 127         (*bucket)[node_index] = other;
 128
 129         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 130         node->bucket_index = UINT_MAX;
 131 }
 132
 133 void node_bucket_deep_copy(pbqp *pbqp, pbqp_node_bucket *dst, pbqp_node_bucket src)
 134 {
 135         unsigned          bucket_index;
 136         unsigned          bucket_length;
 137
 138         node_bucket_init(dst);
 139         bucket_length = node_bucket_get_length(src);
 140
 141         for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
 142                 node_bucket_insert(dst, pbqp_node_deep_copy(pbqp, *dst, src[bucket_index]));
 143         }
 144 }