1 #define __MOJOSHADER_INTERNAL__ 1
2 #include "mojoshader_internal.h"
3
4 typedef struct HashItem
5 {
6 const void *key;
7 const void *value;
8 struct HashItem *next;
9 } HashItem;
10
11 struct HashTable
12 {
13 HashItem **table;
14 uint32 table_len;
15 int stackable;
16 void *data;
17 HashTable_HashFn hash;
18 HashTable_KeyMatchFn keymatch;
19 HashTable_NukeFn nuke;
20 MOJOSHADER_malloc m;
21 MOJOSHADER_free f;
22 void *d;
23 };
24
calc_hash(const HashTable * table,const void * key)25 static inline uint32 calc_hash(const HashTable *table, const void *key)
26 {
27 return table->hash(key, table->data) & (table->table_len-1);
28 } // calc_hash
29
hash_find(const HashTable * table,const void * key,const void ** _value)30 int hash_find(const HashTable *table, const void *key, const void **_value)
31 {
32 HashItem *i;
33 void *data = table->data;
34 const uint32 hash = calc_hash(table, key);
35 HashItem *prev = NULL;
36 for (i = table->table[hash]; i != NULL; i = i->next)
37 {
38 if (table->keymatch(key, i->key, data))
39 {
40 if (_value != NULL)
41 *_value = i->value;
42
43 // Matched! Move to the front of list for faster lookup next time.
44 // (stackable tables have to remain in the same order, though!)
45 if ((!table->stackable) && (prev != NULL))
46 {
47 assert(prev->next == i);
48 prev->next = i->next;
49 i->next = table->table[hash];
50 table->table[hash] = i;
51 } // if
52
53 return 1;
54 } // if
55
56 prev = i;
57 } // for
58
59 return 0;
60 } // hash_find
61
hash_iter(const HashTable * table,const void * key,const void ** _value,void ** iter)62 int hash_iter(const HashTable *table, const void *key,
63 const void **_value, void **iter)
64 {
65 HashItem *item = (HashItem *)*iter;
66 if (item == NULL)
67 item = table->table[calc_hash(table, key)];
68 else
69 item = item->next;
70
71 while (item != NULL)
72 {
73 if (table->keymatch(key, item->key, table->data))
74 {
75 *_value = item->value;
76 *iter = item;
77 return 1;
78 } // if
79 item = item->next;
80 } // while
81
82 // no more matches.
83 *_value = NULL;
84 *iter = NULL;
85 return 0;
86 } // hash_iter
87
hash_iter_keys(const HashTable * table,const void ** _key,void ** iter)88 int hash_iter_keys(const HashTable *table, const void **_key, void **iter)
89 {
90 HashItem *item = (HashItem *)*iter;
91 int idx = 0;
92
93 if (item != NULL)
94 {
95 const HashItem *orig = item;
96 item = item->next;
97 if (item == NULL)
98 idx = calc_hash(table, orig->key) + 1;
99 } // if
100
101 while (!item && (idx < table->table_len))
102 item = table->table[idx++]; // skip empty buckets...
103
104 if (item == NULL) // no more matches?
105 {
106 *_key = NULL;
107 *iter = NULL;
108 return 0;
109 } // if
110
111 *_key = item->key;
112 *iter = item;
113 return 1;
114 } // hash_iter_keys
115
hash_insert(HashTable * table,const void * key,const void * value)116 int hash_insert(HashTable *table, const void *key, const void *value)
117 {
118 HashItem *item = NULL;
119 const uint32 hash = calc_hash(table, key);
120 if ( (!table->stackable) && (hash_find(table, key, NULL)) )
121 return 0;
122
123 // !!! FIXME: grow and rehash table if it gets too saturated.
124 item = (HashItem *) table->m(sizeof (HashItem), table->d);
125 if (item == NULL)
126 return -1;
127
128 item->key = key;
129 item->value = value;
130 item->next = table->table[hash];
131 table->table[hash] = item;
132
133 return 1;
134 } // hash_insert
135
hash_create(void * data,const HashTable_HashFn hashfn,const HashTable_KeyMatchFn keymatchfn,const HashTable_NukeFn nukefn,const int stackable,MOJOSHADER_malloc m,MOJOSHADER_free f,void * d)136 HashTable *hash_create(void *data, const HashTable_HashFn hashfn,
137 const HashTable_KeyMatchFn keymatchfn,
138 const HashTable_NukeFn nukefn,
139 const int stackable,
140 MOJOSHADER_malloc m, MOJOSHADER_free f, void *d)
141 {
142 const uint32 initial_table_size = 256;
143 const uint32 alloc_len = sizeof (HashItem *) * initial_table_size;
144 HashTable *table = (HashTable *) m(sizeof (HashTable), d);
145 if (table == NULL)
146 return NULL;
147 memset(table, '\0', sizeof (HashTable));
148
149 table->table = (HashItem **) m(alloc_len, d);
150 if (table->table == NULL)
151 {
152 f(table, d);
153 return NULL;
154 } // if
155
156 memset(table->table, '\0', alloc_len);
157 table->table_len = initial_table_size;
158 table->stackable = stackable;
159 table->data = data;
160 table->hash = hashfn;
161 table->keymatch = keymatchfn;
162 table->nuke = nukefn;
163 table->m = m;
164 table->f = f;
165 table->d = d;
166 return table;
167 } // hash_create
168
hash_destroy(HashTable * table)169 void hash_destroy(HashTable *table)
170 {
171 uint32 i;
172 void *data = table->data;
173 MOJOSHADER_free f = table->f;
174 void *d = table->d;
175 for (i = 0; i < table->table_len; i++)
176 {
177 HashItem *item = table->table[i];
178 while (item != NULL)
179 {
180 HashItem *next = item->next;
181 table->nuke(item->key, item->value, data);
182 f(item, d);
183 item = next;
184 } // while
185 } // for
186
187 f(table->table, d);
188 f(table, d);
189 } // hash_destroy
190
hash_remove(HashTable * table,const void * key)191 int hash_remove(HashTable *table, const void *key)
192 {
193 HashItem *item = NULL;
194 HashItem *prev = NULL;
195 void *data = table->data;
196 const uint32 hash = calc_hash(table, key);
197 for (item = table->table[hash]; item != NULL; item = item->next)
198 {
199 if (table->keymatch(key, item->key, data))
200 {
201 if (prev != NULL)
202 prev->next = item->next;
203 else
204 table->table[hash] = item->next;
205
206 table->nuke(item->key, item->value, data);
207 table->f(item, table->d);
208 return 1;
209 } // if
210
211 prev = item;
212 } // for
213
214 return 0;
215 } // hash_remove
216
217
218 // this is djb's xor hashing function.
hash_string_djbxor(const char * str,size_t len)219 static inline uint32 hash_string_djbxor(const char *str, size_t len)
220 {
221 register uint32 hash = 5381;
222 while (len--)
223 hash = ((hash << 5) + hash) ^ *(str++);
224 return hash;
225 } // hash_string_djbxor
226
hash_string(const char * str,size_t len)227 static inline uint32 hash_string(const char *str, size_t len)
228 {
229 return hash_string_djbxor(str, len);
230 } // hash_string
231
hash_hash_string(const void * sym,void * data)232 uint32 hash_hash_string(const void *sym, void *data)
233 {
234 (void) data;
235 return hash_string((const char*) sym, strlen((const char *) sym));
236 } // hash_hash_string
237
hash_keymatch_string(const void * a,const void * b,void * data)238 int hash_keymatch_string(const void *a, const void *b, void *data)
239 {
240 (void) data;
241 return (strcmp((const char *) a, (const char *) b) == 0);
242 } // hash_keymatch_string
243
244
245 // string -> string map...
246
stringmap_nuke_noop(const void * key,const void * val,void * d)247 static void stringmap_nuke_noop(const void *key, const void *val, void *d) {}
248
stringmap_nuke(const void * key,const void * val,void * d)249 static void stringmap_nuke(const void *key, const void *val, void *d)
250 {
251 StringMap *smap = (StringMap *) d;
252 smap->f((void *) key, smap->d);
253 smap->f((void *) val, smap->d);
254 } // stringmap_nuke
255
stringmap_create(const int copy,MOJOSHADER_malloc m,MOJOSHADER_free f,void * d)256 StringMap *stringmap_create(const int copy, MOJOSHADER_malloc m,
257 MOJOSHADER_free f, void *d)
258 {
259 HashTable_NukeFn nuke = copy ? stringmap_nuke : stringmap_nuke_noop;
260 StringMap *smap;
261 smap = hash_create(0,hash_hash_string,hash_keymatch_string,nuke,0,m,f,d);
262 if (smap != NULL)
263 smap->data = smap;
264 return smap;
265 } // stringmap_create
266
stringmap_destroy(StringMap * smap)267 void stringmap_destroy(StringMap *smap)
268 {
269 hash_destroy(smap);
270 } // stringmap_destroy
271
stringmap_insert(StringMap * smap,const char * key,const char * value)272 int stringmap_insert(StringMap *smap, const char *key, const char *value)
273 {
274 assert(key != NULL);
275 if (smap->nuke == stringmap_nuke_noop) // no copy?
276 return hash_insert(smap, key, value);
277
278 int rc = -1;
279 char *k = (char *) smap->m(strlen(key) + 1, smap->d);
280 char *v = (char *) (value ? smap->m(strlen(value) + 1, smap->d) : NULL);
281 int failed = ( (!k) || ((!v) && (value)) );
282
283 if (!failed)
284 {
285 strcpy(k, key);
286 if (value != NULL)
287 strcpy(v, value);
288 failed = ((rc = hash_insert(smap, k, v)) <= 0);
289 } // if
290
291 if (failed)
292 {
293 smap->f(k, smap->d);
294 smap->f(v, smap->d);
295 } // if
296
297 return rc;
298 } // stringmap_insert
299
stringmap_remove(StringMap * smap,const char * key)300 int stringmap_remove(StringMap *smap, const char *key)
301 {
302 return hash_remove(smap, key);
303 } // stringmap_remove
304
stringmap_find(const StringMap * smap,const char * key,const char ** _value)305 int stringmap_find(const StringMap *smap, const char *key, const char **_value)
306 {
307 const void *value = NULL;
308 const int retval = hash_find(smap, key, &value);
309 *_value = (const char *) value;
310 return retval;
311 } // stringmap_find
312
313
314 // The string cache... !!! FIXME: use StringMap internally for this.
315
316 typedef struct StringBucket
317 {
318 char *string;
319 struct StringBucket *next;
320 } StringBucket;
321
322 struct StringCache
323 {
324 StringBucket **hashtable;
325 uint32 table_size;
326 MOJOSHADER_malloc m;
327 MOJOSHADER_free f;
328 void *d;
329 };
330
stringcache(StringCache * cache,const char * str)331 const char *stringcache(StringCache *cache, const char *str)
332 {
333 return stringcache_len(cache, str, strlen(str));
334 } // stringcache
335
stringcache_len(StringCache * cache,const char * str,const unsigned int len)336 const char *stringcache_len(StringCache *cache, const char *str,
337 const unsigned int len)
338 {
339 const uint8 hash = hash_string(str, len) & (cache->table_size-1);
340 StringBucket *bucket = cache->hashtable[hash];
341 StringBucket *prev = NULL;
342 while (bucket)
343 {
344 const char *bstr = bucket->string;
345 if ((strncmp(bstr, str, len) == 0) && (bstr[len] == 0))
346 {
347 // Matched! Move this to the front of the list.
348 if (prev != NULL)
349 {
350 assert(prev->next == bucket);
351 prev->next = bucket->next;
352 bucket->next = cache->hashtable[hash];
353 cache->hashtable[hash] = bucket;
354 } // if
355 return bstr; // already cached
356 } // if
357 prev = bucket;
358 bucket = bucket->next;
359 } // while
360
361 // no match, add to the table.
362 bucket = (StringBucket *) cache->m(sizeof (StringBucket), cache->d);
363 if (bucket == NULL)
364 return NULL;
365 bucket->string = (char *) cache->m(len + 1, cache->d);
366 if (bucket->string == NULL)
367 {
368 cache->f(bucket, cache->d);
369 return NULL;
370 } // if
371 memcpy(bucket->string, str, len);
372 bucket->string[len] = '\0';
373 bucket->next = cache->hashtable[hash];
374 cache->hashtable[hash] = bucket;
375 return bucket->string;
376 } // stringcache_len
377
stringcache_fmt(StringCache * cache,const char * fmt,...)378 const char *stringcache_fmt(StringCache *cache, const char *fmt, ...)
379 {
380 char buf[128]; // use the stack if reasonable.
381 char *ptr = NULL;
382 int len = 0; // number of chars, NOT counting null-terminator!
383 va_list ap;
384
385 va_start(ap, fmt);
386 len = vsnprintf(buf, sizeof (buf), fmt, ap);
387 va_end(ap);
388
389 if (len > sizeof (buf))
390 {
391 ptr = (char *) cache->m(len, cache->d);
392 if (ptr == NULL)
393 return NULL;
394
395 va_start(ap, fmt);
396 vsnprintf(ptr, len, fmt, ap);
397 va_end(ap);
398 } // if
399
400 const char *retval = stringcache_len(cache, ptr ? ptr : buf, len);
401 if (ptr != NULL)
402 cache->f(ptr, cache->d);
403
404 return retval;
405 } // stringcache_fmt
406
stringcache_create(MOJOSHADER_malloc m,MOJOSHADER_free f,void * d)407 StringCache *stringcache_create(MOJOSHADER_malloc m, MOJOSHADER_free f, void *d)
408 {
409 const uint32 initial_table_size = 256;
410 const size_t tablelen = sizeof (StringBucket *) * initial_table_size;
411 StringCache *cache = (StringCache *) m(sizeof (StringCache), d);
412 if (!cache)
413 return NULL;
414 memset(cache, '\0', sizeof (StringCache));
415
416 cache->hashtable = (StringBucket **) m(tablelen, d);
417 if (!cache->hashtable)
418 {
419 f(cache, d);
420 return NULL;
421 } // if
422 memset(cache->hashtable, '\0', tablelen);
423
424 cache->table_size = initial_table_size;
425 cache->m = m;
426 cache->f = f;
427 cache->d = d;
428 return cache;
429 } // stringcache_create
430
stringcache_destroy(StringCache * cache)431 void stringcache_destroy(StringCache *cache)
432 {
433 if (cache == NULL)
434 return;
435
436 MOJOSHADER_free f = cache->f;
437 void *d = cache->d;
438 size_t i;
439
440 for (i = 0; i < cache->table_size; i++)
441 {
442 StringBucket *bucket = cache->hashtable[i];
443 cache->hashtable[i] = NULL;
444 while (bucket)
445 {
446 StringBucket *next = bucket->next;
447 f(bucket->string, d);
448 f(bucket, d);
449 bucket = next;
450 } // while
451 } // for
452
453 f(cache->hashtable, d);
454 f(cache, d);
455 } // stringcache_destroy
456
457
458 // We chain errors as a linked list with a head/tail for easy appending.
459 // These get flattened before passing to the application.
460 typedef struct ErrorItem
461 {
462 MOJOSHADER_error error;
463 struct ErrorItem *next;
464 } ErrorItem;
465
466 struct ErrorList
467 {
468 ErrorItem head;
469 ErrorItem *tail;
470 int count;
471 MOJOSHADER_malloc m;
472 MOJOSHADER_free f;
473 void *d;
474 };
475
errorlist_create(MOJOSHADER_malloc m,MOJOSHADER_free f,void * d)476 ErrorList *errorlist_create(MOJOSHADER_malloc m, MOJOSHADER_free f, void *d)
477 {
478 ErrorList *retval = (ErrorList *) m(sizeof (ErrorList), d);
479 if (retval != NULL)
480 {
481 memset(retval, '\0', sizeof (ErrorList));
482 retval->tail = &retval->head;
483 retval->m = m;
484 retval->f = f;
485 retval->d = d;
486 } // if
487
488 return retval;
489 } // errorlist_create
490
491
errorlist_add(ErrorList * list,const char * fname,const int errpos,const char * str)492 int errorlist_add(ErrorList *list, const char *fname,
493 const int errpos, const char *str)
494 {
495 return errorlist_add_fmt(list, fname, errpos, "%s", str);
496 } // errorlist_add
497
498
errorlist_add_fmt(ErrorList * list,const char * fname,const int errpos,const char * fmt,...)499 int errorlist_add_fmt(ErrorList *list, const char *fname,
500 const int errpos, const char *fmt, ...)
501 {
502 va_list ap;
503 va_start(ap, fmt);
504 const int retval = errorlist_add_va(list, fname, errpos, fmt, ap);
505 va_end(ap);
506 return retval;
507 } // errorlist_add_fmt
508
509
errorlist_add_va(ErrorList * list,const char * _fname,const int errpos,const char * fmt,va_list va)510 int errorlist_add_va(ErrorList *list, const char *_fname,
511 const int errpos, const char *fmt, va_list va)
512 {
513 ErrorItem *error = (ErrorItem *) list->m(sizeof (ErrorItem), list->d);
514 if (error == NULL)
515 return 0;
516
517 char *fname = NULL;
518 if (_fname != NULL)
519 {
520 fname = (char *) list->m(strlen(_fname) + 1, list->d);
521 if (fname == NULL)
522 {
523 list->f(error, list->d);
524 return 0;
525 } // if
526 strcpy(fname, _fname);
527 } // if
528
529 char scratch[128];
530 va_list ap;
531 va_copy(ap, va);
532 const int len = vsnprintf(scratch, sizeof (scratch), fmt, ap);
533 va_end(ap);
534
535 char *failstr = (char *) list->m(len + 1, list->d);
536 if (failstr == NULL)
537 {
538 list->f(error, list->d);
539 list->f(fname, list->d);
540 return 0;
541 } // if
542
543 // If we overflowed our scratch buffer, that's okay. We were going to
544 // allocate anyhow...the scratch buffer just lets us avoid a second
545 // run of vsnprintf().
546 if (len < sizeof (scratch))
547 strcpy(failstr, scratch); // copy it over.
548 else
549 {
550 va_copy(ap, va);
551 vsnprintf(failstr, len + 1, fmt, ap); // rebuild it.
552 va_end(ap);
553 } // else
554
555 error->error.error = failstr;
556 error->error.filename = fname;
557 error->error.error_position = errpos;
558 error->next = NULL;
559
560 list->tail->next = error;
561 list->tail = error;
562
563 list->count++;
564 return 1;
565 } // errorlist_add_va
566
567
errorlist_count(ErrorList * list)568 int errorlist_count(ErrorList *list)
569 {
570 return list->count;
571 } // errorlist_count
572
573
errorlist_flatten(ErrorList * list)574 MOJOSHADER_error *errorlist_flatten(ErrorList *list)
575 {
576 if (list->count == 0)
577 return NULL;
578
579 int total = 0;
580 MOJOSHADER_error *retval = (MOJOSHADER_error *)
581 list->m(sizeof (MOJOSHADER_error) * list->count, list->d);
582 if (retval == NULL)
583 return NULL;
584
585 ErrorItem *item = list->head.next;
586 while (item != NULL)
587 {
588 ErrorItem *next = item->next;
589 // reuse the string allocations
590 memcpy(&retval[total], &item->error, sizeof (MOJOSHADER_error));
591 list->f(item, list->d);
592 item = next;
593 total++;
594 } // while
595
596 assert(total == list->count);
597 list->count = 0;
598 list->head.next = NULL;
599 list->tail = &list->head;
600 return retval;
601 } // errorlist_flatten
602
603
errorlist_destroy(ErrorList * list)604 void errorlist_destroy(ErrorList *list)
605 {
606 if (list == NULL)
607 return;
608
609 MOJOSHADER_free f = list->f;
610 void *d = list->d;
611 ErrorItem *item = list->head.next;
612 while (item != NULL)
613 {
614 ErrorItem *next = item->next;
615 f((void *) item->error.error, d);
616 f((void *) item->error.filename, d);
617 f(item, d);
618 item = next;
619 } // while
620 f(list, d);
621 } // errorlist_destroy
622
623
624 typedef struct BufferBlock
625 {
626 uint8 *data;
627 size_t bytes;
628 struct BufferBlock *next;
629 } BufferBlock;
630
631 struct Buffer
632 {
633 size_t total_bytes;
634 BufferBlock *head;
635 BufferBlock *tail;
636 size_t block_size;
637 MOJOSHADER_malloc m;
638 MOJOSHADER_free f;
639 void *d;
640 };
641
buffer_create(size_t blksz,MOJOSHADER_malloc m,MOJOSHADER_free f,void * d)642 Buffer *buffer_create(size_t blksz, MOJOSHADER_malloc m,
643 MOJOSHADER_free f, void *d)
644 {
645 Buffer *buffer = (Buffer *) m(sizeof (Buffer), d);
646 if (buffer != NULL)
647 {
648 memset(buffer, '\0', sizeof (Buffer));
649 buffer->block_size = blksz;
650 buffer->m = m;
651 buffer->f = f;
652 buffer->d = d;
653 } // if
654 return buffer;
655 } // buffer_create
656
buffer_reserve(Buffer * buffer,const size_t len)657 char *buffer_reserve(Buffer *buffer, const size_t len)
658 {
659 // note that we make the blocks bigger than blocksize when we have enough
660 // data to overfill a fresh block, to reduce allocations.
661 const size_t blocksize = buffer->block_size;
662
663 if (len == 0)
664 return NULL;
665
666 if (buffer->tail != NULL)
667 {
668 const size_t tailbytes = buffer->tail->bytes;
669 const size_t avail = (tailbytes >= blocksize) ? 0 : blocksize - tailbytes;
670 if (len <= avail)
671 {
672 buffer->tail->bytes += len;
673 buffer->total_bytes += len;
674 assert(buffer->tail->bytes <= blocksize);
675 return (char *) buffer->tail->data + tailbytes;
676 } // if
677 } // if
678
679 // need to allocate a new block (even if a previous block wasn't filled,
680 // so this buffer is contiguous).
681 const size_t bytecount = len > blocksize ? len : blocksize;
682 const size_t malloc_len = sizeof (BufferBlock) + bytecount;
683 BufferBlock *item = (BufferBlock *) buffer->m(malloc_len, buffer->d);
684 if (item == NULL)
685 return NULL;
686
687 item->data = ((uint8 *) item) + sizeof (BufferBlock);
688 item->bytes = len;
689 item->next = NULL;
690 if (buffer->tail != NULL)
691 buffer->tail->next = item;
692 else
693 buffer->head = item;
694 buffer->tail = item;
695
696 buffer->total_bytes += len;
697
698 return (char *) item->data;
699 } // buffer_reserve
700
buffer_append(Buffer * buffer,const void * _data,size_t len)701 int buffer_append(Buffer *buffer, const void *_data, size_t len)
702 {
703 const uint8 *data = (const uint8 *) _data;
704
705 // note that we make the blocks bigger than blocksize when we have enough
706 // data to overfill a fresh block, to reduce allocations.
707 const size_t blocksize = buffer->block_size;
708
709 if (len == 0)
710 return 1;
711
712 if (buffer->tail != NULL)
713 {
714 const size_t tailbytes = buffer->tail->bytes;
715 const size_t avail = (tailbytes >= blocksize) ? 0 : blocksize - tailbytes;
716 const size_t cpy = (avail > len) ? len : avail;
717 if (cpy > 0)
718 {
719 memcpy(buffer->tail->data + tailbytes, data, cpy);
720 len -= cpy;
721 data += cpy;
722 buffer->tail->bytes += cpy;
723 buffer->total_bytes += cpy;
724 assert(buffer->tail->bytes <= blocksize);
725 } // if
726 } // if
727
728 if (len > 0)
729 {
730 assert((!buffer->tail) || (buffer->tail->bytes == blocksize));
731 const size_t bytecount = len > blocksize ? len : blocksize;
732 const size_t malloc_len = sizeof (BufferBlock) + bytecount;
733 BufferBlock *item = (BufferBlock *) buffer->m(malloc_len, buffer->d);
734 if (item == NULL)
735 return 0;
736
737 item->data = ((uint8 *) item) + sizeof (BufferBlock);
738 item->bytes = len;
739 item->next = NULL;
740 if (buffer->tail != NULL)
741 buffer->tail->next = item;
742 else
743 buffer->head = item;
744 buffer->tail = item;
745
746 memcpy(item->data, data, len);
747 buffer->total_bytes += len;
748 } // if
749
750 return 1;
751 } // buffer_append
752
buffer_append_fmt(Buffer * buffer,const char * fmt,...)753 int buffer_append_fmt(Buffer *buffer, const char *fmt, ...)
754 {
755 va_list ap;
756 va_start(ap, fmt);
757 const int retval = buffer_append_va(buffer, fmt, ap);
758 va_end(ap);
759 return retval;
760 } // buffer_append_fmt
761
buffer_append_va(Buffer * buffer,const char * fmt,va_list va)762 int buffer_append_va(Buffer *buffer, const char *fmt, va_list va)
763 {
764 char scratch[256];
765
766 va_list ap;
767 va_copy(ap, va);
768 const int len = vsnprintf(scratch, sizeof (scratch), fmt, ap);
769 va_end(ap);
770
771 // If we overflowed our scratch buffer, heap allocate and try again.
772
773 if (len == 0)
774 return 1; // nothing to do.
775 else if (len < sizeof (scratch))
776 return buffer_append(buffer, scratch, len);
777
778 char *buf = (char *) buffer->m(len + 1, buffer->d);
779 if (buf == NULL)
780 return 0;
781 va_copy(ap, va);
782 vsnprintf(buf, len + 1, fmt, ap); // rebuild it.
783 va_end(ap);
784 const int retval = buffer_append(buffer, scratch, len);
785 buffer->f(buf, buffer->d);
786 return retval;
787 } // buffer_append_va
788
buffer_size(Buffer * buffer)789 size_t buffer_size(Buffer *buffer)
790 {
791 return buffer->total_bytes;
792 } // buffer_size
793
buffer_empty(Buffer * buffer)794 void buffer_empty(Buffer *buffer)
795 {
796 BufferBlock *item = buffer->head;
797 while (item != NULL)
798 {
799 BufferBlock *next = item->next;
800 buffer->f(item, buffer->d);
801 item = next;
802 } // while
803 buffer->head = buffer->tail = NULL;
804 buffer->total_bytes = 0;
805 } // buffer_empty
806
buffer_flatten(Buffer * buffer)807 char *buffer_flatten(Buffer *buffer)
808 {
809 char *retval = (char *) buffer->m(buffer->total_bytes + 1, buffer->d);
810 if (retval == NULL)
811 return NULL;
812 BufferBlock *item = buffer->head;
813 char *ptr = retval;
814 while (item != NULL)
815 {
816 BufferBlock *next = item->next;
817 memcpy(ptr, item->data, item->bytes);
818 ptr += item->bytes;
819 buffer->f(item, buffer->d);
820 item = next;
821 } // while
822 *ptr = '\0';
823
824 assert(ptr == (retval + buffer->total_bytes));
825
826 buffer->head = buffer->tail = NULL;
827 buffer->total_bytes = 0;
828
829 return retval;
830 } // buffer_flatten
831
buffer_merge(Buffer ** buffers,const size_t n,size_t * _len)832 char *buffer_merge(Buffer **buffers, const size_t n, size_t *_len)
833 {
834 Buffer *first = NULL;
835 size_t len = 0;
836 size_t i;
837 for (i = 0; i < n; i++)
838 {
839 Buffer *buffer = buffers[i];
840 if (buffer == NULL)
841 continue;
842 if (first == NULL)
843 first = buffer;
844 len += buffer->total_bytes;
845 } // for
846
847 char *retval = (char *) (first ? first->m(len + 1, first->d) : NULL);
848 if (retval == NULL)
849 {
850 *_len = 0;
851 return NULL;
852 } // if
853
854 *_len = len;
855 char *ptr = retval;
856 for (i = 0; i < n; i++)
857 {
858 Buffer *buffer = buffers[i];
859 if (buffer == NULL)
860 continue;
861 BufferBlock *item = buffer->head;
862 while (item != NULL)
863 {
864 BufferBlock *next = item->next;
865 memcpy(ptr, item->data, item->bytes);
866 ptr += item->bytes;
867 buffer->f(item, buffer->d);
868 item = next;
869 } // while
870
871 buffer->head = buffer->tail = NULL;
872 buffer->total_bytes = 0;
873 } // for
874 *ptr = '\0';
875
876 assert(ptr == (retval + len));
877
878 return retval;
879 } // buffer_merge
880
buffer_destroy(Buffer * buffer)881 void buffer_destroy(Buffer *buffer)
882 {
883 if (buffer != NULL)
884 {
885 MOJOSHADER_free f = buffer->f;
886 void *d = buffer->d;
887 buffer_empty(buffer);
888 f(buffer, d);
889 } // if
890 } // buffer_destroy
891
blockscmp(BufferBlock * item,const uint8 * data,size_t len)892 static int blockscmp(BufferBlock *item, const uint8 *data, size_t len)
893 {
894 if (len == 0)
895 return 1; // "match"
896
897 while (item != NULL)
898 {
899 const size_t itemremain = item->bytes;
900 const size_t avail = len < itemremain ? len : itemremain;
901 if (memcmp(item->data, data, avail) != 0)
902 return 0; // not a match.
903
904 if (len == avail)
905 return 1; // complete match!
906
907 len -= avail;
908 data += avail;
909 item = item->next;
910 } // while
911
912 return 0; // not a complete match.
913 } // blockscmp
914
buffer_find(Buffer * buffer,const size_t start,const void * _data,const size_t len)915 ssize_t buffer_find(Buffer *buffer, const size_t start,
916 const void *_data, const size_t len)
917 {
918 if (len == 0)
919 return 0; // I guess that's right.
920
921 if (start >= buffer->total_bytes)
922 return -1; // definitely can't match.
923
924 if (len > (buffer->total_bytes - start))
925 return -1; // definitely can't match.
926
927 // Find the start point somewhere in the center of a buffer.
928 BufferBlock *item = buffer->head;
929 const uint8 *ptr = item->data;
930 size_t pos = 0;
931 if (start > 0)
932 {
933 while (1)
934 {
935 assert(item != NULL);
936 if ((pos + item->bytes) > start) // start is in this block.
937 {
938 ptr = item->data + (start - pos);
939 break;
940 } // if
941
942 pos += item->bytes;
943 item = item->next;
944 } // while
945 } // if
946
947 // okay, we're at the origin of the search.
948 assert(item != NULL);
949 assert(ptr != NULL);
950
951 const uint8 *data = (const uint8 *) _data;
952 const uint8 first = *data;
953 while (item != NULL)
954 {
955 const size_t itemremain = item->bytes - ((size_t)(ptr-item->data));
956 ptr = (uint8 *) memchr(ptr, first, itemremain);
957 while (ptr != NULL)
958 {
959 const size_t retval = pos + ((size_t) (ptr - item->data));
960 if (len == 1)
961 return retval; // we're done, here it is!
962
963 const size_t itemremain = item->bytes - ((size_t)(ptr-item->data));
964 const size_t avail = len < itemremain ? len : itemremain;
965 if ((avail == 0) || (memcmp(ptr, data, avail) == 0))
966 {
967 // okay, we've got a (sub)string match! Move to the next block.
968 // check all blocks until we get a complete match or a failure.
969 if (blockscmp(item->next, data+avail, len-avail))
970 return (ssize_t) retval;
971 } // if
972
973 // try again, further in this block.
974 ptr = (uint8 *) memchr(ptr + 1, first, itemremain - 1);
975 } // while
976
977 pos += item->bytes;
978 item = item->next;
979 if (item != NULL)
980 ptr = item->data;
981 } // while
982
983 return -1; // no match found.
984 } // buffer_find
985
986 // end of mojoshader_common.c ...
987
988