-
Notifications
You must be signed in to change notification settings - Fork 30
/
queue.h
107 lines (101 loc) · 3.68 KB
/
queue.h
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
/*
*
* Copyright (c) 2011, Jue Ruan <[email protected]>
*
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef __FIFO_QUEUE_RJ_H
#define __FIFO_QUEUE_RJ_H
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdio.h>
#include "sort.h"
#include "mem_share.h"
#include "list.h"
#define define_queue_core(list_type, e_type, size_type, inc_size) \
\
typedef struct { e_type* buffer; size_type* links; size_type head, tail, size; size_type* trash; size_type trash_size, trash_cap; size_type off; size_type cap; } list_type; \
\
static inline size_t list_type##_obj_desc_cnt(void *list, int idx){ \
if(idx == 0) return ((list_type*)list)->size * sizeof(e_type); \
else if(idx == 1) return ((list_type*)list)->size * sizeof(size_type); \
else if(idx == 2) return ((list_type*)list)->trash_size * sizeof(size_type); \
else return 1; \
} \
\
static const obj_desc_t list_type##_obj_desc = {.size = sizeof(list_type), .n_child = 3, .addr = {offsetof(list_type, buffer), offsetof(list_type, links), offsetof(list_type, trash)}, .desc = {(struct obj_desc_t*)&OBJ_DESC_DATA, (struct obj_desc_t*)&OBJ_DESC_DATA, (struct obj_desc_t*)&OBJ_DESC_DATA}, .cnt = list_type##_obj_desc_cnt}; \
\
static inline list_type* init_##list_type(){ \
list_type *list = (list_type*)malloc(sizeof(list_type)); \
list->off = 0; \
list->cap = 0; \
list->buffer = NULL; \
list->links = NULL; \
list->trash = NULL; \
list->trash_size = 0; \
list->trash_cap = 0; \
list->head = 0; \
list->tail = 0; \
list->size = 0; \
return list; \
} \
\
static inline size_type count_##list_type(list_type *list){ return list->size; } \
\
static inline void clear_##list_type(list_type *list){ list->trash_size = 0; list->off = 0; list->head = 0; list->tail = 0; list->size = 0; } \
\
static inline void push_##list_type(list_type *list, e_type e){ \
size_type idx; \
if(list->trash_size){ \
idx = list->trash[--list->trash_size]; \
} else { \
encap_list((void**)&(list->buffer), sizeof(e_type), list->off, list->cap, 1, 0); \
list->cap = encap_list((void**)&(list->links), sizeof(size_type), list->off, list->cap, 1, 0); \
idx = list->off ++; \
} \
list->buffer[idx] = e; \
if(list->size == 0){ \
list->head = list->tail = idx; \
} else { \
list->links[list->tail] = idx; \
} \
list->links[idx] = 0; \
list->tail = idx; \
list->size ++; \
} \
\
static inline int pop_##list_type(list_type *list, e_type*e){ \
if(list->size == 0) return 0; \
*e = list->buffer[list->head]; \
list->trash_cap = encap_list((void**)&list->trash, sizeof(size_type), list->trash_size, list->trash_cap, 1, 0); \
list->trash[list->trash_size ++] = list->head; \
list->head = list->links[list->head]; \
list->size --; \
return 1; \
} \
\
static inline void free_##list_type(list_type *list){ \
if(list->buffer) free(list->buffer); \
if(list->links) free(list->links); \
if(list->trash) free(list->trash); \
free(list); \
}
#define define_queue(name, e_type) define_queue_core(name, e_type, size_t, 0xFFFFFU)
define_queue(u32fifo, uint32_t);
define_queue(s32fifo, int32_t);
define_queue(u64fifo, uint64_t);
define_queue(s64fifo, int64_t);
#endif