nsz Git - libfirm/blob - ir/kaps/bucket.c

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