nsz Git - libfirm/blob - bucket.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Buckets for nodes and edges.
  23  * @date    30.11.2008
  24  * @author  Sebastian Buchwald
  25  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "adt/array.h"
  30
  31 #include "bucket.h"
  32 #include "pbqp_edge_t.h"
  33 #include "pbqp_node.h"
  34 #include "pbqp_node_t.h"
  35
  36 int edge_bucket_contains(pbqp_edge_bucket bucket, pbqp_edge *edge)
  37 {
  38         assert(edge);
  39
  40         return edge->bucket_index < edge_bucket_get_length(bucket)
  41                         && bucket[edge->bucket_index] == edge;
  42 }
  43
  44 void edge_bucket_free(pbqp_edge_bucket *bucket)
  45 {
  46         DEL_ARR_F(*bucket);
  47         *bucket = NULL;
  48 }
  49
  50 unsigned edge_bucket_get_length(pbqp_edge_bucket bucket)
  51 {
  52         return ARR_LEN(bucket);
  53 }
  54
  55 void edge_bucket_init(pbqp_edge_bucket *bucket)
  56 {
  57         *bucket = NEW_ARR_F(pbqp_edge *, 0);
  58 }
  59
  60 void edge_bucket_insert(pbqp_edge_bucket *bucket, pbqp_edge *edge)
  61 {
  62         edge->bucket_index = edge_bucket_get_length(*bucket);
  63         ARR_APP1(pbqp_edge *, *bucket, edge);
  64 }
  65
  66 pbqp_edge *edge_bucket_pop(pbqp_edge_bucket *bucket)
  67 {
  68         unsigned   bucket_len = edge_bucket_get_length(*bucket);
  69         pbqp_edge *edge;
  70
  71         assert(bucket_len > 0);
  72
  73         edge = (*bucket)[bucket_len - 1];
  74
  75         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
  76         edge->bucket_index = UINT_MAX;
  77
  78         return edge;
  79 }
  80
  81 void node_bucket_shrink(pbqp_node_bucket *bucket, unsigned len)
  82 {
  83         ARR_SHRINKLEN(*bucket, (int)len);
  84 }
  85
  86 int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node)
  87 {
  88         assert(node);
  89
  90         return node->bucket_index < node_bucket_get_length(bucket)
  91                         && bucket[node->bucket_index] == node;
  92 }
  93
  94 void node_bucket_copy(pbqp_node_bucket *dst, pbqp_node_bucket src)
  95 {
  96         unsigned src_index;
  97         unsigned src_length = node_bucket_get_length(src);
  98
  99         for (src_index = 0; src_index < src_length; ++src_index) {
 100                 node_bucket_insert(dst, src[src_index]);
 101         }
 102 }
 103
 104 void node_bucket_update(pbqp *pbqp, pbqp_node_bucket bucket)
 105 {
 106         unsigned index;
 107         unsigned length = node_bucket_get_length(bucket);
 108
 109         for (index = 0; index < length; ++index) {
 110                 pbqp->nodes[bucket[index]->index] = bucket[index];
 111         }
 112 }
 113
 114 void node_bucket_free(pbqp_node_bucket *bucket)
 115 {
 116         DEL_ARR_F(*bucket);
 117         *bucket = NULL;
 118 }
 119
 120 unsigned node_bucket_get_length(pbqp_node_bucket bucket)
 121 {
 122         return ARR_LEN(bucket);
 123 }
 124
 125 void node_bucket_init(pbqp_node_bucket *bucket)
 126 {
 127         *bucket = NEW_ARR_F(pbqp_node *, 0);
 128 }
 129
 130 void node_bucket_insert(pbqp_node_bucket *bucket, pbqp_node *node)
 131 {
 132         node->bucket_index = node_bucket_get_length(*bucket);
 133         ARR_APP1(pbqp_node *, *bucket, node);
 134 }
 135
 136 pbqp_node *node_bucket_pop(pbqp_node_bucket *bucket)
 137 {
 138         unsigned   bucket_len = node_bucket_get_length(*bucket);
 139         pbqp_node *node;
 140
 141         assert(bucket_len > 0);
 142
 143         node = (*bucket)[bucket_len - 1];
 144         assert(node);
 145
 146         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 147         node->bucket_index = UINT_MAX;
 148
 149         return node;
 150 }
 151
 152 void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node)
 153 {
 154         unsigned   bucket_len = node_bucket_get_length(*bucket);
 155         unsigned   node_index;
 156         pbqp_node *other;
 157
 158         assert(node);
 159         assert(node_bucket_contains(*bucket, node));
 160         assert(bucket_len > 0);
 161
 162         node_index            = node->bucket_index;
 163         other                 = (*bucket)[bucket_len - 1];
 164         other->bucket_index   = node_index;
 165         (*bucket)[node_index] = other;
 166
 167         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 168         node->bucket_index = UINT_MAX;
 169 }
 170
 171 void node_bucket_deep_copy(pbqp *pbqp, pbqp_node_bucket *dst, pbqp_node_bucket src)
 172 {
 173         unsigned          bucket_index;
 174         unsigned          bucket_length;
 175
 176         bucket_length = node_bucket_get_length(src);
 177
 178         for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
 179                 node_bucket_insert(dst, pbqp_node_deep_copy(pbqp, *dst, src[bucket_index]));
 180         }
 181 }