[location/libloc.git] / src / network-list.c

/*
	libloc - A library to determine the location of someone on the Internet

	Copyright (C) 2020 IPFire Development Team <info@ipfire.org>

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	This library is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
	Lesser General Public License for more details.
*/

#include <errno.h>
#include <stdlib.h>

#include <loc/libloc.h>
#include <loc/network.h>
#include <loc/private.h>

struct loc_network_list {
	struct loc_ctx* ctx;
	int refcount;

	struct loc_network** elements;
	size_t elements_size;

	size_t size;
};

static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
	DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
		list, size, list->elements_size + size);

	struct loc_network** elements = reallocarray(list->elements,
			list->elements_size + size, sizeof(*list->elements));
	if (!elements)
		return -errno;

	list->elements = elements;
	list->elements_size += size;

	return 0;
}

LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
		struct loc_network_list** list) {
	struct loc_network_list* l = calloc(1, sizeof(*l));
	if (!l)
		return -ENOMEM;

	l->ctx = loc_ref(ctx);
	l->refcount = 1;

	DEBUG(l->ctx, "Network list allocated at %p\n", l);
	*list = l;
	return 0;
}

LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
	list->refcount++;

	return list;
}

static void loc_network_list_free(struct loc_network_list* list) {
	DEBUG(list->ctx, "Releasing network list at %p\n", list);

	for (unsigned int i = 0; i < list->size; i++)
		loc_network_unref(list->elements[i]);

	loc_unref(list->ctx);
	free(list);
}

LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
	if (!list)
		return NULL;

	if (--list->refcount > 0)
		return list;

	loc_network_list_free(list);
	return NULL;
}

LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
	return list->size;
}

LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
	return list->size == 0;
}

LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
	if (!list->elements)
		return;

	for (unsigned int i = 0; i < list->size; i++)
		loc_network_unref(list->elements[i]);

	free(list->elements);
	list->elements_size = 0;

	list->size = 0;
}

LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
	struct loc_network* network;
	char* s;

	for (unsigned int i = 0; i < list->size; i++) {
		network = list->elements[i];

		s = loc_network_str(network);

		INFO(list->ctx, "%s\n", s);
		free(s);
	}
}

LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
	// Check index
	if (index >= list->size)
		return NULL;

	return loc_network_ref(list->elements[index]);
}

LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
	// Do not add networks that are already on the list
	if (loc_network_list_contains(list, network))
		return 0;

	// Check if we have space left
	if (list->size >= list->elements_size) {
		int r = loc_network_list_grow(list, 64);
		if (r)
			return r;
	}

	DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);

	list->elements[list->size++] = loc_network_ref(network);

	return 0;
}

LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
	// Return nothing when empty
	if (loc_network_list_empty(list)) {
		DEBUG(list->ctx, "%p: Popped empty stack\n", list);
		return NULL;
	}

	struct loc_network* network = list->elements[--list->size];

	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);

	return network;
}

LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
	// Return nothing when empty
	if (loc_network_list_empty(list)) {
		DEBUG(list->ctx, "%p: Popped empty stack\n", list);
		return NULL;
	}

	struct loc_network* network = list->elements[0];

	// Move all elements to the top of the stack
	for (unsigned int i = 0; i < --list->size; i++) {
		list->elements[i] = list->elements[i+1];
	}

	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);

	return network;
}

LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
	for (unsigned int i = 0; i < list->size; i++) {
		if (loc_network_eq(list->elements[i], network))
			return 1;
	}

	return 0;
}

static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
	// Do nothing for invalid indices
	if (i1 >= list->size || i2 >= list->size)
		return;

	struct loc_network* network1 = list->elements[i1];
	struct loc_network* network2 = list->elements[i2];

	list->elements[i1] = network2;
	list->elements[i2] = network1;
}

LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
	unsigned int i = 0;
	unsigned int j = list->size - 1;

	while (i < j) {
		loc_network_list_swap(list, i++, j--);
	}
}

LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
	unsigned int n = list->size;
	int swapped;

	do {
		swapped = 0;

		for (unsigned int i = 1; i < n; i++) {
			if (loc_network_gt(list->elements[i-1], list->elements[i]) > 0) {
				loc_network_list_swap(list, i-1, i);
				swapped = 1;
			}
		}

		n--;
	} while (swapped);
}

LOC_EXPORT int loc_network_list_merge(
		struct loc_network_list* self, struct loc_network_list* other) {
	int r;

	for (unsigned int i = 0; i < other->size; i++) {
		r = loc_network_list_push(self, other->elements[i]);
		if (r)
			return r;
	}

	return 0;
}

LOC_EXPORT int loc_network_list_merge_reverse(
		struct loc_network_list* self, struct loc_network_list* other) {
	int r;

	for (int i = other->size - 1; i >= 0; i--) {
		r = loc_network_list_push(self, other->elements[i]);
		if (r)
			return r;
	}

	return 0;
}
Commit	Line	Data
e0b9ff5f MT	1	/*
	2	libloc - A library to determine the location of someone on the Internet
	3
	4	Copyright (C) 2020 IPFire Development Team <info@ipfire.org>
	5
	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.
	10
	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.
	15	*/
	16
	17	#include <errno.h>
	18	#include <stdlib.h>
	19
	20	#include <loc/libloc.h>
	21	#include <loc/network.h>
	22	#include <loc/private.h>
	23
	24	struct loc_network_list {
	25	struct loc_ctx* ctx;
	26	int refcount;
	27
3b44e421 MT	28	struct loc_network** elements;
	29	size_t elements_size;
	30
e0b9ff5f	31	size_t size;
e0b9ff5f MT	32	};
e0b9ff5f MT	33
3b44e421 MT	34	static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
	35	DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
	36	list, size, list->elements_size + size);
	37
	38	struct loc_network** elements = reallocarray(list->elements,
	39	list->elements_size + size, sizeof(*list->elements));
	40	if (!elements)
	41	return -errno;
	42
	43	list->elements = elements;
	44	list->elements_size += size;
	45
	46	return 0;
	47	}
	48
e0b9ff5f MT	49	LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
	50	struct loc_network_list** list) {
	51	struct loc_network_list* l = calloc(1, sizeof(*l));
	52	if (!l)
	53	return -ENOMEM;
	54
	55	l->ctx = loc_ref(ctx);
	56	l->refcount = 1;
	57
e0b9ff5f MT	58	DEBUG(l->ctx, "Network list allocated at %p\n", l);
	59	*list = l;
	60	return 0;
	61	}
	62
	63	LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
	64	list->refcount++;
	65
	66	return list;
	67	}
	68
	69	static void loc_network_list_free(struct loc_network_list* list) {
	70	DEBUG(list->ctx, "Releasing network list at %p\n", list);
	71
	72	for (unsigned int i = 0; i < list->size; i++)
3b44e421	73	loc_network_unref(list->elements[i]);
e0b9ff5f MT	74
	75	loc_unref(list->ctx);
	76	free(list);
	77	}
	78
	79	LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
	80	if (!list)
	81	return NULL;
	82
	83	if (--list->refcount > 0)
	84	return list;
	85
	86	loc_network_list_free(list);
	87	return NULL;
	88	}
	89
	90	LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
	91	return list->size;
	92	}
	93
	94	LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
	95	return list->size == 0;
	96	}
	97
	98	LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
248f5e04 MT	99	if (!list->elements)
	100	return;
	101
e0b9ff5f	102	for (unsigned int i = 0; i < list->size; i++)
3b44e421	103	loc_network_unref(list->elements[i]);
e0b9ff5f	104
248f5e04 MT	105	free(list->elements);
	106	list->elements_size = 0;
	107
e0b9ff5f MT	108	list->size = 0;
	109	}
	110
	111	LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
	112	struct loc_network* network;
	113	char* s;
	114
	115	for (unsigned int i = 0; i < list->size; i++) {
3b44e421	116	network = list->elements[i];
e0b9ff5f MT	117
	118	s = loc_network_str(network);
	119
	120	INFO(list->ctx, "%s\n", s);
	121	free(s);
	122	}
	123	}
	124
	125	LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
	126	// Check index
	127	if (index >= list->size)
	128	return NULL;
	129
