]> git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/dn2id.c
42c6a6fa03fd3be55328e14ff8bfddd19ccfd253
[openldap] / servers / slapd / back-bdb / dn2id.c
1 /* dn2id.c - routines to deal with the dn2id index */
2 /* $OpenLDAP$ */
3 /*
4  * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
6  */
7
8 #include "portable.h"
9
10 #include <stdio.h>
11 #include <ac/string.h>
12
13 #include "back-bdb.h"
14 #include "idl.h"
15 #include "lutil.h"
16
17 #ifndef BDB_HIER
18 int
19 bdb_dn2id_add(
20         BackendDB       *be,
21         DB_TXN *txn,
22         struct berval   *pbv,
23         Entry           *e )
24 {
25         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
26         DB *db = bdb->bi_dn2id->bdi_db;
27         int             rc;
28         DBT             key, data;
29         char            *buf;
30         struct berval   ptr, pdn;
31
32 #ifdef NEW_LOGGING
33         LDAP_LOG ( INDEX, ARGS, "bdb_dn2id_add( \"%s\", 0x%08lx )\n",
34                 e->e_ndn, (long) e->e_id, 0 );
35 #else
36         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add( \"%s\", 0x%08lx )\n",
37                 e->e_ndn, (long) e->e_id, 0 );
38 #endif
39         assert( e->e_id != NOID );
40
41         DBTzero( &key );
42         key.size = e->e_nname.bv_len + 2;
43         key.ulen = key.size;
44         key.flags = DB_DBT_USERMEM;
45         buf = ch_malloc( key.size );
46         key.data = buf;
47         buf[0] = DN_BASE_PREFIX;
48         ptr.bv_val = buf + 1;
49         ptr.bv_len = e->e_nname.bv_len;
50         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
51         ptr.bv_val[ptr.bv_len] = '\0';
52
53         DBTzero( &data );
54         data.data = (char *) &e->e_id;
55         data.size = sizeof( e->e_id );
56
57         /* store it -- don't override */
58         rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
59         if( rc != 0 ) {
60 #ifdef NEW_LOGGING
61                 LDAP_LOG ( INDEX, ERR, "bdb_dn2id_add: put failed: %s %d\n",
62                         db_strerror(rc), rc, 0 );
63 #else
64                 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add: put failed: %s %d\n",
65                         db_strerror(rc), rc, 0 );
66 #endif
67                 goto done;
68         }
69
70 #ifndef BDB_MULTIPLE_SUFFIXES
71         if( !be_issuffix( be, &ptr )) {
72 #endif
73                 buf[0] = DN_SUBTREE_PREFIX;
74                 rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
75                 if( rc != 0 ) {
76 #ifdef NEW_LOGGING
77                         LDAP_LOG ( INDEX, ERR, 
78                                 "=> bdb_dn2id_add: subtree (%s) put failed: %d\n",
79                                 ptr.bv_val, rc, 0 );
80 #else
81                         Debug( LDAP_DEBUG_ANY,
82                         "=> bdb_dn2id_add: subtree (%s) put failed: %d\n",
83                         ptr.bv_val, rc, 0 );
84 #endif
85                         goto done;
86                 }
87                 
88 #ifdef BDB_MULTIPLE_SUFFIXES
89         if( !be_issuffix( be, &ptr )) {
90 #endif
91                 dnParent( &ptr, &pdn );
92         
93                 key.size = pdn.bv_len + 2;
94                 key.ulen = key.size;
95                 pdn.bv_val[-1] = DN_ONE_PREFIX;
96                 key.data = pdn.bv_val-1;
97                 ptr = pdn;
98
99                 rc = bdb_idl_insert_key( be, db, txn, &key, e->e_id );
100
101                 if( rc != 0 ) {
102 #ifdef NEW_LOGGING
103                         LDAP_LOG ( INDEX, ERR, 
104                                 "=> bdb_dn2id_add: parent (%s) insert failed: %d\n",
105                                 ptr.bv_val, rc, 0 );
106 #else
107                         Debug( LDAP_DEBUG_ANY,
108                                 "=> bdb_dn2id_add: parent (%s) insert failed: %d\n",
109                                         ptr.bv_val, rc, 0 );
110 #endif
111                         goto done;
112                 }
113 #ifndef BDB_MULTIPLE_SUFFIXES
114         }
115
116         while( !be_issuffix( be, &ptr )) {
117 #else
118         for (;;) {
119 #endif
120                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
121
122                 rc = bdb_idl_insert_key( be, db, txn, &key, e->e_id );
123
124                 if( rc != 0 ) {
125 #ifdef NEW_LOGGING
126                         LDAP_LOG ( INDEX, ERR, 
127                                 "=> bdb_dn2id_add: subtree (%s) insert failed: %d\n",
128                                 ptr.bv_val, rc, 0 );
129 #else
130                         Debug( LDAP_DEBUG_ANY,
131                                 "=> bdb_dn2id_add: subtree (%s) insert failed: %d\n",
132                                         ptr.bv_val, rc, 0 );
133 #endif
134                         break;
135                 }
136 #ifdef BDB_MULTIPLE_SUFFIXES
137                 if( be_issuffix( be, &ptr )) break;
138 #endif
139                 dnParent( &ptr, &pdn );
140
141                 key.size = pdn.bv_len + 2;
142                 key.ulen = key.size;
143                 key.data = pdn.bv_val - 1;
144                 ptr = pdn;
145         }
146 #ifdef BDB_MULTIPLE_SUFFIXES
147         }
148 #endif
149
150 done:
151         ch_free( buf );
152 #ifdef NEW_LOGGING
153         LDAP_LOG ( INDEX, RESULTS, "<= bdb_dn2id_add: %d\n", rc, 0, 0 );
154 #else
155         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add: %d\n", rc, 0, 0 );
156 #endif
157         return rc;
158 }
159
160 int
161 bdb_dn2id_delete(
162         BackendDB       *be,
163         DB_TXN *txn,
164         char    *pdnc,
165         Entry           *e )
166 {
167         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
168         DB *db = bdb->bi_dn2id->bdi_db;
169         int             rc;
170         DBT             key;
171         char            *buf;
172         struct berval   pdn, ptr;
173
174 #ifdef NEW_LOGGING
175         LDAP_LOG ( INDEX, ARGS, 
176                 "=> bdb_dn2id_delete ( \"%s\", 0x%08lx )\n", e->e_ndn, e->e_id, 0);
177 #else
178         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete( \"%s\", 0x%08lx )\n",
179                 e->e_ndn, e->e_id, 0 );
180 #endif
181
182         DBTzero( &key );
183         key.size = e->e_nname.bv_len + 2;
184         buf = ch_malloc( key.size );
185         key.data = buf;
186         key.flags = DB_DBT_USERMEM;
187         buf[0] = DN_BASE_PREFIX;
188         ptr.bv_val = buf+1;
189         ptr.bv_len = e->e_nname.bv_len;
190         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
191         ptr.bv_val[ptr.bv_len] = '\0';
192
193         /* delete it */
194         rc = db->del( db, txn, &key, 0 );
195         if( rc != 0 ) {
196 #ifdef NEW_LOGGING
197                 LDAP_LOG ( INDEX, ERR, 
198                         "=> bdb_dn2id_delete: delete failed: %s %d\n", 
199                         db_strerror(rc), rc, 0 );
200 #else
201                 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete: delete failed: %s %d\n",
202                         db_strerror(rc), rc, 0 );
203 #endif
204                 goto done;
205         }
206
207 #ifndef BDB_MULTIPLE_SUFFIXES
208         if( !be_issuffix( be, &ptr )) {
209 #endif
210                 buf[0] = DN_SUBTREE_PREFIX;
211                 rc = db->del( db, txn, &key, 0 );
212                 if( rc != 0 ) {
213 #ifdef NEW_LOGGING
214                         LDAP_LOG ( INDEX, ERR, 
215                                 "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n", 
216                                 ptr.bv_val, rc, 0 );
217 #else
218                         Debug( LDAP_DEBUG_ANY,
219                         "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
220                         ptr.bv_val, rc, 0 );
221 #endif
222                         goto done;
223                 }
224
225 #ifdef BDB_MULTIPLE_SUFFIXES
226         if( !be_issuffix( be, &ptr )) {
227 #endif
228                 dnParent( &ptr, &pdn );
229
230                 key.size = pdn.bv_len + 2;
231                 key.ulen = key.size;
232                 pdn.bv_val[-1] = DN_ONE_PREFIX;
233                 key.data = pdn.bv_val - 1;
234                 ptr = pdn;
235
236                 rc = bdb_idl_delete_key( be, db, txn, &key, e->e_id );
237
238                 if( rc != 0 ) {
239 #ifdef NEW_LOGGING
240                         LDAP_LOG ( INDEX, ERR, 
241                                 "=> bdb_dn2id_delete: parent (%s) delete failed: %d\n", 
242                                 ptr.bv_val, rc, 0 );
243 #else
244                         Debug( LDAP_DEBUG_ANY,
245                                 "=> bdb_dn2id_delete: parent (%s) delete failed: %d\n",
246                                 ptr.bv_val, rc, 0 );
247 #endif
248                         goto done;
249                 }
250 #ifndef BDB_MULTIPLE_SUFFIXES
251         }
252
253         while( !be_issuffix( be, &ptr )) {
254 #else
255         for (;;) {
256 #endif
257                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
258
259                 rc = bdb_idl_delete_key( be, db, txn, &key, e->e_id );
260                 if( rc != 0 ) {
261 #ifdef NEW_LOGGING
262                         LDAP_LOG ( INDEX, ERR, 
263                                 "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n", 
264                                 ptr.bv_val, rc, 0 );
265 #else
266                         Debug( LDAP_DEBUG_ANY,
267                                 "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
268                                 ptr.bv_val, rc, 0 );
269 #endif
270                         goto done;
271                 }
272 #ifdef BDB_MULTIPLE_SUFFIXES
273                 if( be_issuffix( be, &ptr )) break;
274 #endif
275                 dnParent( &ptr, &pdn );
276
277                 key.size = pdn.bv_len + 2;
278                 key.ulen = key.size;
279                 key.data = pdn.bv_val - 1;
280                 ptr = pdn;
281         }
282 #ifdef BDB_MULTIPLE_SUFFIXES
283         }
284 #endif
285
286 done:
287         ch_free( buf );
288 #ifdef NEW_LOGGING
289         LDAP_LOG ( INDEX, RESULTS, "<= bdb_dn2id_delete %d\n", rc, 0, 0 );
290 #else
291         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete %d\n", rc, 0, 0 );
292 #endif
293         return rc;
294 }
295
296 int
297 bdb_dn2id(
298         BackendDB       *be,
299         DB_TXN *txn,
300         struct berval   *dn,
301         ID *id,
302         int flags )
303 {
304         int             rc;
305         DBT             key, data;
306         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
307         DB *db = bdb->bi_dn2id->bdi_db;
308
309 #ifdef NEW_LOGGING
310         LDAP_LOG ( INDEX, ARGS, "=> bdb_dn2id( \"%s\" )\n", dn->bv_val, 0, 0 );
311 #else
312         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id( \"%s\" )\n", dn->bv_val, 0, 0 );
313 #endif
314
315         assert (id);
316  
317         *id = bdb_cache_find_entry_ndn2id(be, &bdb->bi_cache, dn);
318         if (*id != NOID) {
319                 return 0;
320         }
321
322         DBTzero( &key );
323         key.size = dn->bv_len + 2;
324         key.data = ch_malloc( key.size );
325         ((char *)key.data)[0] = DN_BASE_PREFIX;
326         AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
327
328         /* store the ID */
329         DBTzero( &data );
330         data.data = id;
331         data.ulen = sizeof(ID);
332         data.flags = DB_DBT_USERMEM;
333
334         /* fetch it */
335         rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags | flags);
336
337         if( rc != 0 ) {
338 #ifdef NEW_LOGGING
339                 LDAP_LOG ( INDEX, ERR, "<= bdb_dn2id: get failed %s (%d)\n", 
340                         db_strerror(rc), rc, 0 );
341 #else
342                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
343                         db_strerror( rc ), rc, 0 );
344 #endif
345         } else {
346 #ifdef NEW_LOGGING
347                 LDAP_LOG ( INDEX, RESULTS, 
348                         "<= bdb_dn2id: got id=0x%08lx\n", *id, 0, 0 );
349 #else
350                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%08lx\n",
351                         *id, 0, 0 );
352 #endif
353         }
354
355         ch_free( key.data );
356         return rc;
357 }
358
359 int
360 bdb_dn2id_matched(
361         BackendDB       *be,
362         DB_TXN *txn,
363         struct berval   *in,
364         ID *id,
365         ID *id2,
366         int flags )
367 {
368         int             rc;
369         DBT             key, data;
370         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
371         DB *db = bdb->bi_dn2id->bdi_db;
372         char            *buf;
373         struct  berval dn;
374         ID              cached_id;
375
376 #ifdef NEW_LOGGING
377         LDAP_LOG ( INDEX, ARGS, 
378                 "=> bdb_dn2id_matched( \"%s\" )\n", in->bv_val, 0, 0 );
379 #else
380         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_matched( \"%s\" )\n", in->bv_val, 0, 0 );
381 #endif
382
383         DBTzero( &key );
384         key.size = in->bv_len + 2;
385         buf = ch_malloc( key.size );
386         key.data = buf;
387         dn.bv_val = buf+1;
388         dn.bv_len = key.size - 2;
389         AC_MEMCPY( dn.bv_val, in->bv_val, key.size - 1 );
390
391         /* store the ID */
392         DBTzero( &data );
393         data.data = id;
394         data.ulen = sizeof(ID);
395         data.flags = DB_DBT_USERMEM;
396
397         while(1) {
398                 dn.bv_val[-1] = DN_BASE_PREFIX;
399
400                 *id = NOID;
401
402                 /* lookup cache */
403                 cached_id = bdb_cache_find_entry_ndn2id(be, &bdb->bi_cache, &dn);
404  
405                 if (cached_id != NOID) {
406                         rc = 0;
407                         *id = cached_id;
408                         if ( dn.bv_val != buf+1 ) {
409                                 *id2 = *id;
410                         }
411                         break;
412                 } else {
413                         /* fetch it */
414                         rc = db->get(db, txn, &key, &data, bdb->bi_db_opflags | flags );
415                 }
416
417                 if( rc == DB_NOTFOUND ) {
418                         struct berval   pdn;
419
420                         if ( ! be_issuffix( be, &dn ) ) {
421                                 dnParent( &dn, &pdn );
422                         } else {
423 #ifdef NEW_LOGGING
424                                 LDAP_LOG ( INDEX, DETAIL1, 
425                                         "<= bdb_dn2id_matched: no match\n", 0, 0, 0 );
426 #else
427                                 Debug( LDAP_DEBUG_TRACE,
428                                         "<= bdb_dn2id_matched: no match\n",
429                                         0, 0, 0 );
430 #endif
431                                 break;
432                         }
433
434                         key.size = pdn.bv_len + 2;
435                         dn = pdn;
436                         key.data = pdn.bv_val - 1;
437
438                 } else if ( rc == 0 ) {
439                         if( data.size != sizeof( ID ) ) {
440 #ifdef NEW_LOGGING
441                                 LDAP_LOG ( INDEX, DETAIL1, 
442                                         "<= bdb_dn2id_matched: get size mismatch:"
443                                         "expected %ld, got %ld\n",
444                                         (long) sizeof(ID), (long) data.size, 0 );
445 #else
446                                 Debug( LDAP_DEBUG_ANY,
447                                         "<= bdb_dn2id_matched: get size mismatch: "
448                                         "expected %ld, got %ld\n",
449                                         (long) sizeof(ID), (long) data.size, 0 );
450 #endif
451                         }
452
453                         if( dn.bv_val != buf+1 ) {
454                                 *id2 = *id;
455                         }
456
457 #ifdef NEW_LOGGING
458                         LDAP_LOG ( INDEX, DETAIL1, 
459                                 "<= bdb_dn2id_matched: id=0x%08lx: %s %s\n",
460                                 (long) *id, *id2 == 0 ? "entry" : "matched", dn.bv_val );
461 #else
462                         Debug( LDAP_DEBUG_TRACE,
463                                 "<= bdb_dn2id_matched: id=0x%08lx: %s %s\n",
464                                 (long) *id, *id2 == 0 ? "entry" : "matched", dn.bv_val );
465 #endif
466                         break;
467
468                 } else {
469 #ifdef NEW_LOGGING
470                         LDAP_LOG ( INDEX, ERR, 
471                                 "<= bdb_dn2id_matched: get failed: %s (%d)\n",
472                                 db_strerror(rc), rc, 0 );
473 #else
474                         Debug( LDAP_DEBUG_ANY,
475                                 "<= bdb_dn2id_matched: get failed: %s (%d)\n",
476                                 db_strerror(rc), rc, 0 );
477 #endif
478                         break;
479                 }
480         }
481
482         ch_free( buf );
483         return rc;
484 }
485
486 int
487 bdb_dn2id_children(
488         BackendDB       *be,
489         DB_TXN *txn,
490         struct berval *dn, 
491         int flags )
492 {
493         int             rc;
494         DBT             key, data;
495         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
496         DB *db = bdb->bi_dn2id->bdi_db;
497         ID              id;
498
499 #ifdef NEW_LOGGING
500         LDAP_LOG ( INDEX, ARGS, 
501                 "=> bdb_dn2id_children( %s )\n", dn->bv_val, 0, 0 );
502 #else
503         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children( %s )\n",
504                 dn->bv_val, 0, 0 );
505 #endif
506
507         DBTzero( &key );
508         key.size = dn->bv_len + 2;
509         key.data = ch_malloc( key.size );
510         ((char *)key.data)[0] = DN_ONE_PREFIX;
511         AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
512
513         /* we actually could do a empty get... */
514         DBTzero( &data );
515         data.data = &id;
516         data.ulen = sizeof(id);
517         data.flags = DB_DBT_USERMEM;
518         data.doff = 0;
519         data.dlen = sizeof(id);
520
521         rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags | flags );
522         free( key.data );
523
524 #ifdef NEW_LOGGING
525         LDAP_LOG ( INDEX, DETAIL1, 
526                 "<= bdb_dn2id_children( %s ): %schildren (%d)\n", 
527                 dn->bv_val, rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
528                 db_strerror(rc)), rc );
529 #else
530         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children( %s ): %schildren (%d)\n",
531                 dn->bv_val,
532                 rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
533                         db_strerror(rc) ), rc );
534 #endif
535
536         return rc;
537 }
538
539 int
540 bdb_dn2idl(
541         BackendDB       *be,
542         struct berval   *dn,
543         int prefix,
544         ID *ids )
545 {
546         int             rc;
547         DBT             key;
548         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
549         DB *db = bdb->bi_dn2id->bdi_db;
550
551 #ifdef NEW_LOGGING
552         LDAP_LOG ( INDEX, ARGS, 
553                 "=> bdb_dn2ididl( \"%s\" )\n", dn->bv_val, 0, 0 );
554 #else
555         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl( \"%s\" )\n", dn->bv_val, 0, 0 );
556 #endif
557
558 #ifndef BDB_MULTIPLE_SUFFIXES
559         if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn))
560         {
561                 BDB_IDL_ALL(bdb, ids);
562                 return 0;
563         }
564 #endif
565
566         DBTzero( &key );
567         key.size = dn->bv_len + 2;
568         key.ulen = key.size;
569         key.flags = DB_DBT_USERMEM;
570         key.data = ch_malloc( key.size );
571         ((char *)key.data)[0] = prefix;
572         AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
573
574         rc = bdb_idl_fetch_key( be, db, NULL, &key, ids );
575
576         if( rc != 0 ) {
577 #ifdef NEW_LOGGING
578                 LDAP_LOG ( INDEX, ERR, 
579                         "<= bdb_dn2ididl: get failed: %s (%d)\n", db_strerror(rc), rc, 0 );
580 #else
581                 Debug( LDAP_DEBUG_TRACE,
582                         "<= bdb_dn2idl: get failed: %s (%d)\n",
583                         db_strerror( rc ), rc, 0 );
584 #endif
585
586         } else {
587 #ifdef NEW_LOGGING
588                 LDAP_LOG ( INDEX, RESULTS, 
589                         "<= bdb_dn2ididl: id=%ld first=%ld last=%ld\n", 
590                         (long) ids[0], (long) BDB_IDL_FIRST( ids ), 
591                         (long) BDB_IDL_LAST( ids ) );
592 #else
593                 Debug( LDAP_DEBUG_TRACE,
594                         "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
595                         (long) ids[0],
596                         (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
597 #endif
598         }
599
600         ch_free( key.data );
601         return rc;
602 }
603 #else   /* BDB_HIER */
604
605 /* Experimental management routines for a hierarchically structured backend.
606  *
607  * Unsupported! Use at your own risk!
608  *
609  * Instead of a dn2id database, we use an id2parent database. Each entry in
610  * this database is a struct diskNode, containing the ID of the node's parent
611  * and the RDN of the node.
612  */
613 typedef struct diskNode {
614         ID parent;
615         struct berval rdn;
616         struct berval nrdn;
617 } diskNode;
618
619 /* In bdb_db_open() we call bdb_build_tree() which reads the entire id2parent
620  * database into memory (into an AVL tree). Next we iterate through each node
621  * of this tree, connecting each child to its parent. The nodes in this AVL
622  * tree are a struct idNode. The immediate (Onelevel) children of a node are
623  * referenced in the i_kids AVL tree. With this arrangement, there is no need
624  * to maintain the DN_ONE_PREFIX or DN_SUBTREE_PREFIX database keys. Note that
625  * the DN of an entry is constructed by walking up the list of i_parent
626  * pointers, so no full DN is stored on disk anywhere. This makes modrdn
627  * extremely efficient, even when operating on a populated subtree.
628  *
629  * The idNode tree is searched directly from the root when performing id to
630  * entry lookups. The tree is traversed using the i_kids subtrees when
631  * performing dn to id lookups.
632  */
633 typedef struct idNode {
634         ID i_id;
635         struct idNode *i_parent;
636         diskNode *i_rdn;
637         Avlnode *i_kids;
638         ldap_pvt_thread_rdwr_t i_kids_rdwr;
639 } idNode;
640
641
642 /* The main AVL tree is sorted in ID order. The i_kids AVL trees are
643  * sorted in lexical order. These are the various helper routines used
644  * for the searches and sorts.
645  */
646 static int
647 node_find_cmp(
648         const void *id,
649         const void *node
650 )
651 {
652         return *(const ID *)id - ((const idNode *)node)->i_id;
653 }
654
655 static int
656 node_frdn_cmp(
657         const void *v_nrdn,
658         const void *v_n
659 )
660 {
661         const struct berval *nrdn = v_nrdn;
662         const idNode *n = v_n;
663         return ber_bvcmp(nrdn, &n->i_rdn->nrdn);
664 }
665
666 static int
667 node_add_cmp(
668         const void *v_a,
669         const void *v_b
670 )
671 {
672         const idNode *a = v_a, *b = v_b;
673         return a->i_id - b->i_id;
674 }
675
676 static int
677 node_rdn_cmp(
678         const void *v_a,
679         const void *v_b
680 )
681 {
682         const idNode *a = v_a, *b = v_b;
683         /* should be slightly better without ordering drawbacks */
684         return ber_bvcmp(&a->i_rdn->nrdn, &b->i_rdn->nrdn);
685 }
686
687 idNode * bdb_find_id_node(
688         ID id,
689         Avlnode *tree
690 )
691 {
692         return avl_find(tree, &id, node_find_cmp);
693 }
694
695 idNode * bdb_find_rdn_node(
696         struct berval *nrdn,
697         Avlnode *tree
698 )
699 {
700         return avl_find(tree, nrdn, node_frdn_cmp);
701 }
702
703 /* This function links a node into its parent's i_kids tree. */
704 static int bdb_insert_kid(
705         void *v_a,
706         void *v_tree
707 )
708 {
709         idNode *a = v_a;
710         Avlnode *tree = v_tree;
711         int rc;
712
713         if (a->i_rdn->parent == 0)
714                 return 0;
715         a->i_parent = bdb_find_id_node(a->i_rdn->parent, tree);
716         if (!a->i_parent)
717                 return -1;
718         ldap_pvt_thread_rdwr_wlock(&a->i_parent->i_kids_rdwr);
719         rc = avl_insert( &a->i_parent->i_kids, (caddr_t) a,
720                          node_rdn_cmp, avl_dup_error );
721         ldap_pvt_thread_rdwr_wunlock(&a->i_parent->i_kids_rdwr);
722         return rc;
723 }
724
725 /* This function adds a node into the main AVL tree */
726 idNode *bdb_add_node(
727         ID id,
728         char *d,
729         struct bdb_info *bdb
730 )
731 {
732         idNode *node;
733
734         node = (idNode *)ch_malloc(sizeof(idNode));
735         node->i_id = id;
736         node->i_parent = NULL;
737         node->i_kids = NULL;
738         node->i_rdn = (diskNode *)d;
739         node->i_rdn->rdn.bv_val += (long)d;
740         node->i_rdn->nrdn.bv_val += (long)d;
741         ldap_pvt_thread_rdwr_init(&node->i_kids_rdwr);
742         avl_insert( &bdb->bi_tree, (caddr_t) node, node_add_cmp, avl_dup_error );
743         if (id == 1)
744                 bdb->bi_troot = node;
745         return node;
746 }
747
748 /* This function initializes the trees at startup time. */
749 int bdb_build_tree(
750         Backend *be
751 )
752 {
753         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
754         int rc;
755         DBC *cursor;
756         DBT key, data;
757         ID id;
758         idNode *node;
759
760         bdb->bi_tree = NULL;
761
762         rc = bdb->bi_id2parent->bdi_db->cursor(
763                 bdb->bi_id2parent->bdi_db, NULL, &cursor,
764                 bdb->bi_db_opflags );
765         if( rc != 0 ) {
766                 return NOID;
767         }
768
769         DBTzero( &key );
770         DBTzero( &data );
771         key.data = (char *)&id;
772         key.ulen = sizeof( id );
773         key.flags = DB_DBT_USERMEM;
774         data.flags = DB_DBT_MALLOC;
775
776         while (cursor->c_get( cursor, &key, &data, DB_NEXT ) == 0) {
777                 bdb_add_node( id, data.data, bdb );
778         }
779         cursor->c_close( cursor );
780
781         rc = avl_apply(bdb->bi_tree, bdb_insert_kid, bdb->bi_tree,
782                 -1, AVL_INORDER );
783
784         return rc;
785 }
786
787 /* This function constructs a full DN for a given id. We really should
788  * be passing idNodes directly, to save some effort...
789  */
790 int bdb_fix_dn(
791         BackendDB *be,
792         ID id,
793         Entry *e
794 )
795 {
796         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
797         idNode *n, *o;
798         int rlen, nrlen;
799         char *ptr, *nptr;
800         
801         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
802         o = bdb_find_id_node(id, bdb->bi_tree);
803         rlen = be->be_suffix[0].bv_len + 1;
804         nrlen = be->be_nsuffix[0].bv_len + 1;
805         for (n = o; n && n->i_parent; n=n->i_parent) {
806                 rlen += n->i_rdn->rdn.bv_len + 1;
807                 nrlen += n->i_rdn->nrdn.bv_len + 1;
808         }
809         e->e_name.bv_len = rlen - 1;
810         e->e_nname.bv_len = nrlen - 1;
811         e->e_name.bv_val = ch_malloc(rlen + nrlen);
812         e->e_nname.bv_val = e->e_name.bv_val + rlen;
813         ptr = e->e_name.bv_val;
814         nptr = e->e_nname.bv_val;
815         for (n = o; n && n->i_parent; n=n->i_parent) {
816                 ptr = lutil_strcopy(ptr, n->i_rdn->rdn.bv_val);
817                 *ptr++ = ',';
818                 nptr = lutil_strcopy(nptr, n->i_rdn->nrdn.bv_val);
819                 *nptr++ = ',';
820         }
821         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
822
823         strcpy(ptr, be->be_suffix[0].bv_val);
824         strcpy(nptr, be->be_nsuffix[0].bv_val);
825
826         return 0;
827 }
828
829 int
830 bdb_dn2id_add(
831         BackendDB       *be,
832         DB_TXN *txn,
833         struct berval   *pdn,
834         Entry           *e )
835 {
836         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
837         int             rc, rlen, nrlen;
838         DBT             key, data;
839         DB *db = bdb->bi_id2parent->bdi_db;
840         diskNode *d;
841         idNode *n;
842
843         nrlen = dn_rdnlen( be, &e->e_nname );
844         if (nrlen) {
845                 rlen = dn_rdnlen( be, &e->e_name );
846         } else {
847                 rlen = 0;
848         }
849
850         d = ch_malloc(sizeof(diskNode) + rlen + nrlen + 2);
851         d->rdn.bv_len = rlen;
852         d->nrdn.bv_len = nrlen;
853         d->rdn.bv_val = (char *)(d+1);
854         d->nrdn.bv_val = d->rdn.bv_val + rlen + 1;
855         strncpy(d->rdn.bv_val, e->e_dn, rlen);
856         d->rdn.bv_val[rlen] = '\0';
857         strncpy(d->nrdn.bv_val, e->e_ndn, nrlen);
858         d->nrdn.bv_val[nrlen] = '\0';
859         d->rdn.bv_val -= (long)d;
860         d->nrdn.bv_val -= (long)d;
861
862         if (pdn->bv_len) {
863                 bdb_dn2id(be, txn, pdn, &d->parent, 0);
864         } else {
865                 d->parent = 0;
866         }
867
868         DBTzero(&key);
869         DBTzero(&data);
870         key.data = &e->e_id;
871         key.size = sizeof(ID);
872         key.flags = DB_DBT_USERMEM;
873
874         data.data = d;
875         data.size = sizeof(diskNode) + rlen + nrlen + 2;
876         data.flags = DB_DBT_USERMEM;
877
878         rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
879
880         if (rc == 0) {
881                 ldap_pvt_thread_rdwr_wlock(&bdb->bi_tree_rdwr);
882                 n = bdb_add_node( e->e_id, data.data, bdb);
883                 ldap_pvt_thread_rdwr_wunlock(&bdb->bi_tree_rdwr);
884
885                 if (d->parent) {
886                         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
887                         bdb_insert_kid(n, bdb->bi_tree);
888                         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
889                 }
890         } else {
891                 free(d);
892         }
893         return rc;
894 }
895
896 int
897 bdb_dn2id_delete(
898         BackendDB       *be,
899         DB_TXN *txn,
900         char    *pdn,
901         Entry   *e )
902 {
903         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
904         int rc;
905         DBT             key;
906         DB *db = bdb->bi_id2parent->bdi_db;
907         idNode *n;
908
909         DBTzero(&key);
910         key.size = sizeof(e->e_id);
911         key.data = &e->e_id;
912
913         rc = db->del( db, txn, &key, 0);
914
915         ldap_pvt_thread_rdwr_wlock(&bdb->bi_tree_rdwr);
916         n = avl_delete(&bdb->bi_tree, &e->e_id, node_find_cmp);
917         if (n) {
918                 if (n->i_parent) {
919                         ldap_pvt_thread_rdwr_wlock(&n->i_parent->i_kids_rdwr);
920                         avl_delete(&n->i_parent->i_kids, &n->i_rdn->nrdn, node_frdn_cmp);
921                         ldap_pvt_thread_rdwr_wunlock(&n->i_parent->i_kids_rdwr);
922                 }
923                 free(n->i_rdn);
924                 ldap_pvt_thread_rdwr_destroy(&n->i_kids_rdwr);
925                 free(n);
926         }
927         if (e->e_id == 1)
928                 bdb->bi_troot = NULL;
929         ldap_pvt_thread_rdwr_wunlock(&bdb->bi_tree_rdwr);
930
931         return rc;
932 }
933
934 int
935 bdb_dn2id_matched(
936         BackendDB       *be,
937         DB_TXN *txn,
938         struct berval   *in,
939         ID *id,
940         ID *id2,
941         int flags )
942 {
943         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
944         struct berval   rdn;
945         char            *p1, *p2;
946         idNode *n, *p;
947         int             rc = 0;
948
949         if (!bdb->bi_troot)
950                 return DB_NOTFOUND;
951
952         p = bdb->bi_troot;
953         if (be_issuffix(be, in)) {
954                 *id = p->i_id;
955                 return 0;
956         }
957
958         p1 = in->bv_val + in->bv_len - be->be_nsuffix[0].bv_len - 1;
959
960         n = p;
961         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
962         for (;;) {
963                 for (p2 = p1-1; (p2 >= in->bv_val) && !DN_SEPARATOR(*p2); p2--);
964                 rdn.bv_val = p2+1;
965                 rdn.bv_len = p1-rdn.bv_val;
966                 p1 = p2;
967
968                 ldap_pvt_thread_rdwr_rlock(&p->i_kids_rdwr);
969                 n = bdb_find_rdn_node(&rdn, p->i_kids);
970                 ldap_pvt_thread_rdwr_runlock(&p->i_kids_rdwr);
971                 if (!n || p2 < in->bv_val) break;
972                 p = n;
973         }
974         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
975
976         if (n) {
977                 *id = n->i_id;
978         } else if (id2) {
979                 *id2 = p->i_id;
980         } else {
981                 rc = DB_NOTFOUND;
982         }
983
984         return rc;
985 }
986
987 int
988 bdb_dn2id(
989         BackendDB       *be,
990         DB_TXN *txn,
991         struct berval   *dn,
992         ID *id,
993         int flags )
994 {
995         return bdb_dn2id_matched(be, txn, dn, id, NULL, flags);
996 }
997
998 int
999 bdb_dn2id_children(
1000         BackendDB       *be,
1001         DB_TXN *txn,
1002         struct berval   *dn,
1003         int flags )
1004 {
1005         int             rc;
1006         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
1007         ID              id;
1008         idNode *n;
1009
1010         rc = bdb_dn2id(be, txn, dn, &id, flags);
1011         if (rc != 0)
1012                 return rc;
1013
1014         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
1015         n = bdb_find_id_node(id, bdb->bi_tree);
1016         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
1017
1018         if (!n->i_kids)
1019                 return DB_NOTFOUND;
1020         else
1021                 return 0;
1022 }
1023
1024 /* Since we don't store IDLs for onelevel or subtree, we have to construct
1025  * them on the fly... Perhaps the i_kids tree ought to just be an IDL?
1026  */
1027 static int
1028 insert_one(
1029         void *v_n,
1030         void *v_ids
1031 )
1032 {
1033         idNode *n = v_n;
1034         ID *ids = v_ids;
1035         return bdb_idl_insert(ids, n->i_id);
1036 }
1037
1038 static int
1039 insert_sub(
1040         void *v_n,
1041         void *v_ids
1042 )
1043 {
1044         idNode *n = v_n;
1045         ID *ids = v_ids;
1046         int rc;
1047
1048         rc = bdb_idl_insert(ids, n->i_id);
1049         if (rc == 0) {
1050                 ldap_pvt_thread_rdwr_rlock(&n->i_kids_rdwr);
1051                 rc = avl_apply(n->i_kids, insert_sub, ids, -1, AVL_INORDER);
1052                 ldap_pvt_thread_rdwr_runlock(&n->i_kids_rdwr);
1053         }
1054         return rc;
1055 }
1056
1057 int
1058 bdb_dn2idl(
1059         BackendDB       *be,
1060         struct berval   *dn,
1061         int prefix,
1062         ID *ids )
1063 {
1064         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
1065         int             rc;
1066         ID              id;
1067         idNode          *n;
1068
1069         if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn)) {
1070                 BDB_IDL_ALL(bdb, ids);
1071                 return 0;
1072         }
1073
1074         rc = bdb_dn2id(be, NULL, dn, &id, 0);
1075         if (rc) return rc;
1076
1077         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
1078         n = bdb_find_id_node(id, bdb->bi_tree);
1079         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
1080
1081         ids[0] = 0;
1082         ldap_pvt_thread_rdwr_rlock(&n->i_kids_rdwr);
1083         if (prefix == DN_ONE_PREFIX) {
1084                 rc = avl_apply(n->i_kids, insert_one, ids, -1, AVL_INORDER);
1085         } else {
1086                 rc = bdb_idl_insert(ids, id);
1087                 if (n->i_kids)
1088                         rc = avl_apply(n->i_kids, insert_sub, ids, -1, AVL_INORDER);
1089         }
1090         ldap_pvt_thread_rdwr_runlock(&n->i_kids_rdwr);
1091         return rc;
1092 }
1093 #endif  /* BDB_HIER */