From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12682 invoked by alias); 22 Jun 2009 19:51:44 -0000 Received: (qmail 12673 invoked by uid 22791); 22 Jun 2009 19:51:44 -0000 X-SWARE-Spam-Status: No, hits=-2.4 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mx2.redhat.com (HELO mx2.redhat.com) (66.187.237.31) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 22 Jun 2009 19:51:33 +0000 Received: from int-mx2.corp.redhat.com (int-mx2.corp.redhat.com [172.16.27.26]) by mx2.redhat.com (8.13.8/8.13.8) with ESMTP id n5MJpWJl001718 for ; Mon, 22 Jun 2009 15:51:32 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx2.corp.redhat.com (8.13.1/8.13.1) with ESMTP id n5MJpVFw027612; Mon, 22 Jun 2009 15:51:31 -0400 Received: from host0.dyn.jankratochvil.net (sebastian-int.corp.redhat.com [172.16.52.221]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n5MJpTQl014032; Mon, 22 Jun 2009 15:51:30 -0400 Received: from host0.dyn.jankratochvil.net (localhost [127.0.0.1]) by host0.dyn.jankratochvil.net (8.14.3/8.14.3) with ESMTP id n5MJpTNB009068; Mon, 22 Jun 2009 21:51:29 +0200 Received: (from jkratoch@localhost) by host0.dyn.jankratochvil.net (8.14.3/8.14.3/Submit) id n5MJpS9V009067; Mon, 22 Jun 2009 21:51:28 +0200 Date: Mon, 22 Jun 2009 19:51:00 -0000 From: Jan Kratochvil To: Tom Tromey Cc: gdb-patches@sourceware.org Subject: Re: [patch] Accelerate blocks sorting Message-ID: <20090622195128.GA8401@host0.dyn.jankratochvil.net> References: <20090622173856.GA6649@host0.dyn.jankratochvil.net> <20090622183526.GA31281@host0.dyn.jankratochvil.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.19 (2009-01-05) X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2009-06/txt/msg00582.txt.bz2 On Mon, 22 Jun 2009 21:26:37 +0200, Tom Tromey wrote: > Yeah. It isn't the return, but the splitting. I see it now, thanks for looking it up. Checked-in. Thanks, Jan http://sourceware.org/ml/gdb-cvs/2009-06/msg00135.html --- src/gdb/ChangeLog 2009/06/22 18:17:01 1.10619 +++ src/gdb/ChangeLog 2009/06/22 19:50:10 1.10620 @@ -1,4 +1,10 @@ -2009-05-07 Sami Wagiaalla +2009-06-22 Jan Kratochvil + + PR gdb/9988: + * buildsym.c (block_compar): New function. + (end_symtab): Replace the bubble sort by a qsort based code. + +2009-06-22 Sami Wagiaalla * MAINTAINERS (Write After Approval): Add self. --- src/gdb/buildsym.c 2009/06/17 18:41:50 1.71 +++ src/gdb/buildsym.c 2009/06/22 19:50:10 1.72 @@ -899,6 +899,19 @@ } } +/* Helper function for qsort. Parametes are `struct block *' pointers, + function sorts them in descending order by their BLOCK_START. */ + +static int +block_compar (const void *ap, const void *bp) +{ + const struct block *a = *(const struct block **) ap; + const struct block *b = *(const struct block **) bp; + + return ((BLOCK_START (b) > BLOCK_START (a)) + - (BLOCK_START (b) < BLOCK_START (a))); +} + /* Finish the symbol definitions for one main source file, close off all the lexical contexts for that file (creating struct block's for them), then make the struct symtab for that file and put it in the @@ -952,32 +965,28 @@ OBJF_REORDERED is true, then sort the pending blocks. */ if ((objfile->flags & OBJF_REORDERED) && pending_blocks) { - /* FIXME! Remove this horrid bubble sort and use merge sort!!! */ - int swapped; - do - { - struct pending_block *pb, *pbnext; + unsigned count = 0; + struct pending_block *pb; + struct block **barray, **bp; + struct cleanup *back_to; - pb = pending_blocks; - pbnext = pb->next; - swapped = 0; + for (pb = pending_blocks; pb != NULL; pb = pb->next) + count++; - while (pbnext) - { - /* swap blocks if unordered! */ + barray = xmalloc (sizeof (*barray) * count); + back_to = make_cleanup (xfree, barray); - if (BLOCK_START (pb->block) < BLOCK_START (pbnext->block)) - { - struct block *tmp = pb->block; - pb->block = pbnext->block; - pbnext->block = tmp; - swapped = 1; - } - pb = pbnext; - pbnext = pbnext->next; - } - } - while (swapped); + bp = barray; + for (pb = pending_blocks; pb != NULL; pb = pb->next) + *bp++ = pb->block; + + qsort (barray, count, sizeof (*barray), block_compar); + + bp = barray; + for (pb = pending_blocks; pb != NULL; pb = pb->next) + pb->block = *bp++; + + do_cleanups (back_to); } /* Cleanup any undefined types that have been left hanging around