]>
git.ipfire.org Git - people/ms/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 <libloc/address.h>
22 #include <libloc/libloc.h>
23 #include <libloc/network.h>
24 #include <libloc/private.h>
26 struct loc_network_list
{
30 struct loc_network
** elements
;
36 static int loc_network_list_grow(struct loc_network_list
* list
) {
37 size_t size
= list
->elements_size
* 2;
41 DEBUG(list
->ctx
, "Growing network list %p by %zu to %zu\n",
42 list
, size
, list
->elements_size
+ size
);
44 struct loc_network
** elements
= reallocarray(list
->elements
,
45 list
->elements_size
+ size
, sizeof(*list
->elements
));
49 list
->elements
= elements
;
50 list
->elements_size
+= size
;
55 LOC_EXPORT
int loc_network_list_new(struct loc_ctx
* ctx
,
56 struct loc_network_list
** list
) {
57 struct loc_network_list
* l
= calloc(1, sizeof(*l
));
61 l
->ctx
= loc_ref(ctx
);
64 DEBUG(l
->ctx
, "Network list allocated at %p\n", l
);
69 LOC_EXPORT
struct loc_network_list
* loc_network_list_ref(struct loc_network_list
* list
) {
75 static void loc_network_list_free(struct loc_network_list
* list
) {
76 DEBUG(list
->ctx
, "Releasing network list at %p\n", list
);
79 loc_network_list_clear(list
);
85 LOC_EXPORT
struct loc_network_list
* loc_network_list_unref(struct loc_network_list
* list
) {
86 if (--list
->refcount
> 0)
89 loc_network_list_free(list
);
93 LOC_EXPORT
size_t loc_network_list_size(struct loc_network_list
* list
) {
97 LOC_EXPORT
int loc_network_list_empty(struct loc_network_list
* list
) {
98 return list
->size
== 0;
101 LOC_EXPORT
void loc_network_list_clear(struct loc_network_list
* list
) {
105 for (unsigned int i
= 0; i
< list
->size
; i
++)
106 loc_network_unref(list
->elements
[i
]);
108 free(list
->elements
);
109 list
->elements
= NULL
;
110 list
->elements_size
= 0;
115 LOC_EXPORT
void loc_network_list_dump(struct loc_network_list
* list
) {
116 struct loc_network
* network
;
118 for (unsigned int i
= 0; i
< list
->size
; i
++) {
119 network
= list
->elements
[i
];
121 INFO(list
->ctx
, "%4d: %s\n",
122 i
, loc_network_str(network
));
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 static off_t
loc_network_list_find(struct loc_network_list
* list
,
135 struct loc_network
* network
, int* found
) {
136 // Insert at the beginning for an empty list
137 if (loc_network_list_empty(list
))
141 off_t hi
= list
->size
- 1;
144 // Since we are working on an ordered list, there is often a good chance that
145 // the network we are looking for is at the end or has to go to the end.
147 result
= loc_network_cmp(network
, list
->elements
[hi
]);
149 // Match, so we are done
155 // This needs to be added after the last one
156 } else if (result
> 0) {
165 clock_t start
= clock();
173 // Check if this is a match
174 result
= loc_network_cmp(network
, list
->elements
[i
]);
180 clock_t end
= clock();
182 // Log how fast this has been
183 DEBUG(list
->ctx
, "Found network in %.4fms at %jd\n",
184 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000, (intmax_t)i
);
201 clock_t end
= clock();
203 // Log how fast this has been
204 DEBUG(list
->ctx
, "Did not find network in %.4fms (last i = %jd)\n",
205 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000, (intmax_t)i
);
211 LOC_EXPORT
int loc_network_list_push(struct loc_network_list
* list
, struct loc_network
* network
) {
214 off_t index
= loc_network_list_find(list
, network
, &found
);
216 // The network has been found on the list. Nothing to do.
220 DEBUG(list
->ctx
, "%p: Inserting network %p at index %jd\n",
221 list
, network
, (intmax_t)index
);
223 // Check if we have space left
224 if (list
->size
>= list
->elements_size
) {
225 int r
= loc_network_list_grow(list
);
230 // The list is now larger
233 // Move all elements out of the way
234 for (unsigned int i
= list
->size
- 1; i
> index
; i
--)
235 list
->elements
[i
] = list
->elements
[i
- 1];
237 // Add the new element at the right place
238 list
->elements
[index
] = loc_network_ref(network
);
243 LOC_EXPORT
struct loc_network
* loc_network_list_pop(struct loc_network_list
* list
) {
244 // Return nothing when empty
245 if (loc_network_list_empty(list
)) {
246 DEBUG(list
->ctx
, "%p: Popped empty stack\n", list
);
250 struct loc_network
* network
= list
->elements
[--list
->size
];
252 DEBUG(list
->ctx
, "%p: Popping network %p from stack\n", list
, network
);
257 LOC_EXPORT
struct loc_network
* loc_network_list_pop_first(struct loc_network_list
* list
) {
258 // Return nothing when empty
259 if (loc_network_list_empty(list
)) {
260 DEBUG(list
->ctx
, "%p: Popped empty stack\n", list
);
264 struct loc_network
* network
= list
->elements
[0];
266 // Move all elements to the top of the stack
267 for (unsigned int i
= 0; i
< list
->size
- 1; i
++) {
268 list
->elements
[i
] = list
->elements
[i
+1];
271 // The list is shorter now
274 DEBUG(list
->ctx
, "%p: Popping network %p from stack\n", list
, network
);
279 int loc_network_list_remove(struct loc_network_list
* list
, struct loc_network
* network
) {
282 // Find the network on the list
283 off_t index
= loc_network_list_find(list
, network
, &found
);
285 // Nothing to do if the network wasn't found
289 // Dereference the network at the position
290 loc_network_unref(list
->elements
[index
]);
292 // Move all other elements back
293 for (unsigned int i
= index
; i
< list
->size
- 1; i
++)
294 list
->elements
[i
] = list
->elements
[i
+1];
296 // The list is shorter now
302 LOC_EXPORT
int loc_network_list_contains(struct loc_network_list
* list
, struct loc_network
* network
) {
305 loc_network_list_find(list
, network
, &found
);
310 LOC_EXPORT
int loc_network_list_merge(
311 struct loc_network_list
* self
, struct loc_network_list
* other
) {
314 for (unsigned int i
= 0; i
< other
->size
; i
++) {
315 r
= loc_network_list_push(self
, other
->elements
[i
]);
323 int loc_network_list_summarize(struct loc_ctx
* ctx
,
324 const struct in6_addr
* first
, const struct in6_addr
* last
, struct loc_network_list
** list
) {
332 DEBUG(ctx
, "Summarizing %s - %s\n", loc_address_str(first
), loc_address_str(last
));
334 const int family1
= loc_address_family(first
);
335 const int family2
= loc_address_family(last
);
337 // Check if address families match
338 if (family1
!= family2
) {
339 ERROR(ctx
, "Address families do not match\n");
344 // Check if the last address is larger than the first address
345 if (loc_address_cmp(first
, last
) >= 0) {
346 ERROR(ctx
, "The first address must be smaller than the last address\n");
351 struct loc_network
* network
= NULL
;
352 struct in6_addr start
= *first
;
354 const int family_bit_length
= loc_address_family_bit_length(family1
);
356 while (loc_address_cmp(&start
, last
) <= 0) {
360 // Find the number of trailing zeroes of the start address
361 if (loc_address_all_zeroes(&start
))
362 bits1
= family_bit_length
;
364 bits1
= loc_address_count_trailing_zero_bits(&start
);
365 if (bits1
> family_bit_length
)
366 bits1
= family_bit_length
;
369 // Subtract the start address from the last address and add one
370 // (i.e. how many addresses are in this network?)
371 r
= loc_address_sub(&num
, last
, &start
);
375 loc_address_increment(&num
);
377 // How many bits do we need to represent this address?
378 int bits2
= loc_address_bit_length(&num
) - 1;
380 // Select the smaller one
381 int bits
= (bits1
> bits2
) ? bits2
: bits1
;
384 r
= loc_network_new(ctx
, &network
, &start
, family_bit_length
- bits
);
388 DEBUG(ctx
, "Found network %s\n", loc_network_str(network
));
390 // Push network on the list
391 r
= loc_network_list_push(*list
, network
);
393 loc_network_unref(network
);
397 // The next network starts right after this one
398 start
= *loc_network_get_last_address(network
);
400 // If we have reached the end of possible IP addresses, we stop
401 if (loc_address_all_ones(&start
))
404 loc_address_increment(&start
);
410 void loc_network_list_remove_with_prefix_smaller_than(
411 struct loc_network_list
* list
, const unsigned int prefix
) {
414 // Count how many networks were removed
415 unsigned int removed
= 0;
417 for (unsigned int i
= 0; i
< list
->size
; i
++) {
419 p
= loc_network_prefix(list
->elements
[i
]);
423 loc_network_unref(list
->elements
[i
]);
431 // Move pointers backwards to keep the list filled
432 list
->elements
[i
- removed
] = list
->elements
[i
];
436 list
->size
-= removed
;