2 * Copyright © 2010 Codethink Limited
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the licence, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
19 * Author: Ryan Lortie <desrt@desrt.ca>
26 * The string info map is an efficient data structure designed to be
27 * used with a small set of items. It is used by GSettings schemas for
30 * 1) Implement <choices> with a list of valid strings
32 * 2) Implement <alias> by mapping one string to another
34 * 3) Implement enumerated types by mapping strings to integer values
37 * The map is made out of an array of uint32s. Each entry in the array
38 * is an integer value, followed by a specially formatted string value:
40 * The string starts with the byte 0xff or 0xfe, followed by the
41 * content of the string, followed by a nul byte, followed by
42 * additional nul bytes for padding, followed by a 0xff byte.
44 * Padding is added so that the entire formatted string takes up a
45 * multiple of 4 bytes, and not less than 8 bytes. The requirement
46 * for a string to take up 8 bytes is so that the scanner doesn't lose
47 * synch and mistake a string for an integer value.
49 * The first byte of the formatted string depends on if the integer is
50 * an enum value (0xff) or an alias (0xfe). If it is an alias then the
51 * number refers to the word offset within the info map at which the
52 * integer corresponding to the "target" value is stored.
54 * For example, consider the case of the string info map representing an
55 * enumerated type of 'foo' (value 1) and 'bar' (value 2) and 'baz'
56 * (alias for 'bar'). Note that string info maps are always little
59 * x01 x00 x00 x00 xff 'f' 'o' 'o' x00 x00 x00 xff x02 x00 x00 x00
60 * xff 'b' 'a' 'r' x00 x00 x00 xff x03 x00 x00 x00 xfe 'b' 'a' 'z'
64 * The operations that someone may want to perform with the map:
66 * - lookup if a string is valid (and not an alias)
67 * - lookup the integer value for a enum 'nick'
68 * - lookup the integer value for the target of an alias
69 * - lookup an alias and convert it to its target string
70 * - lookup the enum nick for a given value
72 * In order to lookup if a string is valid, it is padded on either side
73 * (as described) and scanned for in the array. For example, you might
76 * xff 'f' 'o' 'o' x00 x00 x00 xff
78 * In order to lookup the integer value for a nick, the string is padded
79 * on either side and scanned for in the array, as above. Instead of
80 * merely succeeding, we look at the integer value to the left of the
81 * match. This is the enum value.
83 * In order to lookup an alias and convert it to its target enum value,
84 * the string is padded on either side (as described, with 0xfe) and
85 * scanned for. For example, you might look for "baz":
87 * xfe 'b' 'a' 'z' x00 x00 x00 xff
89 * The integer immediately preceding the match then contains the offset
90 * of the integer value of the target. In our example, that's '3'.
91 * This index is dereferenced to find the enum value of '2'.
93 * To convert the alias to its target string, 5 bytes just need to be
94 * added past the start of the integer value to find the start of the
97 * To lookup the enum nick for a given value, the value is searched for
98 * in the array. To ensure that the value isn't matching the inside of a
99 * string, we must check that it is either the first item in the array or
100 * immediately preceded by the byte 0xff. It must also be immediately
101 * followed by the byte 0xff.
103 * Because strings always take up a minimum of 2 words, because 0xff or
104 * 0xfe never appear inside of a utf-8 string and because no two integer
105 * values ever appear in sequence, the only way we can have the
108 * xff __ __ __ __ xff (or 0xfe)
110 * is in the event of an integer nested between two strings.
112 * For implementation simplicity/efficiency, strings may not be more
113 * than 65 characters in length (ie: 17 32bit words after padding).
115 * In the event that we are doing <choices> (ie: not an enum type) then
116 * the value of each choice is set to zero and ignored.
119 #define STRINFO_MAX_WORDS 17
120 G_GNUC_UNUSED
static guint
121 strinfo_string_to_words (const gchar
*string
,
128 size
= strlen (string
);
130 n_words
= MAX (2, (size
+ 6) >> 2);
132 if (n_words
> STRINFO_MAX_WORDS
)
135 words
[0] = GUINT32_TO_LE (alias
? 0xfe : 0xff);
136 words
[n_words
- 1] = GUINT32_TO_BE (0xff);
137 memcpy (((gchar
*) words
) + 1, string
, size
+ 1);
142 G_GNUC_UNUSED
static gint
143 strinfo_scan (const guint32
*strinfo
,
145 const guint32
*words
,
150 if (length
< n_words
)
153 while (i
<= length
- n_words
)
157 for (j
= 0; j
< n_words
; j
++)
158 if (strinfo
[i
+ j
] != words
[j
])
162 return i
; /* match */
164 /* skip at least one word, continue */
171 G_GNUC_UNUSED
static gint
172 strinfo_find_string (const guint32
*strinfo
,
177 guint32 words
[STRINFO_MAX_WORDS
];
183 n_words
= strinfo_string_to_words (string
, words
, alias
);
185 return strinfo_scan (strinfo
+ 1, length
- 1, words
, n_words
);
188 G_GNUC_UNUSED
static gint
189 strinfo_find_integer (const guint32
*strinfo
,
195 for (i
= 0; i
< length
; i
++)
196 if (strinfo
[i
] == GUINT32_TO_LE (value
))
198 const guchar
*charinfo
= (const guchar
*) &strinfo
[i
];
200 /* make sure it has 0xff on either side */
201 if ((i
== 0 || charinfo
[-1] == 0xff) && charinfo
[4] == 0xff)
208 G_GNUC_UNUSED
static gboolean
209 strinfo_is_string_valid (const guint32
*strinfo
,
213 return strinfo_find_string (strinfo
, length
, string
, FALSE
) != -1;
216 G_GNUC_UNUSED
static gboolean
217 strinfo_enum_from_string (const guint32
*strinfo
,
224 index
= strinfo_find_string (strinfo
, length
, string
, FALSE
);
229 *result
= GUINT32_FROM_LE (strinfo
[index
]);
233 G_GNUC_UNUSED
static const gchar
*
234 strinfo_string_from_enum (const guint32
*strinfo
,
240 index
= strinfo_find_integer (strinfo
, length
, value
);
245 return 1 + (const gchar
*) &strinfo
[index
+ 1];
248 G_GNUC_UNUSED
static const gchar
*
249 strinfo_string_from_alias (const guint32
*strinfo
,
255 index
= strinfo_find_string (strinfo
, length
, alias
, TRUE
);
260 return 1 + (const gchar
*) &strinfo
[GUINT32_TO_LE (strinfo
[index
]) + 1];
263 G_GNUC_UNUSED
static GVariant
*
264 strinfo_enumerate (const guint32
*strinfo
,
267 GVariantBuilder builder
;
268 const gchar
*ptr
, *end
;
270 ptr
= (gpointer
) strinfo
;
271 end
= ptr
+ 4 * length
;
275 g_variant_builder_init (&builder
, G_VARIANT_TYPE_STRING_ARRAY
);
279 /* don't include aliases */
281 g_variant_builder_add (&builder
, "s", ptr
+ 1);
283 /* find the end of this string */
284 ptr
= memchr (ptr
, '\xff', end
- ptr
);
285 g_assert (ptr
!= NULL
);
287 /* skip over the int to the next string */
291 return g_variant_builder_end (&builder
);
294 G_GNUC_UNUSED
static void
295 strinfo_builder_append_item (GString
*builder
,
299 guint32 words
[STRINFO_MAX_WORDS
];
302 value
= GUINT32_TO_LE (value
);
304 n_words
= strinfo_string_to_words (string
, words
, FALSE
);
305 g_string_append_len (builder
, (void *) &value
, sizeof value
);
306 g_string_append_len (builder
, (void *) words
, 4 * n_words
);
309 G_GNUC_UNUSED
static gboolean
310 strinfo_builder_append_alias (GString
*builder
,
314 guint32 words
[STRINFO_MAX_WORDS
];
319 index
= strinfo_find_string ((const guint32
*) builder
->str
,
320 builder
->len
/ 4, target
, FALSE
);
325 value
= GUINT32_TO_LE (index
);
327 n_words
= strinfo_string_to_words (alias
, words
, TRUE
);
328 g_string_append_len (builder
, (void *) &value
, sizeof value
);
329 g_string_append_len (builder
, (void *) words
, 4 * n_words
);
334 G_GNUC_UNUSED
static gboolean
335 strinfo_builder_contains (GString
*builder
,
338 return strinfo_find_string ((const guint32
*) builder
->str
,
339 builder
->len
/ 4, string
, FALSE
) != -1 ||
340 strinfo_find_string ((const guint32
*) builder
->str
,
341 builder
->len
/ 4, string
, TRUE
) != -1;
344 G_GNUC_UNUSED
static gboolean
345 strinfo_builder_contains_value (GString
*builder
,
348 return strinfo_string_from_enum ((const guint32
*) builder
->str
,
349 builder
->len
/ 4, value
) != NULL
;