Commit | Line | Data |
---|---|---|
f7f55db8 | 1 | ;;; GNU Guix --- Functional package management for GNU |
ad6f1330 | 2 | ;;; Copyright © 2015, 2016, 2019 Ricardo Wurmus <rekado@elephly.net> |
3a1d01ca | 3 | ;;; Copyright © 2016, 2017, 2019 Tobias Geerinckx-Rice <me@tobias.gr> |
9d466489 | 4 | ;;; Copyright © 2018 Meiyo Peng <meiyo.peng@gmail.com> |
f7f55db8 RW |
5 | ;;; |
6 | ;;; This file is part of GNU Guix. | |
7 | ;;; | |
8 | ;;; GNU Guix is free software; you can redistribute it and/or modify it | |
9 | ;;; under the terms of the GNU General Public License as published by | |
10 | ;;; the Free Software Foundation; either version 3 of the License, or (at | |
11 | ;;; your option) any later version. | |
12 | ;;; | |
13 | ;;; GNU Guix is distributed in the hope that it will be useful, but | |
14 | ;;; WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | ;;; GNU General Public License for more details. | |
17 | ;;; | |
18 | ;;; You should have received a copy of the GNU General Public License | |
19 | ;;; along with GNU Guix. If not, see <http://www.gnu.org/licenses/>. | |
20 | ||
21 | (define-module (gnu packages datastructures) | |
22 | #:use-module (gnu packages) | |
ad6f1330 | 23 | #:use-module (gnu packages documentation) |
754667f0 | 24 | #:use-module (gnu packages perl) |
f7f55db8 RW |
25 | #:use-module ((guix licenses) #:prefix license:) |
26 | #:use-module (guix packages) | |
27 | #:use-module (guix download) | |
d1293d42 | 28 | #:use-module (guix git-download) |
ad6f1330 | 29 | #:use-module (guix build-system cmake) |
f7f55db8 RW |
30 | #:use-module (guix build-system gnu)) |
31 | ||
b4464d38 RW |
32 | (define-public gdsl |
33 | (package | |
34 | (name "gdsl") | |
35 | (version "1.8") | |
36 | (source (origin | |
37 | (method url-fetch) | |
38 | (uri (string-append "http://download.gna.org/gdsl/" | |
39 | "gdsl-" version ".tar.gz")) | |
40 | (sha256 | |
41 | (base32 | |
42 | "1v64jvlnj8jfpphphgjgb36p0kv50kwfyqncf0y12f16v8ydyiaw")))) | |
43 | (build-system gnu-build-system) | |
44 | (home-page "http://home.gna.org/gdsl/") | |
45 | (synopsis "Generic data structures library") | |
46 | (description "The Generic Data Structures Library (GDSL) is a collection | |
47 | of routines for generic data structures manipulation. It is a re-entrant | |
48 | library fully written from scratch in pure ANSI C. It is designed to offer | |
49 | for C programmers common data structures with powerful algorithms, and hidden | |
50 | implementation. Available structures are lists, queues, stacks, hash tables, | |
51 | binary trees, binary search trees, red-black trees, 2D arrays, permutations | |
52 | and heaps.") | |
53 | (license license:gpl2+))) | |
54 | ||
9d466489 MP |
55 | (define-public marisa |
56 | (package | |
57 | (name "marisa") | |
58 | (version "0.2.5") | |
59 | (source | |
60 | (origin | |
61 | (method url-fetch) | |
62 | (uri (string-append "https://github.com/s-yata/marisa-trie" | |
63 | "/releases/download/v" version "/" name "-" | |
64 | version ".tar.gz")) | |
65 | (sha256 | |
66 | (base32 "19ifrcmnbr9whaaf4ly3s9ndyiq9sjqhnfkrxbz9zsb44w2n36hf")))) | |
67 | (build-system gnu-build-system) | |
68 | (home-page "https://github.com/s-yata/marisa-trie") | |
69 | (synopsis "Trie data structure C++ library") | |
70 | (description "Matching Algorithm with Recursively Implemented | |
71 | StorAge (MARISA) is a static and space-efficient trie data structure C++ | |
72 | library.") | |
73 | ||
74 | ;; Dual-licensed, according to docs/readme.en.html (source files lack | |
75 | ;; copyright/license headers.) | |
76 | (license (list license:bsd-2 license:lgpl2.1+)))) | |
77 | ||
f7f55db8 RW |
78 | (define-public sparsehash |
79 | (package | |
80 | (name "sparsehash") | |
81 | (version "2.0.3") | |
82 | (source (origin | |
83 | (method url-fetch) | |
84 | (uri (string-append "https://github.com/sparsehash/sparsehash/" | |
85 | "archive/sparsehash-" version ".tar.gz")) | |
86 | (sha256 | |
87 | (base32 | |
88 | "133szz0ldwch0kd91l0sa57qsnl020njn622szd9cxrjqyjqds85")))) | |
89 | (build-system gnu-build-system) | |
90 | (synopsis "Memory-efficient hashtable implementations") | |
91 | (description | |
92 | "This library contains several hash-map implementations, similar in API | |
93 | to SGI's @code{hash_map} class, but with different performance | |
94 | characteristics. @code{sparse_hash_map} uses very little space overhead, 1-2 | |
d1e4ad1b | 95 | bits per entry. @code{dense_hash_map} is very fast, particularly on lookup. |
f7f55db8 RW |
96 | @code{sparse_hash_set} and @code{dense_hash_set} are the set versions of these |
97 | routines. All these implementation use a hashtable with internal quadratic | |
98 | probing. This method is space-efficient -- there is no pointer overhead -- | |
99 | and time-efficient for good hash functions.") | |
100 | (home-page "https://github.com/sparsehash/sparsehash") | |
101 | (license license:bsd-3))) | |
592ccdd3 TGR |
102 | |
103 | (define-public ssdeep | |
104 | (package | |
105 | (name "ssdeep") | |
106 | (version "2.13") | |
107 | (source (origin | |
108 | (method url-fetch) | |
109 | (uri (string-append "mirror://sourceforge/ssdeep/" | |
110 | name "-" version "/" | |
111 | name "-" version ".tar.gz")) | |
112 | (sha256 | |
113 | (base32 | |
114 | "1igqy0j7jrklb8fdlrm6ald4cyl1fda5ipfl8crzyl6bax2ajk3f")))) | |
115 | (build-system gnu-build-system) | |
116 | (home-page "http://ssdeep.sourceforge.net") | |
117 | (synopsis "Context-triggered piecewise hashing algorithm") | |
118 | (description "ssdeep computes and matches context triggered piecewise | |
119 | hashes (CTPH), also called fuzzy checksums. It can identify similar files | |
120 | that have sequences of identical bytes in the same order, even though bytes | |
121 | in between these sequences may be different in both content and length.") | |
122 | (license license:gpl2+))) | |
754667f0 TGR |
123 | |
124 | (define-public liburcu | |
125 | (package | |
126 | (name "liburcu") | |
2b6cd06e | 127 | (version "0.11.1") |
754667f0 TGR |
128 | (source (origin |
129 | (method url-fetch) | |
130 | (uri (string-append "https://www.lttng.org/files/urcu/" | |
131 | "userspace-rcu-" version ".tar.bz2")) | |
132 | (sha256 | |
133 | (base32 | |
2b6cd06e | 134 | "0l1kxgzch4m8fxiz2hc8fwg56hrvzzspp7n0svnl7i7iycdrgfcj")))) |
754667f0 TGR |
135 | (build-system gnu-build-system) |
136 | (native-inputs | |
137 | `(("perl" ,perl))) ; for tests | |
4dfda8dc | 138 | (home-page "https://liburcu.org/") |
754667f0 TGR |
139 | (synopsis "User-space RCU data synchronisation library") |
140 | (description "liburcu is a user-space @dfn{Read-Copy-Update} (RCU) data | |
141 | synchronisation library. It provides read-side access that scales linearly | |
142 | with the number of cores. liburcu-cds provides efficient data structures | |
143 | based on RCU and lock-free algorithms. These structures include hash tables, | |
144 | queues, stacks, and doubly-linked lists.") | |
145 | (license license:lgpl2.1+))) | |
cc3ac162 TGR |
146 | |
147 | (define-public uthash | |
148 | (package | |
149 | (name "uthash") | |
150 | (version "2.0.2") | |
151 | (source | |
152 | (origin | |
d1293d42 RW |
153 | (method git-fetch) |
154 | (uri (git-reference | |
155 | (url "https://github.com/troydhanson/uthash.git") | |
156 | (commit (string-append "v" version)))) | |
157 | (file-name (git-file-name name version)) | |
cc3ac162 TGR |
158 | (sha256 |
159 | (base32 | |
d1293d42 | 160 | "0kslz8k6lssh7fl7ayzwlj62p0asxs3dq03357ls5ywjad238gqg")))) |
cc3ac162 TGR |
161 | (build-system gnu-build-system) |
162 | (native-inputs | |
163 | `(("perl" ,perl))) | |
164 | (arguments | |
165 | `(#:make-flags | |
166 | (list "CC=gcc") | |
167 | #:phases | |
168 | (modify-phases %standard-phases | |
169 | (delete 'configure) ; nothing to configure | |
170 | (delete 'build) ; nothing to build | |
171 | (replace 'check | |
172 | (lambda* (#:key make-flags #:allow-other-keys) | |
173 | (with-directory-excursion "tests" | |
c9e75159 | 174 | (apply invoke "make" make-flags)))) |
cc3ac162 TGR |
175 | (replace 'install |
176 | ;; There is no top-level Makefile to do this for us. | |
177 | (lambda* (#:key outputs #:allow-other-keys) | |
178 | (let* ((out (assoc-ref outputs "out")) | |
179 | (doc (string-append out "/share/doc/" ,name)) | |
180 | (include (string-append out "/include"))) | |
181 | ;; Don't install HTML files: they're just the below .txt files | |
182 | ;; dolled up, can be stale, and regeneration requires asciidoc. | |
183 | (for-each (λ (file) (install-file file doc)) | |
184 | (find-files "doc" "\\.txt$")) | |
185 | (for-each (λ (file) (install-file file include)) | |
186 | (find-files "src" "\\.h$")) | |
187 | #t)))))) | |
188 | (home-page "https://troydhanson.github.io/uthash/") | |
189 | (synopsis | |
190 | "Hash tables, lists, and other data structures implemented as C macros") | |
191 | (description | |
192 | "uthash implements a hash table and a few other basic data structures | |
193 | as C preprocessor macros. It aims to be minimalistic and efficient: it's | |
194 | around 1,000 lines of code which, being macros, inline automatically. | |
195 | ||
196 | Unlike function calls with fixed prototypes, macros operate on untyped | |
197 | arguments. Thus, they are able to work with any type of structure and key. | |
198 | Any C structure can be stored in a hash table by adding @code{UT_hash_handle} | |
199 | to the structure and choosing one or more fields to act as the key.") | |
200 | (license license:bsd-2))) | |
ad6f1330 RW |
201 | |
202 | (define-public sdsl-lite | |
203 | (package | |
204 | (name "sdsl-lite") | |
205 | (version "2.1.1") | |
206 | (source (origin | |
207 | (method url-fetch) | |
208 | (uri (string-append "https://github.com/simongog/sdsl-lite/" | |
209 | "releases/download/v" version "/" | |
210 | "sdsl-lite-" version | |
211 | ".tar.gz.offline.install.gz")) | |
212 | (sha256 | |
213 | (base32 | |
214 | "1v86ivv3mmdy802i9xkjpxb4cggj3s27wb19ja4sw1klnivjj69g")))) | |
215 | (build-system cmake-build-system) | |
216 | (native-inputs | |
217 | `(("doxygen" ,doxygen))) | |
218 | (home-page "https://github.com/simongog/sdsl-lite") | |
219 | (synopsis "Succinct data structure library") | |
220 | (description "The Succinct Data Structure Library (SDSL) is a powerful and | |
221 | flexible C++11 library implementing succinct data structures. In total, the | |
222 | library contains the highlights of 40 research publications. Succinct data | |
223 | structures can represent an object (such as a bitvector or a tree) in space | |
224 | close to the information-theoretic lower bound of the object while supporting | |
225 | operations of the original object efficiently. The theoretical time | |
226 | complexity of an operation performed on the classical data structure and the | |
227 | equivalent succinct data structure are (most of the time) identical.") | |
228 | (license license:gpl3+))) |