summaryrefslogtreecommitdiffhomepage
path: root/ir/adt/deq.c
blob: a11fad1a49897c80bcb5543caa6aeea845ac6f45 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
 * This file is part of libFirm.
 * Copyright (C) 2016 Matthias Braun
 */
#include "deq.h"

#include "xmalloc.h"
#include <stdlib.h>
#include <string.h>

void deq_init(deq_t *deq)
{
	deq_block_t *block = XMALLOCF(deq_block_t, data, DEQ_BLOCK_DATA_SIZE);
	memset(block, 0, sizeof(deq_block_t));
	deq->left_end  = block;
	deq->right_end = block;
}

void deq_free(deq_t *deq)
{
	for (deq_block_t *block = deq->left_end, *next; block != NULL;
	     block = next) {
	    next = block->next_right;
		free(block);
	}
#ifndef NDEBUG
	deq->left_end = NULL;
	deq->right_end = NULL;
#endif
}

deq_block_t *deq_append_block_left_priv(deq_t *deq)
{
	deq_block_t *const left_end = deq->left_end;
	/* Special case if left and right end are in the same block and
	 * the block is empty. Leaving the right pointer at 0 would be invalid. */
	deq_block_t *newb;
	if (left_end == deq->right_end && left_end->r == left_end->l) {
		newb = left_end;
		assert(newb->next_left == NULL);
		assert(newb->next_right == NULL);
	} else {
		newb = XMALLOCF(deq_block_t, data, DEQ_BLOCK_DATA_SIZE);
		newb->next_left  = NULL;
		newb->next_right = left_end;

		left_end->next_left = newb;
		deq->left_end = newb;
	}
	newb->l = DEQ_BLOCK_DATA_SIZE;
	newb->r = DEQ_BLOCK_DATA_SIZE;
	return newb;
}

deq_block_t *deq_append_block_right_priv(deq_t *deq)
{
	deq_block_t *const right_end = deq->right_end;
	/* Special case if left and right end are in the same block and
	 * the block is empty. Leaving the right pointer at 0 would be invalid. */
	deq_block_t *newb;
	if (right_end == deq->left_end && right_end->r == right_end->l) {
		newb = right_end;
		assert(newb->next_left == NULL);
		assert(newb->next_right == NULL);
	} else {
		newb = XMALLOCF(deq_block_t, data, DEQ_BLOCK_DATA_SIZE);
		newb->next_left  = right_end;
		newb->next_right = NULL;

		right_end->next_right = newb;
		deq->right_end = newb;
	}

	newb->l = 0;
	newb->r = 0;
	return newb;
}

void deq_left_end_block_empty_priv(deq_t *deq)
{
	deq_block_t *const block      = deq->left_end;
	deq_block_t *const next_right = block->next_right;
	assert(block->l == block->r);
	if (next_right != NULL) {
		assert(block != deq->right_end);
		assert(next_right->next_left == block);
		deq->left_end = next_right;
		next_right->next_left = NULL;
		free(block);
	} else {
		assert(block == deq->right_end);
		block->l = 0;
		block->r = 0;
	}
}

void deq_right_end_block_empty_priv(deq_t *deq)
{
	deq_block_t *const block     = deq->right_end;
	deq_block_t *const next_left = block->next_left;
	assert(block->r == block->l);
	if (next_left != NULL) {
		assert(block != deq->left_end);
		assert(next_left->next_right == block);
		deq->right_end = next_left;
		next_left->next_right = NULL;
		free(block);
	} else {
		assert(block == deq->left_end);
		block->l = 0;
		block->r = 0;
	}
}