]>
git.ipfire.org Git - people/ms/libloc.git/blob - src/network.c
2 libloc - A library to determine the location of someone on the Internet
4 Copyright (C) 2017 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.
17 #include <arpa/inet.h>
28 #include <loc/libloc.h>
29 #include <loc/compat.h>
30 #include <loc/country.h>
31 #include <loc/network.h>
32 #include <loc/private.h>
39 struct in6_addr first_address
;
40 struct in6_addr last_address
;
45 enum loc_network_flags flags
;
48 static int valid_prefix(struct in6_addr
* address
, unsigned int prefix
) {
49 // The prefix cannot be larger than 128 bits
53 // And the prefix cannot be zero
57 // For IPv4-mapped addresses the prefix has to be 96 or lager
58 if (IN6_IS_ADDR_V4MAPPED(address
) && prefix
<= 96)
64 static struct in6_addr
prefix_to_bitmask(unsigned int prefix
) {
65 struct in6_addr bitmask
;
67 for (unsigned int i
= 0; i
< 16; i
++)
68 bitmask
.s6_addr
[i
] = 0;
70 for (int i
= prefix
, j
= 0; i
> 0; i
-= 8, j
++) {
72 bitmask
.s6_addr
[j
] = 0xff;
74 bitmask
.s6_addr
[j
] = 0xff << (8 - i
);
80 static struct in6_addr
make_first_address(const struct in6_addr
* address
, const struct in6_addr
* bitmask
) {
83 // Perform bitwise AND
84 for (unsigned int i
= 0; i
< 4; i
++)
85 a
.s6_addr32
[i
] = address
->s6_addr32
[i
] & bitmask
->s6_addr32
[i
];
90 static struct in6_addr
make_last_address(const struct in6_addr
* address
, const struct in6_addr
* bitmask
) {
94 for (unsigned int i
= 0; i
< 4; i
++)
95 a
.s6_addr32
[i
] = address
->s6_addr32
[i
] | ~bitmask
->s6_addr32
[i
];
100 static struct in6_addr
address_increment(const struct in6_addr
* address
) {
101 struct in6_addr a
= *address
;
103 for (int octet
= 15; octet
>= 0; octet
--) {
104 if (a
.s6_addr
[octet
] < 255) {
108 a
.s6_addr
[octet
] = 0;
115 LOC_EXPORT
int loc_network_new(struct loc_ctx
* ctx
, struct loc_network
** network
,
116 struct in6_addr
* address
, unsigned int prefix
) {
117 // Address cannot be unspecified
118 if (IN6_IS_ADDR_UNSPECIFIED(address
)) {
119 DEBUG(ctx
, "Start address is unspecified\n");
123 // Address cannot be loopback
124 if (IN6_IS_ADDR_LOOPBACK(address
)) {
125 DEBUG(ctx
, "Start address is loopback address\n");
129 // Address cannot be link-local
130 if (IN6_IS_ADDR_LINKLOCAL(address
)) {
131 DEBUG(ctx
, "Start address cannot be link-local\n");
135 // Address cannot be site-local
136 if (IN6_IS_ADDR_SITELOCAL(address
)) {
137 DEBUG(ctx
, "Start address cannot be site-local\n");
141 // Validate the prefix
142 if (valid_prefix(address
, prefix
) != 0) {
143 DEBUG(ctx
, "Invalid prefix: %u\n", prefix
);
147 struct loc_network
* n
= calloc(1, sizeof(*n
));
151 n
->ctx
= loc_ref(ctx
);
157 // Convert the prefix into a bitmask
158 struct in6_addr bitmask
= prefix_to_bitmask(n
->prefix
);
160 // Store the first and last address in the network
161 n
->first_address
= make_first_address(address
, &bitmask
);
162 n
->last_address
= make_last_address(&n
->first_address
, &bitmask
);
165 if (IN6_IS_ADDR_V4MAPPED(&n
->first_address
))
168 n
->family
= AF_INET6
;
170 DEBUG(n
->ctx
, "Network allocated at %p\n", n
);
175 LOC_EXPORT
int loc_network_new_from_string(struct loc_ctx
* ctx
, struct loc_network
** network
,
176 const char* address_string
) {
177 struct in6_addr first_address
;
179 unsigned int prefix
= 128;
182 DEBUG(ctx
, "Attempting to parse network %s\n", address_string
);
184 // Make a copy of the string to work on it
185 char* buffer
= strdup(address_string
);
186 address_string
= prefix_string
= buffer
;
188 // Split address and prefix
189 address_string
= strsep(&prefix_string
, "/");
191 DEBUG(ctx
, " Split into address = %s, prefix = %s\n", address_string
, prefix_string
);
194 r
= loc_parse_address(ctx
, address_string
, &first_address
);
196 DEBUG(ctx
, "The address could not be parsed\n");
200 // If a prefix was given, we will try to parse it
202 // Convert prefix to integer
203 prefix
= strtol(prefix_string
, NULL
, 10);
206 DEBUG(ctx
, "The prefix was not parsable: %s\n", prefix_string
);
210 // Map the prefix to IPv6 if needed
211 if (IN6_IS_ADDR_V4MAPPED(&first_address
))
216 // Free temporary buffer
219 // Exit if the parsing was unsuccessful
223 // Create a new network
224 return loc_network_new(ctx
, network
, &first_address
, prefix
);
227 LOC_EXPORT
struct loc_network
* loc_network_ref(struct loc_network
* network
) {
233 static void loc_network_free(struct loc_network
* network
) {
234 DEBUG(network
->ctx
, "Releasing network at %p\n", network
);
236 loc_unref(network
->ctx
);
240 LOC_EXPORT
struct loc_network
* loc_network_unref(struct loc_network
* network
) {
244 if (--network
->refcount
> 0)
247 loc_network_free(network
);
251 static int format_ipv6_address(const struct in6_addr
* address
, char* string
, size_t length
) {
252 const char* ret
= inet_ntop(AF_INET6
, address
, string
, length
);
259 static int format_ipv4_address(const struct in6_addr
* address
, char* string
, size_t length
) {
260 struct in_addr ipv4_address
;
261 ipv4_address
.s_addr
= address
->s6_addr32
[3];
263 const char* ret
= inet_ntop(AF_INET
, &ipv4_address
, string
, length
);
270 LOC_EXPORT
char* loc_network_str(struct loc_network
* network
) {
272 const size_t length
= INET6_ADDRSTRLEN
+ 4;
274 char* string
= malloc(length
);
278 unsigned int prefix
= network
->prefix
;
280 switch (network
->family
) {
282 r
= format_ipv6_address(&network
->first_address
, string
, length
);
286 r
= format_ipv4_address(&network
->first_address
, string
, length
);
296 ERROR(network
->ctx
, "Could not convert network to string: %s\n", strerror(errno
));
303 sprintf(string
+ strlen(string
), "/%u", prefix
);
308 LOC_EXPORT
int loc_network_address_family(struct loc_network
* network
) {
309 return network
->family
;
312 static char* loc_network_format_address(struct loc_network
* network
, const struct in6_addr
* address
) {
313 const size_t length
= INET6_ADDRSTRLEN
;
315 char* string
= malloc(length
);
321 switch (network
->family
) {
323 r
= format_ipv6_address(address
, string
, length
);
327 r
= format_ipv4_address(address
, string
, length
);
336 ERROR(network
->ctx
, "Could not format IP address to string: %s\n", strerror(errno
));
345 LOC_EXPORT
char* loc_network_format_first_address(struct loc_network
* network
) {
346 return loc_network_format_address(network
, &network
->first_address
);
349 LOC_EXPORT
char* loc_network_format_last_address(struct loc_network
* network
) {
350 return loc_network_format_address(network
, &network
->last_address
);
353 LOC_EXPORT
int loc_network_match_address(struct loc_network
* network
, const struct in6_addr
* address
) {
354 // Address must be larger than the start address
355 if (in6_addr_cmp(&network
->first_address
, address
) > 0)
358 // Address must be smaller than the last address
359 if (in6_addr_cmp(&network
->last_address
, address
) < 0)
362 // The address is inside this network
366 LOC_EXPORT
const char* loc_network_get_country_code(struct loc_network
* network
) {
367 return network
->country_code
;
370 LOC_EXPORT
int loc_network_set_country_code(struct loc_network
* network
, const char* country_code
) {
371 // Set empty country code
372 if (!country_code
|| !*country_code
) {
373 *network
->country_code
= '\0';
377 // Check country code
378 if (!loc_country_code_is_valid(country_code
))
381 loc_country_code_copy(network
->country_code
, country_code
);
386 LOC_EXPORT
int loc_network_match_country_code(struct loc_network
* network
, const char* country_code
) {
387 // Check country code
388 if (!loc_country_code_is_valid(country_code
))
391 return (network
->country_code
[0] == country_code
[0])
392 && (network
->country_code
[1] == country_code
[1]);
395 LOC_EXPORT
uint32_t loc_network_get_asn(struct loc_network
* network
) {
399 LOC_EXPORT
int loc_network_set_asn(struct loc_network
* network
, uint32_t asn
) {
405 LOC_EXPORT
int loc_network_match_asn(struct loc_network
* network
, uint32_t asn
) {
406 return network
->asn
== asn
;
409 LOC_EXPORT
int loc_network_has_flag(struct loc_network
* network
, uint32_t flag
) {
410 return network
->flags
& flag
;
413 LOC_EXPORT
int loc_network_set_flag(struct loc_network
* network
, uint32_t flag
) {
414 network
->flags
|= flag
;
419 LOC_EXPORT
int loc_network_match_flag(struct loc_network
* network
, uint32_t flag
) {
420 return loc_network_has_flag(network
, flag
);
423 LOC_EXPORT
int loc_network_eq(struct loc_network
* self
, struct loc_network
* other
) {
424 // Family must be the same
425 if (self
->family
!= other
->family
)
428 // The start address must be the same
429 if (in6_addr_cmp(&self
->first_address
, &other
->first_address
) != 0)
432 // The prefix length must be the same
433 if (self
->prefix
!= other
->prefix
)
439 static int loc_network_gt(struct loc_network
* self
, struct loc_network
* other
) {
440 // Families must match
441 if (self
->family
!= other
->family
)
444 int r
= in6_addr_cmp(&self
->first_address
, &other
->first_address
);
459 if (self
->prefix
> other
->prefix
)
466 LOC_EXPORT
int loc_network_overlaps(struct loc_network
* self
, struct loc_network
* other
) {
467 if (loc_network_match_address(self
, &other
->first_address
) == 0)
470 if (loc_network_match_address(self
, &other
->last_address
) == 0)
473 if (loc_network_match_address(other
, &self
->first_address
) == 0)
476 if (loc_network_match_address(other
, &self
->last_address
) == 0)
482 LOC_EXPORT
int loc_network_is_subnet(struct loc_network
* self
, struct loc_network
* other
) {
483 // If the start address of the other network is smaller than this network,
484 // it cannot be a subnet.
485 if (in6_addr_cmp(&self
->first_address
, &other
->first_address
) < 0)
488 // If the end address of the other network is greater than this network,
489 // it cannot be a subnet.
490 if (in6_addr_cmp(&self
->last_address
, &other
->last_address
) > 0)
496 // XXX DEPRECATED - I find this too difficult to use
497 LOC_EXPORT
int loc_network_is_subnet_of(struct loc_network
* self
, struct loc_network
* other
) {
498 // If the start address of the other network is smaller than this network,
499 // it cannot be a subnet.
500 if (in6_addr_cmp(&self
->first_address
, &other
->first_address
) < 0)
503 // If the end address of the other network is greater than this network,
504 // it cannot be a subnet.
505 if (in6_addr_cmp(&self
->last_address
, &other
->last_address
) > 0)
511 LOC_EXPORT
struct loc_network_list
* loc_network_subnets(struct loc_network
* network
) {
512 struct loc_network_list
* list
;
515 unsigned int prefix
= network
->prefix
+ 1;
517 // Check if the new prefix is valid
518 if (valid_prefix(&network
->first_address
, prefix
))
521 // Create a new list with the result
522 int r
= loc_network_list_new(network
->ctx
, &list
);
524 ERROR(network
->ctx
, "Could not create network list: %d\n", r
);
528 struct loc_network
* subnet1
= NULL
;
529 struct loc_network
* subnet2
= NULL
;
531 // Create the first half of the network
532 r
= loc_network_new(network
->ctx
, &subnet1
, &network
->first_address
, prefix
);
536 // The next subnet starts after the first one
537 struct in6_addr first_address
= address_increment(&subnet1
->last_address
);
539 // Create the second half of the network
540 r
= loc_network_new(network
->ctx
, &subnet2
, &first_address
, prefix
);
544 // Push the both onto the stack (in reverse order)
545 r
= loc_network_list_push(list
, subnet2
);
549 r
= loc_network_list_push(list
, subnet1
);
554 const char* country_code
= loc_network_get_country_code(network
);
556 loc_network_set_country_code(subnet1
, country_code
);
557 loc_network_set_country_code(subnet2
, country_code
);
561 uint32_t asn
= loc_network_get_asn(network
);
563 loc_network_set_asn(subnet1
, asn
);
564 loc_network_set_asn(subnet2
, asn
);
567 loc_network_unref(subnet1
);
568 loc_network_unref(subnet2
);
574 loc_network_unref(subnet1
);
577 loc_network_unref(subnet2
);
580 loc_network_list_unref(list
);
585 LOC_EXPORT
struct loc_network_list
* loc_network_exclude(
586 struct loc_network
* self
, struct loc_network
* other
) {
587 struct loc_network_list
* list
;
590 char* n1
= loc_network_str(self
);
591 char* n2
= loc_network_str(other
);
593 DEBUG(self
->ctx
, "Returning %s excluding %s...\n", n1
, n2
);
600 if (self
->family
!= other
->family
) {
601 DEBUG(self
->ctx
, "Family mismatch\n");
606 // Other must be a subnet of self
607 if (!loc_network_is_subnet_of(other
, self
)) {
608 DEBUG(self
->ctx
, "Network %p is not contained in network %p\n", other
, self
);
613 // We cannot perform this operation if both networks equal
614 if (loc_network_eq(self
, other
)) {
615 DEBUG(self
->ctx
, "Networks %p and %p are equal\n", self
, other
);
620 // Create a new list with the result
621 int r
= loc_network_list_new(self
->ctx
, &list
);
623 ERROR(self
->ctx
, "Could not create network list: %d\n", r
);
627 struct loc_network_list
* subnets
= loc_network_subnets(self
);
629 struct loc_network
* subnet1
= NULL
;
630 struct loc_network
* subnet2
= NULL
;
633 // Fetch both subnets
634 subnet1
= loc_network_list_get(subnets
, 0);
635 subnet2
= loc_network_list_get(subnets
, 1);
638 loc_network_list_unref(subnets
);
641 if (loc_network_eq(other
, subnet1
)) {
642 r
= loc_network_list_push(list
, subnet2
);
646 } else if (loc_network_eq(other
, subnet2
)) {
647 r
= loc_network_list_push(list
, subnet1
);
651 } else if (loc_network_is_subnet_of(other
, subnet1
)) {
652 r
= loc_network_list_push(list
, subnet2
);
656 subnets
= loc_network_subnets(subnet1
);
658 } else if (loc_network_is_subnet_of(other
, subnet2
)) {
659 r
= loc_network_list_push(list
, subnet1
);
663 subnets
= loc_network_subnets(subnet2
);
666 ERROR(self
->ctx
, "We should never get here\n");
670 loc_network_unref(subnet1
);
671 loc_network_unref(subnet2
);
675 loc_network_list_dump(list
);
683 loc_network_unref(subnet1
);
686 loc_network_unref(subnet2
);
689 loc_network_list_unref(list
);
694 LOC_EXPORT
struct loc_network_list
* loc_network_exclude_list(
695 struct loc_network
* network
, struct loc_network_list
* list
) {
696 struct loc_network_list
* to_check
;
698 // Create a new list with all networks to look at
699 int r
= loc_network_list_new(network
->ctx
, &to_check
);
703 struct loc_network
* subnet
= NULL
;
704 struct loc_network_list
* subnets
= NULL
;
706 for (unsigned int i
= 0; i
< loc_network_list_size(list
); i
++) {
707 subnet
= loc_network_list_get(list
, i
);
709 // Find all excluded networks
710 struct loc_network_list
* excluded
= loc_network_exclude(network
, subnet
);
712 // Add them all to the "to check" list
713 loc_network_list_merge(to_check
, excluded
);
714 loc_network_list_unref(excluded
);
718 loc_network_unref(subnet
);
721 r
= loc_network_list_new(network
->ctx
, &subnets
);
723 loc_network_list_unref(to_check
);
727 while (!loc_network_list_empty(to_check
)) {
728 struct loc_network
* subnet_to_check
= loc_network_list_pop(to_check
);
730 // Marks whether this subnet passed all checks
733 for (unsigned int i
= 0; i
< loc_network_list_size(list
); i
++) {
734 subnet
= loc_network_list_get(list
, i
);
736 // Drop this subnet if is is already in list
737 if (loc_network_eq(subnet_to_check
, subnet
)) {
739 loc_network_unref(subnet
);
743 // Drop this subnet if is a subnet of another subnet
744 if (loc_network_is_subnet_of(subnet
, subnet_to_check
)) {
746 loc_network_unref(subnet
);
750 // Break it down if it overlaps
751 if (loc_network_overlaps(subnet_to_check
, subnet
)) {
754 struct loc_network_list
* excluded
= loc_network_exclude(subnet_to_check
, subnet
);
756 loc_network_list_merge(to_check
, excluded
);
757 loc_network_list_unref(excluded
);
760 loc_network_unref(subnet
);
764 loc_network_unref(subnet
);
768 r
= loc_network_list_push(subnets
, subnet_to_check
);
771 loc_network_unref(subnet_to_check
);
774 loc_network_list_unref(to_check
);
779 LOC_EXPORT
int loc_network_to_database_v1(struct loc_network
* network
, struct loc_database_network_v1
* dbobj
) {
781 loc_country_code_copy(dbobj
->country_code
, network
->country_code
);
784 dbobj
->asn
= htobe32(network
->asn
);
787 dbobj
->flags
= htobe16(network
->flags
);
792 LOC_EXPORT
int loc_network_new_from_database_v1(struct loc_ctx
* ctx
, struct loc_network
** network
,
793 struct in6_addr
* address
, unsigned int prefix
, const struct loc_database_network_v1
* dbobj
) {
794 char country_code
[3] = "\0\0";
796 int r
= loc_network_new(ctx
, network
, address
, prefix
);
798 ERROR(ctx
, "Could not allocate a new network: %s", strerror(-r
));
802 // Import country code
803 loc_country_code_copy(country_code
, dbobj
->country_code
);
805 r
= loc_network_set_country_code(*network
, country_code
);
807 ERROR(ctx
, "Could not set country code: %s\n", country_code
);
812 uint32_t asn
= be32toh(dbobj
->asn
);
813 r
= loc_network_set_asn(*network
, asn
);
815 ERROR(ctx
, "Could not set ASN: %d\n", asn
);
820 int flags
= be16toh(dbobj
->flags
);
821 r
= loc_network_set_flag(*network
, flags
);
823 ERROR(ctx
, "Could not set flags: %d\n", flags
);
830 struct loc_network_tree
{
834 struct loc_network_tree_node
* root
;
837 struct loc_network_tree_node
{
841 struct loc_network_tree_node
* zero
;
842 struct loc_network_tree_node
* one
;
844 struct loc_network
* network
;
847 LOC_EXPORT
int loc_network_tree_new(struct loc_ctx
* ctx
, struct loc_network_tree
** tree
) {
848 struct loc_network_tree
* t
= calloc(1, sizeof(*t
));
852 t
->ctx
= loc_ref(ctx
);
855 // Create the root node
856 int r
= loc_network_tree_node_new(ctx
, &t
->root
);
858 loc_network_tree_unref(t
);
862 DEBUG(t
->ctx
, "Network tree allocated at %p\n", t
);
867 LOC_EXPORT
struct loc_network_tree_node
* loc_network_tree_get_root(struct loc_network_tree
* tree
) {
868 return loc_network_tree_node_ref(tree
->root
);
871 static struct loc_network_tree_node
* loc_network_tree_get_node(struct loc_network_tree_node
* node
, int path
) {
872 struct loc_network_tree_node
** n
;
879 // If the desired node doesn't exist, yet, we will create it
881 int r
= loc_network_tree_node_new(node
->ctx
, n
);
889 static struct loc_network_tree_node
* loc_network_tree_get_path(struct loc_network_tree
* tree
, const struct in6_addr
* address
, unsigned int prefix
) {
890 struct loc_network_tree_node
* node
= tree
->root
;
892 for (unsigned int i
= 0; i
< prefix
; i
++) {
893 // Check if the ith bit is one or zero
894 node
= loc_network_tree_get_node(node
, in6_addr_get_bit(address
, i
));
900 static int __loc_network_tree_walk(struct loc_ctx
* ctx
, struct loc_network_tree_node
* node
,
901 int(*filter_callback
)(struct loc_network
* network
, void* data
),
902 int(*callback
)(struct loc_network
* network
, void* data
), void* data
) {
905 // Finding a network ends the walk here
907 if (filter_callback
) {
908 int f
= filter_callback(node
->network
, data
);
912 // Skip network if filter function returns value greater than zero
917 r
= callback(node
->network
, data
);
922 // Walk down on the left side of the tree first
924 r
= __loc_network_tree_walk(ctx
, node
->zero
, filter_callback
, callback
, data
);
929 // Then walk on the other side
931 r
= __loc_network_tree_walk(ctx
, node
->one
, filter_callback
, callback
, data
);
939 LOC_EXPORT
int loc_network_tree_walk(struct loc_network_tree
* tree
,
940 int(*filter_callback
)(struct loc_network
* network
, void* data
),
941 int(*callback
)(struct loc_network
* network
, void* data
), void* data
) {
942 return __loc_network_tree_walk(tree
->ctx
, tree
->root
, filter_callback
, callback
, data
);
945 static void loc_network_tree_free(struct loc_network_tree
* tree
) {
946 DEBUG(tree
->ctx
, "Releasing network tree at %p\n", tree
);
948 loc_network_tree_node_unref(tree
->root
);
950 loc_unref(tree
->ctx
);
954 LOC_EXPORT
struct loc_network_tree
* loc_network_tree_unref(struct loc_network_tree
* tree
) {
955 if (--tree
->refcount
> 0)
958 loc_network_tree_free(tree
);
962 static int __loc_network_tree_dump(struct loc_network
* network
, void* data
) {
963 DEBUG(network
->ctx
, "Dumping network at %p\n", network
);
965 char* s
= loc_network_str(network
);
969 INFO(network
->ctx
, "%s\n", s
);
975 LOC_EXPORT
int loc_network_tree_dump(struct loc_network_tree
* tree
) {
976 DEBUG(tree
->ctx
, "Dumping network tree at %p\n", tree
);
978 return loc_network_tree_walk(tree
, NULL
, __loc_network_tree_dump
, NULL
);
981 LOC_EXPORT
int loc_network_tree_add_network(struct loc_network_tree
* tree
, struct loc_network
* network
) {
982 DEBUG(tree
->ctx
, "Adding network %p to tree %p\n", network
, tree
);
984 struct loc_network_tree_node
* node
= loc_network_tree_get_path(tree
,
985 &network
->first_address
, network
->prefix
);
987 ERROR(tree
->ctx
, "Could not find a node\n");
991 // Check if node has not been set before
993 DEBUG(tree
->ctx
, "There is already a network at this path\n");
997 // Point node to the network
998 node
->network
= loc_network_ref(network
);
1003 static int __loc_network_tree_count(struct loc_network
* network
, void* data
) {
1004 size_t* counter
= (size_t*)data
;
1006 // Increase the counter for each network
1012 LOC_EXPORT
size_t loc_network_tree_count_networks(struct loc_network_tree
* tree
) {
1015 int r
= loc_network_tree_walk(tree
, NULL
, __loc_network_tree_count
, &counter
);
1022 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node
* node
) {
1026 counter
+= __loc_network_tree_count_nodes(node
->zero
);
1029 counter
+= __loc_network_tree_count_nodes(node
->one
);
1034 LOC_EXPORT
size_t loc_network_tree_count_nodes(struct loc_network_tree
* tree
) {
1035 return __loc_network_tree_count_nodes(tree
->root
);
1038 LOC_EXPORT
int loc_network_tree_node_new(struct loc_ctx
* ctx
, struct loc_network_tree_node
** node
) {
1039 struct loc_network_tree_node
* n
= calloc(1, sizeof(*n
));
1043 n
->ctx
= loc_ref(ctx
);
1046 n
->zero
= n
->one
= NULL
;
1048 DEBUG(n
->ctx
, "Network node allocated at %p\n", n
);
1053 LOC_EXPORT
struct loc_network_tree_node
* loc_network_tree_node_ref(struct loc_network_tree_node
* node
) {
1060 static void loc_network_tree_node_free(struct loc_network_tree_node
* node
) {
1061 DEBUG(node
->ctx
, "Releasing network node at %p\n", node
);
1064 loc_network_unref(node
->network
);
1067 loc_network_tree_node_unref(node
->zero
);
1070 loc_network_tree_node_unref(node
->one
);
1072 loc_unref(node
->ctx
);
1076 LOC_EXPORT
struct loc_network_tree_node
* loc_network_tree_node_unref(struct loc_network_tree_node
* node
) {
1080 if (--node
->refcount
> 0)
1083 loc_network_tree_node_free(node
);
1087 LOC_EXPORT
struct loc_network_tree_node
* loc_network_tree_node_get(struct loc_network_tree_node
* node
, unsigned int index
) {
1096 return loc_network_tree_node_ref(node
);
1099 LOC_EXPORT
int loc_network_tree_node_is_leaf(struct loc_network_tree_node
* node
) {
1100 return (!!node
->network
);
1103 LOC_EXPORT
struct loc_network
* loc_network_tree_node_get_network(struct loc_network_tree_node
* node
) {
1104 return loc_network_ref(node
->network
);
1109 struct loc_network_list
{
1110 struct loc_ctx
* ctx
;
1113 struct loc_network
* list
[1024];
1118 LOC_EXPORT
int loc_network_list_new(struct loc_ctx
* ctx
,
1119 struct loc_network_list
** list
) {
1120 struct loc_network_list
* l
= calloc(1, sizeof(*l
));
1124 l
->ctx
= loc_ref(ctx
);
1127 // Do not allow this list to grow larger than this
1130 DEBUG(l
->ctx
, "Network list allocated at %p\n", l
);
1135 LOC_EXPORT
struct loc_network_list
* loc_network_list_ref(struct loc_network_list
* list
) {
1141 static void loc_network_list_free(struct loc_network_list
* list
) {
1142 DEBUG(list
->ctx
, "Releasing network list at %p\n", list
);
1144 for (unsigned int i
= 0; i
< list
->size
; i
++)
1145 loc_network_unref(list
->list
[i
]);
1147 loc_unref(list
->ctx
);
1151 LOC_EXPORT
struct loc_network_list
* loc_network_list_unref(struct loc_network_list
* list
) {
1155 if (--list
->refcount
> 0)
1158 loc_network_list_free(list
);
1162 LOC_EXPORT
size_t loc_network_list_size(struct loc_network_list
* list
) {
1166 LOC_EXPORT
int loc_network_list_empty(struct loc_network_list
* list
) {
1167 return list
->size
== 0;
1170 LOC_EXPORT
void loc_network_list_clear(struct loc_network_list
* list
) {
1171 for (unsigned int i
= 0; i
< list
->size
; i
++)
1172 loc_network_unref(list
->list
[i
]);
1177 LOC_EXPORT
void loc_network_list_dump(struct loc_network_list
* list
) {
1178 struct loc_network
* network
;
1181 for (unsigned int i
= 0; i
< list
->size
; i
++) {
1182 network
= list
->list
[i
];
1184 s
= loc_network_str(network
);
1186 INFO(list
->ctx
, "%s\n", s
);
1191 LOC_EXPORT
struct loc_network
* loc_network_list_get(struct loc_network_list
* list
, size_t index
) {
1193 if (index
>= list
->size
)
1196 return loc_network_ref(list
->list
[index
]);
1199 LOC_EXPORT
int loc_network_list_push(struct loc_network_list
* list
, struct loc_network
* network
) {
1200 // Do not add networks that are already on the list
1201 if (loc_network_list_contains(list
, network
))
1204 // Check if we have space left
1205 if (list
->size
== list
->max_size
) {
1206 ERROR(list
->ctx
, "%p: Could not push network onto the stack: Stack full\n", list
);
1210 DEBUG(list
->ctx
, "%p: Pushing network %p onto stack\n", list
, network
);
1212 list
->list
[list
->size
++] = loc_network_ref(network
);
1217 LOC_EXPORT
struct loc_network
* loc_network_list_pop(struct loc_network_list
* list
) {
1218 // Return nothing when empty
1219 if (loc_network_list_empty(list
)) {
1220 DEBUG(list
->ctx
, "%p: Popped empty stack\n", list
);
1224 struct loc_network
* network
= list
->list
[--list
->size
];
1226 DEBUG(list
->ctx
, "%p: Popping network %p from stack\n", list
, network
);
1231 LOC_EXPORT
int loc_network_list_contains(struct loc_network_list
* list
, struct loc_network
* network
) {
1232 for (unsigned int i
= 0; i
< list
->size
; i
++) {
1233 if (loc_network_eq(list
->list
[i
], network
))
1240 static void loc_network_list_swap(struct loc_network_list
* list
, unsigned int i1
, unsigned int i2
) {
1241 // Do nothing for invalid indices
1242 if (i1
>= list
->size
|| i2
>= list
->size
)
1245 struct loc_network
* network1
= list
->list
[i1
];
1246 struct loc_network
* network2
= list
->list
[i2
];
1248 list
->list
[i1
] = network2
;
1249 list
->list
[i2
] = network1
;
1252 LOC_EXPORT
void loc_network_list_reverse(struct loc_network_list
* list
) {
1254 unsigned int j
= list
->size
- 1;
1257 loc_network_list_swap(list
, i
++, j
--);
1261 LOC_EXPORT
void loc_network_list_sort(struct loc_network_list
* list
) {
1262 unsigned int n
= list
->size
;
1268 for (unsigned int i
= 1; i
< n
; i
++) {
1269 if (loc_network_gt(list
->list
[i
-1], list
->list
[i
]) > 0) {
1270 loc_network_list_swap(list
, i
-1, i
);
1279 LOC_EXPORT
int loc_network_list_merge(
1280 struct loc_network_list
* self
, struct loc_network_list
* other
) {
1283 for (unsigned int i
= 0; i
< other
->size
; i
++) {
1284 r
= loc_network_list_push(self
, other
->list
[i
]);