summaryrefslogtreecommitdiffhomepage
path: root/ir/adt/deq.h
blob: e5fcae27d136fe41526a948966ef63678c87b6aa (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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/*
 * This file is part of libFirm.
 * Copyright (C) 2016 Matthias Braun
 */

/**
 * @file
 * @brief  Double Ended Queue.
 */
#ifndef FIRM_ADT_DEQ_H
#define FIRM_ADT_DEQ_H

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>

/**
 * @ingroup adt
 * @defgroup deq Double Ended Queue
 * Double ended queue data structure. They allow efficient insertion and
 * deletion on both ends.
 * @{
 */

#define DEQ_BLOCK_SIZE        2048
#define DEQ_BLOCK_DATA_SIZE   DEQ_BLOCK_SIZE - sizeof(deq_block_t)

typedef struct deq_block_t deq_block_t;
struct deq_block_t {
	unsigned l;
	unsigned r;
	deq_block_t *next_left;
	deq_block_t *next_right;
	char data[];
};

typedef struct deq_t {
	deq_block_t *left_end;
	deq_block_t *right_end;
} deq_t;

/** @cond PRIVATE */
deq_block_t *deq_append_block_left_priv(deq_t *deq);
deq_block_t *deq_append_block_right_priv(deq_t *deq);
void deq_left_end_block_empty_priv(deq_t *deq);
void deq_right_end_block_empty_priv(deq_t *deq);
/** @endcond */

/** Initialize double ended queue \p deq and allocate a first data block. */
void deq_init(deq_t *deq);

/**
 * Free all data blocks allocated for double ended queue \p deq.
 * Further use of the datastructure is undefined until deq_init() is called.
 */
void deq_free(deq_t *deq);

/** Returns true if the double ended queue \p deq is empty, false otherwise. */
static inline bool deq_empty(deq_t const *const deq)
{
	deq_block_t const *const left_end = deq->left_end;
	return left_end == deq->right_end && left_end->l == left_end->r;
}

/** Return pointer to the object at the elft end of the double ended queue. */
static inline void *deq_left_end(deq_t const *const deq)
{
	deq_block_t *const left_end = deq->left_end;
	return left_end->data + left_end->l;
}

/** Return pointer to object at the right end of the double ended queue. */
static inline void *deq_right_end_obj(deq_t const *const deq, unsigned size)
{
	deq_block_t *const right_end = deq->right_end;
	return right_end->data + right_end->r - size;
}

/**
 * Remove object of size \p size from the left end of double ended queue \p deq.
 */
static inline void deq_shrink_left(deq_t *const deq, unsigned size)
{
	deq_block_t *const left_end = deq->left_end;
	left_end->l += size;
	if (left_end->l >= left_end->r)
		deq_left_end_block_empty_priv(deq);
}

/**
 * Remove object of size \p size from the right end of double ended queue
 * \p deq.
 */
static inline void deq_shrink_right(deq_t *const deq, unsigned size)
{
	deq_block_t *const right_end = deq->right_end;
	assert(right_end->r >= size);
	right_end->r -= size;
	if (right_end->r <= right_end->l)
		deq_right_end_block_empty_priv(deq);
}

/**
 * Allocate space for object of size \p size on the left end of the double ended
 * queue \p deq.  Returns a pointer to the newly allocated space.
 */
static inline void *deq_alloc_left(deq_t *const deq, unsigned size)
{
	assert(size < DEQ_BLOCK_DATA_SIZE);
	deq_block_t *left_end = deq->left_end;
	if (left_end->l < size)
		left_end = deq_append_block_left_priv(deq);
	left_end->l -= size;
	return left_end->data + left_end->l;
}

/**
 * Allocate space for object of size \p size on the right end of the double
 * ended queue \p deq.  Returns a pointer to the newly allocated space.
 */
static inline void *deq_alloc_right(deq_t *const deq, unsigned size)
{
	assert(size < DEQ_BLOCK_DATA_SIZE);
	deq_block_t *right_end = deq->right_end;
	if (right_end->r + size > DEQ_BLOCK_DATA_SIZE)
		right_end = deq_append_block_right_priv(deq);
	void *result = right_end->data + right_end->r;
	right_end->r += size;
	return result;
}

static inline deq_block_t const *deq_get_left_end_block(deq_t const *const deq)
{
	return deq->left_end;
}

static inline deq_block_t *deq_block_next_right(deq_block_t const *const block)
{
	return block->next_right;
}

static inline const void *deq_block_data_begin(deq_block_t const *const block)
{
	return block->data + block->l;
}

static inline const void *deq_block_data_end(deq_block_t const *const block)
{
	return block->data + block->r;
}

/** @} */

#endif