1 /* 2 Copyright (C) 2011-2021, Dirk Krause 3 SPDX-License-Identifier: BSD-3-Clause 4 */ 5 6 /* 7 WARNING: This file was generated by the dkct program (see 8 http://dktools.sourceforge.net/ for details). 9 Changes you make here will be lost if dkct is run again! 10 You should modify the original source and run dkct on it. 11 Original source: dk4sto.ctr 12 */ 13 14 #ifndef DK4STO_H_INCLUDED 15 /** Avoid multiple inclusions. */ 16 #define DK4STO_H_INCLUDED 1 17 18 19 /** @file 20 Sorted and unsorted data storage in 21 AVL trees or double linked lists. 22 23 CRT on Windows: Optional. 24 */ 25 26 #ifndef DK4CONF_H_INCLUDED 27 #if DK4_BUILDING_DKTOOLS4 28 #include "dk4conf.h" 29 #else 30 #include <dktools-4/dk4conf.h> 31 #endif 32 #endif 33 34 #ifndef DK4TYPES_H_INCLUDED 35 #if DK4_BUILDING_DKTOOLS4 36 #include <libdk4base/dk4types.h> 37 #else 38 #include <dktools-4/dk4types.h> 39 #endif 40 #endif 41 42 #ifndef DK4ERROR_H_INCLUDED 43 #if DK4_BUILDING_DKTOOLS4 44 #include <libdk4base/dk4error.h> 45 #else 46 #include <dktools-4/dk4error.h> 47 #endif 48 #endif 49 50 51 /** Evaluation result for an object. 52 */ 53 typedef union { 54 double d; /**< Evaluation to double. */ 55 float f; /**< Evaluation to float. */ 56 long l; /**< Evaluation to long. */ 57 unsigned long ul; /**< Evaluation to unsigned long. */ 58 int i; /**< Evaluation to int. */ 59 unsigned int ui; /**< Evaluation to unsigned int. */ 60 short s; /**< Evaluation to short. */ 61 unsigned short us; /**< Evaluation to unsigned short. */ 62 char c; /**< Evaluation to char. */ 63 unsigned char uc; /**< Evaluation to unsigned char. */ 64 } dk4_object_eval_res_t; 65 66 67 68 /** Internal node for dk4_sto_t. 69 This structure is used internally by the dksto module. 70 */ 71 struct dk4__sto__node { 72 struct dk4__sto__node *p; /**< Parent node in tree. */ 73 struct dk4__sto__node *l; /**< Left child (tree) or neighbour (list). */ 74 struct dk4__sto__node *r; /**< Right child (tree) or neighbour (list). */ 75 void *o; /**< Object to store. */ 76 dk4_object_eval_res_t v; /**< Object evaluation of @a o. */ 77 short b; /**< Balance flag (used in tree only). */ 78 short w; /**< Direction to walk. */ 79 }; 80 81 /** Internal node for dk4_sto_t. 82 */ 83 typedef struct dk4__sto__node dk4_sto_node_t; 84 85 /** Pointer to internal node for dk4_sto_t. 86 */ 87 typedef dk4_sto_node_t *dk4_sto_node_p; 88 89 90 91 /** Evaluation functions. 92 These function type are used to evaluate and compare objects 93 stored in a sorted dk4_sto_t. 94 */ 95 96 /** Object evaluation function for sorted storage. 97 */ 98 typedef char dk4_fct_eval_c_t(void const *obj, int crit); 99 100 /** Object evaluation function for sorted storage. 101 */ 102 typedef unsigned char dk4_fct_eval_uc_t(void const *obj, int crit); 103 104 /** Object evaluation function for sorted storage. 105 */ 106 typedef short dk4_fct_eval_s_t(void const *obj, int crit); 107 108 /** Object evaluation function for sorted storage. 109 */ 110 typedef unsigned short dk4_fct_eval_us_t(void const *obj, int crit); 111 112 /** Object evaluation function for sorted storage. 113 */ 114 typedef int dk4_fct_eval_i_t(void const *obj, int crit); 115 116 /** Object evaluation function for sorted storage. 117 */ 118 typedef unsigned int dk4_fct_eval_ui_t(void const *obj, int crit); 119 120 /** Object evaluation function for sorted storage. 121 */ 122 typedef long dk4_fct_eval_l_t(void const *obj, int crit); 123 124 /** Object evaluation function for sorted storage. 125 */ 126 typedef unsigned long dk4_fct_eval_ul_t(void const *obj, int crit); 127 128 /** Object evaluation function for sorted storage. 129 */ 130 typedef float dk4_fct_eval_f_t(void const *obj, int crit); 131 132 /** Object evaluation function for sorted storage. 133 */ 134 typedef double dk4_fct_eval_d_t(void const *obj, int crit); 135 136 /** Object comparison function for sorted storage. 137 When comparing to objects while inserting a new object into 138 a storage both @a o1 and @a o2 are object pointers. 139 When this function is called from dk4sto_it_find_like() the 140 @a o1 argument is an object pointer from the storage, 141 @a o2 is the pointer passed to dk4sto_it_find_like(). 142 */ 143 typedef int dk4_fct_comp_t(void const *o1, void const *o2, int crit); 144 145 146 147 /** Choice for object evaluation function. 148 */ 149 typedef union { 150 dk4_fct_eval_c_t *c; /**< Evaluate to char. */ 151 dk4_fct_eval_uc_t *uc; /**< Evaluate to unsigned char. */ 152 dk4_fct_eval_s_t *s; /**< Evaluate to short. */ 153 dk4_fct_eval_us_t *us; /**< Evaluate to unsigned short. */ 154 dk4_fct_eval_i_t *i; /**< Evaluate to int. */ 155 dk4_fct_eval_ui_t *ui; /**< Evaluate to unsigned int. */ 156 dk4_fct_eval_l_t *l; /**< Evaluate to long. */ 157 dk4_fct_eval_ul_t*ul; /**< Evaluate to unsigned long. */ 158 dk4_fct_eval_f_t *f; /**< Evaluate to float. */ 159 dk4_fct_eval_d_t *d; /**< Evaluate to double. */ 160 dk4_fct_comp_t *comp; /**< Compare two objects. */ 161 } dk4_object_eval_fct_t; 162 163 164 165 /** Object storage. 166 A storage can be used to store pointers to objects. 167 */ 168 typedef struct dk4__sto__t { 169 dk4_object_eval_fct_t e; /**< Comparison or evaluation function. */ 170 dk4_sto_node_p *d; /**< Critical path for delete operations. */ 171 dk4_sto_node_t *r; /**< Tree root or start of list. */ 172 void *i; /**< Double-linked list of iterators. */ 173 int h; /**< Selection for comparison or evaluation. */ 174 int c; /**< Comparison or evaluation criteria. */ 175 int t; /**< Flag: Use tree, 1=tree, 0=list. */ 176 short l; /**< Path length of critical path. */ 177 } dk4_sto_t; 178 179 180 181 /** Storage iterator. 182 This structure can be used to iterate through a dk4_sto_t. 183 */ 184 struct dk4__sto__iterator { 185 struct dk4__sto__iterator *l; /**< Left neighbour (preceeding iterator). */ 186 struct dk4__sto__iterator *r; /**< Right neighbour (following iterator). */ 187 dk4_sto_t *s; /**< Owner storage. */ 188 dk4_sto_node_t *c; /**< Current node, current position. */ 189 }; 190 191 /** Storage iterator. Can be used to iterate through a dk4_sto_t. 192 */ 193 typedef struct dk4__sto__iterator dk4_sto_it_t; 194 195 196 197 #ifdef __cplusplus 198 extern "C" { 199 #endif 200 201 /** Create new storage. 202 @param erp Error report, may be NULL. 203 @return Pointer to new storage on succcess, NULL on error. 204 Use dk4sto_close() to destroy the storage when done with it. 205 206 Error codes: 207 - DK4_E_INVALID_ARGUMENTS<br> 208 if elsize or nelem is 0, 209 - DK4_E_MATH_OVERFLOW<br> 210 on numeric overflow when calculating the 211 product of elsize and nelem, 212 - DK4_E_MEMORY_ALLOCATION_FAILED<br> 213 with mem.elsize and mem.nelem 214 set if there is not enough memory available. 215 */ 216 dk4_sto_t * 217 dk4sto_open(dk4_er_t *erp); 218 219 /** Destroy storage, release memory. 220 @param st Storage to destroy. 221 */ 222 void 223 dk4sto_close(dk4_sto_t *st); 224 225 /** Remove all pointers from a storage. 226 @param st Storage. 227 */ 228 void 229 dk4sto_remove_all(dk4_sto_t *st); 230 231 /** Remove one pointer from storage. 232 <b>Warning:</b> Do not use dk4sto_it_next() on any iterator 233 of the storage after removing data from a storage. 234 Reset the iterator! 235 @param st Storage. 236 @param o Object pointer to remove. 237 @param erp Error report, may be NULL. 238 @return 1 on success, 0 on error (not found). 239 240 Error codes: 241 - DK4_E_INVALID_ARGUMENTS<br> 242 if st or o is NULL, 243 - DK4_E_NOT_FOUND 244 if o was not found in st. 245 */ 246 int 247 dk4sto_remove(dk4_sto_t *st, void *o, dk4_er_t *erp); 248 249 /** Add object pointer to storage. 250 @param st Storage. 251 @param o Object pointer to add. 252 @param erp Error report, may be NULL. 253 @return 1 on success, 0 on error (not enough memory). 254 255 Error codes: 256 - DK4_E_INVALID_ARGUMENTS<br> 257 if st or os is NULL, 258 - DK4_E_MEMORY_ALLOCATION_FAILED<br> 259 with mem.elsize and mem.nelem 260 set if there is not enough memory available. 261 */ 262 int 263 dk4sto_add(dk4_sto_t *st, void *o, dk4_er_t *erp); 264 265 /** Create iterator for storage. 266 @param st Storage. 267 @param erp Error report, may be NULL. 268 @return Pointer to new iterator on success, NULL on error. 269 Use dk4sto_it_close() to destroy the iterator when done with it. 270 When closing/destroying a storage all iterators for that 271 storage are destroyed automatically. 272 273 Error codes: 274 - DK4_E_INVALID_ARGUMENTS<br> 275 if st is NULL, 276 - DK4_E_MEMORY_ALLOCATION_FAILED<br> 277 with mem.elsize and mem.nelem 278 set if there is not enough memory available. 279 */ 280 dk4_sto_it_t * 281 dk4sto_it_open(dk4_sto_t *st, dk4_er_t *erp); 282 283 /** Destroy iterator. 284 @param it Iterator to destroy. 285 */ 286 void 287 dk4sto_it_close(dk4_sto_it_t *it); 288 289 /** Reset iterator (next call to dk4sto_it_next() will return the 290 first object pointer. 291 @param it Iterator. 292 */ 293 void 294 dk4sto_it_reset(dk4_sto_it_t *it); 295 296 /** Return next object pointer. 297 @param it Iterator. 298 @return Pointer to next object on success, NULL on error 299 (no more pointers available). 300 */ 301 void * 302 dk4sto_it_next(dk4_sto_it_t *it); 303 304 /** Find a pointer exactly. 305 @param i Iterator. 306 @param o Object pointer. 307 @return Object pointer on success, NULL on error (object not found). 308 The next calls to dk4sto_it_next() will return pointers to objects 309 after the specified object \a o. 310 */ 311 void * 312 dk4sto_it_find_exact(dk4_sto_it_t *i, void const *o); 313 314 /** Find object pointer for object evaluating equally to \a o. 315 @param i Iterator. 316 @param o Object pointer. 317 @param cr Comparison criteria. 318 @return Object pointer on success, NULL on error (no such object). 319 */ 320 void * 321 dk4sto_it_find_like(dk4_sto_it_t *i, void const *o, int cr); 322 323 /** Set evaluation function. 324 @param st Storage. 325 @param f Function evaluating a pointer to a char. 326 @param cr Evaluation criteria. 327 @return 1 on success, 0 on error. 328 */ 329 int 330 dk4sto_set_eval_c(dk4_sto_t *st, dk4_fct_eval_c_t *f, int cr); 331 332 /** Set evaluation function. 333 @param st Storage. 334 @param f Function evaluating a pointer to an unsigned char. 335 @param cr Evaluation criteria. 336 @return 1 on success, 0 on error. 337 */ 338 int 339 dk4sto_set_eval_uc(dk4_sto_t *st, dk4_fct_eval_uc_t *f, int cr); 340 341 /** Set evaluation function. 342 @param st Storage. 343 @param f Function evaluating a pointer to a short. 344 @param cr Evaluation criteria. 345 @return 1 on success, 0 on error. 346 */ 347 int 348 dk4sto_set_eval_s(dk4_sto_t *st, dk4_fct_eval_s_t *f, int cr); 349 350 /** Set evaluation function. 351 @param st Storage. 352 @param f Function evaluating a pointer to an unsigned short. 353 @param cr Evaluation criteria. 354 @return 1 on success, 0 on error. 355 */ 356 int 357 dk4sto_set_eval_us(dk4_sto_t *st, dk4_fct_eval_us_t *f, int cr); 358 359 /** Set evaluation function. 360 @param st Storage. 361 @param f Function evaluating a pointer to an int. 362 @param cr Evaluation criteria. 363 @return 1 on success, 0 on error. 364 */ 365 int 366 dk4sto_set_eval_i(dk4_sto_t *st, dk4_fct_eval_i_t *f, int cr); 367 368 /** Set evaluation function. 369 @param st Storage. 370 @param f Function evaluating a pointer to an unsigned int. 371 @param cr Evaluation criteria. 372 @return 1 on success, 0 on error. 373 */ 374 int 375 dk4sto_set_eval_ui(dk4_sto_t *st, dk4_fct_eval_ui_t *f, int cr); 376 377 /** Set evaluation function. 378 @param st Storage. 379 @param f Function evaluating a pointer to a long. 380 @param cr Evaluation criteria. 381 @return 1 on success, 0 on error. 382 */ 383 int 384 dk4sto_set_eval_l(dk4_sto_t *st, dk4_fct_eval_l_t *f, int cr); 385 386 /** Set evaluation function. 387 @param st Storage. 388 @param f Function evaluating a pointer to an unsigned long. 389 @param cr Evaluation criteria. 390 @return 1 on success, 0 on error. 391 */ 392 int 393 dk4sto_set_eval_ul(dk4_sto_t *st, dk4_fct_eval_ul_t *f, int cr); 394 395 /** Set evaluation function. 396 @param st Storage. 397 @param f Function evaluating a pointer to a float. 398 @param cr Evaluation criteria. 399 @return 1 on success, 0 on error. 400 */ 401 int 402 dk4sto_set_eval_f(dk4_sto_t *st, dk4_fct_eval_f_t *f, int cr); 403 404 /** Set evaluation function. 405 @param st Storage. 406 @param f Function evaluating a pointer to a double. 407 @param cr Evaluation criteria. 408 @return 1 on success, 0 on error. 409 */ 410 int 411 dk4sto_set_eval_d(dk4_sto_t *st, dk4_fct_eval_d_t *f, int cr); 412 413 /** Set comparison function. 414 @param st Storage. 415 @param f Function comparing two object pointers. 416 @param cr Comparison criteria. 417 @return 1 on success, 0 on error. 418 */ 419 int 420 dk4sto_set_comp(dk4_sto_t *st, dk4_fct_comp_t *f, int cr); 421 422 /** Allow use of tree structures. 423 This function must be called before adding any data. 424 @param st Storage. 425 @param ok Flag: Trees may be used. 426 @return 1 on success, 0 on error. 427 */ 428 int 429 dk4sto_use_trees(dk4_sto_t *st,int ok); 430 431 /** Find object pointer at the trees root. 432 @param s Storage. 433 */ 434 void * 435 dk4sto_find_root(dk4_sto_t const *s); 436 437 /** Find object pointer for the parent node 438 of the last found object. 439 @param i Iterator. 440 @return Object pointer on success, NULL on error. 441 */ 442 void * 443 dk4sto_it_find_parent(dk4_sto_it_t const *i); 444 445 /** Find object pointer for node on left child of the last found object. 446 @param i Iterator. 447 @return Object pointer on success, NULL on error. 448 */ 449 void * 450 dk4sto_it_find_left(dk4_sto_it_t const *i); 451 452 /** Find object pointer for node on right child of the last found object. 453 @param i Iterator. 454 @return Object pointer on success, NULL on error. 455 */ 456 void * 457 dk4sto_it_find_right(dk4_sto_it_t const *i); 458 459 /** Find object pointer at the trees root. 460 @param i Iterator. 461 */ 462 void * 463 dk4sto_it_find_root(dk4_sto_it_t const *i); 464 465 466 467 #ifdef __cplusplus 468 } 469 #endif 470 471 472 473 474 #endif 475