Fossil SCM

Join duplicated footnotes slightly faster. Fix a comment about auxiliary <tt>cmp_footnote_id()</tt> function.

george 2022-02-09 20:09 markdown-footnotes
Commit 7f6a641808be00f8e68b5c23ce1ec8f3a1964ba53da68ed6076aa8d32fce6471
Parent 92221aaa192e82e…
1 file changed +29 -36
~ src/markdown.c
M src/markdown.c
+29 -36
--- src/markdown.c
+++ src/markdown.c
@@ -274,11 +274,11 @@
274274
 return blob_compare(&lra->id, &lrb->id);
275275
 }
276276
277277
 /* cmp_footnote_id -- comparison function for footnotes qsort.
278278
 * Empty IDs sort last (in undetermined order).
279
- * Equal IDs are sorted in the REVERSED order of definition in the source */
279
+ * Equal IDs are sorted in the order of definition in the source */
280280
 static int cmp_footnote_id(const void *fna, const void *fnb){
281281
 const struct footnote *a = fna, *b = fnb;
282282
 const int szA = blob_size(&a->id), szB = blob_size(&b->id);
283283
 if( szA ){
284284
 if( szB ){
@@ -2498,10 +2498,11 @@
24982498
 struct link_ref *lr;
24992499
 struct footnote *fn;
25002500
 size_t i, beg, end = 0;
25012501
 struct render rndr;
25022502
 Blob text = BLOB_INITIALIZER; /* input after the first pass */
2503
+ Blob *allNotes = &rndr.notes.all;
25032504
25042505
 /* filling the render structure */
25052506
 if( !rndrer ) return;
25062507
 rndr.make = *rndrer;
25072508
 rndr.nBlobCache = 0;
@@ -2565,24 +2566,26 @@
25652566
 qsort(blob_buffer(&rndr.refs),
25662567
 blob_size(&rndr.refs)/sizeof(struct link_ref),
25672568
 sizeof(struct link_ref),
25682569
 cmp_link_ref_sort);
25692570
 }
2570
- rndr.notes.nLbled = COUNT_FOOTNOTES(&rndr.notes.all);
2571
+ rndr.notes.nLbled = COUNT_FOOTNOTES( allNotes );
25712572
25722573
 /* sort footnotes by ID and join duplicates */
25732574
 if( rndr.notes.nLbled > 1 ){
2574
- fn = CAST_AS_FOOTNOTES(&rndr.notes.all);
2575
+ int nDups = 0;
2576
+ fn = CAST_AS_FOOTNOTES( allNotes );
25752577
 qsort(fn, rndr.notes.nLbled, sizeof(struct footnote), cmp_footnote_id);
25762578
25772579
 /* concatenate footnotes with equal labels */
25782580
 for(i=0; i<rndr.notes.nLbled ;){
25792581
 struct footnote *x = fn + i;
25802582
 size_t j = i+1, k = blob_size(&x->text) + 64;
25812583
 while(j<rndr.notes.nLbled && !blob_compare(&x->id, &fn[j].id)){
25822584
 k += blob_size(&fn[j].text) + 10;
25832585
 j++;
2586
+ nDups++;
25842587
 }
25852588
 if( i+1<j ){
25862589
 Blob tmp = empty_blob;
25872590
 blob_reserve(&tmp, k);
25882591
 blob_append_string(&tmp, "<ul class='footnote-joined'>\n");
@@ -2592,76 +2595,66 @@
25922595
 blob_append(&tmp, blob_buffer(&y->text), blob_size(&y->text));
25932596
 blob_append_string(&tmp, "</li>\n");
25942597
25952598
 /* free memory buffer */
25962599
 blob_reset(&y->text);
2597
- if( k!=i ){
2598
- blob_reset(&y->id);
2599
- /* invalidate redundant elements (this is optional) */
2600
- memset(y,0,sizeof(struct footnote));
2601
- y->index = y->defno = y->iMark = y->nUsed = -42;
2602
- }
2600
+ if( k!=i ) blob_reset(&y->id);
26032601
 }
26042602
 blob_append_string(&tmp, "</ul>\n");
26052603
 x->text = tmp;
26062604
 }
26072605
 i = j;
26082606
 }
2609
-
2610
- /* move redundant elements to the end of array and truncate/resize */
2611
- qsort(fn, rndr.notes.nLbled, sizeof(struct footnote), cmp_footnote_id);
2612
- i = rndr.notes.nLbled;
2613
- while( i && !blob_size(&fn[i-1].id) ){ i--; }
2614
- rndr.notes.nLbled = i;
2615
- blob_resize( &rndr.notes.all, i*sizeof(struct footnote) );
2616
-
2617
- /* FIXME: It was expected to work via truncation:
2618
- *
2619
- * blob_truncate( &rndr.notes.all, i*sizeof(struct footnote) );
2620
- *
2621
- * but that way it crashes with
2622
- *
2623
- * free(): double free detected in tcache 2
2624
- *
2625
- * This is strange. */
2626
- }
2627
- assert( COUNT_FOOTNOTES(&rndr.notes.all) == rndr.notes.nLbled );
2628
- fn = CAST_AS_FOOTNOTES(&rndr.notes.all);
2607
+ if( nDups ){ /* clean rndr.notes.all from invalidated footnotes */
2608
+ const int n = rndr.notes.nLbled - nDups;
2609
+ struct Blob filtered = empty_blob;
2610
+ blob_reserve(&filtered, n*sizeof(struct footnote));
2611
+ for(i=0; i<rndr.notes.nLbled; i++){
2612
+ if( blob_size(&fn[i].id) ){
2613
+ blob_append(&filtered, (char*)(fn+i), sizeof(struct footnote));
2614
+ }
2615
+ }
2616
+ blob_reset( allNotes );
2617
+ rndr.notes.all = filtered;
2618
+ rndr.notes.nLbled = n;
2619
+ assert( COUNT_FOOTNOTES(allNotes) == rndr.notes.nLbled );
2620
+ }
2621
+ }
2622
+ fn = CAST_AS_FOOTNOTES( allNotes );
26292623
 for(i=0; i<rndr.notes.nLbled; i++){
26302624
 fn[i].index = i;
26312625
 }