3b44e421	130	return loc_network_ref(list->elements[index]);
e0b9ff5f MT	131	}
	132
	133	LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
	134	// Do not add networks that are already on the list
	135	if (loc_network_list_contains(list, network))
	136	return 0;
	137
	138	// Check if we have space left
3b44e421 MT	139	if (list->size >= list->elements_size) {
	140	int r = loc_network_list_grow(list, 64);
	141	if (r)
	142	return r;
e0b9ff5f MT	143	}
	144
	145	DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
	146
3b44e421	147	list->elements[list->size++] = loc_network_ref(network);
e0b9ff5f MT	148
	149	return 0;
	150	}
	151
	152	LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
	153	// Return nothing when empty
	154	if (loc_network_list_empty(list)) {
	155	DEBUG(list->ctx, "%p: Popped empty stack\n", list);
	156	return NULL;
	157	}
	158
3b44e421	159	struct loc_network* network = list->elements[--list->size];
e0b9ff5f MT	160
	161	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
	162
	163	return network;
	164	}
	165
	166	LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
	167	// Return nothing when empty
	168	if (loc_network_list_empty(list)) {
	169	DEBUG(list->ctx, "%p: Popped empty stack\n", list);
	170	return NULL;
	171	}
	172
3b44e421	173	struct loc_network* network = list->elements[0];
e0b9ff5f MT	174
	175	// Move all elements to the top of the stack
	176	for (unsigned int i = 0; i < --list->size; i++) {
3b44e421	177	list->elements[i] = list->elements[i+1];
e0b9ff5f MT	178	}
	179
	180	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
	181
	182	return network;
	183	}
	184
	185	LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
	186	for (unsigned int i = 0; i < list->size; i++) {
3b44e421	187	if (loc_network_eq(list->elements[i], network))
e0b9ff5f MT	188	return 1;
	189	}
	190
	191	return 0;
	192	}
	193
	194	static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
	195	// Do nothing for invalid indices
	196	if (i1 >= list->size \|\| i2 >= list->size)
	197	return;
	198
3b44e421 MT	199	struct loc_network* network1 = list->elements[i1];
3b44e421 MT	200	struct loc_network* network2 = list->elements[i2];
e0b9ff5f	201
3b44e421 MT	202	list->elements[i1] = network2;
3b44e421 MT	203	list->elements[i2] = network1;
e0b9ff5f MT	204	}
	205
	206	LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
	207	unsigned int i = 0;
	208	unsigned int j = list->size - 1;
	209
	210	while (i < j) {
	211	loc_network_list_swap(list, i++, j--);
	212	}
	213	}
	214
	215	LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
	216	unsigned int n = list->size;
	217	int swapped;
	218
	219	do {
	220	swapped = 0;
	221
	222	for (unsigned int i = 1; i < n; i++) {
3b44e421	223	if (loc_network_gt(list->elements[i-1], list->elements[i]) > 0) {
e0b9ff5f MT	224	loc_network_list_swap(list, i-1, i);
	225	swapped = 1;
	226	}
	227	}
	228
	229	n--;
	230	} while (swapped);
	231	}
	232
	233	LOC_EXPORT int loc_network_list_merge(
	234	struct loc_network_list* self, struct loc_network_list* other) {
	235	int r;
	236
	237	for (unsigned int i = 0; i < other->size; i++) {
3b44e421	238	r = loc_network_list_push(self, other->elements[i]);
e0b9ff5f MT	239	if (r)
	240	return r;
	241	}
	242
	243	return 0;
	244	}
a1024390 MT	245
	246	LOC_EXPORT int loc_network_list_merge_reverse(
	247	struct loc_network_list* self, struct loc_network_list* other) {
	248	int r;
	249
	250	for (int i = other->size - 1; i >= 0; i--) {
	251	r = loc_network_list_push(self, other->elements[i]);
	252	if (r)
	253	return r;
	254	}
	255
	256	return 0;
	257	}