Statistics
| Branch: | Revision:

peerstreamer-src / src / ord_set.c @ 58fb2cdc

History | View | Annotate | Download (3.07 KB)

1 4a486a01 Luca Baldesi
/*
2
 *
3
 *  copyright (c) 2017 luca baldesi
4
 *
5
 */
6
7
#include<ord_set.h>
8
#include<stdlib.h>
9
#include<string.h>
10
11
struct ord_set {
12
        ord_set_size size;
13
        ord_set_size n_elements;
14
        void ** elements;
15
        cmp_func_t cmp;
16
};
17
18
ord_set_size ord_set_check_pos(const struct ord_set *h, const void * n)
19
{
20
        ord_set_size a,b,i;
21
22
        i = 0;
23
        if(h && h->n_elements > 0)
24
        {
25
                a = 0;
26
                b = h->n_elements-1;
27
                i = (b+a)/2;
28
                
29
                while(b > a)
30
                {
31
                        if (h->cmp(n, h->elements[i]) > 0)
32
                                a = i+1;
33
                        if (h->cmp(n, h->elements[i]) < 0)
34
                                b = i ? i-1 : 0;
35
                        if (h->cmp(n, h->elements[i]) == 0)
36
                                a = b = i;
37
                
38
                        i = (b+a)/2;
39
                }
40
                if (h->cmp(n, h->elements[i]) > 0)
41
                        i++;
42
        }
43
44
        return i;        
45
}
46
47
struct ord_set * ord_set_new(ord_set_size size, cmp_func_t cmp)
48
{
49
        struct ord_set * os = NULL;
50
        
51
        if (size && cmp)
52
        {
53
                os = (struct ord_set *) malloc (sizeof(struct ord_set));
54
                os->n_elements = 0;
55
                os->size = size;
56
                os->elements = (void **) malloc (sizeof(void *) * os->size);
57
                os->cmp = cmp;
58
        }
59
        return os;
60
}
61
62
void ord_set_destroy(struct ord_set ** os, uint8_t free_elements)
63
{
64
        ord_set_size i;
65
66
        if(os && *os)
67
        {
68
                if (free_elements)
69
                        for(i = 0; i < (*os)->n_elements; i++)
70
                                free((*os)->elements[i]);
71
                free((*os)->elements);
72
                free(*os);
73
                *os = NULL;
74
        }
75
}
76
77 8f5b2a1b Luca Baldesi
const void * ord_set_find(const struct ord_set * os, const void * el)
78
{
79
        ord_set_size i;
80
        void * res = NULL;
81
82
83
        if(os && el)
84
        {
85
                i = ord_set_check_pos(os, el);
86
                if(i < os->n_elements && os->cmp(os->elements[i], el) == 0)
87
                        res = os->elements[i];
88
        }
89
        return res;
90
}
91
92
uint8_t ord_set_remove(struct ord_set * os, const void * el, uint8_t free_element)
93
{
94
        uint8_t res = 1;
95
        ord_set_size i;
96
97
        if(os && el)
98
        {
99
                i = ord_set_check_pos(os, el);
100
                if(i < os->n_elements && os->cmp(os->elements[i], el) == 0)
101
                {
102
                        if (free_element)
103
                        {
104
                                free(os->elements[i]);
105
                                os->elements[i] = NULL;
106
                        }
107
                        memmove(os->elements + i, os->elements + i + 1, sizeof(void *) * (os->n_elements - i - 1));
108
                        os->n_elements--;
109
                        res = 0;
110
                }
111
        }
112
        return res;
113
}
114
115 4a486a01 Luca Baldesi
void * ord_set_insert(struct ord_set * os, void * el, uint8_t override)
116
{
117
        ord_set_size i;
118
        void * res = NULL;
119
120
        if(os && el)
121
        {
122
                i = ord_set_check_pos(os, el);
123
                if(i>= os->n_elements || os->cmp(os->elements[i], el) != 0)
124
                {
125
                        if((os->n_elements + 1) >= os->size)
126
                        {
127
                                os->size += ORD_SET_INC_SIZE;
128
                                os->elements = (void **) realloc(os->elements,sizeof(void *) * os->size);
129
                        }
130
                        memmove(os->elements + i+1,os->elements + i,sizeof(void *) * (os->n_elements -i));
131
132
                        os->elements[i] = el;
133
                        os->n_elements++;
134
                } else
135
                        if (override)
136
                                os->elements[i] = el;
137
138
                res = os->elements[i];
139
        }
140
        return res;
141
}
142
143
const void * ord_set_iter(const struct ord_set * os, const void * iter)
144
{
145
        void * ptr = NULL;
146
        ord_set_size i;
147
148
        if (os)
149
        {
150
                if(iter)
151
                {
152
                        i = ord_set_check_pos(os, iter);
153
                        if (i < os->n_elements-1)
154
                                ptr = os->elements[i+1];
155
                }
156
                else 
157
                        if (os->n_elements > 0)
158
                                ptr = os->elements[0];
159
        }
160
        return ptr;
161
}
162
163
ord_set_size ord_set_length(const struct ord_set * os)
164
{
165
        if (os)
166
                return os->n_elements;
167
        return 0;
168
}
169 4d6f8fd5 Luca Baldesi
170
int8_t ord_set_dummy_cmp(const void * p1, const void * p2)
171
{
172
        if (p1 == p2)
173
                return 0;
174
        return p1 < p2 ? -1 : 1;
175
}