1/* -*- tab-width: 4; -*- */
2/* vi: set sw=2 ts=4 expandtab: */
3
4/*
5 * Copyright 2010-2020 The Khronos Group Inc.
6 * SPDX-License-Identifier: Apache-2.0
7 */
8
9/**
10 * @internal
11 * @file hashlist.c
12 * @~English
13 *
14 * @brief Functions for creating and using a hash list of key-value
15 * pairs.
16 *
17 * @author Mark Callow, HI Corporation
18 */
19
20#include <stdio.h>
21#include <stdlib.h>
22#include <string.h>
23#include <assert.h>
24
25// This is to avoid compile warnings. strlen is defined as returning
26// size_t and is used by the uthash macros. This avoids having to
27// make changes to uthash and a bunch of casts in this file. The
28// casts would be required because the key and value lengths in KTX
29// are specified as 4 byte quantities so we can't change _keyAndValue
30// below to use size_t.
31#define strlen(x) ((unsigned int)strlen(x))
32
33#include "uthash.h"
34
35#include "ktx.h"
36#include "ktxint.h"
37
38
39/**
40 * @internal
41 * @struct ktxKVListEntry
42 * @brief Hash list entry structure
43 */
44typedef struct ktxKVListEntry {
45 unsigned int keyLen; /*!< Length of the key */
46 char* key; /*!< Pointer to key string */
47 unsigned int valueLen; /*!< Length of the value */
48 void* value; /*!< Pointer to the value */
49 UT_hash_handle hh; /*!< handle used by UT hash */
50} ktxKVListEntry;
51
52
53/**
54 * @memberof ktxHashList @public
55 * @~English
56 * @brief Construct an empty hash list for storing key-value pairs.
57 *
58 * @param [in] pHead pointer to the location to write the list head.
59 */
60void
61ktxHashList_Construct(ktxHashList* pHead)
62{
63 *pHead = NULL;
64}
65
66
67/**
68 * @memberof ktxHashList @public
69 * @~English
70 * @brief Construct a hash list by copying another.
71 *
72 * @param [in] pHead pointer to head of the list.
73 * @param [in] orig head of the original hash list.
74 */
75void
76ktxHashList_ConstructCopy(ktxHashList* pHead, ktxHashList orig)
77{
78 ktxHashListEntry* entry = orig;
79 *pHead = NULL;
80 for (; entry != NULL; entry = ktxHashList_Next(entry)) {
81 (void)ktxHashList_AddKVPair(pHead,
82 entry->key, entry->valueLen, entry->value);
83 }
84}
85
86
87/**
88 * @memberof ktxHashList @public
89 * @~English
90 * @brief Destruct a hash list.
91 *
92 * All memory associated with the hash list's keys and values
93 * is freed.
94 *
95 * @param [in] pHead pointer to the hash list to be destroyed.
96 */
97void
98ktxHashList_Destruct(ktxHashList* pHead)
99{
100 ktxKVListEntry* kv;
101 ktxKVListEntry* head = *pHead;
102
103 for(kv = head; kv != NULL;) {
104 ktxKVListEntry* tmp = (ktxKVListEntry*)kv->hh.next;
105 HASH_DELETE(hh, head, kv);
106 free(kv);
107 kv = tmp;
108 }
109}
110
111
112/**
113 * @memberof ktxHashList @public
114 * @~English
115 * @brief Create an empty hash list for storing key-value pairs.
116 *
117 * @param [in,out] ppHl address of a variable in which to set a pointer to
118 * the newly created hash list.
119 *
120 * @return KTX_SUCCESS or one of the following error codes.
121 * @exception KTX_OUT_OF_MEMORY if not enough memory.
122 */
123KTX_error_code
124ktxHashList_Create(ktxHashList** ppHl)
125{
126 ktxHashList* hl = (ktxHashList*)malloc(sizeof (ktxKVListEntry*));
127 if (hl == NULL)
128 return KTX_OUT_OF_MEMORY;
129
130 ktxHashList_Construct(hl);
131 *ppHl = hl;
132 return KTX_SUCCESS;
133}
134
135
136/**
137 * @memberof ktxHashList @public
138 * @~English
139 * @brief Create a copy of a hash list.
140 *
141 * @param [in,out] ppHl address of a variable in which to set a pointer to
142 * the newly created hash list.
143 * @param [in] orig head of the ktxHashList to copy.
144 *
145 * @return KTX_SUCCESS or one of the following error codes.
146 * @exception KTX_OUT_OF_MEMORY if not enough memory.
147 */
148KTX_error_code
149ktxHashList_CreateCopy(ktxHashList** ppHl, ktxHashList orig)
150{
151 ktxHashList* hl = (ktxHashList*)malloc(sizeof (ktxKVListEntry*));
152 if (hl == NULL)
153 return KTX_OUT_OF_MEMORY;
154
155 ktxHashList_ConstructCopy(hl, orig);
156 *ppHl = hl;
157 return KTX_SUCCESS;
158}
159
160
161/**
162 * @memberof ktxHashList @public
163 * @~English
164 * @brief Destroy a hash list.
165 *
166 * All memory associated with the hash list's keys and values
167 * is freed. The hash list is also freed.
168 *
169 * @param [in] pHead pointer to the hash list to be destroyed.
170 */
171void
172ktxHashList_Destroy(ktxHashList* pHead)
173{
174 ktxHashList_Destruct(pHead);
175 free(pHead);
176}
177
178#if !__clang__ && __GNUC__ // Grumble clang grumble
179// These are in uthash.h macros. I don't want to change that file.
180#pragma GCC diagnostic push
181#pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
182#endif
183
184/**
185 * @memberof ktxHashList @public
186 * @~English
187 * @brief Add a key value pair to a hash list.
188 *
189 * The value can be empty, i.e, its length can be 0.
190 *
191 * @param [in] pHead pointer to the head of the target hash list.
192 * @param [in] key pointer to the UTF8 NUL-terminated string to be used as the key.
193 * @param [in] valueLen the number of bytes of data in @p value.
194 * @param [in] value pointer to the bytes of data constituting the value.
195 *
196 * @return KTX_SUCCESS or one of the following error codes.
197 * @exception KTX_INVALID_VALUE if @p pHead, @p key or @p value are NULL, @p key is an
198 * empty string or @p valueLen == 0.
199 */
200KTX_error_code
201ktxHashList_AddKVPair(ktxHashList* pHead, const char* key, unsigned int valueLen, const void* value)
202{
203 if (pHead && key && (valueLen == 0 || value)) {
204 unsigned int keyLen = (unsigned int)strlen(key) + 1;
205 ktxKVListEntry* kv;
206
207 if (keyLen == 1)
208 return KTX_INVALID_VALUE; /* Empty string */
209
210 /* Allocate all the memory as a block */
211 kv = (ktxKVListEntry*)malloc(sizeof(ktxKVListEntry) + keyLen + valueLen);
212 /* Put key first */
213 kv->key = (char *)kv + sizeof(ktxKVListEntry);
214 kv->keyLen = keyLen;
215 memcpy(kv->key, key, keyLen);
216 /* then value */
217 kv->valueLen = valueLen;
218 if (valueLen > 0) {
219 kv->value = kv->key + keyLen;
220 memcpy(kv->value, value, valueLen);
221 } else {
222 kv->value = 0;
223 }
224
225 HASH_ADD_KEYPTR( hh, *pHead, kv->key, kv->keyLen-1, kv);
226 return KTX_SUCCESS;
227 } else
228 return KTX_INVALID_VALUE;
229}
230
231
232/**
233 * @memberof ktxHashList @public
234 * @~English
235 * @brief Delete a key value pair in a hash list.
236 *
237 * Is a nop if the key is not in the hash.
238 *
239 * @param [in] pHead pointer to the head of the target hash list.
240 * @param [in] key pointer to the UTF8 NUL-terminated string to be used as the key.
241 *
242 * @return KTX_SUCCESS or one of the following error codes.
243 * @exception KTX_INVALID_VALUE if @p pHead is NULL or @p key is an empty
244 * string.
245 */
246KTX_error_code
247ktxHashList_DeleteKVPair(ktxHashList* pHead, const char* key)
248{
249 if (pHead && key) {
250 ktxKVListEntry* kv;
251
252 HASH_FIND_STR( *pHead, key, kv ); /* kv: pointer to target entry. */
253 if (kv != NULL)
254 HASH_DEL(*pHead, kv);
255 return KTX_SUCCESS;
256 } else
257 return KTX_INVALID_VALUE;
258}
259
260
261/**
262 * @memberof ktxHashList @public
263 * @~English
264 * @brief Delete an entry from a hash list.
265 *
266 * @param [in] pHead pointer to the head of the target hash list.
267 * @param [in] pEntry pointer to the ktxHashListEntry to delete.
268 *
269 * @return KTX_SUCCESS or one of the following error codes.
270 * @exception KTX_INVALID_VALUE if @p pHead is NULL or @p key is an empty
271 * string.
272 */
273KTX_error_code
274ktxHashList_DeleteEntry(ktxHashList* pHead, ktxHashListEntry* pEntry)
275{
276 if (pHead && pEntry) {
277 HASH_DEL(*pHead, pEntry);
278 return KTX_SUCCESS;
279 } else
280 return KTX_INVALID_VALUE;
281}
282
283
284/**
285 * @memberof ktxHashList @public
286 * @~English
287 * @brief Looks up a key in a hash list and returns the entry.
288 *
289 * @param [in] pHead pointer to the head of the target hash list.
290 * @param [in] key pointer to a UTF8 NUL-terminated string to find.
291 * @param [in,out] ppEntry @p *ppEntry is set to the point at the
292 * ktxHashListEntry.
293 *
294 * @return KTX_SUCCESS or one of the following error codes.
295 *
296 * @exception KTX_INVALID_VALUE if @p This, @p key or @p pValueLen or @p ppValue
297 * is NULL.
298 * @exception KTX_NOT_FOUND an entry matching @p key was not found.
299 */
300KTX_error_code
301ktxHashList_FindEntry(ktxHashList* pHead, const char* key,
302 ktxHashListEntry** ppEntry)
303{
304 if (pHead && key) {
305 ktxKVListEntry* kv;
306
307 HASH_FIND_STR( *pHead, key, kv ); /* kv: output pointer */
308
309 if (kv) {
310 *ppEntry = kv;
311 return KTX_SUCCESS;
312 } else
313 return KTX_NOT_FOUND;
314 } else
315 return KTX_INVALID_VALUE;
316}
317
318
319/**
320 * @memberof ktxHashList @public
321 * @~English
322 * @brief Looks up a key in a hash list and returns the value.
323 *
324 * @param [in] pHead pointer to the head of the target hash list.
325 * @param [in] key pointer to a UTF8 NUL-terminated string to find.
326 * @param [in,out] pValueLen @p *pValueLen is set to the number of bytes of
327 * data in the returned value.
328 * @param [in,out] ppValue @p *ppValue is set to the point to the value for
329 * @p key.
330 *
331 * @return KTX_SUCCESS or one of the following error codes.
332 *
333 * @exception KTX_INVALID_VALUE if @p This, @p key or @p pValueLen or @p ppValue
334 * is NULL.
335 * @exception KTX_NOT_FOUND an entry matching @p key was not found.
336 */
337KTX_error_code
338ktxHashList_FindValue(ktxHashList *pHead, const char* key, unsigned int* pValueLen, void** ppValue)
339{
340 if (pValueLen && ppValue) {
341 ktxHashListEntry* pEntry;
342 KTX_error_code result;
343
344 result = ktxHashList_FindEntry(pHead, key, &pEntry);
345 if (result == KTX_SUCCESS) {
346 ktxHashListEntry_GetValue(pEntry, pValueLen, ppValue);
347 return KTX_SUCCESS;
348 } else
349 return result;
350 } else
351 return KTX_INVALID_VALUE;
352}
353
354#if !__clang__ && __GNUC__
355#pragma GCC diagnostic pop
356#endif
357
358/**
359 * @memberof ktxHashList @public
360 * @~English
361 * @brief Returns the next entry in a ktxHashList.
362 *
363 * Use for iterating through the list:
364 * @code
365 * ktxHashListEntry* entry;
366 * for (entry = listHead; entry != NULL; entry = ktxHashList_Next(entry)) {
367 * ...
368 * };
369 * @endcode
370 *
371 * Note
372 *
373 * @param [in] entry pointer to a hash list entry. Note that a ktxHashList*,
374 * i.e. the list head, is also a pointer to an entry so
375 * can be passed to this function.
376 *
377 * @return a pointer to the next entry or NULL.
378 *
379 */
380ktxHashListEntry*
381ktxHashList_Next(ktxHashListEntry* entry)
382{
383 if (entry) {
384 return ((ktxKVListEntry*)entry)->hh.next;
385 } else
386 return NULL;
387}
388
389
390/**
391 * @memberof ktxHashList @public
392 * @~English
393 * @brief Serialize a hash list to a block of data suitable for writing
394 * to a file.
395 *
396 * The caller is responsible for freeing the data block returned by this
397 * function.
398 *
399 * @param [in] pHead pointer to the head of the target hash list.
400 * @param [in,out] pKvdLen @p *pKvdLen is set to the number of bytes of
401 * data in the returned data block.
402 * @param [in,out] ppKvd @p *ppKvd is set to the point to the block of
403 * memory containing the serialized data or
404 * NULL. if the hash list is empty.
405 *
406 * @return KTX_SUCCESS or one of the following error codes.
407 *
408 * @exception KTX_INVALID_VALUE if @p This, @p pKvdLen or @p ppKvd is NULL.
409 * @exception KTX_OUT_OF_MEMORY there was not enough memory to serialize the
410 * data.
411 */
412KTX_error_code
413ktxHashList_Serialize(ktxHashList* pHead,
414 unsigned int* pKvdLen, unsigned char** ppKvd)
415{
416
417 if (pHead && pKvdLen && ppKvd) {
418 ktxKVListEntry* kv;
419 unsigned int bytesOfKeyValueData = 0;
420 unsigned int keyValueLen;
421 unsigned char* sd;
422 char padding[4] = {0, 0, 0, 0};
423
424 for (kv = *pHead; kv != NULL; kv = kv->hh.next) {
425 /* sizeof(sd) is to make space to write keyAndValueByteSize */
426 keyValueLen = kv->keyLen + kv->valueLen + sizeof(ktx_uint32_t);
427 /* Add valuePadding */
428 keyValueLen = _KTX_PAD4(keyValueLen);
429 bytesOfKeyValueData += keyValueLen;
430 }
431
432 if (bytesOfKeyValueData == 0) {
433 *pKvdLen = 0;
434 *ppKvd = NULL;
435 } else {
436 sd = malloc(bytesOfKeyValueData);
437 if (!sd)
438 return KTX_OUT_OF_MEMORY;
439
440 *pKvdLen = bytesOfKeyValueData;
441 *ppKvd = sd;
442
443 for (kv = *pHead; kv != NULL; kv = kv->hh.next) {
444 int padLen;
445
446 keyValueLen = kv->keyLen + kv->valueLen;
447 *(ktx_uint32_t*)sd = keyValueLen;
448 sd += sizeof(ktx_uint32_t);
449 memcpy(sd, kv->key, kv->keyLen);
450 sd += kv->keyLen;
451 if (kv->valueLen > 0)
452 memcpy(sd, kv->value, kv->valueLen);
453 sd += kv->valueLen;
454 padLen = _KTX_PAD4_LEN(keyValueLen);
455 memcpy(sd, padding, padLen);
456 sd += padLen;
457 }
458 }
459 return KTX_SUCCESS;
460 } else
461 return KTX_INVALID_VALUE;
462}
463
464
465int sort_by_key_codepoint(ktxKVListEntry* a, ktxKVListEntry* b) {
466 return strcmp(a->key, b->key);
467}
468
469/**
470 * @memberof ktxHashList @public
471 * @~English
472 * @brief Sort a hash list in order of the UTF8 codepoints.
473 *
474 * @param [in] pHead pointer to the head of the target hash list.
475 *
476 * @return KTX_SUCCESS or one of the following error codes.
477 *
478 * @exception KTX_INVALID_VALUE if @p This is NULL.
479 */
480KTX_error_code
481ktxHashList_Sort(ktxHashList* pHead)
482{
483 if (pHead) {
484 //ktxKVListEntry* kv = (ktxKVListEntry*)pHead;
485
486 HASH_SORT(*pHead, sort_by_key_codepoint);
487 return KTX_SUCCESS;
488 } else {
489 return KTX_INVALID_VALUE;
490 }
491}
492
493
494/**
495 * @memberof ktxHashList @public
496 * @~English
497 * @brief Construct a hash list from a block of serialized key-value
498 * data read from a file.
499 * @note The bytes of the 32-bit key-value lengths within the serialized data
500 * are expected to be in native endianness.
501 *
502 * @param [in] pHead pointer to the head of the target hash list.
503 * @param [in] kvdLen the length of the serialized key-value data.
504 * @param [in] pKvd pointer to the serialized key-value data.
505 * table.
506 *
507 * @return KTX_SUCCESS or one of the following error codes.
508 *
509 * @exception KTX_INVALID_OPERATION if @p pHead does not point to an empty list.
510 * @exception KTX_INVALID_VALUE if @p pKvd or @p pHt is NULL or kvdLen == 0.
511 * @exception KTX_OUT_OF_MEMORY there was not enough memory to create the hash
512 * table.
513 */
514KTX_error_code
515ktxHashList_Deserialize(ktxHashList* pHead, unsigned int kvdLen, void* pKvd)
516{
517 char* src = pKvd;
518 KTX_error_code result;
519
520 if (kvdLen == 0 || pKvd == NULL || pHead == NULL)
521 return KTX_INVALID_VALUE;
522
523 if (*pHead != NULL)
524 return KTX_INVALID_OPERATION;
525
526 result = KTX_SUCCESS;
527 while (result == KTX_SUCCESS && src < (char *)pKvd + kvdLen) {
528 char* key;
529 unsigned int keyLen, valueLen;
530 void* value;
531 ktx_uint32_t keyAndValueByteSize = *((ktx_uint32_t*)src);
532
533 src += sizeof(keyAndValueByteSize);
534 key = src;
535 keyLen = (unsigned int)strlen(key) + 1;
536 value = key + keyLen;
537
538 valueLen = keyAndValueByteSize - keyLen;
539 result = ktxHashList_AddKVPair(pHead, key, valueLen,
540 valueLen > 0 ? value : NULL);
541 if (result == KTX_SUCCESS) {
542 src += _KTX_PAD4(keyAndValueByteSize);
543 }
544 }
545 return result;
546}
547
548
549/**
550 * @memberof ktxHashListEntry @public
551 * @~English
552 * @brief Return the key of a ktxHashListEntry
553 *
554 * @param [in] This The target hash list entry.
555 * @param [in,out] pKeyLen @p *pKeyLen is set to the byte length of
556 * the returned key.
557 * @param [in,out] ppKey @p *ppKey is set to the point to the value of
558 * @p the key.
559 *
560 * @return KTX_SUCCESS or one of the following error codes.
561 *
562 * @exception KTX_INVALID_VALUE if @p pKvd or @p pHt is NULL or kvdLen == 0.
563 */
564KTX_error_code
565ktxHashListEntry_GetKey(ktxHashListEntry* This,
566 unsigned int* pKeyLen, char** ppKey)
567{
568 if (pKeyLen && ppKey) {
569 ktxKVListEntry* kv = (ktxKVListEntry*)This;
570 *pKeyLen = kv->keyLen;
571 *ppKey = kv->key;
572 return KTX_SUCCESS;
573 } else
574 return KTX_INVALID_VALUE;
575}
576
577
578/**
579 * @memberof ktxHashListEntry @public
580 * @~English
581 * @brief Return the value from a ktxHashListEntry
582 *
583 * @param [in] This The target hash list entry.
584 * @param [in,out] pValueLen @p *pValueLen is set to the number of bytes of
585 * data in the returned value.
586 * @param [in,out] ppValue @p *ppValue is set to point to the value of
587 * of the target entry.
588 *
589 * @return KTX_SUCCESS or one of the following error codes.
590 *
591 * @exception KTX_INVALID_VALUE if @p pKvd or @p pHt is NULL or kvdLen == 0.
592 */
593KTX_error_code
594ktxHashListEntry_GetValue(ktxHashListEntry* This,
595 unsigned int* pValueLen, void** ppValue)
596{
597 if (pValueLen && ppValue) {
598 ktxKVListEntry* kv = (ktxKVListEntry*)This;
599 *pValueLen = kv->valueLen;
600 *ppValue = kv->valueLen > 0 ? kv->value : NULL;
601 return KTX_SUCCESS;
602 } else
603 return KTX_INVALID_VALUE;
604}
605