Add deduplicated and memory-efficient string pool
[people/ms/libloc.git] / src / stringpool.c
CommitLineData
62b83e6d
MT
1/*
2 libloc - A library to determine the location of someone on the Internet
3
4 Copyright (C) 2017 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 <stddef.h>
19#include <stdio.h>
20#include <stdlib.h>
21#include <string.h>
22
23#include <loc/libloc.h>
24#include "libloc-private.h"
25#include "stringpool.h"
26
27struct loc_stringpool {
28 struct loc_ctx* ctx;
29
30 int refcount;
31 char* data;
32 char* pos;
33
34 ssize_t max_length;
35};
36
37LOC_EXPORT int loc_stringpool_new(struct loc_ctx* ctx, struct loc_stringpool** pool, size_t max_length) {
38 if (max_length <= 0)
39 return -EINVAL;
40
41 struct loc_stringpool* p = calloc(1, sizeof(*p));
42 if (!p)
43 return -ENOMEM;
44
45 p->ctx = loc_ref(ctx);
46 p->refcount = 1;
47 p->max_length = max_length;
48
49 // Allocate the data section
50 p->data = malloc(p->max_length);
51 p->pos = p->data;
52
53 DEBUG(p->ctx, "String pool allocated at %p\n", p);
54 DEBUG(p->ctx, " Maximum size: %zu bytes\n", p->max_length);
55 *pool = p;
56
57 return 0;
58}
59
60LOC_EXPORT struct loc_stringpool* loc_stringpool_ref(struct loc_stringpool* pool) {
61 pool->refcount++;
62
63 return pool;
64}
65
66static void loc_stringpool_free(struct loc_stringpool* pool) {
67 DEBUG(pool->ctx, "Releasing string pool %p\n", pool);
68
69 loc_unref(pool->ctx);
70
71 free(pool->data);
72 free(pool);
73}
74
75LOC_EXPORT struct loc_stringpool* loc_stringpool_unref(struct loc_stringpool* pool) {
76 if (--pool->refcount > 0)
77 return NULL;
78
79 loc_stringpool_free(pool);
80
81 return NULL;
82}
83
84static off_t loc_stringpool_get_offset(struct loc_stringpool* pool, const char* pos) {
85 if (pos < pool->data)
86 return -EFAULT;
87
88 if (pos > (pool->data + pool->max_length))
89 return -EFAULT;
90
91 return pos - pool->data;
92}
93
94static off_t loc_stringpool_get_next_offset(struct loc_stringpool* pool, off_t offset) {
95 const char* string = loc_stringpool_get(pool, offset);
96
97 return offset + strlen(string) + 1;
98}
99
100static size_t loc_stringpool_space_left(struct loc_stringpool* pool) {
101 return pool->max_length - loc_stringpool_get_offset(pool, pool->pos);
102}
103
104LOC_EXPORT const char* loc_stringpool_get(struct loc_stringpool* pool, off_t offset) {
105 if (offset >= (ssize_t)pool->max_length)
106 return NULL;
107
108 const char* string = pool->data + offset;
109
110 // If the string is empty, we have reached the end
111 if (!*string)
112 return NULL;
113
114 return string;
115}
116
117static off_t loc_stringpool_find(struct loc_stringpool* pool, const char* s) {
118 if (!s || !*s)
119 return -EINVAL;
120
121 off_t offset = 0;
122 while (offset < pool->max_length) {
123 const char* string = loc_stringpool_get(pool, offset);
124 if (!string)
125 break;
126
127 int r = strcmp(s, string);
128 if (r == 0)
129 return offset;
130
131 offset = loc_stringpool_get_next_offset(pool, offset);
132 }
133
134 return -ENOENT;
135}
136
137static off_t loc_stringpool_append(struct loc_stringpool* pool, const char* string) {
138 if (!string || !*string)
139 return -EINVAL;
140
141 DEBUG(pool->ctx, "Appending '%s' to string pool at %p\n", string, pool);
142
143 // Check if we have enough space left
144 size_t l = strlen(string) + 1;
145 if (l > loc_stringpool_space_left(pool)) {
146 DEBUG(pool->ctx, "Not enough space to append '%s'\n", string);
147 DEBUG(pool->ctx, " Need %zu bytes but only have %zu\n", l, loc_stringpool_space_left(pool));
148 return -ENOSPC;
149 }
150
151 off_t offset = loc_stringpool_get_offset(pool, pool->pos);
152
153 // Copy string byte by byte
154 while (*string && loc_stringpool_space_left(pool) > 1) {
155 *pool->pos++ = *string++;
156 }
157
158 // Terminate the string
159 *pool->pos++ = '\0';
160
161 return offset;
162}
163
164LOC_EXPORT off_t loc_stringpool_add(struct loc_stringpool* pool, const char* string) {
165 off_t offset = loc_stringpool_find(pool, string);
166 if (offset >= 0) {
167 DEBUG(pool->ctx, "Found '%s' at position %jd\n", string, offset);
168 return offset;
169 }
170
171 return loc_stringpool_append(pool, string);
172}
173
174LOC_EXPORT void loc_stringpool_dump(struct loc_stringpool* pool) {
175 off_t offset = 0;
176
177 while (offset < pool->max_length) {
178 const char* string = loc_stringpool_get(pool, offset);
179 if (!string)
180 break;
181
182 printf("%jd (%zu): %s\n", offset, strlen(string), string);
183
184 offset = loc_stringpool_get_next_offset(pool, offset);
185 }
186}