1 /* q.h 2 Header file for q.c. 3 4 Part of the swftools package. 5 6 Copyright (c) 2001,2002,2003,2004 Matthias Kramm <kramm@quiss.org> 7 8 This program is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 2 of the License, or 11 (at your option) any later version. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with this program; if not, write to the Free Software 20 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ 21 22 #ifndef __q_h__ 23 #define __q_h__ 24 25 #include <stdio.h> 26 #include <stdint.h> 27 #include "mem.h" 28 29 #ifdef __cplusplus 30 extern "C" { 31 #endif 32 33 #define NEW(t,y) t*y = (t*)rfx_calloc(sizeof(t)); 34 #define PTR_AS_INT(p) (((char*)(p))-((char*)NULL)) 35 #define INT_AS_PTR(i) (((char*)NULL)+(int)(i)) 36 37 /* dynamically growing mem section */ 38 typedef struct _mem_t { 39 char*buffer; 40 int len; 41 int pos; 42 int read_pos; 43 } mem_t; 44 45 /* fifo buffered growing mem region */ 46 typedef struct _ringbuffer_t 47 { 48 void*internal; 49 int available; 50 } ringbuffer_t; 51 52 /* non-nul terminated string */ 53 typedef struct _string_t { 54 const char*str; 55 int len; 56 } string_t; 57 58 /* key/value pairs of strings */ 59 typedef struct _map_t { 60 void*internal; 61 } map_t; 62 63 /* type information */ 64 typedef char (*equals_func)(const void*o1, const void*o2); 65 typedef unsigned int (*hash_func)(const void*o); 66 typedef void* (*dup_func)(const void*o); 67 typedef void (*free_func)(void*o); 68 69 typedef struct _type_t { 70 equals_func equals; 71 hash_func hash; 72 dup_func dup; 73 free_func free; 74 } type_t; 75 76 extern type_t charptr_type; 77 extern type_t stringstruct_type; 78 extern type_t ptr_type; 79 extern type_t int_type; 80 81 typedef struct _dictentry { 82 void*key; 83 unsigned int hash; 84 void*data; 85 struct _dictentry*next; 86 } dictentry_t; 87 88 /* (void*) pointers referenced by strings */ 89 typedef struct _dict { 90 dictentry_t**slots; 91 type_t*key_type; 92 int hashsize; 93 int num; 94 } dict_t; 95 96 /* array of key/value pairs, with fast lookup */ 97 typedef struct _array_entry { 98 void*name; 99 void*data; 100 } array_entry_t; 101 102 typedef struct _array { 103 int num; 104 int size; 105 array_entry_t*d; 106 dict_t*entry2pos; 107 } array_t; 108 109 /* array of strings, string<->int mapping, 110 with O(1) for int->string lookup and 111 ~O(n/hashsize) for string->int lookup */ 112 typedef struct _stringarray_t 113 { 114 void*internal; 115 } stringarray_t; 116 117 /* heap */ 118 typedef struct _heap { 119 void**elements; 120 char*data; 121 int elem_size; 122 int size; 123 int max_size; 124 int(*compare)(const void *, const void *); 125 } heap_t; 126 127 /* trie (with rollback) */ 128 typedef struct _trielayer { 129 struct _trielayer*row[256]; 130 unsigned char*rest; 131 void*data; 132 } trielayer_t; 133 134 typedef struct _trie { 135 trielayer_t* start; 136 void*rollback; 137 } trie_t; 138 139 /* move to front list structure */ 140 typedef struct _mtf_item { 141 const void*key; 142 int num; 143 struct _mtf_item*next; 144 } mtf_item_t; 145 146 typedef struct _mtf { 147 mtf_item_t*first; 148 type_t*type; 149 } mtf_t; 150 151 char* strdup_n(const char*str, int size); 152 char* allocprintf(const char*str, ...); 153 154 float medianf(float*values, int n); 155 156 unsigned int crc32_add_byte(unsigned int crc32, unsigned char b); 157 unsigned int crc32_add_string(unsigned int crc32, const char*s); 158 unsigned int crc32_add_bytes(unsigned int checksum, const void*s, int len); 159 160 void mem_init(mem_t*mem); 161 int mem_put(mem_t*m, void*data, int length); 162 int mem_putstring(mem_t*m, string_t str); 163 int mem_get(mem_t*m, void*data, int length); 164 void mem_clear(mem_t*mem); 165 void mem_destroy(mem_t*mem); 166 167 void ringbuffer_init(ringbuffer_t*r); 168 void ringbuffer_put(ringbuffer_t*r, void*buf, int size); 169 int ringbuffer_read(ringbuffer_t*r, void*buf, int size); 170 void ringbuffer_clear(ringbuffer_t*r); 171 172 /* old style functions- should be renamed */ 173 string_t string_new(const char*text, int len); 174 string_t string_new2(const char*text); 175 void string_dup(string_t*str, const char*text); 176 void string_dup2(string_t*str, const char*text, int len); 177 178 char* string_cstr(string_t*str); 179 char* string_escape(string_t*str); 180 string_t* string_new3(const char*text, int len); 181 string_t* string_new4(const char*text); 182 void string_free(string_t*s); 183 unsigned int string_hash(const string_t*str); 184 unsigned int string_hash2(const char*str); 185 unsigned int string_hash3(const char*str, int len); 186 uint64_t string_hash64(const char*str); 187 void string_set(string_t*str, const char*text); 188 void string_set2(string_t*str, const char*text, int len); 189 string_t*string_dup3(string_t*s); 190 int string_equals(string_t*str, const char*text); 191 192 char* concat2(const char* t1, const char* t2); 193 char* concat3(const char* t1, const char* t2, const char* t3); 194 195 void stringarray_init(stringarray_t*sa, int hashsize); 196 void stringarray_put(stringarray_t*sa, string_t str); 197 198 char* stringarray_at(stringarray_t*sa, int pos); 199 string_t stringarray_at2(stringarray_t*sa, int pos); 200 int stringarray_find(stringarray_t*sa, string_t*str); 201 void stringarray_clear(stringarray_t*sa); 202 void stringarray_destroy(stringarray_t*sa); 203 204 dict_t*dict_new(); 205 dict_t*dict_new2(type_t*type); 206 void dict_init(dict_t*dict, int size); 207 void dict_init2(dict_t*dict, type_t*type, int size); 208 dictentry_t*dict_put(dict_t*h, const void*key, void* data); 209 void dict_put2(dict_t*h, const char*s, void*data); 210 int dict_count(dict_t*h); 211 void dict_dump(dict_t*h, FILE*fi, const char*prefix); 212 dictentry_t* dict_get_slot(dict_t*h, const void*key); 213 char dict_contains(dict_t*h, const void*s); 214 void* dict_lookup(dict_t*h, const void*s); 215 char dict_del(dict_t*h, const void*s); 216 char dict_del2(dict_t*h, const void*key, void*data); 217 dict_t*dict_clone(dict_t*); 218 219 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data); 220 void dict_foreach_value(dict_t*h, void (*runFunction)(void*)); 221 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*)); 222 void dict_clear(dict_t*h); 223 void dict_destroy_shallow(dict_t*dict); 224 void dict_destroy(dict_t*dict); 225 #define DICT_ITERATE_DATA(d,t,v) \ 226 int v##_i;dictentry_t*v##_e;t v;\ 227 for(v##_i=0;v##_i<(d)->hashsize;v##_i++) \ 228 for(v##_e=(d)->slots[v##_i]; v##_e && ((v=(t)v##_e->data)||1); v##_e=v##_e->next) 229 #define DICT_ITERATE_KEY(d,t,v) \ 230 int v##_i;dictentry_t*v##_e;t v;\ 231 for(v##_i=0;v##_i<(d)->hashsize;v##_i++) \ 232 for(v##_e=(d)->slots[v##_i];v##_e && ((v=(t)v##_e->key)||1);v##_e=v##_e->next) 233 #define DICT_ITERATE_ITEMS(d,t1,v1,t2,v2) \ 234 int v1##_i;dictentry_t*v1##_e;t1 v1;t2 v2; \ 235 for(v1##_i=0;v1##_i<(d)->hashsize;v1##_i++) \ 236 for(v1##_e=(d)->slots[v1##_i]; v1##_e && (((v1=(t1)v1##_e->key)||1)&&((v2=(t2)v1##_e->data)||1)); v1##_e=v1##_e->next) 237 238 void map_init(map_t*map); 239 void map_put(map_t*map, string_t t1, string_t t2); 240 const char* map_lookup(map_t*map, const char*name); 241 void map_dump(map_t*map, FILE*fi, const char*prefix); 242 void map_clear(map_t*map); 243 void map_destroy(map_t*map); 244 245 void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *)); 246 heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *)); 247 heap_t* heap_clone(heap_t*o); 248 void heap_clear(heap_t*h); 249 void heap_destroy(heap_t*h); 250 void heap_put(heap_t*h, void*e); 251 int heap_size(heap_t*h); 252 void* heap_peek(heap_t*h); 253 void* heap_chopmax(heap_t*h); 254 void heap_dump(heap_t*h, FILE*fi); 255 void** heap_flatten(heap_t*h); 256 257 trie_t*trie_new(); 258 void trie_put(trie_t*t, unsigned const char*id, void*data); 259 char trie_remove(trie_t*t, unsigned const char*id); 260 void*trie_lookup(trie_t*t, unsigned const char*id); 261 int trie_contains(trie_t*t, unsigned const char*id); 262 void trie_remember(trie_t*t); 263 void trie_rollback(trie_t*t); 264 void trie_dump(trie_t*t); 265 266 mtf_t* mtf_new(type_t*type); 267 void mtf_increase(mtf_t*m, const void*key); 268 void mtf_destroy(mtf_t*m); 269 270 array_t* array_new1(); 271 array_t* array_new2(type_t*type); 272 void array_free(array_t*array); 273 void*array_getkey(array_t*array, int nr); 274 void*array_getvalue(array_t*array, int nr); 275 int array_append(array_t*array, const void*name, void*data); 276 #define array_contains(a,b) (array_find((a),(b))>=0) 277 int array_find(array_t*array, const void*name); 278 int array_find2(array_t*array, const void*name, void*data); 279 int array_update(array_t*array, const void*name, void*data); 280 int array_append_if_new(array_t*array, const void*name, void*data); 281 #define array_length(a) ((a)->num) 282 283 #define DECLARE(x) struct _##x;typedef struct _##x x##_t; 284 #define DECLARE_LIST(x) \ 285 struct _##x##_list { \ 286 struct _##x* x; \ 287 struct _##x##_list*next; \ 288 }; \ 289 typedef struct _##x##_list x##_list_t; 290 int list_length_(void*_list); 291 void*list_clone_(void*_list); 292 void list_append_(void*_list, void*entry); 293 void list_prepend_(void*_list, void*entry); 294 void list_free_(void*_list); 295 void list_deep_free_(void*_list); 296 void list_concat_(void*l1, void*l2); 297 #define list_new() ((void*)0) 298 #define list_append(list, e) {sizeof((list)->next);list_append_(&(list),(e));} 299 #define list_concat(l1, l2) {sizeof((l1)->next);sizeof((l2)->next);list_concat_(&(l1),&(l2));} 300 #define list_prepend(list, e) {sizeof((list)->next);list_prepend_(&(list),(e));} 301 #define list_free(list) {sizeof((list)->next);list_free_(&(list));} 302 #define list_deep_free(list) {sizeof((list)->next);list_deep_free_(&(list));} 303 #define list_clone(list) (sizeof((list)->next),(list?list_clone_(&(list)):0)) 304 #define list_length(list) (sizeof((list)->next),list_length_(list)) 305 306 #ifdef __cplusplus 307 } 308 #endif 309 310 #endif //__q_h__ 311