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_t.h"
   6
   7 int edge_bucket_contains(pbqp_edge_bucket bucket, pbqp_edge *edge)
   8 {
   9         assert(edge);
  10
  11         return edge->bucket_index < edge_bucket_get_length(bucket)
  12                         && bucket[edge->bucket_index] == edge;
  13 }
  14
  15 void edge_bucket_free(pbqp_edge_bucket *bucket)
  16 {
  17         DEL_ARR_F(*bucket);
  18         *bucket = NULL;
  19 }
  20
  21 unsigned edge_bucket_get_length(pbqp_edge_bucket bucket)
  22 {
  23         return ARR_LEN(bucket);
  24 }
  25
  26 void edge_bucket_init(pbqp_edge_bucket *bucket)
  27 {
  28         *bucket = NEW_ARR_F(pbqp_edge *, 0);
  29 }
  30
  31 void edge_bucket_insert(pbqp_edge_bucket *bucket, pbqp_edge *edge)
  32 {
  33         edge->bucket_index = edge_bucket_get_length(*bucket);
  34         ARR_APP1(pbqp_edge *, *bucket, edge);
  35 }
  36
  37 pbqp_edge *edge_bucket_pop(pbqp_edge_bucket *bucket)
  38 {
  39         unsigned   bucket_len = edge_bucket_get_length(*bucket);
  40         pbqp_edge *edge;
  41
  42         assert(bucket_len > 0);
  43
  44         edge = (*bucket)[bucket_len - 1];
  45
  46         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
  47         edge->bucket_index = UINT_MAX;
  48
  49         return edge;
  50 }
  51
  52 int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node)
  53 {
  54         assert(node);
  55
  56         return node->bucket_index < node_bucket_get_length(bucket)
  57                         && bucket[node->bucket_index] == node;
  58 }
  59
  60 void node_bucket_free(pbqp_node_bucket *bucket)
  61 {
  62         DEL_ARR_F(*bucket);
  63         *bucket = NULL;
  64 }
  65
  66 unsigned node_bucket_get_length(pbqp_node_bucket bucket)
  67 {
  68         return ARR_LEN(bucket);
  69 }
  70
  71 void node_bucket_init(pbqp_node_bucket *bucket)
  72 {
  73         *bucket = NEW_ARR_F(pbqp_node *, 0);
  74 }
  75
  76 void node_bucket_insert(pbqp_node_bucket *bucket, pbqp_node *node)
  77 {
  78         node->bucket_index = node_bucket_get_length(*bucket);
  79         ARR_APP1(pbqp_node *, *bucket, node);
  80 }
  81
  82 void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node)
  83 {
  84         unsigned   last_bucket_index = node_bucket_get_length(*bucket) - 1;
  85         unsigned   node_index;
  86         pbqp_node *other;
  87
  88         assert(node);
  89         assert(node_bucket_contains(*bucket, node));
  90
  91         node_index            = node->index;
  92         other                 = (*bucket)[last_bucket_index];
  93         other->bucket_index   = node_index;
  94         (*bucket)[node_index] = other;
  95
  96         ARR_SHRINKLEN(*bucket, last_bucket_index);
  97 }