26322626
 assert( rndr.notes.nMarks==0 );
26332627
26342628
 /* second pass: actual rendering */
26352629
 if( rndr.make.prolog ) rndr.make.prolog(ob, rndr.make.opaque);
26362630
 parse_block(ob, &rndr, blob_buffer(&text), blob_size(&text));
26372631
2638
- if( (blob_size(&rndr.notes.all) || rndr.notes.misref.nUsed) ){
2632
+ if( (blob_size(allNotes) || rndr.notes.misref.nUsed) ){
26392633
26402634
 /* Footnotes must be parsed for the correct discovery of (back)links */
26412635
 Blob *notes = new_work_buffer( &rndr );
26422636
 Blob *tmp = new_work_buffer( &rndr );
2643
- const struct Blob *origin = &rndr.notes.all;
26442637
 int nMarks = -1;
26452638
26462639
 /* inline notes may get appended to rndr.notes.all while rendering */
26472640
 while(1){
26482641
 struct footnote *aNotes;
2649
- const int N = COUNT_FOOTNOTES(origin);
2642
+ const int N = COUNT_FOOTNOTES( allNotes );
26502643
26512644
 /* make a shallow copy of `origin` */
26522645
 blob_truncate(notes,0);
2653
- blob_append(notes, blob_buffer(origin), blob_size(origin));
2646
+ blob_append(notes, blob_buffer(allNotes), blob_size(allNotes));
26542647
 aNotes = CAST_AS_FOOTNOTES(notes);
26552648
 qsort(aNotes, N, sizeof(struct footnote), cmp_footnote_sort);
26562649
26572650
 if( nMarks == rndr.notes.nMarks ) break;
26582651
 nMarks = rndr.notes.nMarks;
26592652
26602653
 for(i=0; i<N; i++){
26612654
 const int j = aNotes[i].index;
2662
- struct footnote *x = CAST_AS_FOOTNOTES(origin) + j;
2655
+ struct footnote *x = CAST_AS_FOOTNOTES(allNotes) + j;
26632656
 assert( 0<=j && j<N );
26642657
 if( x->bRndred || !x->nUsed ) continue;
26652658
 assert( x->iMark > 0 );
26662659
 assert( blob_size(&x->text) );
26672660
 blob_truncate(tmp,0);
@@ -2708,16 +2701,16 @@
27082701
 blob_reset(&lr[i].id);
27092702
 blob_reset(&lr[i].link);
27102703
 blob_reset(&lr[i].title);
27112704
 }
27122705
 blob_reset(&rndr.refs);
2713
- fn = CAST_AS_FOOTNOTES(&rndr.notes.all);
2714
- end = COUNT_FOOTNOTES(&rndr.notes.all);
2706
+ fn = CAST_AS_FOOTNOTES( allNotes );
2707
+ end = COUNT_FOOTNOTES( allNotes );
27152708
 for(i=0; i<end; i++){
27162709
 if(blob_size(&fn[i].id)) blob_reset(&fn[i].id);
27172710
 blob_reset(&fn[i].text);
27182711
 }
27192712
 blob_reset(&rndr.notes.all);
27202713
 for(i=0; i<rndr.nBlobCache; i++){
27212714
 fossil_free(rndr.aBlobCache[i]);
27222715
 }
27232716
 }
27242717
--- src/markdown.c
+++ src/markdown.c
@@ -274,11 +274,11 @@
274 return blob_compare(&lra->id, &lrb->id);
275 }
276
277 /* cmp_footnote_id -- comparison function for footnotes qsort.
278 * Empty IDs sort last (in undetermined order).
279 * Equal IDs are sorted in the REVERSED order of definition in the source */
280 static int cmp_footnote_id(const void *fna, const void *fnb){
281 const struct footnote *a = fna, *b = fnb;
282 const int szA = blob_size(&a->id), szB = blob_size(&b->id);
283 if( szA ){
284 if( szB ){
@@ -2498,10 +2498,11 @@
2498 struct link_ref *lr;
2499 struct footnote *fn;
2500 size_t i, beg, end = 0;
2501 struct render rndr;
2502 Blob text = BLOB_INITIALIZER; /* input after the first pass */
 
2503
2504 /* filling the render structure */
2505 if( !rndrer ) return;
2506 rndr.make = *rndrer;
2507 rndr.nBlobCache = 0;
@@ -2565,24 +2566,26 @@
2565 qsort(blob_buffer(&rndr.refs),
2566 blob_size(&rndr.refs)/sizeof(struct link_ref),
2567 sizeof(struct link_ref),
2568 cmp_link_ref_sort);
2569 }
2570 rndr.notes.nLbled = COUNT_FOOTNOTES(&rndr.notes.all);
2571
2572 /* sort footnotes by ID and join duplicates */
2573 if( rndr.notes.nLbled > 1 ){
2574 fn = CAST_AS_FOOTNOTES(&rndr.notes.all);
 
2575 qsort(fn, rndr.notes.nLbled, sizeof(struct footnote), cmp_footnote_id);
2576
2577 /* concatenate footnotes with equal labels */
2578 for(i=0; i<rndr.notes.nLbled ;){
2579 struct footnote *x = fn + i;
2580 size_t j = i+1, k = blob_size(&x->text) + 64;
2581 while(j<rndr.notes.nLbled && !blob_compare(&x->id, &fn[j].id)){
2582 k += blob_size(&fn[j].text) + 10;
2583 j++;
 
2584 }
2585 if( i+1<j ){
2586 Blob tmp = empty_blob;
2587 blob_reserve(&tmp, k);
2588 blob_append_string(&tmp, "<ul class='footnote-joined'>\n");
@@ -2592,76 +2595,66 @@
2592 blob_append(&tmp, blob_buffer(&y->text), blob_size(&y->text));
2593 blob_append_string(&tmp, "</li>\n");
2594
2595 /* free memory buffer */
2596 blob_reset(&y->text);
2597 if( k!=i ){
2598 blob_reset(&y->id);
2599 /* invalidate redundant elements (this is optional) */
2600 memset(y,0,sizeof(struct footnote));
2601 y->index = y->defno = y->iMark = y->nUsed = -42;
2602 }
2603 }
2604 blob_append_string(&tmp, "</ul>\n");
2605 x->text = tmp;
2606 }
2607 i = j;
2608 }
2609
2610 /* move redundant elements to the end of array and truncate/resize */
2611 qsort(fn, rndr.notes.nLbled, sizeof(struct footnote), cmp_footnote_id);
2612 i = rndr.notes.nLbled;
2613 while( i && !blob_size(&fn[i-1].id) ){ i--; }
2614 rndr.notes.nLbled = i;
2615 blob_resize( &rndr.notes.all, i*sizeof(struct footnote) );
2616
2617 /* FIXME: It was expected to work via truncation:
2618 *
2619 * blob_truncate( &rndr.notes.all, i*sizeof(struct footnote) );
2620 *
2621 * but that way it crashes with
2622 *
2623 * free(): double free detected in tcache 2
2624 *
2625 * This is strange. */
2626 }
2627 assert( COUNT_FOOTNOTES(&rndr.notes.all) == rndr.notes.nLbled );
2628 fn = CAST_AS_FOOTNOTES(&rndr.notes.all);
2629 for(i=0; i<rndr.notes.nLbled; i++){
2630 fn[i].index = i;
2631 }
2632 assert( rndr.notes.nMarks==0 );
2633
2634 /* second pass: actual rendering */
2635 if( rndr.make.prolog ) rndr.make.prolog(ob, rndr.make.opaque);
2636 parse_block(ob, &rndr, blob_buffer(&text), blob_size(&text));
2637
2638 if( (blob_size(&rndr.notes.all) || rndr.notes.misref.nUsed) ){
2639
2640 /* Footnotes must be parsed for the correct discovery of (back)links */
2641 Blob *notes = new_work_buffer( &rndr );
2642 Blob *tmp = new_work_buffer( &rndr );
2643 const struct Blob *origin = &rndr.notes.all;
2644 int nMarks = -1;
2645
2646 /* inline notes may get appended to rndr.notes.all while rendering */
2647 while(1){
2648 struct footnote *aNotes;
2649 const int N = COUNT_FOOTNOTES(origin);
2650
2651 /* make a shallow copy of `origin` */
2652 blob_truncate(notes,0);
2653 blob_append(notes, blob_buffer(origin), blob_size(origin));
2654 aNotes = CAST_AS_FOOTNOTES(notes);
2655 qsort(aNotes, N, sizeof(struct footnote), cmp_footnote_sort);
2656
2657 if( nMarks == rndr.notes.nMarks ) break;
2658 nMarks = rndr.notes.nMarks;
2659
2660 for(i=0; i<N; i++){
2661 const int j = aNotes[i].index;
2662 struct footnote *x = CAST_AS_FOOTNOTES(origin) + j;
2663 assert( 0<=j && j<N );
2664 if( x->bRndred || !x->nUsed ) continue;
2665 assert( x->iMark > 0 );
2666 assert( blob_size(&x->text) );
2667 blob_truncate(tmp,0);
@@ -2708,16 +2701,16 @@
2708 blob_reset(&lr[i].id);
2709 blob_reset(&lr[i].link);
2710 blob_reset(&lr[i].title);
2711 }
2712 blob_reset(&rndr.refs);
2713 fn = CAST_AS_FOOTNOTES(&rndr.notes.all);
2714 end = COUNT_FOOTNOTES(&rndr.notes.all);
2715 for(i=0; i<end; i++){
2716 if(blob_size(&fn[i].id)) blob_reset(&fn[i].id);
2717 blob_reset(&fn[i].text);
2718 }
2719 blob_reset(&rndr.notes.all);
2720 for(i=0; i<rndr.nBlobCache; i++){
2721 fossil_free(rndr.aBlobCache[i]);
2722 }
2723 }
2724
--- src/markdown.c
+++ src/markdown.c
@@ -274,11 +274,11 @@
274 return blob_compare(&lra->id, &lrb->id);
275 }
276
277 /* cmp_footnote_id -- comparison function for footnotes qsort.
278 * Empty IDs sort last (in undetermined order).
279 * Equal IDs are sorted in the order of definition in the source */
280 static int cmp_footnote_id(const void *fna, const void *fnb){
281 const struct footnote *a = fna, *b = fnb;
282 const int szA = blob_size(&a->id), szB = blob_size(&b->id);
283 if( szA ){
284 if( szB ){
@@ -2498,10 +2498,11 @@
2498 struct link_ref *lr;
2499 struct footnote *fn;
2500 size_t i, beg, end = 0;
2501 struct render rndr;
2502 Blob text = BLOB_INITIALIZER; /* input after the first pass */
2503 Blob *allNotes = &rndr.notes.all;
2504
2505 /* filling the render structure */
2506 if( !rndrer ) return;
2507 rndr.make = *rndrer;
2508 rndr.nBlobCache = 0;
@@ -2565,24 +2566,26 @@
2566 qsort(blob_buffer(&rndr.refs),
2567 blob_size(&rndr.refs)/sizeof(struct link_ref),
2568 sizeof(struct link_ref),
2569 cmp_link_ref_sort);
2570 }
2571 rndr.notes.nLbled = COUNT_FOOTNOTES( allNotes );
2572
2573 /* sort footnotes by ID and join duplicates */
2574 if( rndr.notes.nLbled > 1 ){
2575 int nDups = 0;
2576 fn = CAST_AS_FOOTNOTES( allNotes );
2577 qsort(fn, rndr.notes.nLbled, sizeof(struct footnote), cmp_footnote_id);
2578
2579 /* concatenate footnotes with equal labels */
2580 for(i=0; i<rndr.notes.nLbled ;){
2581 struct footnote *x = fn + i;
2582 size_t j = i+1, k = blob_size(&x->text) + 64;
2583 while(j<rndr.notes.nLbled && !blob_compare(&x->id, &fn[j].id)){
2584 k += blob_size(&fn[j].text) + 10;
2585 j++;
2586 nDups++;
2587 }
2588 if( i+1<j ){
2589 Blob tmp = empty_blob;
2590 blob_reserve(&tmp, k);
2591 blob_append_string(&tmp, "<ul class='footnote-joined'>\n");
@@ -2592,76 +2595,66 @@
2595 blob_append(&tmp, blob_buffer(&y->text), blob_size(&y->text));
2596 blob_append_string(&tmp, "</li>\n");
2597
2598 /* free memory buffer */
2599 blob_reset(&y->text);
2600 if( k!=i ) blob_reset(&y->id);
 
 
 
 
 
2601 }
2602 blob_append_string(&tmp, "</ul>\n");
2603 x->text = tmp;
2604 }
2605 i = j;
2606 }
2607 if( nDups ){ /* clean rndr.notes.all from invalidated footnotes */
2608 const int n = rndr.notes.nLbled - nDups;
2609 struct Blob filtered = empty_blob;
2610 blob_reserve(&filtered, n*sizeof(struct footnote));
2611 for(i=0; i<rndr.notes.nLbled; i++){
2612 if( blob_size(&fn[i].id) ){
2613 blob_append(&filtered, (char*)(fn+i), sizeof(struct footnote));
2614 }
2615 }
2616 blob_reset( allNotes );
2617 rndr.notes.all = filtered;
2618 rndr.notes.nLbled = n;
2619 assert( COUNT_FOOTNOTES(allNotes) == rndr.notes.nLbled );
2620 }
2621 }
2622 fn = CAST_AS_FOOTNOTES( allNotes );
 
 
 
 
2623 for(i=0; i<rndr.notes.nLbled; i++){
2624 fn[i].index = i;
2625 }
2626 assert( rndr.notes.nMarks==0 );
2627
2628 /* second pass: actual rendering */
2629 if( rndr.make.prolog ) rndr.make.prolog(ob, rndr.make.opaque);
2630 parse_block(ob, &rndr, blob_buffer(&text), blob_size(&text));
2631
2632 if( (blob_size(allNotes) || rndr.notes.misref.nUsed) ){
2633
2634 /* Footnotes must be parsed for the correct discovery of (back)links */
2635 Blob *notes = new_work_buffer( &rndr );
2636 Blob *tmp = new_work_buffer( &rndr );
 
2637 int nMarks = -1;
2638
2639 /* inline notes may get appended to rndr.notes.all while rendering */
2640 while(1){
2641 struct footnote *aNotes;
2642 const int N = COUNT_FOOTNOTES( allNotes );
2643
2644 /* make a shallow copy of `origin` */
2645 blob_truncate(notes,0);
2646 blob_append(notes, blob_buffer(allNotes), blob_size(allNotes));
2647 aNotes = CAST_AS_FOOTNOTES(notes);
2648 qsort(aNotes, N, sizeof(struct footnote), cmp_footnote_sort);
2649
2650 if( nMarks == rndr.notes.nMarks ) break;
2651 nMarks = rndr.notes.nMarks;
2652
2653 for(i=0; i<N; i++){
2654 const int j = aNotes[i].index;
2655 struct footnote *x = CAST_AS_FOOTNOTES(allNotes) + j;
2656 assert( 0<=j && j<N );
2657 if( x->bRndred || !x->nUsed ) continue;
2658 assert( x->iMark > 0 );
2659 assert( blob_size(&x->text) );
2660 blob_truncate(tmp,0);
@@ -2708,16 +2701,16 @@
2701 blob_reset(&lr[i].id);
2702 blob_reset(&lr[i].link);
2703 blob_reset(&lr[i].title);
2704 }
2705 blob_reset(&rndr.refs);
2706 fn = CAST_AS_FOOTNOTES( allNotes );
2707 end = COUNT_FOOTNOTES( allNotes );
2708 for(i=0; i<end; i++){
2709 if(blob_size(&fn[i].id)) blob_reset(&fn[i].id);
2710 blob_reset(&fn[i].text);
2711 }
2712 blob_reset(&rndr.notes.all);
2713 for(i=0; i<rndr.nBlobCache; i++){
2714 fossil_free(rndr.aBlobCache[i]);
2715 }
2716 }
2717

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button