src/libcaptive/rtl/generictable.c

   1 /* $Id$
   2  * Implementation of Rtl*GenericTable*() of libcaptive
   3  * Copyright (C) 2002 Jan Kratochvil <project-captive@jankratochvil.net>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; exactly version 2 of June 1991 is required
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19
  20 #include "config.h"
  21
  22 #include "reactos/ntos/rtl.h"   /* self */
  23 #include <glib/gtypes.h>
  24 #include <glib/gmessages.h>
  25 #include <glib/ghash.h>
  26 #include <glib/gtree.h>
  27 #include <string.h>
  28 #include "captive/macros.h"
  29 #include <glib/gstrfuncs.h>
  30
  31
  32 struct table_info {
  33         RTL_GENERIC_TABLE *GenericTable;
  34         /* g_tree_nnodes() is expensive! Use 'GenericTable->ElementCount'. */
  35         /* map (struct table_key_info *)->(struct table_key_info *) */
  36         GTree *gtree;
  37         struct table_key_info **array;  /* NULL or valid items */
  38         struct table_key_info **enumerate_arrayp;       /* NULL if not inside enumeration */
  39         /* Used for tracking of parent of unfound element for 'NodeOrParent' */
  40         const struct table_key_info *last_table_key_info_compare_func_a_table_key_info;
  41         const struct table_key_info *last_table_key_info_compare_func_b_table_key_info;
  42         };
  43
  44 struct table_key_info {
  45         struct table_info *table_info;
  46         gpointer key;
  47         size_t key_size;        /* may be NULL if unknown */
  48         };
  49
  50 /* map PRTL_GENERIC_TABLE->(struct table_info *) */
  51 static GHashTable *GenericTable_to_table_info_hash;
  52
  53 static void GenericTable_to_table_info_hash_init(void)
  54 {
  55         if (GenericTable_to_table_info_hash)
  56                 return;
  57         GenericTable_to_table_info_hash=g_hash_table_new(g_direct_hash,g_direct_equal);
  58 }
  59
  60
  61 /* Internal to table_info_array_new().
  62  * Complies to 'GTraverseFunc'.
  63  */
  64 static gboolean table_info_array_new_func
  65                 (struct table_key_info *key_info,struct table_key_info *value_info,struct table_key_info ***r_fillptr)
  66 {
  67         /* Do not validate_table_key_info() here to prevent loop. */
  68         g_return_val_if_fail(key_info!=NULL,TRUE);
  69         g_return_val_if_fail(value_info!=NULL,TRUE);
  70         g_return_val_if_fail(key_info==value_info,TRUE);
  71         g_return_val_if_fail(r_fillptr,TRUE);
  72         g_return_val_if_fail(*r_fillptr,TRUE);
  73
  74         **r_fillptr=key_info;
  75         *r_fillptr++;
  76
  77         return FALSE;   /* continue traversal */
  78 }
  79
  80 /* It is valid to return NULL if 0==table_info->GenericTable->ElementCount */
  81 static struct table_key_info **table_info_array_new(const struct table_info *table_info)
  82 {
  83 struct table_key_info **r,**r_fill;
  84
  85         g_return_val_if_fail(table_info!=NULL,NULL);
  86         /* Do not validate_table_info() here to prevent loop. */
  87         g_return_val_if_fail(table_info->GenericTable!=NULL,NULL);
  88
  89         captive_newn(r,table_info->GenericTable->ElementCount);
  90         r_fill=r;
  91         g_tree_foreach(table_info->gtree,
  92                         (GTraverseFunc)table_info_array_new_func,       /* func */
  93                         &r_fill);       /* user_data */
  94         g_assert(r_fill==r+table_info->GenericTable->ElementCount);
  95
  96         return r;
  97 }
  98
  99 /* Internal to validate_GenericTable().
 100  * Complies to 'GTraverseFunc'.
 101  */
 102 static gboolean validate_GenericTable_func
 103                 (struct table_key_info *key_info,struct table_key_info *value_info,const struct table_info *table_info)
 104 {
 105 RTL_GENERIC_TABLE *GenericTable;
 106
 107         g_return_val_if_fail(key_info!=NULL,TRUE);
 108         g_return_val_if_fail(value_info!=NULL,TRUE);
 109         g_return_val_if_fail(key_info==value_info,TRUE);
 110         /* Do not validate_table_info() here to prevent loop. */
 111         g_return_val_if_fail(table_info!=NULL,TRUE);
 112         g_return_val_if_fail(key_info->table_info==table_info,TRUE);
 113
 114         GenericTable=table_info->GenericTable;
 115         g_assert(GenericEqual==(*GenericTable->CompareRoutine)(GenericTable,key_info->key,key_info->key));
 116
 117         return FALSE;   /* continue traversal */
 118 }
 119
 120 static gboolean validate_GenericTable(RTL_GENERIC_TABLE *GenericTable)
 121 {
 122 const struct table_info *table_info;
 123
 124         g_return_val_if_fail(GenericTable!=NULL,FALSE);
 125
 126         GenericTable_to_table_info_hash_init();
 127         /* do not use GenericTable_to_table_info() here to prevent deadlocks! */
 128         table_info=g_hash_table_lookup(GenericTable_to_table_info_hash,GenericTable);
 129         g_return_val_if_fail(table_info!=NULL,FALSE);
 130
 131         g_return_val_if_fail(table_info->GenericTable==GenericTable,FALSE);
 132         g_return_val_if_fail(table_info->gtree!=NULL,FALSE);
 133         g_tree_foreach(table_info->gtree,
 134                         (GTraverseFunc)validate_GenericTable_func,      /* func */
 135                         (gpointer/*de-const*/)table_info);      /* user_data */
 136
 137         g_return_val_if_fail(GenericTable->RootElement==NULL,FALSE);    /* we do not store it inside */
 138         g_return_val_if_fail(GenericTable->ElementCount==(ULONG)g_tree_nnodes(table_info->gtree),FALSE);
 139         g_return_val_if_fail(GenericTable->CompareRoutine!=NULL,FALSE);
 140         g_return_val_if_fail(GenericTable->AllocateRoutine!=NULL,FALSE);
 141         g_return_val_if_fail(GenericTable->FreeRoutine!=NULL,FALSE);
 142
 143         /* check the 'array' validitity if it is valid (==if exists) */
 144         if (table_info->array) {
 145                 /* check postponed here as it requires a pretty consistent structure */
 146 struct table_key_info **array_check=table_info_array_new(table_info);
 147
 148                 g_assert(0==memcmp(table_info->array,array_check,sizeof(*array_check)*table_info->GenericTable->ElementCount));
 149                 g_free(array_check);
 150                 }
 151         g_return_val_if_fail(!table_info->enumerate_arrayp
 152                                         || table_info->enumerate_arrayp<table_info->array+GenericTable->ElementCount,
 153                         FALSE);
 154
 155         return TRUE;
 156 }
 157
 158
 159 static gboolean validate_table_info(const struct table_info *table_info)
 160 {
 161         g_return_val_if_fail(table_info!=NULL,FALSE);
 162         g_return_val_if_fail(table_info->GenericTable!=NULL,FALSE);
 163
 164         g_return_val_if_fail(TRUE==validate_GenericTable(table_info->GenericTable),FALSE);
 165
 166         return TRUE;
 167 }
 168
 169
 170 static struct table_info *GenericTable_to_table_info(RTL_GENERIC_TABLE *GenericTable)
 171 {
 172 struct table_info *r;
 173
 174         g_return_val_if_fail(GenericTable!=NULL,NULL);
 175
 176         GenericTable_to_table_info_hash_init();
 177         r=g_hash_table_lookup(GenericTable_to_table_info_hash,GenericTable);
 178         g_return_val_if_fail(TRUE==validate_table_info(r),NULL);
 179
 180         return r;
 181 }
 182
 183
 184 static gboolean validate_table_key_info(const struct table_key_info *table_key_info)
 185 {
 186         g_return_val_if_fail(table_key_info!=NULL,FALSE);
 187
 188         g_return_val_if_fail(TRUE==validate_table_info(table_key_info->table_info),FALSE);
 189         g_return_val_if_fail(table_key_info->key!=NULL,FALSE);
 190         /* key_size may be NULL if it is unknown */
 191
 192         return TRUE;
 193 }
 194
 195
 196 static gboolean table_info_array_create(struct table_info *table_info)
 197 {
 198         g_return_val_if_fail(TRUE==validate_table_info(table_info),FALSE);
 199
 200         if (!table_info->array)
 201                 table_info->array=table_info_array_new(table_info);
 202
 203         return TRUE;
 204 }
 205
 206 static gboolean table_info_array_delete(struct table_info *table_info)
 207 {
 208         g_return_val_if_fail(TRUE==validate_table_info(table_info),FALSE);
 209
 210         g_free(table_info->array);
 211         table_info->array=NULL;
 212         table_info->enumerate_arrayp=NULL;      /* enumeration no longer possible */
 213
 214         return TRUE;
 215 }
 216
 217
 218 /* Returns: -1 if not found, >=0 if position found. */
 219 static gint table_info_array_find_key_compare(struct table_info *table_info,gpointer key)
 220 {
 221 RTL_GENERIC_TABLE *GenericTable;
 222 gint r,i;
 223
 224         g_return_val_if_fail(TRUE==validate_table_info(table_info),-1);
 225
 226         table_info_array_create(table_info);
 227         GenericTable=table_info->GenericTable;
 228         r=-1;   /* not yet found */
 229         for (i=0;(ULONG)i<table_info->GenericTable->ElementCount;i++)
 230                 if (GenericEqual==(*GenericTable->CompareRoutine)(GenericTable,table_info->array[i]->key,key)) {
 231                         g_assert(r==-1);
 232                         r=i;
 233                         }
 234         return r;
 235 }
 236
 237
 238 /* Returns: -1 if not found, >=0 if position found. */
 239 static gint table_info_array_find_key_pointer(struct table_info *table_info,gpointer key)
 240 {
 241 gint r,i;
 242
 243         g_return_val_if_fail(TRUE==validate_table_info(table_info),-1);
 244
 245         table_info_array_create(table_info);
 246         r=-1;   /* not yet found */
 247         for (i=0;(ULONG)i<table_info->GenericTable->ElementCount;i++)
 248                 if (table_info->array[i]==key) {
 249                         g_assert(r==-1);
 250                         r=i;
 251                         }
 252         return r;
 253 }
 254
 255
 256 /* Complies with 'GCompareDataFunc'. */
 257 static gint table_key_info_compare_func
 258                 (const struct table_key_info *a_table_key_info,const struct table_key_info *b_table_key_info,struct table_info *table_info)
 259 {
 260 RTL_GENERIC_TABLE *GenericTable;
 261
 262         g_return_val_if_fail(TRUE==validate_table_key_info(a_table_key_info),FALSE);
 263         g_return_val_if_fail(TRUE==validate_table_key_info(b_table_key_info),FALSE);
 264         g_return_val_if_fail(TRUE==validate_table_info(table_info),FALSE);
 265         g_return_val_if_fail(table_info==a_table_key_info->table_info,FALSE);
 266         g_return_val_if_fail(table_info==b_table_key_info->table_info,FALSE);
 267
 268         table_info->last_table_key_info_compare_func_a_table_key_info=a_table_key_info;
 269         table_info->last_table_key_info_compare_func_b_table_key_info=b_table_key_info;
 270
 271         GenericTable=table_info->GenericTable;
 272         switch ((*GenericTable->CompareRoutine)(GenericTable,a_table_key_info->key,b_table_key_info->key)) {
 273                 case GenericLessThan:    return -1;
 274                 case GenericGreaterThan: return +1;
 275                 case GenericEqual:       return 0;
 276                 default: g_assert_not_reached();
 277                 }
 278         g_return_val_if_reached(0);
 279 }
 280
 281
 282 /* Complies with 'GDestroyNotify'.
 283  * It has the problem that no user_data are passed here!
 284  */
 285 static void table_key_info_destroy_func(struct table_key_info *table_key_info)
 286 {
 287 RTL_GENERIC_TABLE *GenericTable;
 288
 289         g_return_if_fail(TRUE==validate_table_key_info(table_key_info));
 290
 291         GenericTable=table_key_info->table_info->GenericTable;
 292         (*GenericTable->FreeRoutine)(GenericTable,table_key_info->key);
 293         g_free(table_key_info);
 294 }
 295
 296
 297 /**
 298  * RtlInitializeGenericTable:
 299  * @GenericTable: Already allocated memory where the GenericTable header is initialized.
 300  * %NULL value is forbidden.
 301  * @CompareRoutine: Routine returning %GenericLessThan, %GenericGreaterThan or %GenericEqual for two items.
 302  * %NULL value is forbidden.
 303  * @AllocateRoutine: Item memory allocator.
 304  * %NULL value is forbidden.
 305  * @FreeRoutine: Item memory deallocator.
 306  * %NULL value is forbidden.
 307  *
 308  * Initializes @GenericTable. Such GenericTable can never be destroyed.
 309  */
 310 VOID RtlInitializeGenericTable(IN OUT PRTL_GENERIC_TABLE GenericTable,
 311                 IN PVOID CompareRoutine,IN PVOID AllocateRoutine,IN PVOID FreeRoutine,IN ULONG UserParameter)
 312 {
 313 struct table_info *table_info;
 314
 315         g_return_if_fail(GenericTable!=NULL);
 316         g_return_if_fail(CompareRoutine!=NULL);
 317         g_return_if_fail(AllocateRoutine!=NULL);
 318         g_return_if_fail(FreeRoutine!=NULL);
 319
 320         GenericTable_to_table_info_hash_init();
 321         g_assert(g_hash_table_lookup(GenericTable_to_table_info_hash,GenericTable)==NULL);
 322
 323         CAPTIVE_MEMZERO(GenericTable);
 324         GenericTable->ElementCount=0;
 325         GenericTable->CompareRoutine=CompareRoutine;
 326         GenericTable->AllocateRoutine=AllocateRoutine;
 327         GenericTable->FreeRoutine=FreeRoutine;
 328         GenericTable->UserParameter=UserParameter;
 329
 330         captive_new0(table_info);
 331         table_info->GenericTable=GenericTable;
 332         table_info->gtree=g_tree_new_full(
 333                         (GCompareDataFunc)table_key_info_compare_func,  /* key_compare_func */
 334                         table_info,     /* key_compare_data */
 335                         (GDestroyNotify)table_key_info_destroy_func,    /* key_destroy_func */
 336                         NULL);  /* value_destroy_func */
 337         table_info->array=NULL; /* deleted now */
 338         table_info->enumerate_arrayp=NULL;      /* not yet enumerating */
 339
 340         g_hash_table_insert(GenericTable_to_table_info_hash,GenericTable,table_info);
 341         g_assert(TRUE==validate_GenericTable(GenericTable));
 342 }
 343
 344
 345 /**
 346  * RtlInsertElementGenericTable:
 347  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 348  * %NULL value is forbidden.
 349  * @Element: Pointer to your buffer for the data to copy to the inserted element.
 350  * %NULL value is forbidden.
 351  * @ElementSize: Size of @Element to copy.
 352  * %0 value is forbidden.
 353  * @NewElement: Optionally returns whether new element was created.
 354  * %NULL value is permitted.
 355  *
 356  * If @Element does not exist in @GenericTable yet it will allocate and copy @Element
 357  * to new memory block, the function will return %TRUE in @NewElement and it will return
 358  * the address of the new allocated element.
 359  *
 360  * If @Element already exists in @GenericTable it the function will return %FALSE in @NewElement
 361  * and it will return you the pointer to the old element data already existing in @GenericTable.
 362  *
 363  * Returns: Pointer to a fresh allocated element or a pointer to the already existing
 364  * element in @GenericTable. Function will never return @Element address unless the passed
 365  * @Element address is the already copied instance linked to @GenericTable.
 366  */
 367 PVOID RtlInsertElementGenericTable(IN OUT PRTL_GENERIC_TABLE GenericTable,
 368                 IN PVOID Element,IN ULONG ElementSize,PBOOLEAN NewElement OPTIONAL)
 369 {
 370 struct table_info *table_info;
 371 struct table_key_info *Element_table_key_info,*r_table_key_info;
 372 gpointer Element_table_key_info_key_new;
 373
 374         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),NULL);
 375         g_return_val_if_fail(Element!=NULL,NULL);
 376         g_return_val_if_fail(ElementSize>0,NULL);
 377
 378         table_info=GenericTable_to_table_info(GenericTable);
 379         captive_new(Element_table_key_info);
 380         Element_table_key_info->table_info=table_info;
 381         Element_table_key_info->key=Element;
 382         Element_table_key_info->key_size=ElementSize;
 383         if ((r_table_key_info=g_tree_lookup(table_info->gtree,Element_table_key_info))) {
 384                 /* found existing key */
 385                 g_free(Element_table_key_info);
 386                 if (NewElement)
 387                         *NewElement=FALSE;
 388                 return r_table_key_info->key;
 389                 }
 390
 391         /* Insert new item. */
 392         table_info_array_delete(table_info);
 393         /* Copy the Element data. */
 394         Element_table_key_info_key_new=(*GenericTable->AllocateRoutine)(
 395                         GenericTable,   /* Table */
 396                         Element_table_key_info->key_size);      /* ByteSize */
 397         g_assert(Element_table_key_info_key_new!=NULL);
 398         memcpy(Element_table_key_info_key_new,Element_table_key_info->key,Element_table_key_info->key_size);
 399         Element_table_key_info->key=Element_table_key_info_key_new;
 400
 401         g_tree_insert(table_info->gtree,
 402                         Element_table_key_info, /* key */
 403                         Element_table_key_info);        /* value */
 404         GenericTable->ElementCount++;
 405         if (NewElement)
 406                 *NewElement=TRUE;
 407         g_assert(TRUE==validate_GenericTable(GenericTable));
 408
 409         return Element_table_key_info->key;
 410 }
 411
 412
 413 /**
 414  * RtlInsertElementGenericTableFull:
 415  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 416  * %NULL value is forbidden.
 417  * @Element: Pointer to your buffer for the data to copy to the inserted element.
 418  * %NULL value is forbidden.
 419  * @ElementSize: Size of @Element to copy.
 420  * %0 value is forbidden.
 421  * @NewElement: Optionally returns whether new element was created.
 422  * %NULL value is permitted.
 423  * @NodeOrParent: Value returned by RtlLookupElementGenericTableFull().
 424  * %NULL value is permitted iff @SearchResult==%TableEmptyTree.
 425  * @SearchResult: Value returned by RtlLookupElementGenericTableFull().
 426  *
 427  * See RtlInsertElementGenericTable() for the functionality description.
 428  * You must call RtlLookupElementGenericTableFull() before this function with
 429  * no @GenericTable modifications between these two calls.
 430  *
 431  * Additional two parameters @NodeOrParent and @SearchResult should make the
 432  * operation faster although libcaptive only sanity checks them.
 433  * libcaptive implements this function only as a wrapper around RtlInsertElementGenericTable().
 434  *
 435  * Returns: Pointer to a fresh allocated element or a pointer to the already existing
 436  * element in @GenericTable. Function will never return @Element address unless the passed
 437  * @Element address is the already copied instance linked to @GenericTable.
 438  */
 439 PVOID RtlInsertElementGenericTableFull(PRTL_GENERIC_TABLE GenericTable,
 440                 PVOID Element,ULONG ElementSize,PBOOLEAN NewElement OPTIONAL,PVOID NodeOrParent,TABLE_SEARCH_RESULT SearchResult)
 441 {
 442 struct table_info *table_info;
 443 gint Element_pos_entry,Element_pos,NodeOrParent_pos_entry,NodeOrParent_pos;
 444 ULONG ElementCount_entry;
 445 PVOID r;
 446 BOOLEAN NewElement_tmp;
 447 PVOID NodeOrParent_check;
 448 TABLE_SEARCH_RESULT SearchResult_check;
 449
 450         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),NULL);
 451         g_return_val_if_fail(Element!=NULL,NULL);
 452         g_return_val_if_fail(ElementSize>0,NULL);
 453
 454         RtlLookupElementGenericTableFull(GenericTable,Element,&NodeOrParent_check,&SearchResult_check);
 455         g_assert(NodeOrParent_check==NodeOrParent);
 456         g_assert(SearchResult_check==SearchResult);
 457
 458         if (!NewElement)
 459                 NewElement=&NewElement_tmp;
 460         table_info=GenericTable_to_table_info(GenericTable);
 461         Element_pos_entry=table_info_array_find_key_compare(table_info,Element);
 462         NodeOrParent_pos_entry=(NodeOrParent==NULL ? -1 : table_info_array_find_key_compare(table_info,NodeOrParent));
 463         ElementCount_entry=GenericTable->ElementCount;
 464
 465         r=RtlInsertElementGenericTable(GenericTable,Element,ElementSize,NewElement);
 466         g_assert(r!=NULL);
 467         Element_pos=table_info_array_find_key_compare(table_info,Element);
 468         g_assert(Element_pos==table_info_array_find_key_compare(table_info,r));
 469         NodeOrParent_pos=(NodeOrParent==NULL ? -1 : table_info_array_find_key_compare(table_info,NodeOrParent));
 470
 471         switch (SearchResult) {
 472                 case TableEmptyTree:
 473                         g_assert(ElementCount_entry==0);
 474                         g_assert(GenericTable->ElementCount==1);        /* just inserted */
 475                         g_assert(r!=Element);
 476                         g_assert(*NewElement);
 477                         g_assert(Element_pos_entry==-1);
 478                         g_assert(Element_pos==0);
 479                         g_assert(NodeOrParent==NULL);
 480                         g_assert(NodeOrParent_pos_entry==-1);
 481                         g_assert(NodeOrParent_pos==-1);
 482                         break;
 483                 case TableFoundNode:
 484                         g_assert(ElementCount_entry>=1);
 485                         g_assert(ElementCount_entry==GenericTable->ElementCount);
 486                         g_assert(r==Element);
 487                         g_assert(!*NewElement);
 488                         g_assert(Element_pos_entry>=0);
 489                         g_assert(Element_pos==Element_pos_entry);
 490                         g_assert(NodeOrParent!=NULL);
 491                         g_assert(GenericEqual==(*GenericTable->CompareRoutine)(GenericTable,Element,NodeOrParent));
 492                         g_assert(NodeOrParent_pos_entry!=-1);
 493                         g_assert(NodeOrParent_pos_entry==Element_pos_entry);
 494                         g_assert(NodeOrParent_pos==NodeOrParent_pos_entry);
 495                         break;
 496                 case TableInsertAsLeft:
 497                         g_assert(ElementCount_entry+1==GenericTable->ElementCount);
 498                         g_assert(r!=Element);
 499                         g_assert(*NewElement);
 500                         g_assert(Element_pos_entry==-1);
 501                         g_assert(Element_pos>=0);
 502                         g_assert(NodeOrParent!=NULL);
 503                         g_assert(GenericLessThan==(*GenericTable->CompareRoutine)(GenericTable,Element,NodeOrParent));
 504                         g_assert(NodeOrParent_pos_entry!=-1);
 505                         g_assert(NodeOrParent_pos==NodeOrParent_pos_entry+1);
 506                         g_assert(Element_pos+1==NodeOrParent_pos);
 507                         break;
 508                 case TableInsertAsRight:
 509                         g_assert(ElementCount_entry+1==GenericTable->ElementCount);
 510                         g_assert(r!=Element);
 511                         g_assert(*NewElement);
 512                         g_assert(Element_pos_entry==-1);
 513                         g_assert(Element_pos>=0);
 514                         g_assert(NodeOrParent!=NULL);
 515                         g_assert(GenericGreaterThan==(*GenericTable->CompareRoutine)(GenericTable,Element,NodeOrParent));
 516                         g_assert(NodeOrParent_pos_entry!=-1);
 517                         g_assert(NodeOrParent_pos==NodeOrParent_pos_entry+0);
 518                         g_assert(Element_pos-1==NodeOrParent_pos);
 519                         break;
 520
 521                 default:
 522                         g_assert_not_reached();
 523                 }
 524         return r;
 525 }
 526
 527 /**
 528  * RtlDeleteElementGenericTable:
 529  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 530  * %NULL value is forbidden.
 531  * @Element: Pointer to your buffer to locate the right element of @GenericTable you want to delete.
 532  * %NULL value is forbidden.
 533  *
 534  * Deletes the specified @Element from @GenericTable. Memory referenced
 535  * by @Element is used only to find the right element of @GenericTable.
 536  *
 537  * Returns: %TRUE iff @Element was found (and therefore successfuly deleted).
 538  */
 539 BOOLEAN RtlDeleteElementGenericTable(PRTL_GENERIC_TABLE GenericTable,PVOID Element)
 540 {
 541 struct table_info *table_info;
 542 struct table_key_info *Element_table_key_info;
 543
 544         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),FALSE);
 545         g_return_val_if_fail(Element!=NULL,FALSE);
 546
 547         table_info=GenericTable_to_table_info(GenericTable);
 548         captive_new_alloca(Element_table_key_info);
 549         Element_table_key_info->table_info=table_info;
 550         Element_table_key_info->key=Element;
 551         Element_table_key_info->key_size=0;     /* 0 means unknown */
 552         if (!g_tree_lookup(table_info->gtree,Element_table_key_info)) {
 553                 /* not found */
 554                 return FALSE;
 555                 }
 556
 557         /* delete the item */
 558         g_assert(GenericTable->ElementCount>=1);
 559         table_info_array_delete(table_info);
 560         g_tree_remove(table_info->gtree,Element_table_key_info);
 561         GenericTable->ElementCount--;
 562         g_assert(TRUE==validate_GenericTable(GenericTable));
 563
 564         return TRUE;
 565 }
 566
 567
 568 /**
 569  * RtlLookupElementGenericTable:
 570  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 571  * %NULL value is forbidden.
 572  * @Element: Pointer to your buffer for the data to locate the right element of @GenericTable.
 573  * %NULL value is forbidden.
 574  *
 575  * This call is just a parameter-reduced wrapper around RtlLookupElementGenericTableFull().
 576  *
 577  * Returns: Data pointer to data of the element found in @GenericTable.
 578  * %NULL value if no such element was found in @GenericTable.
 579  */
 580 PVOID RtlLookupElementGenericTable(PRTL_GENERIC_TABLE GenericTable,PVOID Element)
 581 {
 582 PVOID NodeOrParent_tmp;
 583 TABLE_SEARCH_RESULT SearchResult_tmp;
 584
 585         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),NULL);
 586         g_return_val_if_fail(Element!=NULL,NULL);
 587
 588         return RtlLookupElementGenericTableFull(GenericTable,Element,&NodeOrParent_tmp,&SearchResult_tmp);
 589 }
 590
 591
 592 /**
 593  * RtlLookupElementGenericTableFull:
 594  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 595  * %NULL value is forbidden.
 596  * @Element: Pointer to your buffer for the data to locate the right element of @GenericTable.
 597  * %NULL value is forbidden.
 598  * @NodeOrParentp: Returns %NULL if %TableEmptyTree. Returns function return value if %TableFoundNode.
 599  * Returns the data pointer of the possible (it would be the sure parent after insert) parent node
 600  * if %TableInsertAsLeft or TableInsertAsRight.
 601  * %NULL value is forbidden. FIXME: Is it forbidden by W32?
 602  * @SearchResultp: Returns %TableEmptyTree, %TableFoundNode, %TableInsertAsLeft or %TableInsertAsRight
 603  * according to the behaviour for the following RtlInsertElementGenericTableFull().
 604  * %NULL value is forbidden. FIXME: Is it forbidden by W32?
 605  *
 606  * Attempts to find the specified @Element in @GenericTable.
 607  *
 608  * Returns: Data pointer to data of the element found in @GenericTable.
 609  * %NULL value if no such element was found in @GenericTable.
 610  */
 611 PVOID RtlLookupElementGenericTableFull(PRTL_GENERIC_TABLE GenericTable,
 612                 PVOID Element,OUT PVOID *NodeOrParentp,OUT TABLE_SEARCH_RESULT *SearchResultp)
 613 {
 614 struct table_info *table_info;
 615 struct table_key_info *Element_table_key_info;
 616 const struct table_key_info *parent_table_key_info,*found_table_key_info;
 617 gint leftorright;
 618
 619         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),NULL);
 620         g_return_val_if_fail(Element!=NULL,NULL);
 621         g_return_val_if_fail(NodeOrParentp!=NULL,NULL);
 622         g_return_val_if_fail(SearchResultp!=NULL,NULL);
 623
 624         /* empty table? */
 625         if (RtlIsGenericTableEmpty(GenericTable)) {
 626                 if (NodeOrParentp)
 627                         *NodeOrParentp=NULL;
 628                 if (SearchResultp)
 629                         *SearchResultp=TableEmptyTree;
 630                 return NULL;
 631                 }
 632
 633         /* try to find */
 634         table_info=GenericTable_to_table_info(GenericTable);
 635         captive_new_alloca(Element_table_key_info);
 636         Element_table_key_info->table_info=table_info;
 637         Element_table_key_info->key=Element;
 638         Element_table_key_info->key_size=0;     /* 0 means unknown */
 639         table_info->last_table_key_info_compare_func_a_table_key_info=NULL;
 640         table_info->last_table_key_info_compare_func_b_table_key_info=NULL;
 641         found_table_key_info=g_tree_lookup(table_info->gtree,Element_table_key_info);
 642         g_assert(table_info->last_table_key_info_compare_func_a_table_key_info!=NULL);  /* tree is not empty */
 643         g_assert(table_info->last_table_key_info_compare_func_b_table_key_info!=NULL);  /* tree is not empty */
 644         g_assert(0      /* at least one table_key_info_compare_func() must be always the looked up 'Element_table_key_info' */
 645                         || table_info->last_table_key_info_compare_func_a_table_key_info==Element_table_key_info
 646                         || table_info->last_table_key_info_compare_func_b_table_key_info==Element_table_key_info);
 647         g_assert(0      /* at most  one table_key_info_compare_func() must be always the looked up 'Element_table_key_info' */
 648                         || table_info->last_table_key_info_compare_func_a_table_key_info!=Element_table_key_info
 649                         || table_info->last_table_key_info_compare_func_b_table_key_info!=Element_table_key_info);
 650
 651         /* found? */
 652         if (found_table_key_info) {
 653                 if (NodeOrParentp)
 654                         *NodeOrParentp=found_table_key_info->key;
 655                 if (SearchResultp)
 656                         *SearchResultp=TableFoundNode;
 657                 return found_table_key_info->key;
 658                 }
 659
 660         /* not found: TableInsertAsLeft or TableInsertAsRight? */
 661         parent_table_key_info=(table_info->last_table_key_info_compare_func_a_table_key_info==Element_table_key_info
 662                         ? table_info->last_table_key_info_compare_func_b_table_key_info
 663                         : table_info->last_table_key_info_compare_func_a_table_key_info);
 664         if (NodeOrParentp)
 665                 *NodeOrParentp=parent_table_key_info->key;
 666         leftorright=table_key_info_compare_func(parent_table_key_info,Element_table_key_info,table_info);
 667         g_assert(leftorright!=0);       /* it would be already 'TableFoundNode' in such case */
 668         if (SearchResultp)
 669                 *SearchResultp=(leftorright<0 ? TableInsertAsLeft : TableInsertAsRight);
 670         return NULL;
 671 }
 672
 673
 674 /**
 675  * RtlEnumerateGenericTable:
 676  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 677  * %NULL value is forbidden.
 678  * Passing empty table is permitted (returns %NULL value immediately).
 679  * @Restart: %TRUE to start the enumeration from the start.
 680  * %FALSE value is forbidden if enumeration was not yet started or @GenericTable
 681  * was modified in the meanwhile.
 682  *
 683  * Returns element data pointer for each item containe in @GenericTable in the sorted order.
 684  *
 685  * You may proceed at most one pending enumeration for one @GenericTable.
 686  * Use RtlEnumerateGenericTableWithoutSplaying() if you want multiple enumerations for @GenericTable at once.
 687  *
 688  * FIXME: Does W32 handle @GenericTable modifications during pending RtlEnumerateGenericTable()?
 689  *
 690  * Returns: Next (or first if @Restart) element of @GenericTable.
 691  * %NULL value if no more entries are found. It is permitted to call this function
 692  * multiple times with @Restart==%FALSE even if all the entries were already enumerated
 693  * as long as @GenericTable is not modified (returns %NULL for each such call).
 694  */
 695 PVOID RtlEnumerateGenericTable(PRTL_GENERIC_TABLE GenericTable,BOOLEAN Restart)
 696 {
 697 PVOID *r;
 698 struct table_info *table_info;
 699
 700         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),NULL);
 701         table_info=GenericTable_to_table_info(GenericTable);
 702         /* If !Restart we must already started enumeration
 703          * or we must not modify GenericTable in the meanwhile.
 704          */
 705         g_return_val_if_fail(Restart || table_info->enumerate_arrayp,NULL);
 706
 707         if (Restart) {
 708                 table_info_array_create(table_info);
 709                 table_info->enumerate_arrayp=table_info->array;
 710                 }
 711         if (!table_info->enumerate_arrayp)      /* end reached */
 712                 return NULL;
 713         g_assert(table_info->enumerate_arrayp< table_info->array+GenericTable->ElementCount);   /* OK even if empty table */
 714         r=(*table_info->enumerate_arrayp)->key;
 715         table_info->enumerate_arrayp++;
 716         g_assert(table_info->enumerate_arrayp<=table_info->array+GenericTable->ElementCount);
 717         /* End of enumeration? */
 718         if (table_info->enumerate_arrayp==table_info->array+GenericTable->ElementCount)
 719                 table_info->enumerate_arrayp=NULL;
 720
 721         return r;
 722 }
 723
 724
 725 /**
 726  * RtlEnumerateGenericTableWithoutSplaying:
 727  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 728  * %NULL value is forbidden.
 729  * Passing empty table is permitted (returns %NULL value immediately).
 730  * @RestartKey: Pointer to undeterminable storage #PVOID to keep track of the enumeration progess.
 731  * Initialize the pointed value to %NULL to start the enumeration from the start.
 732  * Non %NULL pointer value is forbidden if enumeration of this @RestartKey was not yet started or @GenericTable
 733  * was modified in the meanwhile.
 734  * %NULL pointer is forbidden.
 735  *
 736  * Returns element data pointer for each item containe in @GenericTable in the sorted order.
 737  *
 738  * You may proceed multiple enumerations for one @GenericTable by using different @RestartKey
 739  * pointer to track each enumeration state. You may find RtlEnumerateGenericTable()
 740  * easier if just one enumeration at once is needed.
 741  *
 742  * FIXME: Does W32 handle @GenericTable modifications during pending RtlEnumerateGenericTableWithoutSplaying()?
 743  *
 744  * FIXME: Detect possible modifications of @GenericTable reliably. Modification sequence number
 745  * must be introduced for such feature.
 746  *
 747  * Returns: Next (or first if *@RestartKey==%NULL on entry) element of @GenericTable.
 748  * %NULL value if no more entries are found. It is permitted to call this function
 749  * multiple times without nullifying of *@RestartKey even if all the entries were already enumerated
 750  * as long as @GenericTable is not modified (returns %NULL for each such call).
 751  * Function may modify the value pointed at by @RestartKey.
 752  */
 753 PVOID RtlEnumerateGenericTableWithoutSplaying(PRTL_GENERIC_TABLE GenericTable,PVOID *RestartKey)
 754 {
 755 struct table_info *table_info;
 756 gint RestartKey_pos;
 757
 758         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),NULL);
 759         g_return_val_if_fail(RestartKey!=NULL,NULL);
 760
 761         table_info=GenericTable_to_table_info(GenericTable);
 762
 763         /* Empty? */
 764         if (!GenericTable->ElementCount) {
 765                 /* either unitialized '*RestartKey' by caller or a modification in the meantime */
 766                 g_assert(!*RestartKey);
 767                 return NULL;
 768                 }
 769
 770         /* Restart? */
 771         if (!*RestartKey) {
 772                 table_info_array_create(table_info);
 773                 *RestartKey=table_info->array[0];
 774                 return *RestartKey;
 775                 }
 776
 777         /* Modifications in the meanwhile? FIXME: We may miss some. */
 778         g_assert(!GenericTable->ElementCount || table_info->array!=NULL);
 779
 780         RestartKey_pos=table_info_array_find_key_pointer(table_info,*RestartKey);
 781         /* May fail on some modification in the meantime. */
 782         g_assert(RestartKey_pos>=0);
 783
 784         RestartKey_pos++;
 785         /* End of enumeration? */
 786         if ((ULONG)RestartKey_pos==GenericTable->ElementCount) {
 787                 /* Do not modify '*RestartKey' to keep returning NULL forever */
 788                 return NULL;
 789                 }
 790
 791         g_assert((ULONG)RestartKey_pos<GenericTable->ElementCount);
 792         *RestartKey=table_info->array[RestartKey_pos];
 793         return *RestartKey;
 794 }
 795
 796
 797 /**
 798  * RtlGetElementGenericTable:
 799  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 800  * %NULL value is forbidden.
 801  * @I: %0 based index of the requested element.
 802  * Value >=RtlNumberGenericTableElements(@GenericTable) is permitted by W32 documentation.
 803  * Value >=RtlNumberGenericTableElements(@GenericTable) is currently forbidden by libcaptive
 804  * for debugging purposes.
 805  *
 806  * Returns the @I -th element of sorted elements of @GenericTable.
 807  *
 808  * Returns: Requested element or %NULL if @I>=RtlNumberGenericTableElements(@GenericTable).
 809  * Currently libcaptive can never return %NULL.
 810  */
 811 PVOID RtlGetElementGenericTable(PRTL_GENERIC_TABLE GenericTable,ULONG I)
 812 {
 813 struct table_info *table_info;
 814
 815         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),NULL);
 816
 817         /* Catch such case for debugging purposes as it is permitted by W32 docs. */
 818         g_assert(I<GenericTable->ElementCount);
 819         if (I>=GenericTable->ElementCount)
 820                 return NULL;
 821
 822         table_info=GenericTable_to_table_info(GenericTable);
 823         table_info_array_create(table_info);
 824         return table_info->array[I];
 825 }
 826
 827
 828 /**
 829  * RtlNumberGenericTableElements:
 830  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 831  * %NULL value is forbidden.
 832  *
 833  * Count the elements of @GenericTable;
 834  *
 835  * Returns: Number of elements stored in @GenericTable.
 836  */
 837 ULONG RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE GenericTable)
 838 {
 839         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),0);
 840
 841         return GenericTable->ElementCount;
 842 }
 843
 844
 845 /**
 846  * RtlIsGenericTableEmpty:
 847  * @GenericTable: Existing GenericTable initialized by RtlInitializeGenericTable().
 848  * %NULL value is forbidden.
 849  *
 850  * Check if the @GenericTable is empty.
 851  *
 852  * Returns: %TRUE iff 0==RtlNumberGenericTableElements(@GenericTable).
 853  */
 854 BOOLEAN RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE GenericTable)
 855 {
 856         g_return_val_if_fail(TRUE==validate_GenericTable(GenericTable),TRUE);
 857
 858         return !GenericTable->ElementCount;
 859 }
 860
 861
 862 #if 0   /* AVL structure not yet implemented */
 863 VOID RtlInitializeGenericTableAvl(PRTL_AVL_TABLE AvlTable,PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
 864                 PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,PRTL_AVL_FREE_ROUTINE FreeRoutine,PVOID UserParameter);
 865 PVOID RtlInsertElementGenericTableAvl(PRTL_AVL_TABLE AvlTable,PVOID Element,ULONG ElementSize,PBOOLEAN NewElement OPTIONAL);
 866 PVOID RtlInsertElementGenericTableFullAvl(PRTL_AVL_TABLE AvlTable,
 867                 PVOID Element,ULONG ElementSize,PBOOLEAN NewElement OPTIONAL,PVOID NodeOrParent,TABLE_SEARCH_RESULT SearchResult);
 868 BOOLEAN RtlDeleteElementGenericTableAvl(PRTL_AVL_TABLE AvlTable,PVOID Element);
 869 PVOID RtlLookupElementGenericTableAvl(PRTL_AVL_TABLE AvlTable,PVOID Element);
 870 PVOID RtlLookupElementGenericTableFullAvl(PRTL_AVL_TABLE AvlTable,
 871                 PVOID Element,OUT PVOID *NodeOrParent,OUT TABLE_SEARCH_RESULT *SearchResult);
 872 PVOID RtlEnumerateGenericTableAvl(PRTL_AVL_TABLE AvlTable,BOOLEAN Restart);
 873 PVOID RtlEnumerateGenericTableWithoutSplayingAvl(PRTL_AVL_TABLE AvlTable,PVOID *RestartKey);
 874 PVOID RtlGetElementGenericTableAvl(PRTL_AVL_TABLE AvlTable,ULONG I);
 875 ULONG RtlNumberGenericTableElementsAvl(PRTL_AVL_TABLE AvlTable);
 876 BOOLEAN RtlIsGenericTableEmptyAvl(PRTL_AVL_TABLE AvlTable);
 877 #endif /* 0 */