From 0c79f9cfade3b5a8fc8bb24cad944e70109b86e5 Mon Sep 17 00:00:00 2001 From: Tristan Gingold Date: Wed, 20 Mar 2019 07:37:03 +0100 Subject: move algos to grt. --- Makefile.in | 1 + src/algos.adb | 55 ----------------------------------------------- src/algos.ads | 28 ------------------------ src/grt/grt-algos.adb | 55 +++++++++++++++++++++++++++++++++++++++++++++++ src/grt/grt-algos.ads | 28 ++++++++++++++++++++++++ src/synth/synth-stmts.adb | 5 +++-- src/vhdl/sem_expr.adb | 7 +++--- 7 files changed, 91 insertions(+), 88 deletions(-) delete mode 100644 src/algos.adb delete mode 100644 src/algos.ads create mode 100644 src/grt/grt-algos.adb create mode 100644 src/grt/grt-algos.ads diff --git a/Makefile.in b/Makefile.in index 9f9f18f02..9c2624f9e 100644 --- a/Makefile.in +++ b/Makefile.in @@ -207,6 +207,7 @@ copy-sources.gcc: version.ads $(CP) -p $(srcdir)/src/psl/*.ad? $(gcc_vhdl_dir) $(CP) -p $(srcdir)/src/grt/grt.ad? $(gcc_vhdl_dir) $(CP) -p $(srcdir)/src/grt/grt-fcvt.ad? $(gcc_vhdl_dir) + $(CP) -p $(srcdir)/src/grt/grt-algos.ad? $(gcc_vhdl_dir) $(CP) -p $(srcdir)/src/ortho/*.ad? $(gcc_vhdl_dir) $(CP) -p $(srcdir)/src/ortho/gcc/*.ad? $(gcc_vhdl_dir) $(CP) -p $(srcdir)/src/ortho/gcc/*.c $(gcc_vhdl_dir) diff --git a/src/algos.adb b/src/algos.adb deleted file mode 100644 index e40971495..000000000 --- a/src/algos.adb +++ /dev/null @@ -1,55 +0,0 @@ --- Generic algorithms --- Copyright (C) 2016 Tristan Gingold --- --- GHDL is free software; you can redistribute it and/or modify it under --- the terms of the GNU General Public License as published by the Free --- Software Foundation; either version 2, or (at your option) any later --- version. --- --- GHDL is distributed in the hope that it will be useful, but WITHOUT ANY --- WARRANTY; without even the implied warranty of MERCHANTABILITY or --- FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --- for more details. --- --- You should have received a copy of the GNU General Public License --- along with GHDL; see the file COPYING. If not, write to the Free --- Software Foundation, 59 Temple Place - Suite 330, Boston, MA --- 02111-1307, USA. - -package body Algos is - procedure Heap_Sort (N : Natural) is - -- An heap is an almost complete binary tree whose each edge is less - -- than or equal as its decendent. - - -- Bubble down element I of a partially ordered heap of length N in - -- array ARR. - procedure Bubble_Down (I, N : Natural) - is - Child : Natural; - Parent : Natural := I; - begin - loop - Child := 2 * Parent; - if Child < N and then Lt (Child, Child + 1) then - Child := Child + 1; - end if; - exit when Child > N; - exit when not Lt (Parent, Child); - Swap (Parent, Child); - Parent := Child; - end loop; - end Bubble_Down; - - begin - -- Heapify - for I in reverse 1 .. N / 2 loop - Bubble_Down (I, N); - end loop; - - -- Sort - for I in reverse 2 .. N loop - Swap (1, I); - Bubble_Down (1, I - 1); - end loop; - end Heap_Sort; -end Algos; diff --git a/src/algos.ads b/src/algos.ads deleted file mode 100644 index 39004d3ac..000000000 --- a/src/algos.ads +++ /dev/null @@ -1,28 +0,0 @@ --- Generic algorithms --- Copyright (C) 2016 Tristan Gingold --- --- GHDL is free software; you can redistribute it and/or modify it under --- the terms of the GNU General Public License as published by the Free --- Software Foundation; either version 2, or (at your option) any later --- version. --- --- GHDL is distributed in the hope that it will be useful, but WITHOUT ANY --- WARRANTY; without even the implied warranty of MERCHANTABILITY or --- FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --- for more details. --- --- You should have received a copy of the GNU General Public License --- along with GHDL; see the file COPYING. If not, write to the Free --- Software Foundation, 59 Temple Place - Suite 330, Boston, MA --- 02111-1307, USA. - -package Algos is - -- Heap sort the N elements. - generic - -- Compare two elements, return true iff OP1 < OP2. - with function Lt (Op1, Op2 : Natural) return Boolean; - - -- Swap two elements. - with procedure Swap (From : Natural; To : Natural); - procedure Heap_Sort (N : Natural); -end Algos; diff --git a/src/grt/grt-algos.adb b/src/grt/grt-algos.adb new file mode 100644 index 000000000..9482e8208 --- /dev/null +++ b/src/grt/grt-algos.adb @@ -0,0 +1,55 @@ +-- Generic algorithms +-- Copyright (C) 2016 Tristan Gingold +-- +-- GHDL is free software; you can redistribute it and/or modify it under +-- the terms of the GNU General Public License as published by the Free +-- Software Foundation; either version 2, or (at your option) any later +-- version. +-- +-- GHDL is distributed in the hope that it will be useful, but WITHOUT ANY +-- WARRANTY; without even the implied warranty of MERCHANTABILITY or +-- FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +-- for more details. +-- +-- You should have received a copy of the GNU General Public License +-- along with GHDL; see the file COPYING. If not, write to the Free +-- Software Foundation, 59 Temple Place - Suite 330, Boston, MA +-- 02111-1307, USA. + +package body Grt.Algos is + procedure Heap_Sort (N : Natural) is + -- An heap is an almost complete binary tree whose each edge is less + -- than or equal as its decendent. + + -- Bubble down element I of a partially ordered heap of length N in + -- array ARR. + procedure Bubble_Down (I, N : Natural) + is + Child : Natural; + Parent : Natural := I; + begin + loop + Child := 2 * Parent; + if Child < N and then Lt (Child, Child + 1) then + Child := Child + 1; + end if; + exit when Child > N; + exit when not Lt (Parent, Child); + Swap (Parent, Child); + Parent := Child; + end loop; + end Bubble_Down; + + begin + -- Heapify + for I in reverse 1 .. N / 2 loop + Bubble_Down (I, N); + end loop; + + -- Sort + for I in reverse 2 .. N loop + Swap (1, I); + Bubble_Down (1, I - 1); + end loop; + end Heap_Sort; +end Grt.Algos; diff --git a/src/grt/grt-algos.ads b/src/grt/grt-algos.ads new file mode 100644 index 000000000..85fe93ac3 --- /dev/null +++ b/src/grt/grt-algos.ads @@ -0,0 +1,28 @@ +-- Generic algorithms +-- Copyright (C) 2016 Tristan Gingold +-- +-- GHDL is free software; you can redistribute it and/or modify it under +-- the terms of the GNU General Public License as published by the Free +-- Software Foundation; either version 2, or (at your option) any later +-- version. +-- +-- GHDL is distributed in the hope that it will be useful, but WITHOUT ANY +-- WARRANTY; without even the implied warranty of MERCHANTABILITY or +-- FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +-- for more details. +-- +-- You should have received a copy of the GNU General Public License +-- along with GHDL; see the file COPYING. If not, write to the Free +-- Software Foundation, 59 Temple Place - Suite 330, Boston, MA +-- 02111-1307, USA. + +package Grt.Algos is + -- Heap sort the N elements. + generic + -- Compare two elements, return true iff OP1 < OP2. + with function Lt (Op1, Op2 : Natural) return Boolean; + + -- Swap two elements. + with procedure Swap (From : Natural; To : Natural); + procedure Heap_Sort (N : Natural); +end Grt.Algos; diff --git a/src/synth/synth-stmts.adb b/src/synth/synth-stmts.adb index 3d8ee03f6..df49a624c 100644 --- a/src/synth/synth-stmts.adb +++ b/src/synth/synth-stmts.adb @@ -21,7 +21,7 @@ with Ada.Unchecked_Deallocation; with Types; use Types; -with Algos; +with Grt.Algos; with Areapools; with Errorout; use Errorout; @@ -278,7 +278,8 @@ package body Synth.Stmts is Arr (To) := T; end Swap; - procedure Wid_Heap_Sort is new Algos.Heap_Sort (Lt => Lt, Swap => Swap); + procedure Wid_Heap_Sort is + new Grt.Algos.Heap_Sort (Lt => Lt, Swap => Swap); begin Wid_Heap_Sort (Arr'Length); end Sort_Wire_Id_Array; diff --git a/src/vhdl/sem_expr.adb b/src/vhdl/sem_expr.adb index dabcce490..1aeaf0e2d 100644 --- a/src/vhdl/sem_expr.adb +++ b/src/vhdl/sem_expr.adb @@ -16,7 +16,7 @@ -- Software Foundation, 59 Temple Place - Suite 330, Boston, MA -- 02111-1307, USA. -with Algos; +with Grt.Algos; with Std_Package; use Std_Package; with Errorout; use Errorout; with Flags; use Flags; @@ -2189,7 +2189,7 @@ package body Sem_Expr is end Swap; procedure Str_Heap_Sort is - new Algos.Heap_Sort (Lt => Lt, Swap => Swap); + new Grt.Algos.Heap_Sort (Lt => Lt, Swap => Swap); begin Str_Heap_Sort (Info.Nbr_Choices); end Sort_String_Choices; @@ -2433,7 +2433,8 @@ package body Sem_Expr is Swap_Choice_Info (Info, From, To); end Swap; - procedure Disc_Heap_Sort is new Algos.Heap_Sort (Lt => Lt, Swap => Swap); + procedure Disc_Heap_Sort is + new Grt.Algos.Heap_Sort (Lt => Lt, Swap => Swap); begin Disc_Heap_Sort (Info.Nbr_Choices); end Sort_Discrete_Choices; -- cgit v1.2.3