valueset.c 4.77 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Michael Beck's avatar
Michael Beck committed
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 */

/**
 * @file
 * @author    Michael Beck
 * @brief     A value set, containing expression for values.
 */
#include "valueset.h"
#include "irnode_t.h"
#include "iropt_t.h"
#include "hashptr.h"

static ir_valueset_entry_t null_valueset_entry;

#undef DO_REHASH
#define HashSet                   ir_valueset_t
#define HashSetIterator           ir_valueset_iterator_t
#define ValueType                 ir_valueset_entry_t
#define NullValue                 null_valueset_entry
#define KeyType                   ir_node*
#define ConstKeyType              const ir_node*
#define GetKey(entry)             (entry).value
26
#define InitData(self,entry,key)  do { (entry).value = (key); (entry).list.next = NULL; (entry).list.prev = NULL; } while (0)
Michael Beck's avatar
Michael Beck committed
27
28
29
30
#define Hash(self,key)            ir_node_hash(key)
#define KeysEqual(self,key1,key2) (key1) == (key2)
#define SetRangeEmpty(ptr,size)   memset(ptr, 0, (size) * sizeof((ptr)[0]))
#define EntrySetEmpty(entry)      (entry).value = NULL
31
#define EntrySetDeleted(entry)    do { (entry).data.value = (ir_node*) -1; list_del(&(entry).data.list); } while (0)
Michael Beck's avatar
Michael Beck committed
32
33
34
35
36
37
#define EntryIsEmpty(entry)       ((entry).data.value == NULL)
#define EntryIsDeleted(entry)     ((entry).data.value == (ir_node*)-1)

#define hashset_init            ir_valueset_init
#define hashset_init_size       ir_valueset_init_size
#define hashset_destroy         ir_valueset_destroy
38
39
ir_valueset_entry_t *ir_valueset_insert_(ir_valueset_t *self, ir_node *value);
#define hashset_insert          ir_valueset_insert_
Michael Beck's avatar
Michael Beck committed
40
#define hashset_remove          ir_valueset_remove
41
42
43
ir_valueset_entry_t *ir_valueset_find_(const ir_valueset_t *self,
                                       const ir_node *value);
#define hashset_find            ir_valueset_find_
Michael Beck's avatar
Michael Beck committed
44
45
46
47
48
49
50
#define hashset_size            ir_valueset_size

#define ADDITIONAL_INIT         INIT_LIST_HEAD(&self->elem_list); INIT_LIST_HEAD(&self->all_iters);
#define ADDITIONAL_TERM         INIT_LIST_HEAD(&self->elem_list); INIT_LIST_HEAD(&self->all_iters);

#define HAVE_OWN_RESIZE

51
#include "hashset.c.h"
Michael Beck's avatar
Michael Beck committed
52
53
54
55
56

/**
 * Resize the hashset
 * @internal
 */
57
static void resize(HashSet *self, size_t new_size)
Michael Beck's avatar
Michael Beck committed
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
{
	HashSetEntry *old_entries = self->entries;
	HashSetEntry *new_entries;
	list_head    list = self->elem_list;
	int          res = 1;

	/* allocate a new array with double size */
	new_entries = Alloc(new_size);
	SetRangeEmpty(new_entries, new_size);

	/* use the new array */
	self->entries      = new_entries;
	self->num_buckets  = new_size;
	self->num_elements = 0;
	self->num_deleted  = 0;
#ifndef NDEBUG
	self->entries_version++;
#endif
	reset_thresholds(self);

	assert(!list_empty(&self->elem_list));
	list.next->prev = &list;
	list.prev->next = &list;

	/* reinsert all elements */
	INIT_LIST_HEAD(&self->elem_list);
	list_for_each_entry(ValueType, entry, &list, list) {
		res &= ir_valueset_insert(self, entry->value, entry->expr);
	}
	/* all re-inserted data must be new, if not, we found a node twice ... */
	assert(res == 1);
yb9976's avatar
yb9976 committed
89
	(void)res;
Michael Beck's avatar
Michael Beck committed
90
91
92
93
94
95
96

	/* now we can free the old array */
	Free(old_entries);
}

int ir_valueset_insert(ir_valueset_t *valueset, ir_node *value, ir_node *expr)
{
97
	ir_valueset_entry_t *entry = ir_valueset_insert_(valueset, value);
Michael Beck's avatar
Michael Beck committed
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

	if (entry->list.next != NULL) {
		/* this value is already inserted, do nothing */
		return 0;
	}

	/* new element added */
	entry->expr = expr;
	list_add_tail(&entry->list, &valueset->elem_list);
	return 1;
}

int ir_valueset_replace(ir_valueset_t *valueset, ir_node *value, ir_node *expr)
{
	int res = 0;
113
	ir_valueset_entry_t *entry = ir_valueset_insert_(valueset, value);
Michael Beck's avatar
Michael Beck committed
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

	if (entry->expr != expr) {
		entry->expr = expr;
		res = 1;
	}
	if (entry->list.next == NULL) {
		/* we have added a new element */
		list_add_tail(&entry->list, &valueset->elem_list);
		return 1;
	}
	return res;
}

void *ir_valueset_lookup(const ir_valueset_t *valueset, const ir_node *value)
{
129
	ir_valueset_entry_t *entry = ir_valueset_find_(valueset, value);
Michael Beck's avatar
Michael Beck committed
130
131
132
133
134
135
	if (entry != NULL)
		return entry->expr;
	return NULL;
}

void ir_valueset_iterator_init(ir_valueset_iterator_t *iterator,
136
137
                               const ir_valueset_t *valueset)
{
Michael Beck's avatar
Michael Beck committed
138
139
140
141
	iterator->iter     = valueset->elem_list.next;
	iterator->valueset = valueset;
}

142
143
ir_node *ir_valueset_iterator_next(ir_valueset_iterator_t *iterator, ir_node **expr)
{
Michael Beck's avatar
Michael Beck committed
144
145
146
147
148
149
150
151
152
153
154
155
156
157
	ir_valueset_entry_t *entry;

	if (iterator->iter == &iterator->valueset->elem_list) {
		*expr = NULL;
		return NULL;
	}

	entry = list_entry(iterator->iter, ir_valueset_entry_t, list);
	iterator->iter = iterator->iter->next;

	*expr = entry->expr;
	return entry->value;
}

158
159
void ir_valueset_remove_iterator(ir_valueset_t *valueset, ir_valueset_iterator_t *iterator)
{
160
	ir_valueset_entry_t *rem = list_entry(iterator->iter->prev, ir_valueset_entry_t, list);
Michael Beck's avatar
Michael Beck committed
161
162
163

	ir_valueset_remove(valueset, rem->value);
}