]>
git.ipfire.org Git - location/libloc.git/blob - src/network-list.c
2 libloc - A library to determine the location of someone on the Internet
4 Copyright (C) 2020 IPFire Development Team <info@ipfire.org>
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 This library 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 GNU
14 Lesser General Public License for more details.
21 #include <loc/libloc.h>
22 #include <loc/network.h>
23 #include <loc/private.h>
25 struct loc_network_list
{
29 struct loc_network
** elements
;
35 static int loc_network_list_grow(struct loc_network_list
* list
, size_t size
) {
36 DEBUG(list
->ctx
, "Growing network list %p by %zu to %zu\n",
37 list
, size
, list
->elements_size
+ size
);
39 struct loc_network
** elements
= reallocarray(list
->elements
,
40 list
->elements_size
+ size
, sizeof(*list
->elements
));
44 list
->elements
= elements
;
45 list
->elements_size
+= size
;
50 LOC_EXPORT
int loc_network_list_new(struct loc_ctx
* ctx
,
51 struct loc_network_list
** list
) {
52 struct loc_network_list
* l
= calloc(1, sizeof(*l
));
56 l
->ctx
= loc_ref(ctx
);
59 DEBUG(l
->ctx
, "Network list allocated at %p\n", l
);
64 LOC_EXPORT
struct loc_network_list
* loc_network_list_ref(struct loc_network_list
* list
) {
70 static void loc_network_list_free(struct loc_network_list
* list
) {
71 DEBUG(list
->ctx
, "Releasing network list at %p\n", list
);
73 for (unsigned int i
= 0; i
< list
->size
; i
++)
74 loc_network_unref(list
->elements
[i
]);
80 LOC_EXPORT
struct loc_network_list
* loc_network_list_unref(struct loc_network_list
* list
) {
84 if (--list
->refcount
> 0)
87 loc_network_list_free(list
);
91 LOC_EXPORT
size_t loc_network_list_size(struct loc_network_list
* list
) {
95 LOC_EXPORT
int loc_network_list_empty(struct loc_network_list
* list
) {
96 return list
->size
== 0;
99 LOC_EXPORT
void loc_network_list_clear(struct loc_network_list
* list
) {
103 for (unsigned int i
= 0; i
< list
->size
; i
++)
104 loc_network_unref(list
->elements
[i
]);
106 free(list
->elements
);
107 list
->elements_size
= 0;
112 LOC_EXPORT
void loc_network_list_dump(struct loc_network_list
* list
) {
113 struct loc_network
* network
;
116 for (unsigned int i
= 0; i
< list
->size
; i
++) {
117 network
= list
->elements
[i
];
119 s
= loc_network_str(network
);
121 INFO(list
->ctx
, "%s\n", s
);
126 LOC_EXPORT
struct loc_network
* loc_network_list_get(struct loc_network_list
* list
, size_t index
) {
128 if (index
>= list
->size
)
131 return loc_network_ref(list
->elements
[index
]);
134 //MOVE FUNCTION GOES HERE
136 static off_t
loc_network_list_find(struct loc_network_list
* list
,
137 struct loc_network
* network
, int* found
) {
139 off_t hi
= list
->size
- 1;
145 clock_t start
= clock();
153 // Check if this is a match
154 int result
= loc_network_cmp(network
, list
->elements
[i
]);
160 clock_t end
= clock();
162 // Log how fast this has been
163 DEBUG(list
->ctx
, "Found network in %.4fms at %jd\n",
164 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000, (intmax_t)i
);
177 clock_t end
= clock();
179 // Log how fast this has been
180 DEBUG(list
->ctx
, "Did not find network in %.4fms (last i = %jd)\n",
181 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000, (intmax_t)i
);
187 LOC_EXPORT
int loc_network_list_push(struct loc_network_list
* list
, struct loc_network
* network
) {
190 off_t index
= loc_network_list_find(list
, network
, &found
);
192 // The network has been found on the list. Nothing to do.
196 DEBUG(list
->ctx
, "%p: Inserting network %p at index %jd\n",
197 list
, network
, (intmax_t)index
);
199 // Check if we have space left
200 if (list
->size
>= list
->elements_size
) {
201 int r
= loc_network_list_grow(list
, 64);
206 // The list is now larger
209 // Move all elements out of the way
210 for (unsigned int i
= list
->size
- 1; i
> index
; i
--)
211 list
->elements
[i
] = list
->elements
[i
- 1];
213 // Add the new element at the right place
214 list
->elements
[index
] = loc_network_ref(network
);
219 LOC_EXPORT
struct loc_network
* loc_network_list_pop(struct loc_network_list
* list
) {
220 // Return nothing when empty
221 if (loc_network_list_empty(list
)) {
222 DEBUG(list
->ctx
, "%p: Popped empty stack\n", list
);
226 struct loc_network
* network
= list
->elements
[--list
->size
];
228 DEBUG(list
->ctx
, "%p: Popping network %p from stack\n", list
, network
);
233 LOC_EXPORT
struct loc_network
* loc_network_list_pop_first(struct loc_network_list
* list
) {
234 // Return nothing when empty
235 if (loc_network_list_empty(list
)) {
236 DEBUG(list
->ctx
, "%p: Popped empty stack\n", list
);
240 struct loc_network
* network
= list
->elements
[0];
242 // Move all elements to the top of the stack
243 for (unsigned int i
= 0; i
< --list
->size
; i
++) {
244 list
->elements
[i
] = list
->elements
[i
+1];
247 DEBUG(list
->ctx
, "%p: Popping network %p from stack\n", list
, network
);
252 LOC_EXPORT
int loc_network_list_contains(struct loc_network_list
* list
, struct loc_network
* network
) {
255 loc_network_list_find(list
, network
, &found
);
260 static void loc_network_list_swap(struct loc_network_list
* list
, unsigned int i1
, unsigned int i2
) {
261 // Do nothing for invalid indices
262 if (i1
>= list
->size
|| i2
>= list
->size
)
265 struct loc_network
* network1
= list
->elements
[i1
];
266 struct loc_network
* network2
= list
->elements
[i2
];
268 list
->elements
[i1
] = network2
;
269 list
->elements
[i2
] = network1
;
272 LOC_EXPORT
void loc_network_list_reverse(struct loc_network_list
* list
) {
274 unsigned int j
= list
->size
- 1;
277 loc_network_list_swap(list
, i
++, j
--);
281 LOC_EXPORT
void loc_network_list_sort(struct loc_network_list
* list
) {
282 unsigned int n
= list
->size
;
288 for (unsigned int i
= 1; i
< n
; i
++) {
289 if (loc_network_gt(list
->elements
[i
-1], list
->elements
[i
]) > 0) {
290 loc_network_list_swap(list
, i
-1, i
);
299 LOC_EXPORT
int loc_network_list_merge(
300 struct loc_network_list
* self
, struct loc_network_list
* other
) {
303 for (unsigned int i
= 0; i
< other
->size
; i
++) {
304 r
= loc_network_list_push(self
, other
->elements
[i
]);
312 LOC_EXPORT
int loc_network_list_merge_reverse(
313 struct loc_network_list
* self
, struct loc_network_list
* other
) {
316 for (int i
= other
->size
- 1; i
>= 0; i
--) {
317 r
= loc_network_list_push(self
, other
->elements
[i
]);