Add deduplicated and memory-efficient string pool
[people/ms/libloc.git] / src / stringpool.c
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
27 struct 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
37 LOC_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
60 LOC_EXPORT struct loc_stringpool* loc_stringpool_ref(struct loc_stringpool* pool) {
61         pool->refcount++;
62
63         return pool;
64 }
65
66 static 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
75 LOC_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
84 static 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
94 static 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
100 static size_t loc_stringpool_space_left(struct loc_stringpool* pool) {
101         return pool->max_length - loc_stringpool_get_offset(pool, pool->pos);
102 }
103
104 LOC_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
117 static 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
137 static 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
164 LOC_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
174 LOC_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 }