]>
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
= NULL
;
108 list
->elements_size
= 0;
113 LOC_EXPORT
void loc_network_list_dump(struct loc_network_list
* list
) {
114 struct loc_network
* network
;
117 for (unsigned int i
= 0; i
< list
->size
; i
++) {
118 network
= list
->elements
[i
];
120 s
= loc_network_str(network
);
122 INFO(list
->ctx
, "%4d: %s\n", i
, s
);
127 LOC_EXPORT
struct loc_network
* loc_network_list_get(struct loc_network_list
* list
, size_t index
) {
129 if (index
>= list
->size
)
132 return loc_network_ref(list
->elements
[index
]);
135 static off_t
loc_network_list_find(struct loc_network_list
* list
,
136 struct loc_network
* network
, int* found
) {
138 off_t hi
= list
->size
- 1;
141 // Since we are working on an ordered list, there is often a good chance that
142 // the network we are looking for is at the end or has to go to the end.
144 result
= loc_network_cmp(network
, list
->elements
[hi
]);
146 // Match, so we are done
152 // This needs to be added after the last one
153 } else if (result
> 0) {
162 clock_t start
= clock();
170 // Check if this is a match
171 result
= loc_network_cmp(network
, list
->elements
[i
]);
177 clock_t end
= clock();
179 // Log how fast this has been
180 DEBUG(list
->ctx
, "Found network in %.4fms at %jd\n",
181 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000, (intmax_t)i
);
196 clock_t end
= clock();
198 // Log how fast this has been
199 DEBUG(list
->ctx
, "Did not find network in %.4fms (last i = %jd)\n",
200 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000, (intmax_t)i
);
206 LOC_EXPORT
int loc_network_list_push(struct loc_network_list
* list
, struct loc_network
* network
) {
209 off_t index
= loc_network_list_find(list
, network
, &found
);
211 // The network has been found on the list. Nothing to do.
215 DEBUG(list
->ctx
, "%p: Inserting network %p at index %jd\n",
216 list
, network
, (intmax_t)index
);
218 // Check if we have space left
219 if (list
->size
>= list
->elements_size
) {
220 int r
= loc_network_list_grow(list
, 64);
225 // The list is now larger
228 // Move all elements out of the way
229 for (unsigned int i
= list
->size
- 1; i
> index
; i
--)
230 list
->elements
[i
] = list
->elements
[i
- 1];
232 // Add the new element at the right place
233 list
->elements
[index
] = loc_network_ref(network
);
238 LOC_EXPORT
struct loc_network
* loc_network_list_pop(struct loc_network_list
* list
) {
239 // Return nothing when empty
240 if (loc_network_list_empty(list
)) {
241 DEBUG(list
->ctx
, "%p: Popped empty stack\n", list
);
245 struct loc_network
* network
= list
->elements
[--list
->size
];
247 DEBUG(list
->ctx
, "%p: Popping network %p from stack\n", list
, network
);
252 LOC_EXPORT
struct loc_network
* loc_network_list_pop_first(struct loc_network_list
* list
) {
253 // Return nothing when empty
254 if (loc_network_list_empty(list
)) {
255 DEBUG(list
->ctx
, "%p: Popped empty stack\n", list
);
259 struct loc_network
* network
= list
->elements
[0];
261 // Move all elements to the top of the stack
262 for (unsigned int i
= 0; i
< list
->size
- 1; i
++) {
263 list
->elements
[i
] = list
->elements
[i
+1];
266 // The list is shorter now
269 DEBUG(list
->ctx
, "%p: Popping network %p from stack\n", list
, network
);
274 LOC_EXPORT
int loc_network_list_contains(struct loc_network_list
* list
, struct loc_network
* network
) {
277 loc_network_list_find(list
, network
, &found
);
282 LOC_EXPORT
int loc_network_list_merge(
283 struct loc_network_list
* self
, struct loc_network_list
* other
) {
286 for (unsigned int i
= 0; i
< other
->size
; i
++) {
287 r
= loc_network_list_push(self
, other
->elements
[i
]);