Statistics
| Branch: | Tag: | Revision:

sssimulator / EventScheduler / ord_array.c @ master

History | View | Annotate | Download (4.95 KB)

1
/*
2
 * this is sssim: the simple & stupid simulator
3
 *
4
 *  copyright (c) 2015 luca baldesi
5
 *
6
 *  this is free software; see gpl-3.0.txt
7
 */
8

    
9
#include "ord_array.h"
10

    
11
struct ord_array {
12
        cmp_func_t el_cmp;
13
        void ** elements;
14
        uint32_t size;
15
        uint32_t n_elements;
16
        uint32_t first_el;
17
};
18

    
19
uint32_t ord_array_last_el(const struct ord_array * oa)
20
{
21
        return oa->n_elements ? (oa->first_el + oa->n_elements -1) % oa->size : oa->first_el;
22
}
23

    
24
void ord_array_print(const struct ord_array *oa)
25
/* this function is intended to be used for debug only */
26
{
27
        uint32_t i, last_el;
28

    
29
        if(oa)
30
        {
31
                last_el = ord_array_last_el(oa);
32
                fprintf(stderr,"[DEBUG] first el %d\n",oa->first_el);
33
                fprintf(stderr,"[DEBUG] last el %d\n",last_el);
34
                fprintf(stderr,"[DEBUG] n elements %d\n",oa->n_elements);
35
                fprintf(stderr,"[");
36
                for(i=0; i < oa->size; i++)
37
                {
38
                        if(oa->n_elements > 0)
39
                        {
40
                                if(last_el > oa->first_el)
41
                                {
42
                                        if(i >= oa->first_el && i<= last_el)
43
                                                fprintf(stderr,"1");
44
                                        else
45
                                                fprintf(stderr,"0");
46
                                } else
47
                                {
48
                                        if (last_el == oa->first_el)
49
                                        {
50
                                                if (i == last_el)
51
                                                        fprintf(stderr,"1");
52
                                                else
53
                                                        fprintf(stderr,"0");
54
                                        } else
55
                                        {
56
                                                if((i >= 0 && i <= last_el) ||
57
                                                        (i >= oa->first_el && i < oa->size))
58
                                                        fprintf(stderr,"1");
59
                                                else
60
                                                        fprintf(stderr,"0");
61
                                        } 
62
                                }
63
                        } else
64
                                fprintf(stderr,"0");
65
                }
66
                fprintf(stderr,"]\n");
67
        } else
68
                fprintf(stderr,"[<unallocated>]");
69
}
70

    
71
uint32_t ord_array_check_pos(const struct ord_array * h, const void *el)
72
{
73
        uint32_t a,b,i, last_el, limit;
74

    
75
        i = 0;
76
        if(h && h->n_elements > 0)
77
        {
78
                last_el = ord_array_last_el(h);
79
//                fprintf(stderr,"[DEBUG] -----------------------------\n");
80
//                ord_array_print(h);
81
                if(last_el >= h->first_el || h->el_cmp(el, h->elements[h->size - 1]) < 0)
82
                {
83
                        a = h->first_el;
84
                        b = last_el >= a ? last_el : h->size - 1;
85
                } else
86
                {
87
                        a = 0;
88
                        b = last_el;
89
                } 
90
                i = (b+a)/2;
91
                limit = b;
92
                
93
//                fprintf(stderr,"[DEBUG] a: %d, b: %d, i:%d\n", a, b ,i);
94
                while(b > a)
95
                {
96
                        if ((h->el_cmp(el, h->elements[i])) > 0)
97
                                a = i+1;
98
                        if ((h->el_cmp(el, h->elements[i])) < 0)
99
                                b = i;// ? i-1 : 0;
100
                        if ((h->el_cmp(el, h->elements[i])) == 0)
101
                                a = b = i;
102
                
103
                        i = (b+a)/2;
104
                }
105

    
106

    
107
                while (i <= limit && (h->el_cmp(el, h->elements[i])) >= 0)
108
                        i = (i + 1);
109
                i %= h->size;
110

    
111
        }
112

    
113
        if(h && h->n_elements == 0)
114
                i = h->first_el;
115

    
116
        return i;        
117
}
118

    
119
int ord_array_init(struct ord_array * oa, const uint32_t size, cmp_func_t el_cmp)
120
{
121
        if(oa)
122
        {
123
                oa->size = size;
124
                oa->elements = (void **) malloc(oa->size * sizeof(void *));
125
                // memset(oa->elements, 0, oa->size * sizeof(void *));
126
                oa->n_elements = 0;
127
                oa->first_el = 0;
128
                oa->el_cmp = el_cmp;
129
        }
130

    
131
        return oa->elements == NULL || oa->el_cmp == NULL || oa->size == 0 ? -1 : 0;
132
}
133

    
134
struct ord_array * ord_array_new(const uint32_t size, cmp_func_t el_cmp)
135
{
136
        struct ord_array * oa = NULL;
137
        oa = (struct ord_array *) malloc(sizeof(struct ord_array));
138
        if (oa)
139
                if(ord_array_init(oa,size, el_cmp) != 0)
140
                        ord_array_destroy(&oa);
141
        return oa;
142
}
143

    
144
void ord_array_destroy(struct ord_array **oa)
145
{
146
        if(oa)
147
        {
148
                if((*oa)->elements)
149
                        free((*oa)->elements);
150
                free(*oa);
151
                *oa = NULL;
152
        }
153
}
154

    
155
int ord_array_insert(struct ord_array *oa, void *el)
156
{
157
        uint32_t i, last_el, n_elr, n_ell;
158

    
159
        if (oa && el)
160
        {
161
                if((oa->n_elements + 1) > oa->size)  // we run out of space!
162
                {
163
                        oa->size *= 2;
164
                        oa->elements = (void **) realloc(oa->elements, sizeof(void *) * oa->size);
165
                        memmove(oa->elements + oa->size/2, oa->elements, sizeof(void *) * oa->first_el);
166
                }
167

    
168
                i = ord_array_check_pos(oa, el);
169
//                fprintf(stderr,"[DEBUG] position %d\n",i);
170
                last_el = ord_array_last_el(oa);
171
                n_elr = last_el >= oa->first_el ? oa->n_elements : oa->size - oa->first_el;  // number of elements on the right of the ring
172
                n_ell = oa->n_elements - n_elr;  // number of elements on the left of the ring
173

    
174
                // we always shift to the right
175
                if(i >= oa->first_el)        // we are on the right of the ring
176
                {
177
                        if(oa->first_el + oa->n_elements >= oa->size)  // we have not space on the right side
178
                        {
179
                                // first we move the left part by one
180
                                memmove(oa->elements + 1, oa->elements, sizeof(void *) * n_ell);
181
                                // then we move the last element from the right to the left
182
                                memmove(oa->elements, oa->elements + oa->size - 1, sizeof(void *) * 1);
183
                        }
184
                        // we shift the amount of elements on the right wrt position i
185
                        memmove(oa->elements + i + 1, oa->elements + i, sizeof(void *) * (oa->size - i - 1)); 
186
                } else  // we are on the left
187
                        memmove(oa->elements + i + 1, oa->elements + i, sizeof(void *) * (n_ell -i));
188

    
189
                oa->elements[i] = el;
190
                oa->n_elements++;
191

    
192
//                fprintf(stderr,"[DEBUG] after insertion\n");
193
//                ord_array_print(oa);
194
                return 0;
195
        } else
196
                return -1;
197
}
198

    
199
void * ord_array_pop(struct ord_array * oa)
200
{
201
        void * res = NULL;
202

    
203
        if(oa && oa->n_elements > 0)
204
        {
205
                res = oa->elements[oa->first_el];
206
                oa->first_el = (oa->first_el + 1) % oa->size;
207
                oa->n_elements--;
208
        }
209
        return res;
210
}
211

    
212
uint32_t ord_array_length(const struct ord_array* oa)
213
{
214
        if(oa)
215
                return oa->n_elements;
216
        else
217
                return 0;
218
}