1 /*! \file namevaluetree.h 2 * \brief The NameValueTree helper object (includes XML parser). 3 * 4 * The NameValueTree is a very important utility class in this library. 5 * It is used whenever a dynamic linked list is required. This actually 6 * not just a list but a tree, that is each element not only has neighbors but 7 * also childs. This tree-like structure allows the list class to take 8 * care of XML constructs. There is a method to convert a list into 9 * BEEP XML format and vice versa. 10 * 11 * This list object is utilized more or less whenever there is need 12 * for a dynamically assigned structure. Some examples are 13 * 14 * - profile registry (active profiles) 15 * - BEEP XML processing 16 * - MIME headers 17 * 18 * As such, the class should be highly optimized. The list is only single-linked 19 * as - as of now - we do not see any reason to walk the list 20 * backwards or delete a list entry in the middle. Using single links 21 * saves some storage as well as CPU cycles in this case. 22 * 23 * The list actually consists of two data structures: 24 * 25 * - the list root (one per tree) 26 * - the list entries (multiple per list). 27 * 28 * The list provides keyed access. A list can be searched based on 29 * a string or unsigned key. Each entry provides string or unsigned 30 * values to this key. Each entry can have on void* pointer to point 31 * to whatever larger data type the caller may need. 32 * 33 * If XML is represented, a true tree is build. The hierarchie 34 * reflects the nesting of XML elements. 35 * 36 * - A XML element with subordinates does not have a value but 37 * a pointer to the root of the subordinate. 38 * - A XML end node does not have a pointer to a subordinate. 39 * Instead, it has a pointer to its character representation 40 * of the XML value (that pointer may be NULL if there was no 41 * data in the XML container). 42 * - If an XML element has attributes, these attributes are 43 * stored in a separate NameValueTree. However, this "tree" 44 * is not a real tree but always a "flat" list. 45 * - If there is CDATA present with a given element, that 46 * CDATA is stored in a special CDATA pointer. 47 * 48 * The same rules are used to persists a NameValueTree to XML. 49 * 50 * \author Rainer Gerhards <rgerhards@adiscon.com> 51 * \date 2003-08-04 52 * Initial version as part of liblogging 0.2 begun. 53 * 54 * Copyright 2002-2014 55 * Rainer Gerhards and Adiscon GmbH. All Rights Reserved. 56 * 57 * Redistribution and use in source and binary forms, with or without 58 * modification, are permitted provided that the following conditions are 59 * met: 60 * 61 * * Redistributions of source code must retain the above copyright 62 * notice, this list of conditions and the following disclaimer. 63 * 64 * * Redistributions in binary form must reproduce the above copyright 65 * notice, this list of conditions and the following disclaimer in 66 * the documentation and/or other materials provided with the 67 * distribution. 68 * 69 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 70 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 71 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 72 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 73 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 74 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 75 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 76 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 77 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 78 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 79 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 80 */ 81 #ifndef __LIB3195_SBNVT_H_INCLUDED__ 82 #define __LIB3195_SBNVT_H_INCLUDED__ 1 83 #include "beepsession.h" 84 85 #define sbNVTRCHECKVALIDOBJECT(x) {assert(x != NULL); assert(x->OID == OIDsbNVTR);} 86 #define sbNVTECHECKVALIDOBJECT(x) {assert(x != NULL); assert(x->OID == OIDsbNVTE);} 87 88 /** 89 * The list root object. 90 */ 91 struct sbNVTEObject; 92 struct sbStrBObject; 93 struct sbNVTRObject 94 { 95 srObjID OID; /**< object ID */ 96 struct sbNVTEObject *pFirst; /**< first element in this list */ 97 struct sbNVTEObject *pLast; /**< last element in this list */ 98 struct sbNVTEObject *pParent; /**< parent of this element */ 99 }; 100 typedef struct sbNVTRObject sbNVTRObj; 101 102 103 /** 104 * The list entry object. 105 * 106 * Please note that keys and values are optional. There are 107 * different types provided in case a caller has need for 108 * different types. It is up the caller to using them. 109 * All pointers are NULL if not used (and all may be NULL!). 110 */ 111 struct sbNVTEObject 112 { 113 srObjID OID; /**< object ID */ 114 struct sbNVTEObject *pNext; /**< next element in list */ 115 sbNVTRObj *pChild; /**< pointer to child list */ 116 sbNVTRObj *pXMLProps; /**< pointer to XML properties, if any */ 117 void *pUsr; /**< user supplied-pointer for user use */ 118 void (*pUsrDestroy)(void*); /**< pointer to user-supplied destructor for pUsr */ 119 char *pszKey; /**< entry key as character */ 120 unsigned uKey; /**< entry integer Key (for faster searches with integer values */ 121 int uKeyPresent; /**< boolean - is uKey presen? (we can't tell from the value...) */ 122 char *pszValue; /**< associated character value */ 123 unsigned uValue; /**< associated unsigned value */ 124 int bIsSetUValue; /**< TRUE = uValue is set (valid), FALSE otherwise */ 125 char *pCDATA; /**< associated CDATA */ 126 }; 127 typedef struct sbNVTEObject sbNVTEObj; 128 129 130 /** 131 * Destructor for root elements - destroys a complete list. 132 * 133 * We walk the list from to to bottom and destroy every single 134 * element. If an entry element contains other lists, they call 135 * recursively back to this method to distroy these lists. 136 */ 137 void sbNVTRDestroy(sbNVTRObj* pThis); 138 139 /** 140 * Destructor for entry elements. 141 * 142 * This destructor destroys all elements directly 143 * associated with this entry element. As such, 144 * XML Properties and Childs are destroyed, but not 145 * the parent or sibling, as they may remain valid 146 * in another context. 147 * 148 * If there is a user pointer, the supplied free() 149 * function is called on it. 150 * 151 */ 152 void sbNVTEDestroy(sbNVTEObj* pThis); 153 154 /** 155 * Construct a NameValueTree Root Object. 156 * Use this constructor whenever a new object is created! 157 * 158 * \retval pointer to the new object or NULL, if 159 * an error occured. 160 */ 161 sbNVTRObj* sbNVTRConstruct(void); 162 163 /** 164 * Construct a NameValueTree Entry Object. 165 * Use this constructor whenever a new object is created! 166 * 167 * \retval pointer to the new object or NULL, if 168 * an error occured. 169 */ 170 sbNVTEObj* sbNVTEConstruct(void); 171 172 /** 173 * Unlink the first element from a name value tree. 174 * The element is not destroyed, but simply unlinked. 175 * \note It is the caller's responsibility to unlink the 176 * element when he is done! 177 * 178 * It is valid to call this mothod on a linked list 179 * WITHOUT any elements. In this case, NULL is returned. 180 * 181 * \retval pointer to unlinked element or NULL if list 182 * was empty. 183 */ 184 sbNVTEObj* sbNVTUnlinkElement(sbNVTRObj* pRoot); 185 186 /** 187 * Find the next element with a given string key inside the 188 * list. 189 * 190 * \note A list may contain multiple entries with the same key. 191 * As such, this method receives a pointer to the last 192 * entry found and continues search from there. Call the method 193 * until NULL is returned, in which case no further match is 194 * found. 195 * 196 * \param pRoot Root of the list to be searched. 197 * \param pStart Starting entry for the search. If NULL, search 198 * will begin at the first entry. Please note that 199 * pStart MUST belong to pRoot, otherwise results are 200 * unpredictable. 201 * \param pszSearch String to search for. If this pointer 202 * is NULL, the next element is returned without 203 * any comparision. In short, with this parameter 204 * being NULL, the method can be used to walk the list. 205 * \retval pointer to found element or NULL, if no (more) 206 * element is found. 207 */ 208 sbNVTEObj* sbNVTSearchKeySZ(sbNVTRObj* pRoot, sbNVTEObj* pStart, char* pszSearch); 209 210 /** 211 * Find the next element with a given integer key inside the 212 * list. 213 * 214 * \note A list may contain multiple entries with the same key. 215 * As such, this method receives a pointer to the last 216 * entry found and continues search from there. Call the method 217 * until NULL is returned, in which case no further match is 218 * found. 219 * 220 * \param pRoot Root of the list to be searched. 221 * \param pStart Starting entry for the search. If NULL, search 222 * will begin at the first entry. Please note that 223 * pStart MUST belong to pRoot, otherwise results are 224 * unpredictable. 225 * \param uSearch Unsinged Integer to search for. 226 * \retval pointer to found element or NULL, if no (more) 227 * element is found. 228 */ 229 sbNVTEObj* sbNVTSearchKeyU(sbNVTRObj* pRoot, sbNVTEObj* pStart, unsigned uSearch); 230 231 232 /** 233 * Set the string key for a given entry. 234 * The string key is copied to a new buffer if 235 * so requested. 236 * 237 * \param pszKey Pointer to string making up the key. 238 * \param bCopy TRUE duplicate string, FALSE = use 239 * supplied buffer. In case of FALSE, the 240 * caller should no longer work with the 241 * supplied buffer as ownership moves to the 242 * name value tree. Results would be 243 * unpredictable at best... 244 */ 245 srRetVal sbNVTESetKeySZ(sbNVTEObj* pThis, char* pszKey, int bCopy); 246 247 /** 248 * Set the string value for a given entry. 249 * The string key is copied to a new buffer if so 250 * requested. 251 * 252 * \param pszVal New string to be set. 253 * \param bCopy TRUE duplicate string, FALSE = use 254 * supplied buffer. In case of FALSE, the 255 * caller should no longer work with the 256 * supplied buffer as ownership moves to the 257 * name value tree. Results would be 258 * unpredictable at best... 259 */ 260 srRetVal sbNVTESetValueSZ(sbNVTEObj* pThis, char* pszVal, int bCopy); 261 262 /** 263 * Set the integer key for a given entry. 264 * \param uKey new key 265 */ 266 srRetVal sbNVTESetKeyU(sbNVTEObj* pThis, unsigned uKey); 267 268 /** 269 * Remove the integer key for a given entry. 270 */ 271 srRetVal sbNVTEUnsetKeyU(sbNVTEObj* pThis); 272 273 /** 274 * Set the integer value for a given entry. 275 * \param uKey new value 276 */ 277 srRetVal sbNVTESetValueU(sbNVTEObj* pThis, unsigned uVal); 278 279 280 /** 281 * Set the user pointer for a given entry. 282 * \param pPtr ponter to user supplied buffer 283 * \param pPtrDestroy pointer to user-supplied method to destroy 284 * the buffer. This is necessary as the NameValueTree module 285 * may destroy the buffer at any time without the user actually 286 * knowing. As such, it must have a destructor. To avaoid 287 * coding errors and "too quick" hacks, this pointer is not 288 * allowed to be NULL. If you do not need any destructor, 289 * provide a pointer to an empty function in this case. 290 * The prototype is void Destruct(void* ptr) with ptr 291 * being the pinter supplied in pPtr. 292 */ 293 srRetVal sbNVTESetUsrPtr(sbNVTEObj* pThis, void *pPtr, void(pPtrDestroy)(void*)); 294 295 296 /** 297 * Unlinks a root element (complete list) from its parent. 298 * If the root element has no parent, nothing happens. This 299 * is no error. 300 */ 301 void sbNVTRUnlinkFromParent(sbNVTRObj *pRoot); 302 303 /** 304 * Add an entry to the end of a NameValueTree List. 305 * A new entry element is constructed and added onto the 306 * end of the list. 307 * 308 * \param pRoot Root of the list the element is to be 309 * added to. 310 * \retval pointer to newly created list element or 311 * NULL if error occured. 312 */ 313 sbNVTEObj* sbNVTAddEntry(sbNVTRObj* pRoot); 314 315 316 /** 317 * Remove the user point from an element. This is needed 318 * if the element got deleted by the user itself. If not done, 319 * the list destructor would try to delete the object, thus 320 * resulting in a double-free. 321 * 322 * If the user pointer is not set, nothing happens. 323 */ 324 void sbNVTEUnsetUsrPtr(sbNVTEObj *pEntry); 325 326 /** 327 * Remove a keyed entry from a root element. The key 328 * search is done on the unsigned key. The first entry 329 * with a matching key value is removed. Do not use 330 * this method on a list with potentially multiple 331 * keys of the same value - or be sure to know EXACTLY 332 * what you are doing and why... 333 * 334 * The entry shall not only be unlinked from the tree 335 * but also destroyed. 336 */ 337 srRetVal sbNVTRRemoveKeyU(sbNVTRObj *pRoot, unsigned uKey); 338 339 340 /** 341 * Checks if a list has the named element. Can also 342 * check if it is the only element in the list. 343 * 344 * \param pEltname Name of the element to look for (e.g. "ok") 345 * \param bMustBeOnly TRUE = must be the only element, FALSE, can 346 * be one of many elements. Please note that the only 347 * element acutally means the only in this whole list (not 348 * the only of this name). 349 * \retval if the element could be found, a pointer to it 350 * is returned. NULL is returned if it is not found OR 351 * it is not the only entry and bMustBeOnly is TRUE. 352 */ 353 sbNVTEObj *sbNVTRHasElement(sbNVTRObj* pRoot, char *pEltname, int bMustBeOnly); 354 355 356 /** 357 * Link a child list to the current entry. 358 * 359 * \param pEntry Pointer to the entry where the child is to be added. 360 * \param pChildRoot Pointer to the to-be-added list. 361 */ 362 srRetVal sbNVTESetChild(sbNVTEObj *pEntry, sbNVTRObj *pChildRoot); 363 364 /** 365 * Print out a whole tree structure. This is a debug aid 366 * and ONLY AVAILABLE IN DEBUG BUILDS! 367 * 368 * We walk the tree and call ourselfs recursively. 369 * 370 * \param iLevel - the current level (tree-depth) we are in. 371 */ 372 void sbNVTDebugPrintTree(sbNVTRObj *pRoot, int iLevel); 373 374 /** 375 * Removes the first entry from a list. The entry 376 * will be unlinked and then destroyed. It is valid 377 * to call this function on an empty list. In this case, 378 * nothing will happen. 379 */ 380 srRetVal sbNVTRRemoveFirst(sbNVTRObj* pRoot); 381 382 /** 383 * Populate a NameValueTree based on a BEEP XML stream. 384 * 385 * This is a mini BEEP XML parser. It parses those constructs 386 * supported by BEEP XML. It does NOT check the DTD, this needs 387 * to be done by the caller. 388 * 389 * This is a "one stop" method, which means that it will do 390 * anything needed to do the job. The method detects syntax 391 * errors, only. If one is detected, an error state is 392 * returned. In this case, the status of the provided 393 * NameValueTree structure is undefined - probably some 394 * elements have been added, others not. It is highly 395 * recommended that the caller discards the NameValueTree 396 * structure if this method does not return error-free. 397 * 398 * If a pre-populated NameValueTree is provided, the 399 * elements found in the XML stream are ADDED to it. 400 * 401 * This is a single-pass parser. 402 * 403 * ABNF for our Mini XML Parser: 404 * 405 * \note This is Pseudo-ABNF, mostly following 406 * http://www.ietf.org/rfc/rfc2234.txt. 407 * 408 * BEEPXML = XMLSTREAM 409 * XMLSTREAM = *WHITESPACE *XMLELEMENT 410 * XMLELEMENT = (XMLNODE / XMLCONTAINER / CDATA) *WHITESPACE 411 * CDATA = "<![CDATA[" CDATAVALUE "]]>" ; "CDATA" must be upper case, only. 412 * ; Been to lazy to write it down in "right" ABNF ;) 413 * XMLNODE = "<" TAGwPARAMS 1*WHITESPACE "/>" ; is it really 1*WHITESPACE or just 414 * ; *WHITESPACE? In the implementation, we use *WHITESPACE when reading 415 * XMLCONTAINER = "<" TAGwPARAMS ">" (XMLVALUE / XMLSTREAM) "</" *WHITESPACE TAG ">" 416 * ; begin and end tag must be exactly the same. 417 * TAGwPARAMS = TAG *(1*WHITESPACE PARAM) *WHITESPACE 418 * TAG = XMLNAME 419 * PARAM = XMLNAME ["='" XMLVALUE "'"] 420 * XMLNAME = NON-WHITESPACE NO "/" / "<" / ">" / "=" / ";" 421 * XMLVALUE = *(PRINTABLECHAR / ESCSEQ) 422 * CDATAVALUE = all printable chars except "]" 423 * WHITESPACE = %d09 / %d10 / %d13 / %d32 ; C isspace() 424 * PRINTABLECHAR = all printable chars 425 * ESCSEQ = "&" XMLNAME ";" 426 * 427 * \param pszXML Pointer to a string containing the XML stream. May be 428 * NULL, in which case no processing takes place. 429 */ 430 srRetVal sbNVTRParseXML(sbNVTRObj *pRoot, char *pszXML); 431 432 /** 433 * Remove an entry with a specific pUsr from a root element. 434 * The first entry with a matching pUsr is removed. Do not use 435 * this method on a list with potentially multiple 436 * identical pUsrs - or be sure to know EXACTLY 437 * what you are doing and why... 438 * 439 * \param pUsr The pUsr to find and delete. This may 440 * be NULL but keep the above warning about 441 * multiple values in mind! 442 * 443 * The entry shall not only be unlinked from the tree 444 * but also be destroyed. 445 */ 446 srRetVal sbNVTRRemovEntryWithpUsr(sbNVTRObj *pRoot, void* pUsr); 447 448 /** 449 * Remove a keyed entry from a root element. The key 450 * search is done on the unsigned key. The first entry 451 * with a matching key value is removed. Do not use 452 * this method on a list with potentially multiple 453 * keys of the same value - or be sure to know EXACTLY 454 * what you are doing and why... 455 * 456 * The entry shall not only be unlinked from the tree 457 * but also be destroyed. 458 */ 459 srRetVal sbNVTRRemoveKeyU(sbNVTRObj *pRoot, unsigned uKey); 460 461 /** 462 * Unlink an entry from the current list. 463 * 464 * \param pRoot pointer to the root of this list 465 * \param pEntry pointer to the entry to be unlinked 466 * \param pointer to the element immediately before the 467 * to be unlinked entry in the list. May be NULL, 468 * in which case the to be unlinked element is the 469 * first element of the list. 470 */ 471 void sbNVTEUnlinkFromList(sbNVTRObj *pRoot, sbNVTEObj* pEntry, sbNVTEObj* pPrev); 472 473 /** 474 * This method searches for a specific pUsr and returns the 475 * entry in question PLUS the previous element. This is done 476 * for performance reasons - it 477 * saves us from doubly-linking the list, which would otherwise 478 * be required and for sure be overdone in the current state 479 * of affairs. 480 * 481 * \note A list may contain multiple entries with the same key. 482 * As such, this method receives a pointer to the last 483 * entry found and continues search from there. Call the method 484 * until NULL is returned, in which case no further match is 485 * found. 486 * 487 * \param pRoot Root of the list to be searched. 488 * \param pStart Starting entry for the search. If NULL, search 489 * will begin at the first entry. Please note that 490 * pStart MUST belong to pRoot, otherwise results are 491 * unpredictable. 492 * \param pUsr pUsr to search for. 493 * \param ppPrevEntry Pointer to a pointer to the previous element. 494 * This is needed so that that element can be 495 * updated during unlink operations. Is NULL if 496 * there is no previous element. 497 * \retval pointer to found element or NULL, if no (more) 498 * element is found. 499 */ 500 sbNVTEObj* sbNVTSearchpUsrAndPrev(sbNVTRObj* pRoot, sbNVTEObj* pStart, void *pUsr, sbNVTEObj** ppPrevEntry); 501 502 /** 503 * This is more or less a duplicate of the sbNVTSearchKeyU. The 504 * difference is that this method also delivers back the 505 * previous entry. This is done for performance reasons - it 506 * saves us from doubly-linking the list, which would otherwise 507 * be required and for sure be overdone in the current state 508 * of affairs. 509 * 510 * \paramm AllParams are like sbNVTSearchKeyU plus 511 * \param ppPrevEntry Pointer to a pointer to the previous element. 512 * This is needed so that that element can be 513 * updated during unlink operations. Is NULL if 514 * there is no previous element. 515 */ 516 sbNVTEObj* sbNVTSearchKeyUAndPrev(sbNVTRObj* pRoot, sbNVTEObj* pStart, unsigned uSearch, sbNVTEObj** ppPrevEntry); 517 518 /** 519 * Return the uValue for this object. 520 * If the uValue is already set, it is returned. If it is 521 * not yet set, we look at the szValue and see if we can 522 * convert it to an uValue. If that succeeds, we return 523 * the converted value. If that does not succeed, -1 is 524 * returned and an error is flagged. 525 * 526 * \param puValue [out] pointer to an unsinged that should 527 * receive the uValue. Please note 528 * that we can not directly return this 529 * as a return value because we need to convey an error state 530 * which may happen at any time. 531 */ 532 srRetVal sbNVTEGetValueU(sbNVTEObj* pThis, unsigned* puValue); 533 534 /** 535 * XML-Escape a string. The resulting string is suitable for use 536 * in #pcdata, that is as a string BETWEEN XML tags (e.g. 537 * <tag>string</tag>. It is NOT suitable to be used inside 538 * a tag parameter (e.g. <tag p="string">). 539 * 540 * \param pszToEscape The string to be escaped. Should not be 541 * NULL. If it is NULL, the return value will also be NULL. 542 * \retval Pointer to an XML-escaped string or NULL, if no 543 * memory for that string could be allocated. IMPORTANT: the 544 * caller MUST free() that buffer once he is done with the 545 * string, otherwise a memory leak will be left. 546 */ 547 char* sbNVTXMLEscapePCDATA(char *pszToEscape); 548 549 550 /** 551 * XML-Escape a string. The resulting string is suitable for use 552 * in #pcdata, that is as a string BETWEEN XML tags (e.g. 553 * <tag>string</tag>. It is NOT suitable to be used inside 554 * a tag parameter (e.g. <tag p="string">). 555 * 556 * \param pszToEscape The string to be escaped. Should not be 557 * NULL. If it is NULL, the provided string buffer will not be 558 * modified. 559 * 560 * \param pStr Pointer to a sbStrBObj to be filled with 561 * the escaped string. 562 */ 563 srRetVal sbNVTXMLEscapePCDATAintoStrB(char *pszToEscape, struct sbStrBObject *pStr); 564 565 /** 566 * Duplicate a string and return it. This is a general utility, it 567 * was just defined first in the context of NVTE. 568 * 569 * \param pszStrToDup String to be duplicated. MUST not be NULL. 570 * \retval duplicated string. Must be free()ed if no longer needed. 571 */ 572 char* sbNVTEUtilStrDup(char *pszStrToDup); 573 574 #endif 575