ldns/drill: Update vendor branch to 1.6.9
[dragonfly.git] / contrib / ldns / dnssec_zone.c
1 /*
2  * special zone file structures and functions for better dnssec handling
3  */
4
5 #include <ldns/config.h>
6
7 #include <ldns/ldns.h>
8
9 ldns_dnssec_rrs *
10 ldns_dnssec_rrs_new()
11 {
12         ldns_dnssec_rrs *new_rrs;
13         new_rrs = LDNS_MALLOC(ldns_dnssec_rrs);
14         if(!new_rrs) return NULL;
15         new_rrs->rr = NULL;
16         new_rrs->next = NULL;
17         return new_rrs;
18 }
19
20 INLINE void
21 ldns_dnssec_rrs_free_internal(ldns_dnssec_rrs *rrs, int deep)
22 {
23         ldns_dnssec_rrs *next;
24         while (rrs) {
25                 next = rrs->next;
26                 if (deep) {
27                         ldns_rr_free(rrs->rr);
28                 }
29                 LDNS_FREE(rrs);
30                 rrs = next;
31         }
32 }
33
34 void
35 ldns_dnssec_rrs_free(ldns_dnssec_rrs *rrs)
36 {
37         ldns_dnssec_rrs_free_internal(rrs, 0);
38 }
39
40 void
41 ldns_dnssec_rrs_deep_free(ldns_dnssec_rrs *rrs)
42 {
43         ldns_dnssec_rrs_free_internal(rrs, 1);
44 }
45
46 ldns_status
47 ldns_dnssec_rrs_add_rr(ldns_dnssec_rrs *rrs, ldns_rr *rr)
48 {
49         int cmp;
50         ldns_dnssec_rrs *new_rrs;
51         if (!rrs || !rr) {
52                 return LDNS_STATUS_ERR;
53         }
54
55         /* this could be done more efficiently; name and type should already
56            be equal */
57         cmp = ldns_rr_compare(rrs->rr,
58                                           rr);
59         /* should we error on equal? */
60         if (cmp <= 0) {
61                 if (rrs->next) {
62                         return ldns_dnssec_rrs_add_rr(rrs->next, rr);
63                 } else {
64                         new_rrs = ldns_dnssec_rrs_new();
65                         new_rrs->rr = rr;
66                         rrs->next = new_rrs;
67                 }
68         } else if (cmp > 0) {
69                 /* put the current old rr in the new next, put the new
70                    rr in the current container */
71                 new_rrs = ldns_dnssec_rrs_new();
72                 new_rrs->rr = rrs->rr;
73                 new_rrs->next = rrs->next;
74                 rrs->rr = rr;
75                 rrs->next = new_rrs;
76         }
77         return LDNS_STATUS_OK;
78 }
79
80 void
81 ldns_dnssec_rrs_print(FILE *out, ldns_dnssec_rrs *rrs)
82 {
83         if (!rrs) {
84                 fprintf(out, "<void>");
85         } else {
86                 if (rrs->rr) {
87                         ldns_rr_print(out, rrs->rr);
88                 }
89                 if (rrs->next) {
90                         ldns_dnssec_rrs_print(out, rrs->next);
91                 }
92         }
93 }
94
95 ldns_dnssec_rrsets *
96 ldns_dnssec_rrsets_new()
97 {
98         ldns_dnssec_rrsets *new_rrsets;
99         new_rrsets = LDNS_MALLOC(ldns_dnssec_rrsets);
100         if(!new_rrsets) return NULL;
101         new_rrsets->rrs = NULL;
102         new_rrsets->type = 0;
103         new_rrsets->signatures = NULL;
104         new_rrsets->next = NULL;
105         return new_rrsets;
106 }
107
108 INLINE void
109 ldns_dnssec_rrsets_free_internal(ldns_dnssec_rrsets *rrsets, int deep)
110 {
111         if (rrsets) {
112                 if (rrsets->rrs) {
113                         ldns_dnssec_rrs_free_internal(rrsets->rrs, deep);
114                 }
115                 if (rrsets->next) {
116                         ldns_dnssec_rrsets_free_internal(rrsets->next, deep);
117                 }
118                 if (rrsets->signatures) {
119                         ldns_dnssec_rrs_free_internal(rrsets->signatures, deep);
120                 }
121                 LDNS_FREE(rrsets);
122         }
123 }
124
125 void
126 ldns_dnssec_rrsets_free(ldns_dnssec_rrsets *rrsets)
127 {
128         ldns_dnssec_rrsets_free_internal(rrsets, 0);
129 }
130
131 void
132 ldns_dnssec_rrsets_deep_free(ldns_dnssec_rrsets *rrsets)
133 {
134         ldns_dnssec_rrsets_free_internal(rrsets, 1);
135 }
136
137 ldns_rr_type
138 ldns_dnssec_rrsets_type(ldns_dnssec_rrsets *rrsets)
139 {
140         if (rrsets) {
141                 return rrsets->type;
142         } else {
143                 return 0;
144         }
145 }
146
147 ldns_status
148 ldns_dnssec_rrsets_set_type(ldns_dnssec_rrsets *rrsets,
149                                            ldns_rr_type type)
150 {
151         if (rrsets) {
152                 rrsets->type = type;
153                 return LDNS_STATUS_OK;
154         }
155         return LDNS_STATUS_ERR;
156 }
157
158 ldns_dnssec_rrsets *
159 ldns_dnssec_rrsets_new_frm_rr(ldns_rr *rr)
160 {
161         ldns_dnssec_rrsets *new_rrsets;
162         ldns_rr_type rr_type;
163         bool rrsig;
164
165         new_rrsets = ldns_dnssec_rrsets_new();
166         rr_type = ldns_rr_get_type(rr);
167         if (rr_type == LDNS_RR_TYPE_RRSIG) {
168                 rrsig = true;
169                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
170         } else {
171                 rrsig = false;
172         }
173         if (!rrsig) {
174                 new_rrsets->rrs = ldns_dnssec_rrs_new();
175                 new_rrsets->rrs->rr = rr;
176         } else {
177                 new_rrsets->signatures = ldns_dnssec_rrs_new();
178                 new_rrsets->signatures->rr = rr;
179         }
180         new_rrsets->type = rr_type;
181         return new_rrsets;
182 }
183
184 ldns_status
185 ldns_dnssec_rrsets_add_rr(ldns_dnssec_rrsets *rrsets, ldns_rr *rr)
186 {
187         ldns_dnssec_rrsets *new_rrsets;
188         ldns_rr_type rr_type;
189         bool rrsig = false;
190         ldns_status result = LDNS_STATUS_OK;
191
192         if (!rrsets || !rr) {
193                 return LDNS_STATUS_ERR;
194         }
195
196         rr_type = ldns_rr_get_type(rr);
197
198         if (rr_type == LDNS_RR_TYPE_RRSIG) {
199                 rrsig = true;
200                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
201         }
202
203         if (!rrsets->rrs && rrsets->type == 0 && !rrsets->signatures) {
204                 if (!rrsig) {
205                         rrsets->rrs = ldns_dnssec_rrs_new();
206                         rrsets->rrs->rr = rr;
207                         rrsets->type = rr_type;
208                 } else {
209                         rrsets->signatures = ldns_dnssec_rrs_new();
210                         rrsets->signatures->rr = rr;
211                         rrsets->type = rr_type;
212                 }
213                 return LDNS_STATUS_OK;
214         }
215
216         if (rr_type > ldns_dnssec_rrsets_type(rrsets)) {
217                 if (rrsets->next) {
218                         result = ldns_dnssec_rrsets_add_rr(rrsets->next, rr);
219                 } else {
220                         new_rrsets = ldns_dnssec_rrsets_new_frm_rr(rr);
221                         rrsets->next = new_rrsets;
222                 }
223         } else if (rr_type < ldns_dnssec_rrsets_type(rrsets)) {
224                 /* move the current one into the new next, 
225                    replace field of current with data from new rr */
226                 new_rrsets = ldns_dnssec_rrsets_new();
227                 new_rrsets->rrs = rrsets->rrs;
228                 new_rrsets->type = rrsets->type;
229                 new_rrsets->signatures = rrsets->signatures;
230                 new_rrsets->next = rrsets->next;
231                 if (!rrsig) {
232                         rrsets->rrs = ldns_dnssec_rrs_new();
233                         rrsets->rrs->rr = rr;
234                         rrsets->signatures = NULL;
235                 } else {
236                         rrsets->rrs = NULL;
237                         rrsets->signatures = ldns_dnssec_rrs_new();
238                         rrsets->signatures->rr = rr;
239                 }
240                 rrsets->type = rr_type;
241                 rrsets->next = new_rrsets;
242         } else {
243                 /* equal, add to current rrsets */
244                 if (rrsig) {
245                         if (rrsets->signatures) {
246                                 result = ldns_dnssec_rrs_add_rr(rrsets->signatures, rr);
247                         } else {
248                                 rrsets->signatures = ldns_dnssec_rrs_new();
249                                 rrsets->signatures->rr = rr;
250                         }
251                 } else {
252                         if (rrsets->rrs) {
253                                 result = ldns_dnssec_rrs_add_rr(rrsets->rrs, rr);
254                         } else {
255                                 rrsets->rrs = ldns_dnssec_rrs_new();
256                                 rrsets->rrs->rr = rr;
257                         }
258                 }
259         }
260
261         return result;
262 }
263
264 void
265 ldns_dnssec_rrsets_print_soa(FILE *out,
266                                             ldns_dnssec_rrsets *rrsets,
267                                             bool follow,
268                                             bool show_soa)
269 {
270         if (!rrsets) {
271                 fprintf(out, "<void>\n");
272         } else {
273                 if (rrsets->rrs &&
274                     (show_soa ||
275                         ldns_rr_get_type(rrsets->rrs->rr) != LDNS_RR_TYPE_SOA
276                     )
277                    ) {
278                         ldns_dnssec_rrs_print(out, rrsets->rrs);
279                         if (rrsets->signatures) {
280                                 ldns_dnssec_rrs_print(out, rrsets->signatures);
281                         }
282                 }
283                 if (follow && rrsets->next) {
284                         ldns_dnssec_rrsets_print_soa(out, rrsets->next, follow, show_soa);
285                 }
286         }
287 }
288
289 void
290 ldns_dnssec_rrsets_print(FILE *out, ldns_dnssec_rrsets *rrsets, bool follow)
291 {
292         ldns_dnssec_rrsets_print_soa(out, rrsets, follow, true);
293 }
294
295 ldns_dnssec_name *
296 ldns_dnssec_name_new()
297 {
298         ldns_dnssec_name *new_name;
299
300         new_name = LDNS_MALLOC(ldns_dnssec_name);
301         if (!new_name) {
302                 return NULL;
303         }
304
305         new_name->name = NULL;
306         new_name->rrsets = NULL;
307         new_name->name_alloced = false;
308         new_name->nsec = NULL;
309         new_name->nsec_signatures = NULL;
310
311         new_name->is_glue = false;
312         new_name->hashed_name = NULL;
313
314         return new_name;
315 }
316
317 ldns_dnssec_name *
318 ldns_dnssec_name_new_frm_rr(ldns_rr *rr)
319 {
320         ldns_dnssec_name *new_name = ldns_dnssec_name_new();
321
322         new_name->name = ldns_rr_owner(rr);
323         if(ldns_dnssec_name_add_rr(new_name, rr) != LDNS_STATUS_OK) {
324                 ldns_dnssec_name_free(new_name);
325                 return NULL;
326         }
327
328         return new_name;
329 }
330
331 INLINE void
332 ldns_dnssec_name_free_internal(ldns_dnssec_name *name,
333                                int deep)
334 {
335         if (name) {
336                 if (name->name_alloced) {
337                         ldns_rdf_deep_free(name->name);
338                 }
339                 if (name->rrsets) {
340                         ldns_dnssec_rrsets_free_internal(name->rrsets, deep);
341                 }
342                 if (name->nsec && deep) {
343                         ldns_rr_free(name->nsec);
344                 }
345                 if (name->nsec_signatures) {
346                         ldns_dnssec_rrs_free_internal(name->nsec_signatures, deep);
347                 }
348                 if (name->hashed_name) {
349                         if (deep) {
350                                 ldns_rdf_deep_free(name->hashed_name);
351                         }
352                 }
353                 LDNS_FREE(name);
354         }
355 }
356
357 void
358 ldns_dnssec_name_free(ldns_dnssec_name *name)
359 {
360   ldns_dnssec_name_free_internal(name, 0);
361 }
362
363 void
364 ldns_dnssec_name_deep_free(ldns_dnssec_name *name)
365 {
366   ldns_dnssec_name_free_internal(name, 1);
367 }
368
369 ldns_rdf *
370 ldns_dnssec_name_name(ldns_dnssec_name *name)
371 {
372         if (name) {
373                 return name->name;
374         }
375         return NULL;
376 }
377
378 void
379 ldns_dnssec_name_set_name(ldns_dnssec_name *rrset,
380                                          ldns_rdf *dname)
381 {
382         if (rrset && dname) {
383                 rrset->name = dname;
384         }
385 }
386
387 ldns_rr *
388 ldns_dnssec_name_nsec(ldns_dnssec_name *rrset)
389 {
390         if (rrset) {
391                 return rrset->nsec;
392         }
393         return NULL;
394 }
395
396 void
397 ldns_dnssec_name_set_nsec(ldns_dnssec_name *rrset, ldns_rr *nsec)
398 {
399         if (rrset && nsec) {
400                 rrset->nsec = nsec;
401         }
402 }
403
404 int
405 ldns_dnssec_name_cmp(const void *a, const void *b)
406 {
407         ldns_dnssec_name *na = (ldns_dnssec_name *) a;
408         ldns_dnssec_name *nb = (ldns_dnssec_name *) b;
409
410         if (na && nb) {
411                 return ldns_dname_compare(ldns_dnssec_name_name(na),
412                                                          ldns_dnssec_name_name(nb));
413         } else if (na) {
414                 return 1;
415         } else if (nb) {
416                 return -1;
417         } else {
418                 return 0;
419         }
420 }
421
422 ldns_status
423 ldns_dnssec_name_add_rr(ldns_dnssec_name *name,
424                                     ldns_rr *rr)
425 {
426         ldns_status result = LDNS_STATUS_OK;
427         ldns_rdf *name_name;
428         bool hashed_name = false;
429         ldns_rr_type rr_type;
430         ldns_rr_type typecovered = 0;
431
432         /* special handling for NSEC3 and NSECX covering RRSIGS */
433
434         if (!name || !rr) {
435                 return LDNS_STATUS_ERR;
436         }
437
438         rr_type = ldns_rr_get_type(rr);
439
440         if (rr_type == LDNS_RR_TYPE_RRSIG) {
441                 typecovered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
442         }
443
444 #ifdef HAVE_SSL
445         if (rr_type == LDNS_RR_TYPE_NSEC3 ||
446             typecovered == LDNS_RR_TYPE_NSEC3) {
447                 name_name = ldns_nsec3_hash_name_frm_nsec3(rr,
448                                                                                    ldns_dnssec_name_name(name));
449                 hashed_name = true;
450         } else {
451                 name_name = ldns_dnssec_name_name(name);
452         }
453 #else
454         name_name = ldns_dnssec_name_name(name);
455 #endif /* HAVE_SSL */
456
457         if (rr_type == LDNS_RR_TYPE_NSEC ||
458             rr_type == LDNS_RR_TYPE_NSEC3) {
459                 /* XX check if is already set (and error?) */
460                 name->nsec = rr;
461         } else if (typecovered == LDNS_RR_TYPE_NSEC ||
462                          typecovered == LDNS_RR_TYPE_NSEC3) {
463                 if (name->nsec_signatures) {
464                         result = ldns_dnssec_rrs_add_rr(name->nsec_signatures, rr);
465                 } else {
466                         name->nsec_signatures = ldns_dnssec_rrs_new();
467                         name->nsec_signatures->rr = rr;
468                 }
469         } else {
470                 /* it's a 'normal' RR, add it to the right rrset */
471                 if (name->rrsets) {
472                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
473                 } else {
474                         name->rrsets = ldns_dnssec_rrsets_new();
475                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
476                 }
477         }
478
479         if (hashed_name) {
480                 ldns_rdf_deep_free(name_name);
481         }
482
483         return result;
484 }
485
486 ldns_dnssec_rrsets *
487 ldns_dnssec_name_find_rrset(ldns_dnssec_name *name,
488                                            ldns_rr_type type) {
489         ldns_dnssec_rrsets *result;
490
491         result = name->rrsets;
492         while (result) {
493                 if (result->type == type) {
494                         return result;
495                 } else {
496                         result = result->next;
497                 }
498         }
499         return NULL;
500 }
501
502 ldns_dnssec_rrsets *
503 ldns_dnssec_zone_find_rrset(ldns_dnssec_zone *zone,
504                                            ldns_rdf *dname,
505                                            ldns_rr_type type)
506 {
507         ldns_rbnode_t *node;
508
509         if (!zone || !dname) {
510                 return NULL;
511         }
512
513         node = ldns_rbtree_search(zone->names, dname);
514         if (node) {
515                 return ldns_dnssec_name_find_rrset((ldns_dnssec_name *)node->data,
516                                                                         type);
517         } else {
518                 return NULL;
519         }
520 }
521
522 void
523 ldns_dnssec_name_print_soa(FILE *out, ldns_dnssec_name *name, bool show_soa)
524 {
525         if (name) {
526                 if(name->rrsets) {
527                         ldns_dnssec_rrsets_print_soa(out, name->rrsets, true, show_soa);
528                 } else {
529                         fprintf(out, ";; Empty nonterminal: ");
530                         ldns_rdf_print(out, name->name);
531                         fprintf(out, "\n");
532                 }
533                 if(name->nsec) {
534                         ldns_rr_print(out, name->nsec);
535                 }
536                 if (name->nsec_signatures) {
537                         ldns_dnssec_rrs_print(out, name->nsec_signatures);
538                 }
539         } else {
540                 fprintf(out, "<void>\n");
541         }
542 }
543
544 void
545 ldns_dnssec_name_print(FILE *out, ldns_dnssec_name *name)
546 {
547         ldns_dnssec_name_print_soa(out, name, true);
548 }
549
550 ldns_dnssec_zone *
551 ldns_dnssec_zone_new()
552 {
553         ldns_dnssec_zone *zone = LDNS_MALLOC(ldns_dnssec_zone);
554         if(!zone) return NULL;
555         zone->soa = NULL;
556         zone->names = NULL;
557
558         return zone;
559 }
560
561 void
562 ldns_dnssec_name_node_free(ldns_rbnode_t *node, void *arg) {
563         (void) arg;
564         ldns_dnssec_name_free((ldns_dnssec_name *)node->data);
565         free(node);
566 }
567
568 void
569 ldns_dnssec_name_node_deep_free(ldns_rbnode_t *node, void *arg) {
570         (void) arg;
571         ldns_dnssec_name_deep_free((ldns_dnssec_name *)node->data);
572         free(node);
573 }
574
575 void
576 ldns_dnssec_zone_free(ldns_dnssec_zone *zone)
577 {
578         if (zone) {
579                 if (zone->names) {
580                         /* destroy all name structures within the tree */
581                         ldns_traverse_postorder(zone->names,
582                                                     ldns_dnssec_name_node_free,
583                                                     NULL);
584                         free(zone->names);
585                 }
586                 LDNS_FREE(zone);
587         }
588 }
589
590 void
591 ldns_dnssec_zone_deep_free(ldns_dnssec_zone *zone)
592 {
593         if (zone) {
594                 if (zone->names) {
595                         /* destroy all name structures within the tree */
596                         ldns_traverse_postorder(zone->names,
597                                                     ldns_dnssec_name_node_deep_free,
598                                                     NULL);
599                         free(zone->names);
600                 }
601                 LDNS_FREE(zone);
602         }
603 }
604
605 /* use for dname comparison in tree */
606 int
607 ldns_dname_compare_v(const void *a, const void *b) {
608         return ldns_dname_compare((ldns_rdf *)a, (ldns_rdf *)b);
609 }
610
611 #ifdef HAVE_SSL
612 ldns_rbnode_t *
613 ldns_dnssec_zone_find_nsec3_original(ldns_dnssec_zone *zone,
614                                      ldns_rr *rr) {
615         ldns_rbnode_t *current_node = ldns_rbtree_first(zone->names);
616         ldns_dnssec_name *current_name;
617         ldns_rdf *hashed_name;
618
619         hashed_name = ldns_dname_label(ldns_rr_owner(rr), 0);
620
621         while (current_node != LDNS_RBTREE_NULL) {
622                 current_name = (ldns_dnssec_name *) current_node->data;
623                 if (!current_name->hashed_name) {
624                         current_name->hashed_name =
625                                 ldns_nsec3_hash_name_frm_nsec3(rr, current_name->name);
626                 }
627                 if (ldns_dname_compare(hashed_name,
628                                                    current_name->hashed_name)
629                     == 0) {
630                         ldns_rdf_deep_free(hashed_name);
631                         return current_node;
632                 }
633                 current_node = ldns_rbtree_next(current_node);
634         }
635         ldns_rdf_deep_free(hashed_name);
636         return NULL;
637 }
638
639 ldns_status
640 ldns_dnssec_zone_add_rr(ldns_dnssec_zone *zone, ldns_rr *rr)
641 {
642         ldns_status result = LDNS_STATUS_OK;
643         ldns_dnssec_name *cur_name;
644         ldns_rbnode_t *cur_node;
645         ldns_rr_type type_covered = 0;
646
647         if (!zone || !rr) {
648                 return LDNS_STATUS_ERR;
649         }
650
651         if (!zone->names) {
652                 zone->names = ldns_rbtree_create(ldns_dname_compare_v);
653                 if(!zone->names) return LDNS_STATUS_MEM_ERR;
654         }
655
656         /* we need the original of the hashed name if this is
657            an NSEC3, or an RRSIG that covers an NSEC3 */
658         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG) {
659                 type_covered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
660         }
661         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 ||
662             type_covered == LDNS_RR_TYPE_NSEC3) {
663                 cur_node = ldns_dnssec_zone_find_nsec3_original(zone,
664                                                                                            rr);
665                 if (!cur_node) {
666                         return LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND;
667                 }
668         } else {
669                 cur_node = ldns_rbtree_search(zone->names, ldns_rr_owner(rr));
670         }
671
672         if (!cur_node) {
673                 /* add */
674                 cur_name = ldns_dnssec_name_new_frm_rr(rr);
675                 if(!cur_name) return LDNS_STATUS_MEM_ERR;
676                 cur_node = LDNS_MALLOC(ldns_rbnode_t);
677                 if(!cur_node) {
678                         ldns_dnssec_name_free(cur_name);
679                         return LDNS_STATUS_MEM_ERR;
680                 }
681                 cur_node->key = ldns_rr_owner(rr);
682                 cur_node->data = cur_name;
683                 (void)ldns_rbtree_insert(zone->names, cur_node);
684         } else {
685                 cur_name = (ldns_dnssec_name *) cur_node->data;
686                 result = ldns_dnssec_name_add_rr(cur_name, rr);
687         }
688
689         if (result != LDNS_STATUS_OK) {
690                 fprintf(stderr, "error adding rr: ");
691                 ldns_rr_print(stderr, rr);
692         }
693
694         /*TODO ldns_dnssec_name_print_names(stdout, zone->names, 0);*/
695         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_SOA) {
696                 zone->soa = cur_name;
697         }
698
699         return result;
700 }
701 #endif /* HAVE_SSL */
702
703 void
704 ldns_dnssec_zone_names_print(FILE *out, ldns_rbtree_t *tree, bool print_soa)
705 {
706         ldns_rbnode_t *node;
707         ldns_dnssec_name *name;
708
709         node = ldns_rbtree_first(tree);
710         while (node != LDNS_RBTREE_NULL) {
711                 name = (ldns_dnssec_name *) node->data;
712                 ldns_dnssec_name_print_soa(out, name, print_soa);
713                 fprintf(out, ";\n");
714                 node = ldns_rbtree_next(node);
715         }
716 }
717
718 void
719 ldns_dnssec_zone_print(FILE *out, ldns_dnssec_zone *zone)
720 {
721         if (zone) {
722                 if (zone->soa) {
723                         fprintf(out, ";; Zone: ");
724                         ldns_rdf_print(out, ldns_dnssec_name_name(zone->soa));
725                         fprintf(out, "\n;\n");
726                         ldns_dnssec_rrsets_print(
727                             out,
728                             ldns_dnssec_name_find_rrset(zone->soa,
729                                                                           LDNS_RR_TYPE_SOA),
730                             false);
731                         fprintf(out, ";\n");
732                 }
733
734                 if (zone->names) {
735                         ldns_dnssec_zone_names_print(out, zone->names, false);
736                 }
737         }
738 }
739
740 ldns_status
741 ldns_dnssec_zone_add_empty_nonterminals(ldns_dnssec_zone *zone)
742 {
743         ldns_dnssec_name *new_name;
744         ldns_rdf *cur_name;
745         ldns_rdf *next_name;
746         ldns_rbnode_t *cur_node, *next_node, *new_node;
747
748         /* for the detection */
749         uint16_t i, cur_label_count, next_label_count;
750         uint16_t soa_label_count = 0;
751         ldns_rdf *l1, *l2;
752         int lpos;
753
754         if (!zone) {
755                 return LDNS_STATUS_ERR;
756         }
757         if (zone->soa && zone->soa->name) {
758                 soa_label_count = ldns_dname_label_count(zone->soa->name);
759         }
760         
761         cur_node = ldns_rbtree_first(zone->names);
762         while (cur_node != LDNS_RBTREE_NULL) {
763                 next_node = ldns_rbtree_next(cur_node);
764                 
765                 /* skip glue */
766                 while (next_node != LDNS_RBTREE_NULL && 
767                        next_node->data &&
768                        ((ldns_dnssec_name *)next_node->data)->is_glue
769                 ) {
770                         next_node = ldns_rbtree_next(next_node);
771                 }
772
773                 if (next_node == LDNS_RBTREE_NULL) {
774                         next_node = ldns_rbtree_first(zone->names);
775                 }
776
777                 cur_name = ((ldns_dnssec_name *)cur_node->data)->name;
778                 next_name = ((ldns_dnssec_name *)next_node->data)->name;
779                 cur_label_count = ldns_dname_label_count(cur_name);
780                 next_label_count = ldns_dname_label_count(next_name);
781
782                 /* Since the names are in canonical order, we can
783                  * recognize empty non-terminals by their labels;
784                  * every label after the first one on the next owner
785                  * name is a non-terminal if it either does not exist
786                  * in the current name or is different from the same
787                  * label in the current name (counting from the end)
788                  */
789                 for (i = 1; i < next_label_count - soa_label_count; i++) {
790                         lpos = (int)cur_label_count - (int)next_label_count + (int)i;
791                         if (lpos >= 0) {
792                                 l1 = ldns_dname_label(cur_name, (uint8_t)lpos);
793                         } else {
794                                 l1 = NULL;
795                         }
796                         l2 = ldns_dname_label(next_name, i);
797
798                         if (!l1 || ldns_dname_compare(l1, l2) != 0) {
799                                 /* We have an empty nonterminal, add it to the
800                                  * tree
801                                  */
802                                 new_name = ldns_dnssec_name_new();
803                                 if (!new_name) {
804                                         return LDNS_STATUS_MEM_ERR;
805                                 }
806                                 new_name->name = ldns_dname_clone_from(next_name,
807                                                                        i);
808                                 if (!new_name) {
809                                         ldns_dnssec_name_free(new_name);
810                                         return LDNS_STATUS_MEM_ERR;
811                                 }
812                                 new_name->name_alloced = true;
813                                 new_node = LDNS_MALLOC(ldns_rbnode_t);
814                                 if (!new_node) {
815                                         ldns_dnssec_name_free(new_name);
816                                         return LDNS_STATUS_MEM_ERR;
817                                 }
818                                 new_node->key = new_name->name;
819                                 new_node->data = new_name;
820                                 (void)ldns_rbtree_insert(zone->names, new_node);
821                         }
822                         ldns_rdf_deep_free(l1);
823                         ldns_rdf_deep_free(l2);
824                 }
825                 
826                 /* we might have inserted a new node after
827                  * the current one so we can't just use next()
828                  */
829                 if (next_node != ldns_rbtree_first(zone->names)) {
830                         cur_node = next_node;
831                 } else {
832                         cur_node = LDNS_RBTREE_NULL;
833                 }
834         }
835         return LDNS_STATUS_OK;
836 }