Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.03 KB)

1 9eb656e7 Luca Baldesi
/*******************************************************************
2
* PeerStreamer-ng is a P2P video streaming application exposing a ReST
3
* interface.
4
* Copyright (C) 2015 Luca Baldesi <luca.baldesi@unitn.it>
5
*
6
* This program is free software: you can redistribute it and/or modify
7
* it under the terms of the GNU Affero General Public License as published by
8
* the Free Software Foundation, either version 3 of the License, or
9
* (at your option) any later version.
10
*
11
* This program is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
* GNU Affero General Public License for more details.
15
*
16
* You should have received a copy of the GNU Affero General Public License
17
* along with this program.  If not, see <http://www.gnu.org/licenses/>.
18
*******************************************************************/
19
20
#include <math.h>
21
#include <stdint.h>
22
#include <string.h>
23
#include <malloc.h>
24
25
#include "int_bucket.h"
26
27
struct int_bucket {
28
        uint32_t *occurrences;
29
        uint32_t *integers;
30
        uint32_t size;
31
        uint32_t n_elements;
32
};
33
34 c03fc03d Luca Baldesi
void int_bucket_flush(struct int_bucket * h)
35
{
36
        h->n_elements = 0;
37
}
38
39 9eb656e7 Luca Baldesi
uint32_t int_bucket_check_pos(const struct int_bucket *h, const uint32_t n)
40
{
41
        uint32_t a,b,i;
42
43
        i = 0;
44
        if(h && h->n_elements > 0)
45
        {
46
                a = 0;
47
                b = h->n_elements-1;
48
                i = (b+a)/2;
49
                
50
                while(b > a)
51
                {
52
                        if (n > h->integers[i])
53
                                a = i+1;
54
                        if (n < h->integers[i])
55
                                b = i ? i-1 : 0;
56
                        if (n == h->integers[i])
57
                                a = b = i;
58
                
59
                        i = (b+a)/2;
60
                }
61
                if (n > (h->integers[i]))
62
                        i++;
63
        }
64
65
        return i;        
66
}
67
68
int int_bucket_init(struct int_bucket *ib,const uint32_t size)
69
{
70
        if(ib)
71
        {
72
                ib->size = size;
73
                ib->occurrences = (uint32_t *) malloc(ib->size * sizeof(uint32_t));
74
                ib->integers = (uint32_t *) malloc(ib->size * sizeof(uint32_t));
75
                ib->n_elements = 0;
76
        }
77
        return ib->occurrences == NULL && ib->integers == NULL ? -1 : 0;
78
}
79
        
80
struct int_bucket * int_bucket_new(const uint32_t size)
81
{
82
        struct int_bucket * ib = NULL;
83
        ib = (struct int_bucket *) malloc(sizeof(struct int_bucket));
84
        if (ib)
85
                int_bucket_init(ib,size);
86
        return ib;
87
}
88
89
void int_bucket_destroy(struct int_bucket **ib)
90
{
91
        if(*ib)
92
        {
93
                if(*ib != NULL && (*ib)->occurrences != NULL)
94
                        free(((*ib)->occurrences));
95
                if(*ib != NULL && (*ib)->integers != NULL)
96
                        free(((*ib)->integers));
97
                free(*ib);
98
                *ib=NULL;
99
        }
100
}
101
102
uint32_t int_bucket_length(const struct int_bucket *ib)
103
{
104
        return ib->n_elements;
105
}
106
107
int int_bucket_insert(struct int_bucket * ib,const uint32_t n,const uint32_t occurr)
108
{
109
        uint32_t i;
110
111
        if(ib)
112
        {
113
                i = int_bucket_check_pos(ib,n);
114
                if(i>= ib->n_elements || ib->integers[i] != n)
115
                {
116
                        if((ib->n_elements + 1) >= ib->size)
117
                        {
118
                                ib->size += INT_BUCKET_INC_SIZE;
119
                                ib->occurrences = (uint32_t *) realloc(ib->occurrences,sizeof(uint32_t) * ib->size);
120
                                ib->integers = (uint32_t *) realloc(ib->integers,sizeof(uint32_t) * ib->size);
121
                        }
122
                        memmove(ib->integers + i+1,ib->integers + i,sizeof(uint32_t) * (ib->n_elements -i));
123
                        memmove(ib->occurrences + i+1,ib->occurrences + i,sizeof(uint32_t) * (ib->n_elements -i));
124
125
                        ib->integers[i] = n;
126
                        ib->occurrences[i] = occurr;
127
                        ib->n_elements++;
128
                } else
129
                        ib->occurrences[i] += occurr;
130
                return 0;
131
        }
132
        return -1;
133
}
134
135
void int_bucket_sum(struct int_bucket *dst, const struct int_bucket *op)
136
{
137
        uint32_t i;
138
        if (dst && op)
139
                for (i = 0; i<op->n_elements;i++)
140
                        int_bucket_insert(dst,op->integers[i],op->occurrences[i]);
141
}
142
143
double int_bucket_occurr_norm(const struct int_bucket *ib)
144
{
145
        double sum = 0;
146
        uint32_t i;
147
148
        sum = 0;
149
        for (i = 0; ib && i<ib->n_elements; i++)
150
        {
151
//                fprintf(stderr,"Element %d with occurrence %d\n",ib->integers[i],ib->occurrences[i]);
152
                sum += (ib->occurrences[i])*(ib->occurrences[i]);
153
        }
154
155
        return sqrt(sum);
156
}
157
158
const uint32_t * int_bucket_iter(const struct int_bucket *ib, const uint32_t * iter)
159
{
160
        const uint32_t * res = NULL;
161
        uint32_t pos;
162
163
        if (ib && (ib->n_elements))
164 3d7e9165 Luca Baldesi
        {
165 9eb656e7 Luca Baldesi
                if (iter)
166
                {
167
                        pos = int_bucket_check_pos(ib, *iter);
168
                        if (pos < (ib->n_elements-1))
169
                                res = iter+1;
170
                } else
171
                        res = ib->integers;
172 3d7e9165 Luca Baldesi
        }
173 9eb656e7 Luca Baldesi
        return res;
174
}