Statistics
| Branch: | Revision:

peerstreamer-src / src / int_bucket.c @ 9eb656e7

History | View | Annotate | Download (3.96 KB)

1
/*******************************************************************
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
uint32_t int_bucket_check_pos(const struct int_bucket *h, const uint32_t n)
35
{
36
        uint32_t a,b,i;
37

    
38
        i = 0;
39
        if(h && h->n_elements > 0)
40
        {
41
                a = 0;
42
                b = h->n_elements-1;
43
                i = (b+a)/2;
44
                
45
                while(b > a)
46
                {
47
                        if (n > h->integers[i])
48
                                a = i+1;
49
                        if (n < h->integers[i])
50
                                b = i ? i-1 : 0;
51
                        if (n == h->integers[i])
52
                                a = b = i;
53
                
54
                        i = (b+a)/2;
55
                }
56
                if (n > (h->integers[i]))
57
                        i++;
58
        }
59

    
60
        return i;        
61
}
62

    
63
int int_bucket_init(struct int_bucket *ib,const uint32_t size)
64
{
65
        if(ib)
66
        {
67
                ib->size = size;
68
                ib->occurrences = (uint32_t *) malloc(ib->size * sizeof(uint32_t));
69
                ib->integers = (uint32_t *) malloc(ib->size * sizeof(uint32_t));
70
                ib->n_elements = 0;
71
        }
72
        return ib->occurrences == NULL && ib->integers == NULL ? -1 : 0;
73
}
74
        
75
struct int_bucket * int_bucket_new(const uint32_t size)
76
{
77
        struct int_bucket * ib = NULL;
78
        ib = (struct int_bucket *) malloc(sizeof(struct int_bucket));
79
        if (ib)
80
                int_bucket_init(ib,size);
81
        return ib;
82
}
83

    
84
void int_bucket_destroy(struct int_bucket **ib)
85
{
86
        if(*ib)
87
        {
88
                if(*ib != NULL && (*ib)->occurrences != NULL)
89
                        free(((*ib)->occurrences));
90
                if(*ib != NULL && (*ib)->integers != NULL)
91
                        free(((*ib)->integers));
92
                free(*ib);
93
                *ib=NULL;
94
        }
95
}
96

    
97
uint32_t int_bucket_length(const struct int_bucket *ib)
98
{
99
        return ib->n_elements;
100
}
101

    
102
int int_bucket_insert(struct int_bucket * ib,const uint32_t n,const uint32_t occurr)
103
{
104
        uint32_t i;
105

    
106
        if(ib)
107
        {
108
                i = int_bucket_check_pos(ib,n);
109
                if(i>= ib->n_elements || ib->integers[i] != n)
110
                {
111
                        if((ib->n_elements + 1) >= ib->size)
112
                        {
113
                                ib->size += INT_BUCKET_INC_SIZE;
114
                                ib->occurrences = (uint32_t *) realloc(ib->occurrences,sizeof(uint32_t) * ib->size);
115
                                ib->integers = (uint32_t *) realloc(ib->integers,sizeof(uint32_t) * ib->size);
116
                        }
117
                        memmove(ib->integers + i+1,ib->integers + i,sizeof(uint32_t) * (ib->n_elements -i));
118
                        memmove(ib->occurrences + i+1,ib->occurrences + i,sizeof(uint32_t) * (ib->n_elements -i));
119

    
120
                        ib->integers[i] = n;
121
                        ib->occurrences[i] = occurr;
122
                        ib->n_elements++;
123
                } else
124
                        ib->occurrences[i] += occurr;
125
                return 0;
126
        }
127
        return -1;
128
}
129

    
130
void int_bucket_sum(struct int_bucket *dst, const struct int_bucket *op)
131
{
132
        uint32_t i;
133
        if (dst && op)
134
                for (i = 0; i<op->n_elements;i++)
135
                        int_bucket_insert(dst,op->integers[i],op->occurrences[i]);
136
}
137

    
138
double int_bucket_occurr_norm(const struct int_bucket *ib)
139
{
140
        double sum = 0;
141
        uint32_t i;
142

    
143
        sum = 0;
144
        for (i = 0; ib && i<ib->n_elements; i++)
145
        {
146
//                fprintf(stderr,"Element %d with occurrence %d\n",ib->integers[i],ib->occurrences[i]);
147
                sum += (ib->occurrences[i])*(ib->occurrences[i]);
148
        }
149

    
150
        return sqrt(sum);
151
}
152

    
153
const uint32_t * int_bucket_iter(const struct int_bucket *ib, const uint32_t * iter)
154
{
155
        const uint32_t * res = NULL;
156
        uint32_t pos;
157

    
158
        if (ib && (ib->n_elements))
159
                if (iter)
160
                {
161
                        pos = int_bucket_check_pos(ib, *iter);
162
                        if (pos < (ib->n_elements-1))
163
                                res = iter+1;
164
                } else
165
                        res = ib->integers;
166
        return res;
167
}