index.html
Main Page
|
modules.html
Modules
|
namespaces.html
Namespace List
|
hierarchy.html
Class Hierarchy
|
annotated.html
Data Structures
|
dirs.html
Directories
|
files.html
File List
|
namespacemembers.html
Namespace Members
|
functions.html
Data Fields
|
pages.html
Related Pages
dir_000004.html
dbus
dbus-hash.c
00001
/* -*- mode: C; c-file-style: "gnu" -*- */
00002
/* dbus-hash.c Generic hash table utility (internal to D-BUS implementation)
00003
*
00004
* Copyright (C) 2002  Red Hat, Inc.
00005
* Copyright (c) 1991-1993 The Regents of the University of California.
00006
* Copyright (c) 1994 Sun Microsystems, Inc.
00007
*
00008
* Hash table implementation based on generic/tclHash.c from the Tcl
00009
* source code. The original Tcl license applies to portions of the
00010
* code from tclHash.c; the Tcl license follows this standad D-BUS
00011
* license information.
00012
*
00013
* Licensed under the Academic Free License version 2.1
00014
*
00015
* This program is free software; you can redistribute it and/or modify
00016
* it under the terms of the GNU General Public License as published by
00017
* the Free Software Foundation; either version 2 of the License, or
00018
* (at your option) any later version.
00019
*
00020
* This program is distributed in the hope that it will be useful,
00021
* but WITHOUT ANY WARRANTY; without even the implied warranty of
00022
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00023
* GNU General Public License for more details.
00024
*
00025
* You should have received a copy of the GNU General Public License
00026
* along with this program; if not, write to the Free Software
00027
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00028
*
00029
*/
00030
/*
00031
* The following copyright applies to code from the Tcl distribution.
00032
*
00033
* Copyright (c) 1991-1993 The Regents of the University of California.
00034
* Copyright (c) 1994 Sun Microsystems, Inc.
00035
*
00036
* This software is copyrighted by the Regents of the University of
00037
* California, Sun Microsystems, Inc., Scriptics Corporation, and
00038
* other parties.  The following terms apply to all files associated
00039
* with the software unless explicitly disclaimed in individual files.
00040
*
00041
* The authors hereby grant permission to use, copy, modify,
00042
* distribute, and license this software and its documentation for any
00043
* purpose, provided that existing copyright notices are retained in
00044
* all copies and that this notice is included verbatim in any
00045
* distributions. No written agreement, license, or royalty fee is
00046
* required for any of the authorized uses.  Modifications to this
00047
* software may be copyrighted by their authors and need not follow
00048
* the licensing terms described here, provided that the new terms are
00049
* clearly indicated on the first page of each file where they apply.
00050
*
00051
* IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
00052
* PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
00053
* DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
00054
* OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
00055
* OF THE POSSIBILITY OF SUCH DAMAGE.
00056
*
00057
* THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
00058
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
00059
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
00060
* NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
00061
* AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
00062
* MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
00063
*
00064
* GOVERNMENT USE: If you are acquiring this software on behalf of the
00065
* U.S. government, the Government shall have only "Restricted Rights"
00066
* in the software and related documentation as defined in the Federal
00067
* Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
00068
* are acquiring the software on behalf of the Department of Defense,
00069
* the software shall be classified as "Commercial Computer Software"
00070
* and the Government shall have only "Restricted Rights" as defined
00071
* in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
00072
* foregoing, the authors grant the U.S. Government and others acting
00073
* in its behalf permission to use and distribute the software in
00074
* accordance with the terms specified in this license.
00075
*/
00076
00077
#include "dbus-hash.h"
00078
#include "dbus-internals.h"
00079
#include "dbus-mempool.h"
00080
group__DBusHashTableInternals.html#ga10
00103
#define REBUILD_MULTIPLIER  3
00104
group__DBusHashTableInternals.html#ga11
00121
#define RANDOM_INDEX(table, i) \
00122
(((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
00123
group__DBusHashTableInternals.html#ga12
00129
#define DBUS_SMALL_HASH_TABLE 4
00130
group__DBusHashTableInternals.html#ga0
00134
typedef
struct
structDBusHashEntry.html
DBusHashEntry
DBusHashEntry;
00135
structDBusHashEntry.html
00142
struct
DBusHashEntry
00143 {
structDBusHashEntry.html#o0
00144
DBusHashEntry *
structDBusHashEntry.html#o0
next
;
structDBusHashEntry.html#o1
00148
void
*
structDBusHashEntry.html#o1
key
;
structDBusHashEntry.html#o2
00149
void
*
structDBusHashEntry.html#o2
value
;
00150 };
00151
group__DBusHashTableInternals.html#ga1
00155
typedef
DBusHashEntry* (* DBusFindEntryFunction) (
structDBusHashTable.html
DBusHashTable
*table,
00156
void
*key,
00157
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00158                                                   DBusHashEntry      ***bucket,
00159                                                   DBusPreallocatedHash *preallocated);
00160
structDBusHashTable.html
00167
struct
structDBusHashTable.html
DBusHashTable
{
structDBusHashTable.html#o0
00168
int
structDBusHashTable.html#o0
refcount
;
structDBusHashTable.html#o1
00170
DBusHashEntry **
structDBusHashTable.html#o1
buckets
;
00174   DBusHashEntry *
structDBusHashTable.html#o2
static_buckets
[
group__DBusHashTableInternals.html#ga12
DBUS_SMALL_HASH_TABLE
];
structDBusHashTable.html#o3
00178
int
structDBusHashTable.html#o3
n_buckets
;
structDBusHashTable.html#o4
00181
int
structDBusHashTable.html#o4
n_entries
;
structDBusHashTable.html#o5
00184
int
structDBusHashTable.html#o5
hi_rebuild_size
;
structDBusHashTable.html#o6
00187
int
structDBusHashTable.html#o6
lo_rebuild_size
;
structDBusHashTable.html#o7
00190
int
structDBusHashTable.html#o7
down_shift
;
structDBusHashTable.html#o8
00194
int
structDBusHashTable.html#o8
mask
;
structDBusHashTable.html#o9
00197
group__DBusHashTable.html#ga31
DBusHashType
structDBusHashTable.html#o9
key_type
;
structDBusHashTable.html#o10
00200
group__DBusHashTableInternals.html#ga1
DBusFindEntryFunction
structDBusHashTable.html#o10
find_function
;
structDBusHashTable.html#o11
00202
group__DBusMemory.html#ga8
DBusFreeFunction
structDBusHashTable.html#o11
free_key_function
;
structDBusHashTable.html#o12
00203
group__DBusMemory.html#ga8
DBusFreeFunction
structDBusHashTable.html#o12
free_value_function
;
structDBusHashTable.html#o13
00205
structDBusMemPool.html
DBusMemPool
*
structDBusHashTable.html#o13
entry_pool
;
00206 };
00207
structDBusRealHashIter.html
00211
typedef
struct
00212
{
structDBusRealHashIter.html#o0
00213
structDBusHashTable.html
DBusHashTable
*table;
structDBusRealHashIter.html#o1
00214
DBusHashEntry **bucket;
structDBusRealHashIter.html#o2
00218
DBusHashEntry *entry;
structDBusRealHashIter.html#o3
00219
DBusHashEntry *next_entry;
structDBusRealHashIter.html#o4
00220
int
next_bucket;
structDBusRealHashIter.html#o5
00221
int
n_entries_on_init;
00222 }
structDBusRealHashIter.html
DBusRealHashIter
;
00223
00224
static
DBusHashEntry* find_direct_function      (
structDBusHashTable.html
DBusHashTable
*table,
00225
void
*key,
00226
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00227                                                  DBusHashEntry        ***bucket,
00228                                                  DBusPreallocatedHash   *preallocated);
00229
static
DBusHashEntry* find_string_function      (
structDBusHashTable.html
DBusHashTable
*table,
00230
void
*key,
00231
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00232                                                  DBusHashEntry        ***bucket,
00233                                                  DBusPreallocatedHash   *preallocated);
00234
#ifdef DBUS_BUILD_TESTS
00235
static
DBusHashEntry* find_two_strings_function (
structDBusHashTable.html
DBusHashTable
*table,
00236
void
*key,
00237
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00238                                                  DBusHashEntry        ***bucket,
00239                                                  DBusPreallocatedHash   *preallocated);
00240
#endif
00241
static
unsigned
int
string_hash               (
const
char
*str);
00242
#ifdef DBUS_BUILD_TESTS
00243
static
unsigned
int
two_strings_hash          (
const
char
*str);
00244
#endif
00245
static
void
rebuild_table             (
structDBusHashTable.html
DBusHashTable
*table);
00246
static
DBusHashEntry* alloc_entry               (
structDBusHashTable.html
DBusHashTable
*table);
00247
static
void
remove_entry              (
structDBusHashTable.html
DBusHashTable
*table,
00248                                                  DBusHashEntry         **bucket,
00249                                                  DBusHashEntry          *entry);
00250
static
void
free_entry                (
structDBusHashTable.html
DBusHashTable
*table,
00251                                                  DBusHashEntry          *entry);
00252
static
void
free_entry_data           (
structDBusHashTable.html
DBusHashTable
*table,
00253                                                  DBusHashEntry          *entry);
00254
00255
00291
structDBusHashTable.html
DBusHashTable
*
group__DBusHashTable.html#ga1
00292
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(
group__DBusHashTable.html#ga31
DBusHashType
type,
00293
group__DBusMemory.html#ga8
DBusFreeFunction
key_free_function,
00294
group__DBusMemory.html#ga8
DBusFreeFunction
value_free_function)
00295 {
00296
structDBusHashTable.html
DBusHashTable
*table;
00297
structDBusMemPool.html
DBusMemPool
*entry_pool;
00298
00299   table =
group__DBusMemory.html#ga7
dbus_new0
(
structDBusHashTable.html
DBusHashTable
, 1);
00300
if
(table ==
group__DBusMacros.html#ga4
NULL
)
00301
return
group__DBusMacros.html#ga4
NULL
;
00302
00303   entry_pool =
group__DBusMemPool.html#ga0
_dbus_mem_pool_new
(
sizeof
(DBusHashEntry),
group__DBusMacros.html#ga2
TRUE
);
00304
if
(entry_pool ==
group__DBusMacros.html#ga4
NULL
)
00305     {
00306
group__DBusMemory.html#ga3
dbus_free
(table);
00307
return
group__DBusMacros.html#ga4
NULL
;
00308     }
00309
00310   table->
structDBusHashTable.html#o0
refcount
= 1;
00311   table->
structDBusHashTable.html#o13
entry_pool
= entry_pool;
00312
00313
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTableInternals.html#ga12
DBUS_SMALL_HASH_TABLE
==
group__DBusInternalsUtils.html#ga132
_DBUS_N_ELEMENTS
(table->
structDBusHashTable.html#o2
static_buckets
));
00314
00315   table->
structDBusHashTable.html#o1
buckets
= table->
structDBusHashTable.html#o2
static_buckets
;
00316   table->
structDBusHashTable.html#o3
n_buckets
=
group__DBusHashTableInternals.html#ga12
DBUS_SMALL_HASH_TABLE
;
00317   table->
structDBusHashTable.html#o4
n_entries
= 0;
00318   table->
structDBusHashTable.html#o5
hi_rebuild_size
=
group__DBusHashTableInternals.html#ga12
DBUS_SMALL_HASH_TABLE
*
group__DBusHashTableInternals.html#ga10
REBUILD_MULTIPLIER
;
00319   table->
structDBusHashTable.html#o6
lo_rebuild_size
= 0;
00320   table->
structDBusHashTable.html#o7
down_shift
= 28;
00321   table->
structDBusHashTable.html#o8
mask
= 3;
00322   table->
structDBusHashTable.html#o9
key_type
= type;
00323
00324
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o8
mask
< table->
structDBusHashTable.html#o3
n_buckets
);
00325
00326
switch
(table->
structDBusHashTable.html#o9
key_type
)
00327     {
00328
case
DBUS_HASH_INT:
00329
case
DBUS_HASH_POINTER:
00330
case
DBUS_HASH_ULONG:
00331       table->
structDBusHashTable.html#o10
find_function
= find_direct_function;
00332
break
;
00333
case
DBUS_HASH_STRING:
00334       table->
structDBusHashTable.html#o10
find_function
= find_string_function;
00335
break
;
00336
case
DBUS_HASH_TWO_STRINGS:
00337
#ifdef DBUS_BUILD_TESTS
00338
table->
structDBusHashTable.html#o10
find_function
= find_two_strings_function;
00339
#endif
00340
break
;
00341
default
:
00342
group__DBusInternalsUtils.html#ga131
_dbus_assert_not_reached
(
"Unknown hash table type"
);
00343
break
;
00344     }
00345
00346   table->
structDBusHashTable.html#o11
free_key_function
= key_free_function;
00347   table->
structDBusHashTable.html#o12
free_value_function
= value_free_function;
00348
00349
return
table;
00350 }
00351
00352
00359
structDBusHashTable.html
DBusHashTable
*
group__DBusHashTable.html#ga2
00360
group__DBusHashTable.html#ga2
_dbus_hash_table_ref
(
structDBusHashTable.html
DBusHashTable
*table)
00361 {
00362   table->
structDBusHashTable.html#o0
refcount
+= 1;
00363
00364
return
table;
00365 }
00366
00373
void
group__DBusHashTable.html#ga3
00374
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(
structDBusHashTable.html
DBusHashTable
*table)
00375 {
00376   table->
structDBusHashTable.html#o0
refcount
-= 1;
00377
00378
if
(table->
structDBusHashTable.html#o0
refcount
== 0)
00379     {
00380
#if 0
00381
DBusHashEntry *entry;
00382       DBusHashEntry *next;
00383
int
i;
00384
00385
/* Free the entries in the table. */
00386
for
(i = 0; i < table->n_buckets; i++)
00387         {
00388           entry = table->
structDBusHashTable.html#o1
buckets
[i];
00389
while
(entry !=
group__DBusMacros.html#ga4
NULL
)
00390             {
00391               next = entry->
structDBusHashEntry.html#o0
next
;
00392
00393               free_entry (table, entry);
00394
00395               entry = next;
00396             }
00397         }
00398
#else
00399
DBusHashEntry *entry;
00400
int
i;
00401
00402
/* Free the entries in the table. */
00403
for
(i = 0; i < table->n_buckets; i++)
00404         {
00405           entry = table->
structDBusHashTable.html#o1
buckets
[i];
00406
while
(entry !=
group__DBusMacros.html#ga4
NULL
)
00407             {
00408               free_entry_data (table, entry);
00409
00410               entry = entry->
structDBusHashEntry.html#o0
next
;
00411             }
00412         }
00413
/* We can do this very quickly with memory pools ;-) */
00414
group__DBusMemPool.html#ga1
_dbus_mem_pool_free
(table->
structDBusHashTable.html#o13
entry_pool
);
00415
#endif
00416
00417
/* Free the bucket array, if it was dynamically allocated. */
00418
if
(table->
structDBusHashTable.html#o1
buckets
!= table->
structDBusHashTable.html#o2
static_buckets
)
00419
group__DBusMemory.html#ga3
dbus_free
(table->
structDBusHashTable.html#o1
buckets
);
00420
00421
group__DBusMemory.html#ga3
dbus_free
(table);
00422     }
00423 }
00424
00425
static
DBusHashEntry*
00426 alloc_entry (
structDBusHashTable.html
DBusHashTable
*table)
00427 {
00428   DBusHashEntry *entry;
00429
00430   entry =
group__DBusMemPool.html#ga2
_dbus_mem_pool_alloc
(table->
structDBusHashTable.html#o13
entry_pool
);
00431
00432
return
entry;
00433 }
00434
00435
static
void
00436 free_entry_data (
structDBusHashTable.html
DBusHashTable
*table,
00437                  DBusHashEntry  *entry)
00438 {
00439
if
(table->
structDBusHashTable.html#o11
free_key_function
)
00440     (* table->
structDBusHashTable.html#o11
free_key_function
) (entry->
structDBusHashEntry.html#o1
key
);
00441
if
(table->
structDBusHashTable.html#o12
free_value_function
)
00442     (* table->
structDBusHashTable.html#o12
free_value_function
) (entry->
structDBusHashEntry.html#o2
value
);
00443 }
00444
00445
static
void
00446 free_entry (
structDBusHashTable.html
DBusHashTable
*table,
00447             DBusHashEntry  *entry)
00448 {
00449   free_entry_data (table, entry);
00450
group__DBusMemPool.html#ga3
_dbus_mem_pool_dealloc
(table->
structDBusHashTable.html#o13
entry_pool
, entry);
00451 }
00452
00453
static
void
00454 remove_entry (
structDBusHashTable.html
DBusHashTable
*table,
00455               DBusHashEntry **bucket,
00456               DBusHashEntry  *entry)
00457 {
00458
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table !=
group__DBusMacros.html#ga4
NULL
);
00459
group__DBusInternalsUtils.html#ga130
_dbus_assert
(bucket !=
group__DBusMacros.html#ga4
NULL
);
00460
group__DBusInternalsUtils.html#ga130
_dbus_assert
(*bucket !=
group__DBusMacros.html#ga4
NULL
);
00461
group__DBusInternalsUtils.html#ga130
_dbus_assert
(entry !=
group__DBusMacros.html#ga4
NULL
);
00462
00463
if
(*bucket == entry)
00464     *bucket = entry->
structDBusHashEntry.html#o0
next
;
00465
else
00466     {
00467       DBusHashEntry *prev;
00468       prev = *bucket;
00469
00470
while
(prev->
structDBusHashEntry.html#o0
next
!= entry)
00471         prev = prev->
structDBusHashEntry.html#o0
next
;
00472
00473
group__DBusInternalsUtils.html#ga130
_dbus_assert
(prev !=
group__DBusMacros.html#ga4
NULL
);
00474
00475       prev->
structDBusHashEntry.html#o0
next
= entry->
structDBusHashEntry.html#o0
next
;
00476     }
00477
00478   table->
structDBusHashTable.html#o4
n_entries
-= 1;
00479   free_entry (table, entry);
00480 }
00481
00513
void
group__DBusHashTable.html#ga4
00514
group__DBusHashTable.html#ga4
_dbus_hash_iter_init
(
structDBusHashTable.html
DBusHashTable
*table,
00515
structDBusHashIter.html
DBusHashIter
*iter)
00516 {
00517
structDBusRealHashIter.html
DBusRealHashIter
*real;
00518
00519
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
sizeof
(
structDBusHashIter.html
DBusHashIter
) ==
sizeof
(
structDBusRealHashIter.html
DBusRealHashIter
));
00520
00521   real = (DBusRealHashIter*) iter;
00522
00523   real->
structDBusRealHashIter.html#o0
table
= table;
00524   real->
structDBusRealHashIter.html#o1
bucket
=
group__DBusMacros.html#ga4
NULL
;
00525   real->
structDBusRealHashIter.html#o2
entry
=
group__DBusMacros.html#ga4
NULL
;
00526   real->
structDBusRealHashIter.html#o3
next_entry
=
group__DBusMacros.html#ga4
NULL
;
00527   real->
structDBusRealHashIter.html#o4
next_bucket
= 0;
00528   real->
structDBusRealHashIter.html#o5
n_entries_on_init
= table->
structDBusHashTable.html#o4
n_entries
;
00529 }
00530
00539
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga5
00540
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(
structDBusHashIter.html
DBusHashIter
*iter)
00541 {
00542
structDBusRealHashIter.html
DBusRealHashIter
*real;
00543
00544
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
sizeof
(
structDBusHashIter.html
DBusHashIter
) ==
sizeof
(
structDBusRealHashIter.html
DBusRealHashIter
));
00545
00546   real = (DBusRealHashIter*) iter;
00547
00548
/* if this assertion failed someone probably added hash entries
00549
* during iteration, which is bad.
00550
*/
00551
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o5
n_entries_on_init
>= real->
structDBusRealHashIter.html#o0
table
->
structDBusHashTable.html#o4
n_entries
);
00552
00553
/* Remember that real->entry may have been deleted */
00554
00555
while
(real->
structDBusRealHashIter.html#o3
next_entry
==
group__DBusMacros.html#ga4
NULL
)
00556     {
00557
if
(real->
structDBusRealHashIter.html#o4
next_bucket
>= real->
structDBusRealHashIter.html#o0
table
->
structDBusHashTable.html#o3
n_buckets
)
00558         {
00559
/* invalidate iter and return false */
00560           real->
structDBusRealHashIter.html#o2
entry
=
group__DBusMacros.html#ga4
NULL
;
00561           real->
structDBusRealHashIter.html#o0
table
=
group__DBusMacros.html#ga4
NULL
;
00562           real->
structDBusRealHashIter.html#o1
bucket
=
group__DBusMacros.html#ga4
NULL
;
00563
return
group__DBusMacros.html#ga3
FALSE
;
00564         }
00565
00566       real->
structDBusRealHashIter.html#o1
bucket
= &(real->
structDBusRealHashIter.html#o0
table
->
structDBusHashTable.html#o1
buckets
[real->
structDBusRealHashIter.html#o4
next_bucket
]);
00567       real->
structDBusRealHashIter.html#o3
next_entry
= *(real->
structDBusRealHashIter.html#o1
bucket
);
00568       real->
structDBusRealHashIter.html#o4
next_bucket
+= 1;
00569     }
00570
00571
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o3
next_entry
!=
group__DBusMacros.html#ga4
NULL
);
00572
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o1
bucket
!=
group__DBusMacros.html#ga4
NULL
);
00573
00574   real->
structDBusRealHashIter.html#o2
entry
= real->
structDBusRealHashIter.html#o3
next_entry
;
00575   real->
structDBusRealHashIter.html#o3
next_entry
= real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o0
next
;
00576
00577
return
group__DBusMacros.html#ga2
TRUE
;
00578 }
00579
00588
void
group__DBusHashTable.html#ga6
00589
group__DBusHashTable.html#ga6
_dbus_hash_iter_remove_entry
(
structDBusHashIter.html
DBusHashIter
*iter)
00590 {
00591
structDBusRealHashIter.html
DBusRealHashIter
*real;
00592
00593   real = (
structDBusRealHashIter.html
DBusRealHashIter
*) iter;
00594
00595
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o0
table
!=
group__DBusMacros.html#ga4
NULL
);
00596
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o2
entry
!=
group__DBusMacros.html#ga4
NULL
);
00597
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o1
bucket
!=
group__DBusMacros.html#ga4
NULL
);
00598
00599   remove_entry (real->
structDBusRealHashIter.html#o0
table
, real->
structDBusRealHashIter.html#o1
bucket
, real->
structDBusRealHashIter.html#o2
entry
);
00600
00601   real->
structDBusRealHashIter.html#o2
entry
=
group__DBusMacros.html#ga4
NULL
;
/* make it crash if you try to use this entry */
00602 }
00603
00609
void
*
group__DBusHashTable.html#ga7
00610
group__DBusHashTable.html#ga7
_dbus_hash_iter_get_value
(
structDBusHashIter.html
DBusHashIter
*iter)
00611 {
00612
structDBusRealHashIter.html
DBusRealHashIter
*real;
00613
00614   real = (
structDBusRealHashIter.html
DBusRealHashIter
*) iter;
00615
00616
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o0
table
!=
group__DBusMacros.html#ga4
NULL
);
00617
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o2
entry
!=
group__DBusMacros.html#ga4
NULL
);
00618
00619
return
real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o2
value
;
00620 }
00621
00632
void
group__DBusHashTable.html#ga8
00633
group__DBusHashTable.html#ga8
_dbus_hash_iter_set_value
(
structDBusHashIter.html
DBusHashIter
*iter,
00634
void
*value)
00635 {
00636
structDBusRealHashIter.html
DBusRealHashIter
*real;
00637
00638   real = (
structDBusRealHashIter.html
DBusRealHashIter
*) iter;
00639
00640
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o0
table
!=
group__DBusMacros.html#ga4
NULL
);
00641
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o2
entry
!=
group__DBusMacros.html#ga4
NULL
);
00642
00643
if
(real->
structDBusRealHashIter.html#o0
table
->
structDBusHashTable.html#o12
free_value_function
&& value != real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o2
value
)
00644     (* real->
structDBusRealHashIter.html#o0
table
->
structDBusHashTable.html#o12
free_value_function
) (real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o2
value
);
00645
00646   real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o2
value
= value;
00647 }
00648
00655
int
group__DBusHashTable.html#ga9
00656
group__DBusHashTable.html#ga9
_dbus_hash_iter_get_int_key
(
structDBusHashIter.html
DBusHashIter
*iter)
00657 {
00658
structDBusRealHashIter.html
DBusRealHashIter
*real;
00659
00660   real = (
structDBusRealHashIter.html
DBusRealHashIter
*) iter;
00661
00662
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o0
table
!=
group__DBusMacros.html#ga4
NULL
);
00663
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o2
entry
!=
group__DBusMacros.html#ga4
NULL
);
00664
00665
return
group__DBusInternalsUtils.html#ga133
_DBUS_POINTER_TO_INT
(real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o1
key
);
00666 }
00667
00674
unsigned
long
group__DBusHashTable.html#ga10
00675
group__DBusHashTable.html#ga10
_dbus_hash_iter_get_ulong_key
(
structDBusHashIter.html
DBusHashIter
*iter)
00676 {
00677
structDBusRealHashIter.html
DBusRealHashIter
*real;
00678
00679   real = (
structDBusRealHashIter.html
DBusRealHashIter
*) iter;
00680
00681
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o0
table
!=
group__DBusMacros.html#ga4
NULL
);
00682
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o2
entry
!=
group__DBusMacros.html#ga4
NULL
);
00683
00684
return
(
unsigned
long
) real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o1
key
;
00685 }
00686
00692
const
char
*
group__DBusHashTable.html#ga11
00693
group__DBusHashTable.html#ga11
_dbus_hash_iter_get_string_key
(
structDBusHashIter.html
DBusHashIter
*iter)
00694 {
00695
structDBusRealHashIter.html
DBusRealHashIter
*real;
00696
00697   real = (
structDBusRealHashIter.html
DBusRealHashIter
*) iter;
00698
00699
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o0
table
!=
group__DBusMacros.html#ga4
NULL
);
00700
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o2
entry
!=
group__DBusMacros.html#ga4
NULL
);
00701
00702
return
real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o1
key
;
00703 }
00704
00705
#ifdef DBUS_BUILD_TESTS
00706
00711
const
char
*
00712 _dbus_hash_iter_get_two_strings_key (
structDBusHashIter.html
DBusHashIter
*iter)
00713 {
00714
structDBusRealHashIter.html
DBusRealHashIter
*real;
00715
00716   real = (
structDBusRealHashIter.html
DBusRealHashIter
*) iter;
00717
00718
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o0
table
!=
group__DBusMacros.html#ga4
NULL
);
00719
group__DBusInternalsUtils.html#ga130
_dbus_assert
(real->
structDBusRealHashIter.html#o2
entry
!=
group__DBusMacros.html#ga4
NULL
);
00720
00721
return
real->
structDBusRealHashIter.html#o2
entry
->
structDBusHashEntry.html#o1
key
;
00722 }
00723
#endif
/* DBUS_BUILD_TESTS */
00724
00756
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga12
00757
group__DBusHashTable.html#ga12
_dbus_hash_iter_lookup
(
structDBusHashTable.html
DBusHashTable
*table,
00758
void
*key,
00759
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00760
structDBusHashIter.html
DBusHashIter
*iter)
00761 {
00762
structDBusRealHashIter.html
DBusRealHashIter
*real;
00763   DBusHashEntry *entry;
00764   DBusHashEntry **bucket;
00765
00766
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
sizeof
(
structDBusHashIter.html
DBusHashIter
) ==
sizeof
(
structDBusRealHashIter.html
DBusRealHashIter
));
00767
00768   real = (DBusRealHashIter*) iter;
00769
00770   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, key, create_if_not_found, &bucket,
group__DBusMacros.html#ga4
NULL
);
00771
00772
if
(entry ==
group__DBusMacros.html#ga4
NULL
)
00773
return
group__DBusMacros.html#ga3
FALSE
;
00774
00775   real->
structDBusRealHashIter.html#o0
table
= table;
00776   real->
structDBusRealHashIter.html#o1
bucket
= bucket;
00777   real->
structDBusRealHashIter.html#o2
entry
= entry;
00778   real->
structDBusRealHashIter.html#o3
next_entry
= entry->
structDBusHashEntry.html#o0
next
;
00779   real->
structDBusRealHashIter.html#o4
next_bucket
= (bucket - table->
structDBusHashTable.html#o1
buckets
) + 1;
00780   real->
structDBusRealHashIter.html#o5
n_entries_on_init
= table->
structDBusHashTable.html#o4
n_entries
;
00781
00782
group__DBusInternalsUtils.html#ga130
_dbus_assert
(&(table->
structDBusHashTable.html#o1
buckets
[real->
structDBusRealHashIter.html#o4
next_bucket
-1]) == real->
structDBusRealHashIter.html#o1
bucket
);
00783
00784
return
group__DBusMacros.html#ga2
TRUE
;
00785 }
00786
00787
static
void
00788 add_allocated_entry (
structDBusHashTable.html
DBusHashTable
*table,
00789                      DBusHashEntry   *entry,
00790
unsigned
int
idx,
00791
void
*key,
00792                      DBusHashEntry ***bucket)
00793 {
00794   DBusHashEntry **b;
00795
00796   entry->
structDBusHashEntry.html#o1
key
= key;
00797
00798   b = &(table->
structDBusHashTable.html#o1
buckets
[idx]);
00799   entry->
structDBusHashEntry.html#o0
next
= *b;
00800   *b = entry;
00801
00802
if
(bucket)
00803     *bucket = b;
00804
00805   table->
structDBusHashTable.html#o4
n_entries
+= 1;
00806
00807
/* note we ONLY rebuild when ADDING - because you can iterate over a
00808
* table and remove entries safely.
00809
*/
00810
if
(table->
structDBusHashTable.html#o4
n_entries
>= table->
structDBusHashTable.html#o5
hi_rebuild_size
||
00811       table->
structDBusHashTable.html#o4
n_entries
< table->
structDBusHashTable.html#o6
lo_rebuild_size
)
00812     rebuild_table (table);
00813 }
00814
00815
static
DBusHashEntry*
00816 add_entry (
structDBusHashTable.html
DBusHashTable
*table,
00817
unsigned
int
idx,
00818
void
*key,
00819            DBusHashEntry      ***bucket,
00820            DBusPreallocatedHash *preallocated)
00821 {
00822   DBusHashEntry  *entry;
00823
00824
if
(preallocated ==
group__DBusMacros.html#ga4
NULL
)
00825     {
00826       entry = alloc_entry (table);
00827
if
(entry ==
group__DBusMacros.html#ga4
NULL
)
00828         {
00829
if
(bucket)
00830             *bucket =
group__DBusMacros.html#ga4
NULL
;
00831
return
group__DBusMacros.html#ga4
NULL
;
00832         }
00833     }
00834
else
00835     {
00836       entry = (DBusHashEntry*) preallocated;
00837     }
00838
00839   add_allocated_entry (table, entry, idx, key, bucket);
00840
00841
return
entry;
00842 }
00843
00844
/* This is g_str_hash from GLib which was
00845
* extensively discussed/tested/profiled
00846
*/
00847
static
unsigned
int
00848 string_hash (
const
char
*str)
00849 {
00850
const
char
*p = str;
00851
unsigned
int
h = *p;
00852
00853
if
(h)
00854
for
(p += 1; *p !=
'\0'
; p++)
00855       h = (h << 5) - h + *p;
00856
00857
return
h;
00858 }
00859
00860
#ifdef DBUS_BUILD_TESTS
00861
/* This hashes a memory block with two nul-terminated strings
00862
* in it, used in dbus-object-registry.c at the moment.
00863
*/
00864
static
unsigned
int
00865 two_strings_hash (
const
char
*str)
00866 {
00867
const
char
*p = str;
00868
unsigned
int
h = *p;
00869
00870
if
(h)
00871
for
(p += 1; *p !=
'\0'
; p++)
00872       h = (h << 5) - h + *p;
00873
00874
for
(p += 1; *p !=
'\0'
; p++)
00875     h = (h << 5) - h + *p;
00876
00877
return
h;
00878 }
00879
#endif
/* DBUS_BUILD_TESTS */
00880
group__DBusHashTable.html#ga0
00882
typedef
int (*
group__DBusHashTable.html#ga0
KeyCompareFunc
) (
const
void
*key_a,
const
void
*key_b);
00883
00884
static
DBusHashEntry*
00885 find_generic_function (
structDBusHashTable.html
DBusHashTable
*table,
00886
void
*key,
00887
unsigned
int
idx,
00888
group__DBusHashTable.html#ga0
KeyCompareFunc
compare_func,
00889
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00890                        DBusHashEntry      ***bucket,
00891                        DBusPreallocatedHash *preallocated)
00892 {
00893   DBusHashEntry *entry;
00894
00895
if
(bucket)
00896     *bucket =
group__DBusMacros.html#ga4
NULL
;
00897
00898
/* Search all of the entries in this bucket. */
00899   entry = table->
structDBusHashTable.html#o1
buckets
[idx];
00900
while
(entry !=
group__DBusMacros.html#ga4
NULL
)
00901     {
00902
if
((compare_func ==
group__DBusMacros.html#ga4
NULL
&& key == entry->
structDBusHashEntry.html#o1
key
) ||
00903           (compare_func !=
group__DBusMacros.html#ga4
NULL
&& (* compare_func) (key, entry->
structDBusHashEntry.html#o1
key
) == 0))
00904         {
00905
if
(bucket)
00906             *bucket = &(table->
structDBusHashTable.html#o1
buckets
[idx]);
00907
00908
if
(preallocated)
00909
group__DBusHashTable.html#ga26
_dbus_hash_table_free_preallocated_entry
(table, preallocated);
00910
00911
return
entry;
00912         }
00913
00914       entry = entry->
structDBusHashEntry.html#o0
next
;
00915     }
00916
00917
if
(create_if_not_found)
00918     entry = add_entry (table, idx, key, bucket, preallocated);
00919
else
if
(preallocated)
00920
group__DBusHashTable.html#ga26
_dbus_hash_table_free_preallocated_entry
(table, preallocated);
00921
00922
return
entry;
00923 }
00924
00925
static
DBusHashEntry*
00926 find_string_function (
structDBusHashTable.html
DBusHashTable
*table,
00927
void
*key,
00928
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00929                       DBusHashEntry      ***bucket,
00930                       DBusPreallocatedHash *preallocated)
00931 {
00932
unsigned
int
idx;
00933
00934   idx = string_hash (key) & table->
structDBusHashTable.html#o8
mask
;
00935
00936
return
find_generic_function (table, key, idx,
00937                                 (
group__DBusHashTable.html#ga0
KeyCompareFunc
) strcmp, create_if_not_found, bucket,
00938                                 preallocated);
00939 }
00940
00941
#ifdef DBUS_BUILD_TESTS
00942
static
int
00943 two_strings_cmp (
const
char
*a,
00944
const
char
*b)
00945 {
00946   size_t len_a;
00947   size_t len_b;
00948
int
res;
00949
00950   res = strcmp (a, b);
00951
if
(res != 0)
00952
return
res;
00953
00954   len_a = strlen (a);
00955   len_b = strlen (b);
00956
00957
return
strcmp (a + len_a + 1, b + len_b + 1);
00958 }
00959
#endif
00960
00961
#ifdef DBUS_BUILD_TESTS
00962
static
DBusHashEntry*
00963 find_two_strings_function (
structDBusHashTable.html
DBusHashTable
*table,
00964
void
*key,
00965
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00966                            DBusHashEntry      ***bucket,
00967                            DBusPreallocatedHash *preallocated)
00968 {
00969
unsigned
int
idx;
00970
00971   idx = two_strings_hash (key) & table->
structDBusHashTable.html#o8
mask
;
00972
00973
return
find_generic_function (table, key, idx,
00974                                 (
group__DBusHashTable.html#ga0
KeyCompareFunc
) two_strings_cmp, create_if_not_found, bucket,
00975                                 preallocated);
00976 }
00977
#endif
/* DBUS_BUILD_TESTS */
00978
00979
static
DBusHashEntry*
00980 find_direct_function (
structDBusHashTable.html
DBusHashTable
*table,
00981
void
*key,
00982
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
00983                       DBusHashEntry      ***bucket,
00984                       DBusPreallocatedHash *preallocated)
00985 {
00986
unsigned
int
idx;
00987
00988   idx =
group__DBusHashTableInternals.html#ga11
RANDOM_INDEX
(table, key) & table->
structDBusHashTable.html#o8
mask
;
00989
00990
00991
return
find_generic_function (table, key, idx,
00992
group__DBusMacros.html#ga4
NULL
, create_if_not_found, bucket,
00993                                 preallocated);
00994 }
00995
00996
static
void
00997 rebuild_table (
structDBusHashTable.html
DBusHashTable
*table)
00998 {
00999
int
old_size;
01000
int
new_buckets;
01001   DBusHashEntry **old_buckets;
01002   DBusHashEntry **old_chain;
01003   DBusHashEntry *entry;
01004
group__DBusTypes.html#ga2
dbus_bool_t
growing;
01005
01006
/*
01007
* Allocate and initialize the new bucket array, and set up
01008
* hashing constants for new array size.
01009
*/
01010
01011   growing = table->
structDBusHashTable.html#o4
n_entries
>= table->
structDBusHashTable.html#o5
hi_rebuild_size
;
01012
01013   old_size = table->
structDBusHashTable.html#o3
n_buckets
;
01014   old_buckets = table->
structDBusHashTable.html#o1
buckets
;
01015
01016
if
(growing)
01017     {
01018
/* overflow paranoia */
01019
if
(table->
structDBusHashTable.html#o3
n_buckets
<
group__DBusInternalsUtils.html#ga143
_DBUS_INT_MAX
/ 4 &&
01020           table->
structDBusHashTable.html#o7
down_shift
>= 0)
01021         new_buckets = table->
structDBusHashTable.html#o3
n_buckets
* 4;
01022
else
01023
return
;
/* can't grow anymore */
01024     }
01025
else
01026     {
01027       new_buckets = table->
structDBusHashTable.html#o3
n_buckets
/ 4;
01028
if
(new_buckets <
group__DBusHashTableInternals.html#ga12
DBUS_SMALL_HASH_TABLE
)
01029
return
;
/* don't bother shrinking this far */
01030     }
01031
01032   table->
structDBusHashTable.html#o1
buckets
=
group__DBusMemory.html#ga7
dbus_new0
(DBusHashEntry*, new_buckets);
01033
if
(table->
structDBusHashTable.html#o1
buckets
==
group__DBusMacros.html#ga4
NULL
)
01034     {
01035
/* out of memory, yay - just don't reallocate, the table will
01036
* still work, albeit more slowly.
01037
*/
01038       table->
structDBusHashTable.html#o1
buckets
= old_buckets;
01039
return
;
01040     }
01041
01042   table->
structDBusHashTable.html#o3
n_buckets
= new_buckets;
01043
01044
if
(growing)
01045     {
01046       table->
structDBusHashTable.html#o6
lo_rebuild_size
= table->
structDBusHashTable.html#o5
hi_rebuild_size
;
01047       table->
structDBusHashTable.html#o5
hi_rebuild_size
*= 4;
01048
01049       table->
structDBusHashTable.html#o7
down_shift
-= 2;
/* keep 2 more high bits */
01050       table->
structDBusHashTable.html#o8
mask
= (table->
structDBusHashTable.html#o8
mask
<< 2) + 3;
/* keep 2 more high bits */
01051     }
01052
else
01053     {
01054       table->
structDBusHashTable.html#o5
hi_rebuild_size
= table->
structDBusHashTable.html#o6
lo_rebuild_size
;
01055       table->
structDBusHashTable.html#o6
lo_rebuild_size
/= 4;
01056
01057       table->
structDBusHashTable.html#o7
down_shift
+= 2;
/* keep 2 fewer high bits */
01058       table->
structDBusHashTable.html#o8
mask
= table->
structDBusHashTable.html#o8
mask
>> 2;
/* keep 2 fewer high bits */
01059     }
01060
01061
#if 0
01062
printf (
"%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n"
,
01063           growing ?
"GROW"
:
"SHRINK"
,
01064           table->
structDBusHashTable.html#o6
lo_rebuild_size
,
01065           table->
structDBusHashTable.html#o5
hi_rebuild_size
,
01066           table->
structDBusHashTable.html#o7
down_shift
,
01067           table->
structDBusHashTable.html#o8
mask
);
01068
#endif
01069
01070
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o6
lo_rebuild_size
>= 0);
01071
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o5
hi_rebuild_size
> table->
structDBusHashTable.html#o6
lo_rebuild_size
);
01072
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o8
mask
!= 0);
01073
/* the mask is essentially the max index */
01074
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o8
mask
< table->
structDBusHashTable.html#o3
n_buckets
);
01075
01076
/*
01077
* Rehash all of the existing entries into the new bucket array.
01078
*/
01079
01080
for
(old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
01081     {
01082
for
(entry = *old_chain; entry !=
group__DBusMacros.html#ga4
NULL
; entry = *old_chain)
01083         {
01084
unsigned
int
idx;
01085           DBusHashEntry **bucket;
01086
01087           *old_chain = entry->
structDBusHashEntry.html#o0
next
;
01088
switch
(table->
structDBusHashTable.html#o9
key_type
)
01089             {
01090
case
DBUS_HASH_STRING:
01091               idx = string_hash (entry->
structDBusHashEntry.html#o1
key
) & table->
structDBusHashTable.html#o8
mask
;
01092
break
;
01093
case
DBUS_HASH_TWO_STRINGS:
01094
#ifdef DBUS_BUILD_TESTS
01095
idx = two_strings_hash (entry->
structDBusHashEntry.html#o1
key
) & table->
structDBusHashTable.html#o8
mask
;
01096
#else
01097
idx = 0;
01098
group__DBusInternalsUtils.html#ga131
_dbus_assert_not_reached
(
"two-strings is not enabled"
);
01099
#endif
01100
break
;
01101
case
DBUS_HASH_INT:
01102
case
DBUS_HASH_ULONG:
01103
case
DBUS_HASH_POINTER:
01104               idx =
group__DBusHashTableInternals.html#ga11
RANDOM_INDEX
(table, entry->
structDBusHashEntry.html#o1
key
);
01105
break
;
01106
default
:
01107               idx = 0;
01108
group__DBusInternalsUtils.html#ga131
_dbus_assert_not_reached
(
"Unknown hash table type"
);
01109
break
;
01110             }
01111
01112           bucket = &(table->
structDBusHashTable.html#o1
buckets
[idx]);
01113           entry->
structDBusHashEntry.html#o0
next
= *bucket;
01114           *bucket = entry;
01115         }
01116     }
01117
01118
/* Free the old bucket array, if it was dynamically allocated. */
01119
01120
if
(old_buckets != table->
structDBusHashTable.html#o2
static_buckets
)
01121
group__DBusMemory.html#ga3
dbus_free
(old_buckets);
01122 }
01123
01133
void
*
group__DBusHashTable.html#ga16
01134
group__DBusHashTable.html#ga16
_dbus_hash_table_lookup_string
(
structDBusHashTable.html
DBusHashTable
*table,
01135
const
char
*key)
01136 {
01137   DBusHashEntry *entry;
01138
01139
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_STRING);
01140
01141   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, (
char
*) key,
group__DBusMacros.html#ga3
FALSE
,
group__DBusMacros.html#ga4
NULL
, NULL);
01142
01143
if
(entry)
01144
return
entry->
structDBusHashEntry.html#o2
value
;
01145
else
01146
return
NULL;
01147 }
01148
01149
#ifdef DBUS_BUILD_TESTS
01150
01159
void
*
01160 _dbus_hash_table_lookup_two_strings (
structDBusHashTable.html
DBusHashTable
*table,
01161
const
char
*key)
01162 {
01163   DBusHashEntry *entry;
01164
01165
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_TWO_STRINGS);
01166
01167   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, (
char
*) key,
group__DBusMacros.html#ga3
FALSE
,
group__DBusMacros.html#ga4
NULL
, NULL);
01168
01169
if
(entry)
01170
return
entry->
structDBusHashEntry.html#o2
value
;
01171
else
01172
return
NULL;
01173 }
01174
#endif
/* DBUS_BUILD_TESTS */
01175
01185
void
*
group__DBusHashTable.html#ga17
01186
group__DBusHashTable.html#ga17
_dbus_hash_table_lookup_int
(
structDBusHashTable.html
DBusHashTable
*table,
01187
int
key)
01188 {
01189   DBusHashEntry *entry;
01190
01191
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_INT);
01192
01193   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table,
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(key), FALSE, NULL, NULL);
01194
01195
if
(entry)
01196
return
entry->
structDBusHashEntry.html#o2
value
;
01197
else
01198
return
NULL;
01199 }
01200
01201
#ifdef DBUS_BUILD_TESTS
01202
/* disabled since it's only used for testing */
01212
void
*
01213 _dbus_hash_table_lookup_pointer (
structDBusHashTable.html
DBusHashTable
*table,
01214
void
*key)
01215 {
01216   DBusHashEntry *entry;
01217
01218
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_POINTER);
01219
01220   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, key, FALSE, NULL, NULL);
01221
01222
if
(entry)
01223
return
entry->
structDBusHashEntry.html#o2
value
;
01224
else
01225
return
NULL;
01226 }
01227
#endif
/* DBUS_BUILD_TESTS */
01228
01238
void
*
group__DBusHashTable.html#ga18
01239
group__DBusHashTable.html#ga18
_dbus_hash_table_lookup_ulong
(
structDBusHashTable.html
DBusHashTable
*table,
01240
unsigned
long
key)
01241 {
01242   DBusHashEntry *entry;
01243
01244
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_ULONG);
01245
01246   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, (
void
*) key, FALSE, NULL, NULL);
01247
01248
if
(entry)
01249
return
entry->
structDBusHashEntry.html#o2
value
;
01250
else
01251
return
NULL;
01252 }
01253
01262
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga19
01263
group__DBusHashTable.html#ga19
_dbus_hash_table_remove_string
(
structDBusHashTable.html
DBusHashTable
*table,
01264
const
char
*key)
01265 {
01266   DBusHashEntry *entry;
01267   DBusHashEntry **bucket;
01268
01269
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_STRING);
01270
01271   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, (
char
*) key, FALSE, &bucket, NULL);
01272
01273
if
(entry)
01274     {
01275       remove_entry (table, bucket, entry);
01276
return
group__DBusMacros.html#ga2
TRUE
;
01277     }
01278
else
01279
return
FALSE;
01280 }
01281
01282
#ifdef DBUS_BUILD_TESTS
01283
01291
group__DBusTypes.html#ga2
dbus_bool_t
01292 _dbus_hash_table_remove_two_strings (
structDBusHashTable.html
DBusHashTable
*table,
01293
const
char
*key)
01294 {
01295   DBusHashEntry *entry;
01296   DBusHashEntry **bucket;
01297
01298
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_TWO_STRINGS);
01299
01300   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, (
char
*) key, FALSE, &bucket, NULL);
01301
01302
if
(entry)
01303     {
01304       remove_entry (table, bucket, entry);
01305
return
group__DBusMacros.html#ga2
TRUE
;
01306     }
01307
else
01308
return
FALSE;
01309 }
01310
#endif
/* DBUS_BUILD_TESTS */
01311
01320
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga20
01321
group__DBusHashTable.html#ga20
_dbus_hash_table_remove_int
(
structDBusHashTable.html
DBusHashTable
*table,
01322
int
key)
01323 {
01324   DBusHashEntry *entry;
01325   DBusHashEntry **bucket;
01326
01327
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_INT);
01328
01329   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table,
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(key), FALSE, &bucket, NULL);
01330
01331
if
(entry)
01332     {
01333       remove_entry (table, bucket, entry);
01334
return
group__DBusMacros.html#ga2
TRUE
;
01335     }
01336
else
01337
return
FALSE;
01338 }
01339
01340
#ifdef DBUS_BUILD_TESTS
01341
/* disabled since it's only used for testing */
01350
group__DBusTypes.html#ga2
dbus_bool_t
01351 _dbus_hash_table_remove_pointer (
structDBusHashTable.html
DBusHashTable
*table,
01352
void
*key)
01353 {
01354   DBusHashEntry *entry;
01355   DBusHashEntry **bucket;
01356
01357
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_POINTER);
01358
01359   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, key, FALSE, &bucket, NULL);
01360
01361
if
(entry)
01362     {
01363       remove_entry (table, bucket, entry);
01364
return
group__DBusMacros.html#ga2
TRUE
;
01365     }
01366
else
01367
return
FALSE;
01368 }
01369
#endif
/* DBUS_BUILD_TESTS */
01370
01379
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga21
01380
group__DBusHashTable.html#ga21
_dbus_hash_table_remove_ulong
(
structDBusHashTable.html
DBusHashTable
*table,
01381
unsigned
long
key)
01382 {
01383   DBusHashEntry *entry;
01384   DBusHashEntry **bucket;
01385
01386
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_ULONG);
01387
01388   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, (
void
*) key, FALSE, &bucket, NULL);
01389
01390
if
(entry)
01391     {
01392       remove_entry (table, bucket, entry);
01393
return
group__DBusMacros.html#ga2
TRUE
;
01394     }
01395
else
01396
return
FALSE;
01397 }
01398
01414
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga22
01415
group__DBusHashTable.html#ga22
_dbus_hash_table_insert_string
(
structDBusHashTable.html
DBusHashTable
*table,
01416
char
*key,
01417
void
*value)
01418 {
01419   DBusPreallocatedHash *preallocated;
01420
01421
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_STRING);
01422
01423   preallocated =
group__DBusHashTable.html#ga25
_dbus_hash_table_preallocate_entry
(table);
01424
if
(preallocated == NULL)
01425
return
FALSE;
01426
01427
group__DBusHashTable.html#ga27
_dbus_hash_table_insert_string_preallocated
(table, preallocated,
01428                                                key, value);
01429
01430
return
group__DBusMacros.html#ga2
TRUE
;
01431 }
01432
01433
#ifdef DBUS_BUILD_TESTS
01434
01449
group__DBusTypes.html#ga2
dbus_bool_t
01450 _dbus_hash_table_insert_two_strings (
structDBusHashTable.html
DBusHashTable
*table,
01451
char
*key,
01452
void
*value)
01453 {
01454   DBusHashEntry *entry;
01455
01456
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_TWO_STRINGS);
01457
01458   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, key,
group__DBusMacros.html#ga2
TRUE
, NULL, NULL);
01459
01460
if
(entry == NULL)
01461
return
FALSE;
/* no memory */
01462
01463
if
(table->
structDBusHashTable.html#o11
free_key_function
&& entry->
structDBusHashEntry.html#o1
key
!= key)
01464     (* table->
structDBusHashTable.html#o11
free_key_function
) (entry->
structDBusHashEntry.html#o1
key
);
01465
01466
if
(table->
structDBusHashTable.html#o12
free_value_function
&& entry->
structDBusHashEntry.html#o2
value
!= value)
01467     (* table->
structDBusHashTable.html#o12
free_value_function
) (entry->
structDBusHashEntry.html#o2
value
);
01468
01469   entry->
structDBusHashEntry.html#o1
key
= key;
01470   entry->
structDBusHashEntry.html#o2
value
= value;
01471
01472
return
TRUE;
01473 }
01474
#endif
/* DBUS_BUILD_TESTS */
01475
01491
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga23
01492
group__DBusHashTable.html#ga23
_dbus_hash_table_insert_int
(
structDBusHashTable.html
DBusHashTable
*table,
01493
int
key,
01494
void
*value)
01495 {
01496   DBusHashEntry *entry;
01497
01498
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_INT);
01499
01500   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table,
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(key), TRUE, NULL, NULL);
01501
01502
if
(entry == NULL)
01503
return
FALSE;
/* no memory */
01504
01505
if
(table->
structDBusHashTable.html#o11
free_key_function
&& entry->
structDBusHashEntry.html#o1
key
!=
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(key))
01506     (* table->
structDBusHashTable.html#o11
free_key_function
) (entry->
structDBusHashEntry.html#o1
key
);
01507
01508
if
(table->
structDBusHashTable.html#o12
free_value_function
&& entry->
structDBusHashEntry.html#o2
value
!= value)
01509     (* table->
structDBusHashTable.html#o12
free_value_function
) (entry->
structDBusHashEntry.html#o2
value
);
01510
01511   entry->
structDBusHashEntry.html#o1
key
=
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(key);
01512   entry->
structDBusHashEntry.html#o2
value
= value;
01513
01514
return
TRUE;
01515 }
01516
01517
#ifdef DBUS_BUILD_TESTS
01518
/* disabled since it's only used for testing */
01534
group__DBusTypes.html#ga2
dbus_bool_t
01535 _dbus_hash_table_insert_pointer (
structDBusHashTable.html
DBusHashTable
*table,
01536
void
*key,
01537
void
*value)
01538 {
01539   DBusHashEntry *entry;
01540
01541
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_POINTER);
01542
01543   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, key, TRUE, NULL, NULL);
01544
01545
if
(entry == NULL)
01546
return
FALSE;
/* no memory */
01547
01548
if
(table->
structDBusHashTable.html#o11
free_key_function
&& entry->
structDBusHashEntry.html#o1
key
!= key)
01549     (* table->
structDBusHashTable.html#o11
free_key_function
) (entry->
structDBusHashEntry.html#o1
key
);
01550
01551
if
(table->
structDBusHashTable.html#o12
free_value_function
&& entry->
structDBusHashEntry.html#o2
value
!= value)
01552     (* table->
structDBusHashTable.html#o12
free_value_function
) (entry->
structDBusHashEntry.html#o2
value
);
01553
01554   entry->
structDBusHashEntry.html#o1
key
= key;
01555   entry->
structDBusHashEntry.html#o2
value
= value;
01556
01557
return
TRUE;
01558 }
01559
#endif
/* DBUS_BUILD_TESTS */
01560
01576
group__DBusTypes.html#ga2
dbus_bool_t
group__DBusHashTable.html#ga24
01577
group__DBusHashTable.html#ga24
_dbus_hash_table_insert_ulong
(
structDBusHashTable.html
DBusHashTable
*table,
01578
unsigned
long
key,
01579
void
*value)
01580 {
01581   DBusHashEntry *entry;
01582
01583
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_ULONG);
01584
01585   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, (
void
*) key, TRUE, NULL, NULL);
01586
01587
if
(entry == NULL)
01588
return
FALSE;
/* no memory */
01589
01590
if
(table->
structDBusHashTable.html#o11
free_key_function
&& entry->
structDBusHashEntry.html#o1
key
!= (
void
*) key)
01591     (* table->
structDBusHashTable.html#o11
free_key_function
) (entry->
structDBusHashEntry.html#o1
key
);
01592
01593
if
(table->
structDBusHashTable.html#o12
free_value_function
&& entry->
structDBusHashEntry.html#o2
value
!= value)
01594     (* table->
structDBusHashTable.html#o12
free_value_function
) (entry->
structDBusHashEntry.html#o2
value
);
01595
01596   entry->
structDBusHashEntry.html#o1
key
= (
void
*) key;
01597   entry->
structDBusHashEntry.html#o2
value
= value;
01598
01599
return
TRUE;
01600 }
01601
01609 DBusPreallocatedHash*
group__DBusHashTable.html#ga25
01610
group__DBusHashTable.html#ga25
_dbus_hash_table_preallocate_entry
(
structDBusHashTable.html
DBusHashTable
*table)
01611 {
01612   DBusHashEntry *entry;
01613
01614   entry = alloc_entry (table);
01615
01616
return
(DBusPreallocatedHash*) entry;
01617 }
01618
01626
void
group__DBusHashTable.html#ga26
01627
group__DBusHashTable.html#ga26
_dbus_hash_table_free_preallocated_entry
(
structDBusHashTable.html
DBusHashTable
*table,
01628                                           DBusPreallocatedHash *preallocated)
01629 {
01630   DBusHashEntry *entry;
01631
01632
group__DBusInternalsUtils.html#ga130
_dbus_assert
(preallocated != NULL);
01633
01634   entry = (DBusHashEntry*) preallocated;
01635
01636
/* Don't use free_entry(), since this entry has no key/data */
01637
group__DBusMemPool.html#ga3
_dbus_mem_pool_dealloc
(table->
structDBusHashTable.html#o13
entry_pool
, entry);
01638 }
01639
01653
void
group__DBusHashTable.html#ga27
01654
group__DBusHashTable.html#ga27
_dbus_hash_table_insert_string_preallocated
(
structDBusHashTable.html
DBusHashTable
*table,
01655                                              DBusPreallocatedHash *preallocated,
01656
char
*key,
01657
void
*value)
01658 {
01659   DBusHashEntry *entry;
01660
01661
group__DBusInternalsUtils.html#ga130
_dbus_assert
(table->
structDBusHashTable.html#o9
key_type
== DBUS_HASH_STRING);
01662
group__DBusInternalsUtils.html#ga130
_dbus_assert
(preallocated != NULL);
01663
01664   entry = (* table->
structDBusHashTable.html#o10
find_function
) (table, key, TRUE, NULL, preallocated);
01665
01666
group__DBusInternalsUtils.html#ga130
_dbus_assert
(entry != NULL);
01667
01668
if
(table->
structDBusHashTable.html#o11
free_key_function
&& entry->
structDBusHashEntry.html#o1
key
!= key)
01669     (* table->
structDBusHashTable.html#o11
free_key_function
) (entry->
structDBusHashEntry.html#o1
key
);
01670
01671
if
(table->
structDBusHashTable.html#o12
free_value_function
&& entry->
structDBusHashEntry.html#o2
value
!= value)
01672     (* table->
structDBusHashTable.html#o12
free_value_function
) (entry->
structDBusHashEntry.html#o2
value
);
01673
01674   entry->
structDBusHashEntry.html#o1
key
= key;
01675   entry->
structDBusHashEntry.html#o2
value
= value;
01676 }
01677
01684
int
group__DBusHashTable.html#ga28
01685
group__DBusHashTable.html#ga28
_dbus_hash_table_get_n_entries
(
structDBusHashTable.html
DBusHashTable
*table)
01686 {
01687
return
table->
structDBusHashTable.html#o4
n_entries
;
01688 }
01689
01692
#ifdef DBUS_BUILD_TESTS
01693
#include "dbus-test.h"
01694
#include <stdio.h>
01695
01696
/* If you're wondering why the hash table test takes
01697
* forever to run, it's because we call this function
01698
* in inner loops thus making things quadratic.
01699
*/
01700
static
int
01701 count_entries (
structDBusHashTable.html
DBusHashTable
*table)
01702 {
01703
structDBusHashIter.html
DBusHashIter
iter;
01704
int
count;
01705
01706   count = 0;
01707
group__DBusHashTable.html#ga4
_dbus_hash_iter_init
(table, &iter);
01708
while
(
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(&iter))
01709     ++count;
01710
01711
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count ==
group__DBusHashTable.html#ga28
_dbus_hash_table_get_n_entries
(table));
01712
01713
return
count;
01714 }
01715
01716
/* Copy the foo\0bar\0 double string thing */
01717
static
char
*
01718 _dbus_strdup2 (
const
char
*str)
01719 {
01720   size_t len;
01721
char
*copy;
01722
01723
if
(str == NULL)
01724
return
NULL;
01725
01726   len = strlen (str);
01727   len += strlen ((str + len + 1));
01728
01729   copy =
group__DBusMemory.html#ga0
dbus_malloc
(len + 2);
01730
if
(copy == NULL)
01731
return
NULL;
01732
01733   memcpy (copy, str, len + 2);
01734
01735
return
copy;
01736 }
01737
01743
group__DBusTypes.html#ga2
dbus_bool_t
01744 _dbus_hash_test (
void
)
01745 {
01746
int
i;
01747
structDBusHashTable.html
DBusHashTable
*table1;
01748
structDBusHashTable.html
DBusHashTable
*table2;
01749
structDBusHashTable.html
DBusHashTable
*table3;
01750
structDBusHashTable.html
DBusHashTable
*table4;
01751
structDBusHashIter.html
DBusHashIter
iter;
01752
#define N_HASH_KEYS 5000
01753
char
**keys;
01754
group__DBusTypes.html#ga2
dbus_bool_t
ret = FALSE;
01755
01756   keys =
group__DBusMemory.html#ga6
dbus_new
(
char
*, N_HASH_KEYS);
01757
if
(keys == NULL)
01758
group__DBusInternalsUtils.html#ga131
_dbus_assert_not_reached
(
"no memory"
);
01759
01760
for
(i = 0; i < N_HASH_KEYS; i++)
01761     {
01762       keys[i] =
group__DBusMemory.html#ga0
dbus_malloc
(128);
01763
01764
if
(keys[i] == NULL)
01765
group__DBusInternalsUtils.html#ga131
_dbus_assert_not_reached
(
"no memory"
);
01766     }
01767
01768   printf (
"Computing test hash keys...\n"
);
01769   i = 0;
01770
while
(i < N_HASH_KEYS)
01771     {
01772
int
len;
01773
01774
/* all the hash keys are TWO_STRINGS, but
01775
* then we can also use those as regular strings.
01776
*/
01777
01778       len = sprintf (keys[i],
"Hash key %d"
, i);
01779       sprintf (keys[i] + len + 1,
"Two string %d"
, i);
01780
group__DBusInternalsUtils.html#ga130
_dbus_assert
(*(keys[i] + len) ==
'\0'
);
01781
group__DBusInternalsUtils.html#ga130
_dbus_assert
(*(keys[i] + len + 1) !=
'\0'
);
01782       ++i;
01783     }
01784   printf (
"... done.\n"
);
01785
01786   table1 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_STRING,
01787
group__DBusMemory.html#ga3
dbus_free
,
group__DBusMemory.html#ga3
dbus_free
);
01788
if
(table1 == NULL)
01789
goto
out;
01790
01791   table2 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_INT,
01792                                  NULL,
group__DBusMemory.html#ga3
dbus_free
);
01793
if
(table2 == NULL)
01794
goto
out;
01795
01796   table3 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_ULONG,
01797                                  NULL,
group__DBusMemory.html#ga3
dbus_free
);
01798
if
(table3 == NULL)
01799
goto
out;
01800
01801   table4 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_TWO_STRINGS,
01802
group__DBusMemory.html#ga3
dbus_free
,
group__DBusMemory.html#ga3
dbus_free
);
01803
if
(table4 == NULL)
01804
goto
out;
01805
01806
01807
/* Insert and remove a bunch of stuff, counting the table in between
01808
* to be sure it's not broken and that iteration works
01809
*/
01810   i = 0;
01811
while
(i < 3000)
01812     {
01813
void
*value;
01814
char
*key;
01815
01816       key =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
01817
if
(key == NULL)
01818
goto
out;
01819       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Value!"
);
01820
if
(value == NULL)
01821
goto
out;
01822
01823
if
(!
group__DBusHashTable.html#ga22
_dbus_hash_table_insert_string
(table1,
01824                                            key, value))
01825
goto
out;
01826
01827       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
01828
if
(value == NULL)
01829
goto
out;
01830
01831
if
(!
group__DBusHashTable.html#ga23
_dbus_hash_table_insert_int
(table2,
01832                                         i, value))
01833
goto
out;
01834
01835       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
01836
if
(value == NULL)
01837
goto
out;
01838
01839
if
(!
group__DBusHashTable.html#ga24
_dbus_hash_table_insert_ulong
(table3,
01840                                           i, value))
01841
goto
out;
01842
01843       key = _dbus_strdup2 (keys[i]);
01844
if
(key == NULL)
01845
goto
out;
01846       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Value!"
);
01847
if
(value == NULL)
01848
goto
out;
01849
01850
if
(!_dbus_hash_table_insert_two_strings (table4,
01851                                                 key, value))
01852
goto
out;
01853
01854
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table1) == i + 1);
01855
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table2) == i + 1);
01856
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table3) == i + 1);
01857
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table4) == i + 1);
01858
01859       value =
group__DBusHashTable.html#ga16
_dbus_hash_table_lookup_string
(table1, keys[i]);
01860
group__DBusInternalsUtils.html#ga130
_dbus_assert
(value != NULL);
01861
group__DBusInternalsUtils.html#ga130
_dbus_assert
(strcmp (value,
"Value!"
) == 0);
01862
01863       value =
group__DBusHashTable.html#ga17
_dbus_hash_table_lookup_int
(table2, i);
01864
group__DBusInternalsUtils.html#ga130
_dbus_assert
(value != NULL);
01865
group__DBusInternalsUtils.html#ga130
_dbus_assert
(strcmp (value, keys[i]) == 0);
01866
01867       value =
group__DBusHashTable.html#ga18
_dbus_hash_table_lookup_ulong
(table3, i);
01868
group__DBusInternalsUtils.html#ga130
_dbus_assert
(value != NULL);
01869
group__DBusInternalsUtils.html#ga130
_dbus_assert
(strcmp (value, keys[i]) == 0);
01870
01871       value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
01872
group__DBusInternalsUtils.html#ga130
_dbus_assert
(value != NULL);
01873
group__DBusInternalsUtils.html#ga130
_dbus_assert
(strcmp (value,
"Value!"
) == 0);
01874
01875       ++i;
01876     }
01877
01878   --i;
01879
while
(i >= 0)
01880     {
01881
group__DBusHashTable.html#ga19
_dbus_hash_table_remove_string
(table1,
01882                                       keys[i]);
01883
01884
group__DBusHashTable.html#ga20
_dbus_hash_table_remove_int
(table2, i);
01885
01886
group__DBusHashTable.html#ga21
_dbus_hash_table_remove_ulong
(table3, i);
01887
01888       _dbus_hash_table_remove_two_strings (table4,
01889                                            keys[i]);
01890
01891
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table1) == i);
01892
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table2) == i);
01893
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table3) == i);
01894
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table4) == i);
01895
01896       --i;
01897     }
01898
01899
group__DBusHashTable.html#ga2
_dbus_hash_table_ref
(table1);
01900
group__DBusHashTable.html#ga2
_dbus_hash_table_ref
(table2);
01901
group__DBusHashTable.html#ga2
_dbus_hash_table_ref
(table3);
01902
group__DBusHashTable.html#ga2
_dbus_hash_table_ref
(table4);
01903
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table1);
01904
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table2);
01905
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table3);
01906
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table4);
01907
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table1);
01908
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table2);
01909
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table3);
01910
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table4);
01911   table3 = NULL;
01912
01913
/* Insert a bunch of stuff then check
01914
* that iteration works correctly (finds the right
01915
* values, iter_set_value works, etc.)
01916
*/
01917   table1 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_STRING,
01918
group__DBusMemory.html#ga3
dbus_free
,
group__DBusMemory.html#ga3
dbus_free
);
01919
if
(table1 == NULL)
01920
goto
out;
01921
01922   table2 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_INT,
01923                                  NULL,
group__DBusMemory.html#ga3
dbus_free
);
01924
if
(table2 == NULL)
01925
goto
out;
01926
01927   i = 0;
01928
while
(i < 5000)
01929     {
01930
char
*key;
01931
void
*value;
01932
01933       key =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
01934
if
(key == NULL)
01935
goto
out;
01936       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Value!"
);
01937
if
(value == NULL)
01938
goto
out;
01939
01940
if
(!
group__DBusHashTable.html#ga22
_dbus_hash_table_insert_string
(table1,
01941                                            key, value))
01942
goto
out;
01943
01944       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
01945
if
(value == NULL)
01946
goto
out;
01947
01948
if
(!
group__DBusHashTable.html#ga23
_dbus_hash_table_insert_int
(table2,
01949                                         i, value))
01950
goto
out;
01951
01952
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table1) == i + 1);
01953
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table2) == i + 1);
01954
01955       ++i;
01956     }
01957
01958
group__DBusHashTable.html#ga4
_dbus_hash_iter_init
(table1, &iter);
01959
while
(
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(&iter))
01960     {
01961
const
char
*key;
01962
void
*value;
01963
01964       key =
group__DBusHashTable.html#ga11
_dbus_hash_iter_get_string_key
(&iter);
01965       value =
group__DBusHashTable.html#ga7
_dbus_hash_iter_get_value
(&iter);
01966
01967
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTable.html#ga16
_dbus_hash_table_lookup_string
(table1, key) == value);
01968
01969       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Different value!"
);
01970
if
(value == NULL)
01971
goto
out;
01972
01973
group__DBusHashTable.html#ga8
_dbus_hash_iter_set_value
(&iter, value);
01974
01975
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTable.html#ga16
_dbus_hash_table_lookup_string
(table1, key) == value);
01976     }
01977
01978
group__DBusHashTable.html#ga4
_dbus_hash_iter_init
(table1, &iter);
01979
while
(
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(&iter))
01980     {
01981
group__DBusHashTable.html#ga6
_dbus_hash_iter_remove_entry
(&iter);
01982
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table1) == i - 1);
01983       --i;
01984     }
01985
01986
group__DBusHashTable.html#ga4
_dbus_hash_iter_init
(table2, &iter);
01987
while
(
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(&iter))
01988     {
01989
int
key;
01990
void
*value;
01991
01992       key =
group__DBusHashTable.html#ga9
_dbus_hash_iter_get_int_key
(&iter);
01993       value =
group__DBusHashTable.html#ga7
_dbus_hash_iter_get_value
(&iter);
01994
01995
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTable.html#ga17
_dbus_hash_table_lookup_int
(table2, key) == value);
01996
01997       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Different value!"
);
01998
if
(value == NULL)
01999
goto
out;
02000
02001
group__DBusHashTable.html#ga8
_dbus_hash_iter_set_value
(&iter, value);
02002
02003
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTable.html#ga17
_dbus_hash_table_lookup_int
(table2, key) == value);
02004     }
02005
02006   i = count_entries (table2);
02007
group__DBusHashTable.html#ga4
_dbus_hash_iter_init
(table2, &iter);
02008
while
(
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(&iter))
02009     {
02010
group__DBusHashTable.html#ga6
_dbus_hash_iter_remove_entry
(&iter);
02011
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table2) + 1 == i);
02012       --i;
02013     }
02014
02015
/* add/remove interleaved, to check that we grow/shrink the table
02016
* appropriately
02017
*/
02018   i = 0;
02019
while
(i < 1000)
02020     {
02021
char
*key;
02022
void
*value;
02023
02024       key =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
02025
if
(key == NULL)
02026
goto
out;
02027
02028       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Value!"
);
02029
if
(value == NULL)
02030
goto
out;
02031
02032
if
(!
group__DBusHashTable.html#ga22
_dbus_hash_table_insert_string
(table1,
02033                                            key, value))
02034
goto
out;
02035
02036       ++i;
02037     }
02038
02039   --i;
02040
while
(i >= 0)
02041     {
02042
char
*key;
02043
void
*value;
02044
02045       key =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
02046
if
(key == NULL)
02047
goto
out;
02048       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Value!"
);
02049
if
(value == NULL)
02050
goto
out;
02051
02052
if
(!
group__DBusHashTable.html#ga19
_dbus_hash_table_remove_string
(table1, keys[i]))
02053
goto
out;
02054
02055
if
(!
group__DBusHashTable.html#ga22
_dbus_hash_table_insert_string
(table1,
02056                                            key, value))
02057
goto
out;
02058
02059
if
(!
group__DBusHashTable.html#ga19
_dbus_hash_table_remove_string
(table1, keys[i]))
02060
goto
out;
02061
02062
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTable.html#ga28
_dbus_hash_table_get_n_entries
(table1) == i);
02063
02064       --i;
02065     }
02066
02067
/* nuke these tables */
02068
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table1);
02069
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table2);
02070
02071
02072
/* Now do a bunch of things again using _dbus_hash_iter_lookup() to
02073
* be sure that interface works.
02074
*/
02075   table1 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_STRING,
02076
group__DBusMemory.html#ga3
dbus_free
,
group__DBusMemory.html#ga3
dbus_free
);
02077
if
(table1 == NULL)
02078
goto
out;
02079
02080   table2 =
group__DBusHashTable.html#ga1
_dbus_hash_table_new
(DBUS_HASH_INT,
02081                                  NULL,
group__DBusMemory.html#ga3
dbus_free
);
02082
if
(table2 == NULL)
02083
goto
out;
02084
02085   i = 0;
02086
while
(i < 3000)
02087     {
02088
void
*value;
02089
char
*key;
02090
02091       key =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
02092
if
(key == NULL)
02093
goto
out;
02094       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(
"Value!"
);
02095
if
(value == NULL)
02096
goto
out;
02097
02098
if
(!
group__DBusHashTable.html#ga12
_dbus_hash_iter_lookup
(table1,
02099                                    key, TRUE, &iter))
02100
goto
out;
02101
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTable.html#ga7
_dbus_hash_iter_get_value
(&iter) == NULL);
02102
group__DBusHashTable.html#ga8
_dbus_hash_iter_set_value
(&iter, value);
02103
02104       value =
group__DBusInternalsUtils.html#ga8
_dbus_strdup
(keys[i]);
02105
if
(value == NULL)
02106
goto
out;
02107
02108
if
(!
group__DBusHashTable.html#ga12
_dbus_hash_iter_lookup
(table2,
02109
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(i), TRUE, &iter))
02110
goto
out;
02111
group__DBusInternalsUtils.html#ga130
_dbus_assert
(
group__DBusHashTable.html#ga7
_dbus_hash_iter_get_value
(&iter) == NULL);
02112
group__DBusHashTable.html#ga8
_dbus_hash_iter_set_value
(&iter, value);
02113
02114
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table1) == i + 1);
02115
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table2) == i + 1);
02116
02117
if
(!
group__DBusHashTable.html#ga12
_dbus_hash_iter_lookup
(table1, keys[i], FALSE, &iter))
02118
goto
out;
02119
02120       value =
group__DBusHashTable.html#ga7
_dbus_hash_iter_get_value
(&iter);
02121
group__DBusInternalsUtils.html#ga130
_dbus_assert
(value != NULL);
02122
group__DBusInternalsUtils.html#ga130
_dbus_assert
(strcmp (value,
"Value!"
) == 0);
02123
02124
/* Iterate just to be sure it works, though
02125
* it's a stupid thing to do
02126
*/
02127
while
(
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(&iter))
02128         ;
02129
02130
if
(!
group__DBusHashTable.html#ga12
_dbus_hash_iter_lookup
(table2,
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(i), FALSE, &iter))
02131
goto
out;
02132
02133       value =
group__DBusHashTable.html#ga7
_dbus_hash_iter_get_value
(&iter);
02134
group__DBusInternalsUtils.html#ga130
_dbus_assert
(value != NULL);
02135
group__DBusInternalsUtils.html#ga130
_dbus_assert
(strcmp (value, keys[i]) == 0);
02136
02137
/* Iterate just to be sure it works, though
02138
* it's a stupid thing to do
02139
*/
02140
while
(
group__DBusHashTable.html#ga5
_dbus_hash_iter_next
(&iter))
02141         ;
02142
02143       ++i;
02144     }
02145
02146   --i;
02147
while
(i >= 0)
02148     {
02149
if
(!
group__DBusHashTable.html#ga12
_dbus_hash_iter_lookup
(table1, keys[i], FALSE, &iter))
02150
group__DBusInternalsUtils.html#ga131
_dbus_assert_not_reached
(
"hash entry should have existed"
);
02151
group__DBusHashTable.html#ga6
_dbus_hash_iter_remove_entry
(&iter);
02152
02153
if
(!
group__DBusHashTable.html#ga12
_dbus_hash_iter_lookup
(table2,
group__DBusInternalsUtils.html#ga134
_DBUS_INT_TO_POINTER
(i), FALSE, &iter))
02154
group__DBusInternalsUtils.html#ga131
_dbus_assert_not_reached
(
"hash entry should have existed"
);
02155
group__DBusHashTable.html#ga6
_dbus_hash_iter_remove_entry
(&iter);
02156
02157
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table1) == i);
02158
group__DBusInternalsUtils.html#ga130
_dbus_assert
(count_entries (table2) == i);
02159
02160       --i;
02161     }
02162
02163
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table1);
02164
group__DBusHashTable.html#ga3
_dbus_hash_table_unref
(table2);
02165
02166   ret = TRUE;
02167
02168  out:
02169
for
(i = 0; i < N_HASH_KEYS; i++)
02170
group__DBusMemory.html#ga3
dbus_free
(keys[i]);
02171
02172
group__DBusMemory.html#ga3
dbus_free
(keys);
02173
02174
return
ret;
02175 }
02176
02177
#endif
/* DBUS_BUILD_TESTS */
Generated on Tue Sep 13 01:28:06 2005 for D-BUS by
http://www.doxygen.org/index.html
doxygen
1.4.4
