[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnuastro-commits] master de05eca: linkedlist.h functions added to the b
|
From: |
Mohammad Akhlaghi |
|
Subject: |
[gnuastro-commits] master de05eca: linkedlist.h functions added to the book |
|
Date: |
Mon, 19 Sep 2016 22:55:04 +0000 (UTC) |
branch: master
commit de05eca5777a0b7972418b9f2135741c8e559a96
Author: Mohammad Akhlaghi <address@hidden>
Commit: Mohammad Akhlaghi <address@hidden>
linkedlist.h functions added to the book
The linked list functions were added to the book and some small corrections
were made to the functions to be more clear. The two-way size_t linked
lists were also removed since they were not used anywhere in Gnuastro.
---
doc/gnuastro.texi | 436 +++++++++++++++++++++++++++++++++++++++++++--
lib/gnuastro/linkedlist.h | 81 ++++-----
lib/linkedlist.c | 268 +++++++++++-----------------
3 files changed, 558 insertions(+), 227 deletions(-)
diff --git a/doc/gnuastro.texi b/doc/gnuastro.texi
index 5fd69fc..77ed428 100644
--- a/doc/gnuastro.texi
+++ b/doc/gnuastro.texi
@@ -512,6 +512,7 @@ Gnuastro library
* Array manipulation:: Functions for manipulating arrays.
* Bounding box:: Finding the bounding box.
* FITS files:: Working with FITS datat.
+* Linked lists:: Various types of linked lists.
FITS files (@file{fits.h})
@@ -14740,11 +14741,14 @@ your exciting science.
initially created to be a collection of command-line utilities. However, as
the utilities and their the shared functions grew, internal (not installed)
libraries were added. With the 0.2 release, the libraries are
-installable. In the next releases, Gnuastro's library structure will
-undergo significant evolution for enhanced modularity. It will stabilize
-with the removal of this notice. So as long as this notice is present,
-please install newer versions with extreme care: check the @file{NEWS} file
-for changes in the interface.
+installable. Because of this history in these early phases, the libraries
+are not fully programmer friendly yet: they abort the program on an error,
+their naming and arguments are not fully uniform, or modular, and most of
+the interesting functions (that are currently only used within one utility)
+are still internal to the utility. During the next releases, Gnuastro's
+library structure will undergo significant evolution to address all these
+problems. It will stabilize with the removal of this notice. Check the
address@hidden file for interface changes.
@end cartouche
@menu
@@ -14752,6 +14756,7 @@ for changes in the interface.
* Array manipulation:: Functions for manipulating arrays.
* Bounding box:: Finding the bounding box.
* FITS files:: Working with FITS datat.
+* Linked lists:: Various types of linked lists.
@end menu
@node Overall package, Array manipulation, Gnuastro library, Gnuastro library
@@ -14996,7 +15001,7 @@ last pixels of the overlap will be put in
@code{fpixel_o} and
@code{lpixel_o}.
@end deftypefun
address@hidden FITS files, , Bounding box, Gnuastro library
address@hidden FITS files, Linked lists, Bounding box, Gnuastro library
@subsection FITS files (@file{fits.h})
@cindex FITS
@@ -15478,7 +15483,399 @@ error notice.
@address@hidden deftypefun
address@hidden Linked lists, , FITS files, Gnuastro library
address@hidden Linked lists (@file{linkedlist.h})
address@hidden Array
address@hidden Linked list
+An array is a contiguous region of memory that is very efficient and easy
+to use for recording and later accessing the data. One major problem with
+an array is that the number of elements that go into it must be known in
+advance. This is where linked lists can be very useful: like a metal chain,
+each @emph{node} in a linked list is an independent C structure, keeping
+its own data along with pointer(s) to its immediate neighbor(s). Below we
+have one simple linked list node structure along with an ASCII art
+schematic of how we can use the @code{next} pointer to add any number of
+elements to the list that we want. The linked list is terminated when
address@hidden is a @code{NULL} pointer.
+
address@hidden The second and last lines lines are pushed line space forward,
because
address@hidden the address@hidden' at the start of the line is only seen as `{'
in the book.
address@hidden
+struct float_ll /* --------- --------- */
address@hidden /* | Value | | Value |
*/
+ float value; /* | --- | | --- | */
+ struct ll_node *next; /* | next-|--> | next-|--> NULL */
address@hidden /* --------- ---------
*/
address@hidden example
+
+The schematic shows another great advantage of linked lists: it is very
+easy to add or remove a node anywhere in the list (you just have to change
+one pointer in the structure above). You initially define a variable of
+this type with a @code{NULL} pointer as shown below, then you use functions
+provided for that type of linked list to add elements to the list or pop
+elements from it.
+
address@hidden
+struct float_ll *mylist=NULL
address@hidden example
+
address@hidden last-in-first-out
address@hidden first-in-first-out
address@hidden
+When you add an element to the list, it is conventionally added to the
+``top'' of the list: the general list pointer will point to the newly
+created node, which will point to the previously created node and so on. So
+when you ``pop'' from the top of the list, you are actually retrieving the
+last value you put in and changing the list pointer to the next oldest
+node. This is thus known as a ``last-in-first-out'' list. This is the most
+convenient type of linked list (easier to implement and faster to
+process). Alternatively, you can add each newly created node at the end of
+the list. If you do that, you will get a ``first-in-first-out'' list. But
+that will force you to go through the whole list for each new element that
+is created (this can slow down the processing)@footnote{A better way to get
+a first-in-first-out is to first keep the data as last-in-first-out until
+they are all read. Afterwards, pop each node and immediately add it to the
+new list: practically reversing the last-in-first-out list to a
+first-in-first-out one.}.
+
+Each node in a linked list doesn't have to have a single pointer to the
+next node like the example above. We can define each node with two pointers
+to both the next and previous neighbors, this is called a ``Doubly linked
+list''. In general, lists are very powerful and simple constructs that can
+be very useful. But going into more detail would be out of the scope of
+this short introduction in this
+book. @url{https://en.wikipedia.org/wiki/Linked_list, Wikipedia} has a nice
+and more thorough discussion of the various types of lists, so for more,
+please have a look at that article.
+
+In this section we will review the functions and structures that are
+available in Gnuastro for working on linked lists. For each linked-list
+node sturcture, we will first introduce the structure, then the functions
+for working on the structure. All these structures and functions are
+defined and declared in @file{gnuastro/linkedlist.h}.
+
+
address@hidden Structure gal_linkedlist_fll
+Float linked list (@code{fll}). Each node in this singly-linked list can
+have a single float type value.
address@hidden deftp
address@hidden
+struct gal_linkedlist_fll
address@hidden
+ float v;
+ struct gal_linkedlist_fll *next;
address@hidden;
address@hidden example
+
address@hidden void gal_linkedlist_print_fll_array (struct gal_linkedlist_fll
@code{**afll}, size_t @code{num})
+Print all the values within the linked list to the output terminal. This
+can be used for inspecting the status of the list during development.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_add_to_fll (struct gal_linkedlist_fll
@code{**list}, float @code{value})
+Allocate space for a new node in @code{list}, and put @code{value} into
+it. The new node will be added to the top of the list. So after this
+function, the already existing nodes will be appended to the new node and
address@hidden will point to the newly created node.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_pop_from_fll (struct gal_linkedlist_fll
@code{**list}, float @code{*value})
+Pop a node from the top of @code{list} and put its values in
address@hidden This function will also free the allocated space for the
+popped node and after this function, @code{list} will point to the next
+node.
address@hidden deftypefun
+
address@hidden size_t gal_linkedlist_num_in_fll (struct gal_linkedlist_fll
@code{*list})
+Return the number of nodes in @code{list}, the contents of @code{list} will
+be untouched.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_fll_to_array (struct gal_linkedlist_fll
@code{*list}, float @code{**f}, size_t @code{*num})
+Put the elements of @code{list} into an array @code{f} and store the number
+of nodes in the list in @code{num}. The array will be filled in the same
+order as popped elements from the list. This function will allocate space
+for the @code{num} element @code{f} array internally, so you have to free
+it afterwards.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_free_fll (struct gal_linkedlist_fll
@code{*list})
+Free the space for all the nodes in @code{list}. Note that any values
+within the nodes will also be discarded. This can be used when the list is
+no longer relevant for you. For example, you might have already converted
+the list to an array for future usage with
address@hidden
address@hidden deftypefun
+
address@hidden void gal_linkedlist_free_fll_array (struct gal_linkedlist_fll
@code{**afll}, size_t @code{num})
+Free an array of @code{gal_linkedlist_fll} linked lists (@code{num}
+elements). Each element of the array is a pointer to a linked list, so we
+first need to free the separate linked lists, then the array.
address@hidden deftypefun
+
+
address@hidden Structure gal_linkedlist_tdll
+Two doubles linked list (@code{tdll}. Each node in this singly-linked list
+can have two double type values. It can be used to store an unknown number
+of floating point coordinates (for example RA and Dec).
address@hidden deftp
address@hidden
+struct gal_linkedlist_tdll
address@hidden
+ double a;
+ double b;
+ struct gal_linkedlist_tdll *next;
address@hidden;
address@hidden example
+
address@hidden void gal_linkedlist_add_to_tdll (struct gal_linkedlist_tdll
@code{**list}, double @code{a}, double @code{b})
+Allocate space for a new node in @code{list}, and put the values @code{a}
+and @code{b} into it. The new node will be added to the top of the list. So
+after this function, the already existing nodes will be appended to the new
+node and @code{list} will point to the newly created node.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_pop_from_tdll (struct gal_linkedlist_tdll
@code{**list}, double @code{*a}, double @code{*b})
+Pop a node from the top of @code{list} and put its values in @code{a} and
address@hidden This function will also free the allocated space for the popped
+node and after this function, @code{list} will point to the next node.
address@hidden deftypefun
+
address@hidden size_t gal_linkedlist_num_int_dll (struct gal_linkedlist_tdll
@code{*list})
+Return the number of nodes in @code{list}. The contents of @code{list} will
+be untouched.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_tdll_to_array_inv (struct
gal_linkedlist_tdll @code{*list}, double @code{**d}, size_t @code{*num})
+Put the elements of @code{list} into an array @code{d} in inverse order and
+store the number of nodes in the list in @code{num}. This function will
+allocate space for the @address@hidden element array internally
+so you have to free it afterwards. The two values for each node will be
+stored adjacently, so the array can be seen as a 2D array with @code{num}
+rows and 2 columns.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_free_tdll (struct gal_linkedlist_tdll
@code{*list})
+Free the space for all the nodes in @code{list}. Note that any values
+within the nodes will also be discarded. This can be used when the list is
+no longer relevant for you. For example, you might have already converted
+the list to an array for future usage with
address@hidden
address@hidden deftypefun
+
+
address@hidden Structure gal_linkedlist_stll
+String linked list (@code{stll}. Each node in this singly-linked list has a
+string variable.
address@hidden deftp
address@hidden
+struct gal_linkedlist_stll
address@hidden
+ char *v;
+ struct gal_linkedlist_stll *next;
address@hidden;
address@hidden example
+
address@hidden void gal_linkedlist_add_to_stll (struct gal_linkedlist_stll
@code{**list}, char @code{*value})
+Allocate space for a new node in @code{list}, and store the @code{value}
+pointer into it. The new node will be added to the top of the list. So
+after this function, the already existing nodes will be appended to the new
+node and @code{list} will point to the newly created node.
+
+It is important to remember that this function will only copy the pointer
+in the node, it will not allocate space for the string. So the string
+either has to be a literal string (with a fixed address) or dynamically
+allocated when this linked list is to be filled and used within one
+function.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_pop_from_stll (struct gal_linkedlist_stll
@code{**list}, char @code{**value})
+Pop a node from the top of @code{list} and put its pointer in
address@hidden This function will also free the allocated space for the
+popped node and after this function, @code{list} will point to the next
+node.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_reverse_stll (struct gal_linkedlist_stll
@code{**list})
+Reverse the linked list. The @code{gal_linkedlist_add_to_stll} function
+will make a last-in-first-out list, but commonly you will need a
+first-in-first-out list. This function can thus be useful after adding to
+the list has finished.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_print_stll (struct gal_linkedlist_stll
@code{*list})
+Print all the values within the linked list to the output terminal. This
+can be used for inspecting the status of the list during development.
address@hidden deftypefun
+
address@hidden size_t gal_linkedlist_num_in_stll (struct gal_linkedlist_stll
@code{*list})
+Return the number of nodes in @code{list}. The contents of @code{list} will
+be untouched.
address@hidden deftypefun
+
address@hidden Structure gal_linkedlist_sll
address@hidden @code{size_t}
address@hidden linked list (@code{sll}. Each node in this singly-linked list
+contains a @code{size_t} value. The @code{size_t} type is commonly used for
+``size'' related values: it is an un-signed type (negative values are not
+defined for it), therefore it is ideal for dealing with things like pixel
+indexes in an image (which can not be negative and can be very large).
address@hidden deftp
address@hidden
+struct gal_linkedlist_sll
address@hidden
+ size_t v;
+ struct gal_linkedlist_sll *next;
address@hidden;
address@hidden example
+
address@hidden void gal_linkedlist_add_to_sll (struct gal_linkedlist_sll
@code{**list}, size_t @code{value})
+Allocate space for a new node in @code{list}, and store @code{value} into
+it. The new node will be added to the top of the list. So after this
+function, the already existing nodes will be appended to the new node and
address@hidden will point to the newly created node.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_pop_from_sll (struct gal_linkedlist_sll
@code{**list}, size_t @code{*value})
+Pop a node from the top of @code{list} and put its value in
address@hidden This function will also free the allocated space for the
+popped node and after this function, @code{list} will point to the next
+node.
address@hidden deftypefun
+
address@hidden size_t gal_linkedlist_num_in_sll (struct gal_linkedlist_sll
@code{*list})
+Return the number of nodes in @code{list}. The contents of @code{list} will
+be untouched.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_print_sll (struct gal_linkedlist_sll
@code{*list})
+Print all the values within the linked list to the output terminal. This
+can be used for inspecting the status of the list during development.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_sll_to_array (struct gal_linkedlist_sll
@code{*list}, size_t @code{**s}, size_t @code{*num}, int @code{inverse})
+Put the elements of @code{list} into an array @code{s} and store the number
+of nodes in the list in @code{num}. This function will allocate space for
+the @code{num} element array internally so you have to free it
+afterwards. If the value in @code{inverse} is @code{1}, then the first
+popped value in the list will be the last element in the array, otherwise,
+the array will be filled in the same order that the elements were popped.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_free_sll (struct gal_linkedlist_sll
@code{*list})
+Free the space for all the nodes in @code{list}. Note that any values
+within the nodes will also be discarded. This can be used when the list is
+no longer relevant for you. For example, you might have already converted
+the list to an array for future usage with
address@hidden
address@hidden deftypefun
+
address@hidden Structure gal_linkedlist_osll
address@hidden @code{size_t}
+Ordered @code{size_t} linked list (@code{osll}. Each node in this
+singly-linked list contains a @code{size_t} value and a floating point
+value. The floating point value is used as a reference to add new nodes in
+a sorted manner. At any moment, the first popped node in this list will
+have the smallest @code{tosort} value, and subsequent nodes will have
+larger to values.
address@hidden deftp
address@hidden
+struct gal_linkedlist_osll
address@hidden
+ size_t v;
+ float s;
+ struct gal_linkedlist_osll *next;
address@hidden;
address@hidden example
+
address@hidden void gal_linkedlist_add_to_osll (struct gal_linkedlist_osll
@code{**list}, size_t @code{value}, float @code{tosort})
+Allocate space for a new node in @code{list}, and store @code{value} into
+it. The new node will be added to the list based on the @code{tosort}
+value.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_pop_from_osll (struct gal_linkedlist_osll
@code{**list}, size_t @code{*value}, float @code{*sortvalue})
+Pop a node from the top of @code{list}, put its value in @code{value} and
+its sort value in @code{sortvalue}. This function will also free the
+allocated space for the popped node and after this function, @code{list}
+will point to the next node (which has a larger @code{tosort} element).
address@hidden deftypefun
+
address@hidden void gal_linkedlist_osll_into_sll (struct gal_linkedlist_osll
@code{*in}, struct gal_linkedlist_sll @code{**out})
+Convert the orderd @code{size_t} linked list into an ordinary @code{size_t}
+linked list (no longer sorted). This can be useful when all the elements
+have been added and you just need to pop-out elements.
address@hidden deftypefun
+
address@hidden Structure gal_linkedlist_tosll
address@hidden @code{size_t}
+Two-way, ordered @code{size_t} linked list (@code{tosll}. Each node in this
+Doubly-linked list contains a @code{size_t} value and a floating point
+value. The floating point value is used as a reference to add new nodes in
+a sorted manner. In the functions here, this linked list can be pointed to
+by two pointers (largest and smallest) with the following format:
address@hidden
+ largest pointer
+ |
+ NULL <-- (v0,s0) <--> (v1,s1) <--> ... (vn,sn) --> NULL
+ |
+ smallest pointer
address@hidden example
+At any moment, the two pointers will point the nodes containing the
+``largest'' and ``smallest'' values and the rest of the nodes will be
+ordered. This is useful when during the operations (where an un-known
+number new nodes will be added continuesly) it is important to also know
+the minimum and maximum values.
address@hidden deftp
address@hidden
+struct gal_linkedlist_tosll
address@hidden
+ size_t v;
+ float s;
+ struct gal_linkedlist_tosll *prev;
+ struct gal_linkedlist_tosll *next;
address@hidden;
address@hidden example
+
address@hidden void gal_linkedlist_print_tosll (struct gal_linkedlist_tosll
@code{*largest}, struct gal_linkedlist_tosll @code{*smallest})
+Print all the values within the linked list to the output terminal. This
+can be used for inspecting the status of the list during development.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_add_to_tosll_end (struct
gal_linkedlist_tosll @code{**largest}, struct gal_linkedlist_tosll
@code{**smallest}, size_t @code{value}, float @code{tosort})
+Allocate space for a new node in @code{list}, and store @code{value} into
+it. The new node will be added to the list based on the @code{s} value as
+described in the description of @code{gal_linkedlist_tosll}. If this is the
+first node to be added to the list, both the @code{largest} and
address@hidden pointers can be @code{NULL}.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_pop_from_tosll_start (struct
gal_linkedlist_tosll @code{**lartest}, struct gal_linkedlist_tosll
@code{**smallest}, size_t @code{*value}, float @code{*tosort})
+Pop the node with the smallest @code{s} of @code{list}, then put its value
+in @code{value} and its sort value in @code{sortvalue}. This function will
+also free the allocated space for the popped node and after this function,
address@hidden and @code{smallest} will be modified respectively. Note that
+even though only the smallest pointer will be popped, when there was only
+one node in the list, the @code{largest} pointer also has to change, so we
+need both.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_smallest_tosll (struct gal_linkedlist_tosll
@code{*largest}, struct gal_linkedlist_tosll @code{**smallest})
+Given the @code{largest} pointer, set @code{smallest} as described in
address@hidden
address@hidden deftypefun
+
address@hidden void gal_linkedlist_tosll_into_sll (struct gal_linkedlist_tosll
@code{*in}, struct gal_linkedlist_sll @code{**out})
+Convert the two-way orderd @code{size_t} linked list into an ordinary
address@hidden linked list (no longer sorted). This can be useful when all
+the elements have been added and you just need to pop-out elements.
address@hidden deftypefun
+
address@hidden void gal_linkedlist_tosll_free (struct gal_linkedlist_tosll
@code{*largest})
+Free the space for all the nodes in @code{largest}. Note that any values
+within the nodes will also be discarded.
address@hidden deftypefun
@@ -15499,17 +15896,16 @@ error notice.
@node Developing, GNU Astronomy Utilities list, Libraries, Top
@chapter Developing
-The basic idea of GNU Astronomy Utilities is for an interested
-astronomer to be able to easily understand the code of any of the
-programs, be able to modify the code if she feels there is an
-improvement and finally, to be able to add new programs to the
-existing utilities for their own benefit, and the larger community if
-they are willing to share it. In short, we hope that at least from the
-software point of view, the ``obscurantist faith in the expert's
-special skill and in his personal knowledge and authority'' can be
-broken, see @ref{Science and its tools}. The following software
-architecture can be one of the most basic and easy to understand for
-any interested inquirer.
+The basic idea of GNU Astronomy Utilities is for an interested astronomer
+to be able to easily understand the code of any of the programs, be able to
+modify the code if she feels there is an improvement and finally, to be
+able to add new programs to the existing utilities for their own benefit,
+and the larger community if they are willing to share it. In short, we hope
+that at least from the software point of view, the ``obscurantist faith in
+the expert's special skill and in his personal knowledge and authority''
+can be broken, see @ref{Science and its tools}. The following software
+architecture can be one of the most basic and easy to understand for any
+interested inquirer.
First some general design choices are tackled. It is followed by a
short explanation of the version controlled source. The libraries and
@@ -17518,6 +17914,12 @@ $ ./pgdemoXX
@c Print the index and finish:
@node Index, , GNU Free Documentation License, Top
@unnumbered Index: Macros, structures and functions
+All Gnuastro library macros start with @code{GAL_} and structures and
+functions start with @code{gal_} for @emph{G}NU @emph{A}stronomy
address@hidden The next element in the name is the name of the header
+which declares or defines them, so to use the @code{gal_array_fset_const}
+function, you have to @code{#include <gnuastro/array.h}. See @ref{Gnuastro
+library} for more.
@printindex fn
@unnumbered Index
@printindex cp
diff --git a/lib/gnuastro/linkedlist.h b/lib/gnuastro/linkedlist.h
index 700332f..34155d1 100644
--- a/lib/gnuastro/linkedlist.h
+++ b/lib/gnuastro/linkedlist.h
@@ -47,34 +47,6 @@ __BEGIN_C_DECLS /* From C++ preparations */
-/******************* Two doubles (for coordinates) */
-struct gal_linkedlist_tdll
-{
- double a;
- double b;
- struct gal_linkedlist_tdll *next;
-};
-
-void
-gal_linkedlist_add_to_tdll(struct gal_linkedlist_tdll **list,
- double a, double b);
-
-void
-gal_linkedlist_pop_from_tdll(struct gal_linkedlist_tdll **list,
- double *a, double *b);
-
-size_t
-gal_linkedlist_num_int_dll(struct gal_linkedlist_tdll *list);
-
-void
-gal_linkedlist_tdll_to_array_inv(struct gal_linkedlist_tdll *list,
- double **d, size_t *num);
-
-void
-gal_linkedlist_free_tdll(struct gal_linkedlist_tdll *list);
-
-
-
/******************* float: */
struct gal_linkedlist_fll
{
@@ -110,6 +82,38 @@ gal_linkedlist_free_fll_array(struct gal_linkedlist_fll
**afll,
+
+
+/******************* Two doubles (for coordinates) */
+struct gal_linkedlist_tdll
+{
+ double a;
+ double b;
+ struct gal_linkedlist_tdll *next;
+};
+
+void
+gal_linkedlist_add_to_tdll(struct gal_linkedlist_tdll **list,
+ double a, double b);
+
+void
+gal_linkedlist_pop_from_tdll(struct gal_linkedlist_tdll **list,
+ double *a, double *b);
+
+size_t
+gal_linkedlist_num_int_dll(struct gal_linkedlist_tdll *list);
+
+void
+gal_linkedlist_tdll_to_array_inv(struct gal_linkedlist_tdll *list,
+ double **d, size_t *num);
+
+void
+gal_linkedlist_free_tdll(struct gal_linkedlist_tdll *list);
+
+
+
+
+
/******************* String: */
struct gal_linkedlist_stll
{
@@ -159,28 +163,14 @@ gal_linkedlist_print_sll(struct gal_linkedlist_sll *list);
void
gal_linkedlist_sll_to_array(struct gal_linkedlist_sll *list,
- size_t **f, size_t *num, int inverse);
+ size_t **s, size_t *num, int inverse);
void
gal_linkedlist_free_sll(struct gal_linkedlist_sll *list);
-/******************* Two way size_t: */
-struct gal_linkedlist_tsll
-{
- size_t v;
- struct gal_linkedlist_tsll *next;
- struct gal_linkedlist_tsll *prev;
-};
-
-void
-gal_linkedlist_add_to_tsll_end(struct gal_linkedlist_tsll **last,
- size_t value);
-void
-gal_linkedlist_pop_from_tsll_start(struct gal_linkedlist_tsll **first,
- size_t *value);
@@ -206,6 +196,7 @@ gal_linkedlist_osll_into_sll(struct gal_linkedlist_osll *in,
+
/******************* Two way ordered size_t: */
struct gal_linkedlist_tosll
{
@@ -216,8 +207,8 @@ struct gal_linkedlist_tosll
};
void
-gal_linkedlist_print_tosll(struct gal_linkedlist_tosll *l,
- struct gal_linkedlist_tosll *s);
+gal_linkedlist_print_tosll(struct gal_linkedlist_tosll *largest,
+ struct gal_linkedlist_tosll *smallest);
void
gal_linkedlist_add_to_tosll_end(struct gal_linkedlist_tosll **largest,
diff --git a/lib/linkedlist.c b/lib/linkedlist.c
index f3eb1f1..847583d 100644
--- a/lib/linkedlist.c
+++ b/lib/linkedlist.c
@@ -38,24 +38,39 @@ along with Gnuastro. If not, see
<http://www.gnu.org/licenses/>.
-
/****************************************************************
- ***************** Two doubles ********************
+ ***************** Float ********************
****************************************************************/
void
-gal_linkedlist_add_to_tdll(struct gal_linkedlist_tdll **list,
- double a, double b)
+gal_linkedlist_print_fll_array(struct gal_linkedlist_fll **afll, size_t num)
{
- struct gal_linkedlist_tdll *newnode;
+ size_t i;
+ struct gal_linkedlist_fll *tmp;
+ for(i=0;i<num;++i)
+ {
+ printf(" %lu:\n", i);
+ for(tmp=afll[i];tmp!=NULL;tmp=tmp->next)
+ printf("%f, ", tmp->v);
+ printf("\n");
+ }
+}
+
+
+
+
+
+void
+gal_linkedlist_add_to_fll(struct gal_linkedlist_fll **list, float value)
+{
+ struct gal_linkedlist_fll *newnode;
errno=0;
newnode=malloc(sizeof *newnode);
if(newnode==NULL)
error(EXIT_FAILURE, errno, "linkedlist: New element in "
- "gal_linkedlist_tdll");
+ "gal_linkedlist_fll");
- newnode->a=a;
- newnode->b=b;
+ newnode->v=value;
newnode->next=*list;
*list=newnode;
}
@@ -65,13 +80,11 @@ gal_linkedlist_add_to_tdll(struct gal_linkedlist_tdll
**list,
void
-gal_linkedlist_pop_from_tdll(struct gal_linkedlist_tdll **list,
- double *a, double *b)
+gal_linkedlist_pop_from_fll(struct gal_linkedlist_fll **list, float *value)
{
- struct gal_linkedlist_tdll *tmp=*list;
-
- *a=tmp->a;
- *b=tmp->b;
+ struct gal_linkedlist_fll *tmp;
+ tmp=*list;
+ *value=tmp->v;
*list=tmp->next;
free(tmp);
}
@@ -81,10 +94,10 @@ gal_linkedlist_pop_from_tdll(struct gal_linkedlist_tdll
**list,
size_t
-gal_linkedlist_num_int_dll(struct gal_linkedlist_tdll *list)
+gal_linkedlist_num_in_fll(struct gal_linkedlist_fll *list)
{
size_t num=0;
- struct gal_linkedlist_tdll *tmp;
+ struct gal_linkedlist_fll *tmp;
for(tmp=list;tmp!=NULL;tmp=tmp->next)
++num;
return num;
@@ -95,33 +108,28 @@ gal_linkedlist_num_int_dll(struct gal_linkedlist_tdll
*list)
void
-gal_linkedlist_tdll_to_array_inv(struct gal_linkedlist_tdll *list,
- double **d, size_t *num)
+gal_linkedlist_fll_to_array(struct gal_linkedlist_fll *list,
+ float **f, size_t *num)
{
- size_t i;
- double *td;
- struct gal_linkedlist_tdll *tmp;
+ float *tf;
+ size_t i=0;
+ struct gal_linkedlist_fll *tmp;
/* Find the number of elements: */
if(*num==0)
- *num=gal_linkedlist_num_int_dll(list);
+ *num=gal_linkedlist_num_in_fll(list);
- /* Allocate the space (every element of the list has two
- elements.) */
+ /* Allocate the space: */
errno=0;
- td=*d=malloc(2 * *num * sizeof(double));
- if(*d==NULL)
- error(EXIT_FAILURE, errno, "linkedlist: array of gal_linkedlist_tdll "
+ *f=malloc(*num*sizeof(float));
+ if(*f==NULL)
+ error(EXIT_FAILURE, errno, "linkedlist: array of gal_linkedlist_fll "
"with %lu elements", *num);
+ tf=*f;
- /* Fill in the array in reverse order */
- i = 2 * *num - 2;
+ /* Fill in the array: */
for(tmp=list;tmp!=NULL;tmp=tmp->next)
- {
- td[i]=tmp->a;
- td[i+1]=tmp->b;
- i-=2;
- }
+ tf[i++]=tmp->v;
}
@@ -129,9 +137,9 @@ gal_linkedlist_tdll_to_array_inv(struct gal_linkedlist_tdll
*list,
void
-gal_linkedlist_free_tdll(struct gal_linkedlist_tdll *list)
+gal_linkedlist_free_fll(struct gal_linkedlist_fll *list)
{
- struct gal_linkedlist_tdll *tmp, *ttmp;
+ struct gal_linkedlist_fll *tmp, *ttmp;
tmp=list;
while(tmp!=NULL)
{
@@ -145,6 +153,14 @@ gal_linkedlist_free_tdll(struct gal_linkedlist_tdll *list)
+void
+gal_linkedlist_free_fll_array(struct gal_linkedlist_fll **afll, size_t num)
+{
+ size_t i;
+ for(i=0;i<num;++i)
+ gal_linkedlist_free_fll(afll[i]);
+ free(afll);
+}
@@ -160,39 +176,28 @@ gal_linkedlist_free_tdll(struct gal_linkedlist_tdll *list)
-/****************************************************************
- ***************** Float ********************
- ****************************************************************/
-void
-gal_linkedlist_print_fll_array(struct gal_linkedlist_fll **afll, size_t num)
-{
- size_t i;
- struct gal_linkedlist_fll *tmp;
- for(i=0;i<num;++i)
- {
- printf(" %lu:\n", i);
- for(tmp=afll[i];tmp!=NULL;tmp=tmp->next)
- printf("%f, ", tmp->v);
- printf("\n");
- }
-}
+/****************************************************************
+ ***************** Two doubles ********************
+ ****************************************************************/
void
-gal_linkedlist_add_to_fll(struct gal_linkedlist_fll **list, float value)
+gal_linkedlist_add_to_tdll(struct gal_linkedlist_tdll **list,
+ double a, double b)
{
- struct gal_linkedlist_fll *newnode;
+ struct gal_linkedlist_tdll *newnode;
errno=0;
newnode=malloc(sizeof *newnode);
if(newnode==NULL)
error(EXIT_FAILURE, errno, "linkedlist: New element in "
- "gal_linkedlist_fll");
+ "gal_linkedlist_tdll");
- newnode->v=value;
+ newnode->a=a;
+ newnode->b=b;
newnode->next=*list;
*list=newnode;
}
@@ -202,11 +207,13 @@ gal_linkedlist_add_to_fll(struct gal_linkedlist_fll
**list, float value)
void
-gal_linkedlist_pop_from_fll(struct gal_linkedlist_fll **list, float *value)
+gal_linkedlist_pop_from_tdll(struct gal_linkedlist_tdll **list,
+ double *a, double *b)
{
- struct gal_linkedlist_fll *tmp;
- tmp=*list;
- *value=tmp->v;
+ struct gal_linkedlist_tdll *tmp=*list;
+
+ *a=tmp->a;
+ *b=tmp->b;
*list=tmp->next;
free(tmp);
}
@@ -216,10 +223,10 @@ gal_linkedlist_pop_from_fll(struct gal_linkedlist_fll
**list, float *value)
size_t
-gal_linkedlist_num_in_fll(struct gal_linkedlist_fll *list)
+gal_linkedlist_num_int_dll(struct gal_linkedlist_tdll *list)
{
size_t num=0;
- struct gal_linkedlist_fll *tmp;
+ struct gal_linkedlist_tdll *tmp;
for(tmp=list;tmp!=NULL;tmp=tmp->next)
++num;
return num;
@@ -230,28 +237,33 @@ gal_linkedlist_num_in_fll(struct gal_linkedlist_fll *list)
void
-gal_linkedlist_fll_to_array(struct gal_linkedlist_fll *list,
- float **f, size_t *num)
+gal_linkedlist_tdll_to_array_inv(struct gal_linkedlist_tdll *list,
+ double **d, size_t *num)
{
- float *tf;
- size_t i=0;
- struct gal_linkedlist_fll *tmp;
+ size_t i;
+ double *td;
+ struct gal_linkedlist_tdll *tmp;
/* Find the number of elements: */
if(*num==0)
- *num=gal_linkedlist_num_in_fll(list);
+ *num=gal_linkedlist_num_int_dll(list);
- /* Allocate the space: */
+ /* Allocate the space (every element of the list has two
+ elements.) */
errno=0;
- *f=malloc(*num*sizeof(float));
- if(*f==NULL)
- error(EXIT_FAILURE, errno, "linkedlist: array of gal_linkedlist_fll "
+ td=*d=malloc(2 * *num * sizeof(double));
+ if(*d==NULL)
+ error(EXIT_FAILURE, errno, "linkedlist: array of gal_linkedlist_tdll "
"with %lu elements", *num);
- tf=*f;
- /* Fill in the array: */
+ /* Fill in the array in reverse order */
+ i = 2 * *num - 2;
for(tmp=list;tmp!=NULL;tmp=tmp->next)
- tf[i++]=tmp->v;
+ {
+ td[i]=tmp->a;
+ td[i+1]=tmp->b;
+ i-=2;
+ }
}
@@ -259,9 +271,9 @@ gal_linkedlist_fll_to_array(struct gal_linkedlist_fll *list,
void
-gal_linkedlist_free_fll(struct gal_linkedlist_fll *list)
+gal_linkedlist_free_tdll(struct gal_linkedlist_tdll *list)
{
- struct gal_linkedlist_fll *tmp, *ttmp;
+ struct gal_linkedlist_tdll *tmp, *ttmp;
tmp=list;
while(tmp!=NULL)
{
@@ -275,19 +287,6 @@ gal_linkedlist_free_fll(struct gal_linkedlist_fll *list)
-void
-gal_linkedlist_free_fll_array(struct gal_linkedlist_fll **afll, size_t num)
-{
- size_t i;
- for(i=0;i<num;++i)
- gal_linkedlist_free_fll(afll[i]);
- free(afll);
-}
-
-
-
-
-
@@ -447,27 +446,27 @@ gal_linkedlist_num_in_sll(struct gal_linkedlist_sll *list)
void
gal_linkedlist_sll_to_array(struct gal_linkedlist_sll *list,
- size_t **f, size_t *num, int inverse)
+ size_t **s, size_t *num, int inverse)
{
- size_t i, *tf;
+ size_t i, *ts;
struct gal_linkedlist_sll *tmp;
*num=gal_linkedlist_num_in_sll(list);
errno=0;
- *f=malloc(*num*sizeof(size_t));
- if(*f==NULL)
+ *s=malloc(*num*sizeof(size_t));
+ if(*s==NULL)
error(EXIT_FAILURE, errno, "linkedlist: array of gal_linkedlist_sll "
"with %lu elements", *num);
- tf=*f;
+ ts=*s;
i = inverse ? *num-1: 0;
if(inverse)
for(tmp=list;tmp!=NULL;tmp=tmp->next)
- tf[i--]=tmp->v;
+ ts[i--]=tmp->v;
else
for(tmp=list;tmp!=NULL;tmp=tmp->next)
- tf[i++]=tmp->v;
+ ts[i++]=tmp->v;
}
@@ -522,67 +521,6 @@ gal_linkedlist_free_sll(struct gal_linkedlist_sll *list)
/****************************************************************
- ****************** Two way SLL ***********************
- ***************** size_t ********************
- ****************************************************************/
-
-void
-gal_linkedlist_add_to_tsll_end(struct gal_linkedlist_tsll **last, size_t value)
-{
- struct gal_linkedlist_tsll *newnode;
-
- errno=0;
- newnode=malloc(sizeof *newnode);
- if(newnode==NULL)
- error(EXIT_FAILURE, errno, "linkedlist: New element in "
- "gal_linkedlist_tsll");
-
- newnode->v=value;
- newnode->next=*last;
- newnode->prev=NULL;
- if(*last) /* If *list is not NULL */
- (*last)->prev=newnode;
- *last=newnode;
-}
-
-
-
-
-
-/* Note that start has to be initialized. */
-void
-gal_linkedlist_pop_from_tsll_start(struct gal_linkedlist_tsll **first,
- size_t *value)
-{
- struct gal_linkedlist_tsll *tmp;
- tmp=*first;
- *value=tmp->v;
- *first=tmp->prev;
- free(tmp);
- if(*first)
- (*first)->next=NULL;
-}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-/****************************************************************
****************** Ordered SLL ********************
***************** size_t ********************
****************************************************************/
@@ -699,17 +637,17 @@ gal_linkedlist_osll_into_sll(struct gal_linkedlist_osll
*in,
*/
void
-gal_linkedlist_print_tosll(struct gal_linkedlist_tosll *l,
- struct gal_linkedlist_tosll *s)
+gal_linkedlist_print_tosll(struct gal_linkedlist_tosll *largest,
+ struct gal_linkedlist_tosll *smallest)
{
size_t counter=1; /* We are not counting array elements :-D ! */
- while(l!=NULL)
+ while(largest!=NULL)
{
printf("\t%-5lu (%lu, %.4f) \n", counter++,
- l->v, l->s);
- l=l->next;
- printf("\t\t\t\t(%lu, %.4f)\n", s->v, s->s);
- s=s->prev;
+ largest->v, largest->s);
+ largest=largest->next;
+ printf("\t\t\t\t(%lu, %.4f)\n", smallest->v, smallest->s);
+ smallest=smallest->prev;
}
printf("\n");
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gnuastro-commits] master de05eca: linkedlist.h functions added to the book,
Mohammad Akhlaghi <=