Mercurial > repos > blastem
view tern.c @ 2329:06d5e9b08bdb
Add NTSC composite shader by Sik
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Wed, 23 Aug 2023 21:38:39 -0700 |
parents | 8483c685cf03 |
children |
line wrap: on
line source
/* Copyright 2013 Michael Pavone This file is part of BlastEm. BlastEm is free software distributed under the terms of the GNU General Public License version 3 or greater. See COPYING for full license text. */ #include "tern.h" #include <stddef.h> #include <stdlib.h> #include <string.h> #include <stdio.h> #include "util.h" tern_node * tern_insert(tern_node * head, char const * key, tern_val value, uint8_t valtype) { tern_node ** cur = &head; while(*key) { if (*cur) { while(*cur && (*cur)->el != *key) { if (*key < (*cur)->el) { cur = &(*cur)->left; } else { cur = &(*cur)->right; } } } if (!*cur) { *cur = malloc(sizeof(tern_node)); (*cur)->left = NULL; (*cur)->right = NULL; (*cur)->straight.next = NULL; (*cur)->el = *key; (*cur)->valtype = TVAL_NONE; } cur = &((*cur)->straight.next); key++; } while(*cur && (*cur)->el) { cur = &(*cur)->left; } if (!*cur) { *cur = malloc(sizeof(tern_node)); (*cur)->left = NULL; (*cur)->right = NULL; (*cur)->el = 0; (*cur)->valtype = TVAL_NONE; } if ((*cur)->valtype == TVAL_PTR) { //not freeing tern nodes can also cause leaks, but handling freeing those here is problematic //since updating a sub-tree may involve creating a new root node free((*cur)->straight.value.ptrval); } (*cur)->straight.value = value; (*cur)->valtype = valtype; return head; } uint8_t tern_find(tern_node * head, char const * key, tern_val *ret) { tern_node * cur = head; while (cur) { if (cur->el == *key) { if (*key) { cur = cur->straight.next; key++; } else { *ret = cur->straight.value; return cur->valtype; } } else if (*key < cur->el) { cur = cur->left; } else { cur = cur->right; } } return TVAL_NONE; } tern_node * tern_find_prefix(tern_node * head, char const * key) { tern_node * cur = head; while (cur && *key) { if (cur->el == *key) { cur = cur->straight.next; key++; } else if (*key < cur->el) { cur = cur->left; } else { cur = cur->right; } } return cur; } intptr_t tern_find_int(tern_node * head, char const * key, intptr_t def) { tern_val ret; uint8_t valtype = tern_find(head, key, &ret); if (valtype == TVAL_INT) { return ret.intval; } return def; } tern_node * tern_insert_int(tern_node * head, char const * key, intptr_t value) { tern_val val; val.intval = value; return tern_insert(head, key, val, TVAL_INT); } void * tern_find_ptr_default(tern_node * head, char const * key, void * def) { tern_val ret; uint8_t valtype = tern_find(head, key, &ret); if (valtype == TVAL_PTR) { return ret.ptrval; } return def; } void * tern_find_ptr(tern_node * head, char const * key) { return tern_find_ptr_default(head, key, NULL); } tern_node *tern_find_node(tern_node *head, char const *key) { tern_val ret; uint8_t valtype = tern_find(head, key, &ret); if (valtype == TVAL_NODE) { return ret.ptrval; } return NULL; } uint8_t tern_delete(tern_node **head, char const *key, tern_val *out) { tern_node *cur = *head, **last = head; while (cur) { if (cur->el == *key) { if (*key) { last = &cur->straight.next; cur = cur->straight.next; key++; } else { break; } } else if (*key < cur->el) { last = &cur->left; cur = cur->left; } else { last = &cur->right; cur = cur->right; } } if (!cur) { return TVAL_NONE; } *last = cur->right; uint8_t valtype = cur->valtype; if (out) { *out = cur->straight.value; } free(cur); return valtype; } tern_val tern_find_path_default(tern_node *head, char const *key, tern_val def, uint8_t req_valtype) { tern_val ret; while (*key) { uint8_t valtype = tern_find(head, key, &ret); if (!valtype) { return def; } key = key + strlen(key) + 1; if (*key) { if (valtype != TVAL_NODE) { return def; } head = ret.ptrval; } else if (req_valtype && req_valtype != valtype) { return def; } } return ret; } tern_val tern_find_path(tern_node *head, char const *key, uint8_t valtype) { tern_val def; def.ptrval = NULL; return tern_find_path_default(head, key, def, valtype); } tern_node * tern_insert_ptr(tern_node * head, char const * key, void * value) { tern_val val; val.ptrval = value; return tern_insert(head, key, val, TVAL_PTR); } tern_node * tern_insert_node(tern_node *head, char const *key, tern_node *value) { tern_val val; val.ptrval = value; return tern_insert(head, key, val, TVAL_NODE); } tern_node *tern_insert_path(tern_node *head, char const *key, tern_val val, uint8_t valtype) { const char *next_key = key + strlen(key) + 1; if (*next_key) { tern_node *child = tern_find_node(head, key); child = tern_insert_path(child, next_key, val, valtype); return tern_insert_node(head, key, child); } else { return tern_insert(head, key, val, valtype); } } uint8_t tern_delete_path(tern_node **head, char const *key, tern_val *out) { const char *next_key = key + strlen(key) + 1; if (*next_key) { tern_node *child = tern_find_node(*head, key); if (!child) { return TVAL_NONE; } tern_node *tmp = child; uint8_t valtype = tern_delete_path(&tmp, next_key, out); if (tmp != child) { *head = tern_insert_node(*head, key, tmp); } return valtype; } else { return tern_delete(head, key, out); } } uint32_t tern_count(tern_node *head) { uint32_t count = 0; if (head->left) { count += tern_count(head->left); } if (head->right) { count += tern_count(head->right); } if (!head->el) { count++; } else if (head->straight.next) { count += tern_count(head->straight.next); } return count; } #define MAX_ITER_KEY 127 void tern_foreach_int(tern_node *head, iter_fun fun, void *data, char *keybuf, int pos) { if (!head->el) { keybuf[pos] = 0; fun(keybuf, head->straight.value, head->valtype, data); } if (head->left) { tern_foreach_int(head->left, fun, data, keybuf, pos); } if (head->el && head->straight.next) { if (pos == MAX_ITER_KEY) { fatal_error("tern_foreach_int: exceeded maximum key size"); } keybuf[pos] = head->el; tern_foreach_int(head->straight.next, fun, data, keybuf, pos+1); } if (head->right) { tern_foreach_int(head->right, fun, data, keybuf, pos); } } void tern_foreach(tern_node *head, iter_fun fun, void *data) { if (!head) { return; } //lame, but good enough for my purposes char key[MAX_ITER_KEY+1]; tern_foreach_int(head, fun, data, key, 0); } char * tern_int_key(uint32_t key, char * buf) { int len = 0; uint32_t tmp = key; while (tmp) { tmp >>= 7; ++len; } buf[len] = 0; char * cur = buf + len - 1; while (key) { *(cur--) = (key & 0x7F) + 1; key >>= 7; } return buf; } char * tern_sortable_int_key(uint32_t key, char * buf) { buf[MAX_INT_KEY_SIZE - 1] = 0; char * cur = buf + MAX_INT_KEY_SIZE - 2; while (cur >= buf) { *(cur--) = (key & 0x7F) + 1; key >>= 7; } return buf; } void tern_free(tern_node *head) { if (!head) { return; } tern_free(head->left); tern_free(head->right); if (head->el) { tern_free(head->straight.next); } free(head); }