Commit | Line | Data |
---|---|---|
f7f55db8 | 1 | ;;; GNU Guix --- Functional package management for GNU |
3546771c | 2 | ;;; Copyright © 2015, 2016, 2018, 2019 Ricardo Wurmus <rekado@elephly.net> |
10e318bd | 3 | ;;; Copyright © 2016, 2017, 2019–2021 Tobias Geerinckx-Rice <me@tobias.gr> |
9d466489 | 4 | ;;; Copyright © 2018 Meiyo Peng <meiyo.peng@gmail.com> |
ab15bbea | 5 | ;;; Copyright © 2019, 2020 Efraim Flashner <efraim@flashner.co.il> |
5eb97480 | 6 | ;;; Copyright © 2020 Mark H Weaver <mhw@netris.org> |
0d59aecf | 7 | ;;; Copyright © 2020 Marius Bakke <marius@gnu.org> |
f7f55db8 RW |
8 | ;;; |
9 | ;;; This file is part of GNU Guix. | |
10 | ;;; | |
11 | ;;; GNU Guix is free software; you can redistribute it and/or modify it | |
12 | ;;; under the terms of the GNU General Public License as published by | |
13 | ;;; the Free Software Foundation; either version 3 of the License, or (at | |
14 | ;;; your option) any later version. | |
15 | ;;; | |
16 | ;;; GNU Guix is distributed in the hope that it will be useful, but | |
17 | ;;; WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | ;;; GNU General Public License for more details. | |
20 | ;;; | |
21 | ;;; You should have received a copy of the GNU General Public License | |
22 | ;;; along with GNU Guix. If not, see <http://www.gnu.org/licenses/>. | |
23 | ||
24 | (define-module (gnu packages datastructures) | |
25 | #:use-module (gnu packages) | |
9b26efdd | 26 | #:use-module (gnu packages autotools) |
5eb97480 | 27 | #:use-module (gnu packages boost) |
0d59aecf | 28 | #:use-module (gnu packages build-tools) ;for meson-0.55 |
754667f0 | 29 | #:use-module (gnu packages perl) |
f7f55db8 RW |
30 | #:use-module ((guix licenses) #:prefix license:) |
31 | #:use-module (guix packages) | |
32 | #:use-module (guix download) | |
d1293d42 | 33 | #:use-module (guix git-download) |
ad6f1330 | 34 | #:use-module (guix build-system cmake) |
0d59aecf MB |
35 | #:use-module (guix build-system gnu) |
36 | #:use-module (guix build-system meson)) | |
f7f55db8 | 37 | |
b4464d38 RW |
38 | (define-public gdsl |
39 | (package | |
40 | (name "gdsl") | |
41 | (version "1.8") | |
42 | (source (origin | |
74cb33c2 | 43 | (method git-fetch) |
44 | (uri (git-reference | |
45 | (url "https://example.org") ;only hosted on Software Heritage | |
46 | (commit "6adb53be8b8f9f2e4bbfc92d357eedeefb4c7430"))) | |
47 | (file-name (git-file-name name version)) | |
b4464d38 RW |
48 | (sha256 |
49 | (base32 | |
74cb33c2 | 50 | "0a52g12d9sf9hhcyvwfd7xdazj2a9i9jh97cnlqf2ymvwnvjk1g0")))) |
b4464d38 | 51 | (build-system gnu-build-system) |
74cb33c2 | 52 | (home-page "https://web.archive.org/web/20170502005430/http://home.gna.org/gdsl/") |
b4464d38 RW |
53 | (synopsis "Generic data structures library") |
54 | (description "The Generic Data Structures Library (GDSL) is a collection | |
55 | of routines for generic data structures manipulation. It is a re-entrant | |
56 | library fully written from scratch in pure ANSI C. It is designed to offer | |
57 | for C programmers common data structures with powerful algorithms, and hidden | |
58 | implementation. Available structures are lists, queues, stacks, hash tables, | |
59 | binary trees, binary search trees, red-black trees, 2D arrays, permutations | |
60 | and heaps.") | |
61 | (license license:gpl2+))) | |
62 | ||
9d466489 MP |
63 | (define-public marisa |
64 | (package | |
65 | (name "marisa") | |
9b26efdd | 66 | (version "0.2.6") |
9d466489 MP |
67 | (source |
68 | (origin | |
69 | (method url-fetch) | |
9b26efdd TGR |
70 | (uri (string-append "https://github.com/s-yata/marisa-trie/files/" |
71 | "4832504/marisa-" version ".tar.gz")) | |
9d466489 | 72 | (sha256 |
9b26efdd | 73 | (base32 "1pk6wmi28pa8srb4szybrwfn71jldb61c5vgxsiayxcyg1ya4qqh")))) |
9d466489 | 74 | (build-system gnu-build-system) |
9b26efdd TGR |
75 | (native-inputs |
76 | `(("autoconf" ,autoconf) | |
77 | ("automake" ,automake) | |
78 | ("libtool" ,libtool))) | |
9d466489 MP |
79 | (home-page "https://github.com/s-yata/marisa-trie") |
80 | (synopsis "Trie data structure C++ library") | |
c47485b2 TGR |
81 | (description "@acronym{MARISA, Matching Algorithm with Recursively |
82 | Implemented StorAge} is a static and space-efficient trie data structure C++ | |
9d466489 MP |
83 | library.") |
84 | ||
85 | ;; Dual-licensed, according to docs/readme.en.html (source files lack | |
86 | ;; copyright/license headers.) | |
87 | (license (list license:bsd-2 license:lgpl2.1+)))) | |
88 | ||
f7f55db8 RW |
89 | (define-public sparsehash |
90 | (package | |
91 | (name "sparsehash") | |
907d5ed1 | 92 | (version "2.0.4") |
f7f55db8 | 93 | (source (origin |
fea30e12 EF |
94 | (method git-fetch) |
95 | (uri (git-reference | |
b0e7b699 | 96 | (url "https://github.com/sparsehash/sparsehash") |
fea30e12 EF |
97 | (commit (string-append name "-" version)))) |
98 | (file-name (git-file-name name version)) | |
f7f55db8 RW |
99 | (sha256 |
100 | (base32 | |
907d5ed1 | 101 | "1pf1cjvcjdmb9cd6gcazz64x0cd2ndpwh6ql2hqpypjv725xwxy7")))) |
f7f55db8 RW |
102 | (build-system gnu-build-system) |
103 | (synopsis "Memory-efficient hashtable implementations") | |
104 | (description | |
105 | "This library contains several hash-map implementations, similar in API | |
106 | to SGI's @code{hash_map} class, but with different performance | |
107 | characteristics. @code{sparse_hash_map} uses very little space overhead, 1-2 | |
d1e4ad1b | 108 | bits per entry. @code{dense_hash_map} is very fast, particularly on lookup. |
f7f55db8 RW |
109 | @code{sparse_hash_set} and @code{dense_hash_set} are the set versions of these |
110 | routines. All these implementation use a hashtable with internal quadratic | |
111 | probing. This method is space-efficient -- there is no pointer overhead -- | |
112 | and time-efficient for good hash functions.") | |
113 | (home-page "https://github.com/sparsehash/sparsehash") | |
114 | (license license:bsd-3))) | |
592ccdd3 TGR |
115 | |
116 | (define-public ssdeep | |
117 | (package | |
118 | (name "ssdeep") | |
ffd57da1 TGR |
119 | (version "2.14.1") |
120 | (source | |
121 | (origin | |
122 | (method url-fetch) | |
123 | (uri (string-append "https://github.com/ssdeep-project/ssdeep/" | |
124 | "releases/download/release-" version "/" | |
125 | "ssdeep-" version ".tar.gz")) | |
126 | (sha256 | |
127 | (base32 "04qkjc6kksxkv7xbnk32rwmf3a8czdv2vvrdzfs0kw06h73snbpz")))) | |
592ccdd3 | 128 | (build-system gnu-build-system) |
6be0d9f4 TGR |
129 | (arguments |
130 | `(#:configure-flags | |
131 | (list "--disable-static"))) | |
73e560bc | 132 | (home-page "https://ssdeep-project.github.io") |
592ccdd3 TGR |
133 | (synopsis "Context-triggered piecewise hashing algorithm") |
134 | (description "ssdeep computes and matches context triggered piecewise | |
135 | hashes (CTPH), also called fuzzy checksums. It can identify similar files | |
136 | that have sequences of identical bytes in the same order, even though bytes | |
137 | in between these sequences may be different in both content and length.") | |
138 | (license license:gpl2+))) | |
754667f0 TGR |
139 | |
140 | (define-public liburcu | |
141 | (package | |
142 | (name "liburcu") | |
467f7919 | 143 | (version "0.12.2") |
754667f0 TGR |
144 | (source (origin |
145 | (method url-fetch) | |
146 | (uri (string-append "https://www.lttng.org/files/urcu/" | |
147 | "userspace-rcu-" version ".tar.bz2")) | |
148 | (sha256 | |
149 | (base32 | |
467f7919 | 150 | "0yx69kbx9zd6ayjzvwvglilhdnirq4f1x1sdv33jy8bc9wgc3vsf")))) |
754667f0 | 151 | (build-system gnu-build-system) |
702affc6 TGR |
152 | (arguments |
153 | `(#:configure-flags | |
154 | (list "--disable-static"))) | |
754667f0 TGR |
155 | (native-inputs |
156 | `(("perl" ,perl))) ; for tests | |
4dfda8dc | 157 | (home-page "https://liburcu.org/") |
754667f0 TGR |
158 | (synopsis "User-space RCU data synchronisation library") |
159 | (description "liburcu is a user-space @dfn{Read-Copy-Update} (RCU) data | |
160 | synchronisation library. It provides read-side access that scales linearly | |
161 | with the number of cores. liburcu-cds provides efficient data structures | |
162 | based on RCU and lock-free algorithms. These structures include hash tables, | |
163 | queues, stacks, and doubly-linked lists.") | |
164 | (license license:lgpl2.1+))) | |
cc3ac162 TGR |
165 | |
166 | (define-public uthash | |
167 | (package | |
168 | (name "uthash") | |
e5d193da | 169 | (version "2.1.0") |
cc3ac162 TGR |
170 | (source |
171 | (origin | |
d1293d42 RW |
172 | (method git-fetch) |
173 | (uri (git-reference | |
b0e7b699 | 174 | (url "https://github.com/troydhanson/uthash") |
d1293d42 RW |
175 | (commit (string-append "v" version)))) |
176 | (file-name (git-file-name name version)) | |
cc3ac162 | 177 | (sha256 |
e5d193da | 178 | (base32 "0k80bjbb6ss5wpmfmfji6xbyjm990hg9kcshwwnhdnh73vxkcd1m")))) |
cc3ac162 TGR |
179 | (build-system gnu-build-system) |
180 | (native-inputs | |
181 | `(("perl" ,perl))) | |
182 | (arguments | |
183 | `(#:make-flags | |
184 | (list "CC=gcc") | |
185 | #:phases | |
186 | (modify-phases %standard-phases | |
187 | (delete 'configure) ; nothing to configure | |
188 | (delete 'build) ; nothing to build | |
189 | (replace 'check | |
190 | (lambda* (#:key make-flags #:allow-other-keys) | |
191 | (with-directory-excursion "tests" | |
c9e75159 | 192 | (apply invoke "make" make-flags)))) |
cc3ac162 TGR |
193 | (replace 'install |
194 | ;; There is no top-level Makefile to do this for us. | |
195 | (lambda* (#:key outputs #:allow-other-keys) | |
196 | (let* ((out (assoc-ref outputs "out")) | |
6655e2e2 | 197 | (doc (string-append out "/share/doc/" ,name "-" ,version)) |
cc3ac162 TGR |
198 | (include (string-append out "/include"))) |
199 | ;; Don't install HTML files: they're just the below .txt files | |
200 | ;; dolled up, can be stale, and regeneration requires asciidoc. | |
201 | (for-each (λ (file) (install-file file doc)) | |
202 | (find-files "doc" "\\.txt$")) | |
203 | (for-each (λ (file) (install-file file include)) | |
204 | (find-files "src" "\\.h$")) | |
205 | #t)))))) | |
206 | (home-page "https://troydhanson.github.io/uthash/") | |
207 | (synopsis | |
208 | "Hash tables, lists, and other data structures implemented as C macros") | |
209 | (description | |
210 | "uthash implements a hash table and a few other basic data structures | |
211 | as C preprocessor macros. It aims to be minimalistic and efficient: it's | |
212 | around 1,000 lines of code which, being macros, inline automatically. | |
213 | ||
214 | Unlike function calls with fixed prototypes, macros operate on untyped | |
215 | arguments. Thus, they are able to work with any type of structure and key. | |
216 | Any C structure can be stored in a hash table by adding @code{UT_hash_handle} | |
217 | to the structure and choosing one or more fields to act as the key.") | |
218 | (license license:bsd-2))) | |
ad6f1330 RW |
219 | |
220 | (define-public sdsl-lite | |
221 | (package | |
222 | (name "sdsl-lite") | |
223 | (version "2.1.1") | |
224 | (source (origin | |
225 | (method url-fetch) | |
226 | (uri (string-append "https://github.com/simongog/sdsl-lite/" | |
227 | "releases/download/v" version "/" | |
228 | "sdsl-lite-" version | |
229 | ".tar.gz.offline.install.gz")) | |
230 | (sha256 | |
231 | (base32 | |
aca2bf51 EF |
232 | "1v86ivv3mmdy802i9xkjpxb4cggj3s27wb19ja4sw1klnivjj69g")) |
233 | (modules '((guix build utils))) | |
234 | (snippet | |
235 | '(begin | |
236 | (delete-file-recursively "external") #t)) | |
237 | (patches | |
238 | (list (origin | |
239 | (method url-fetch) | |
240 | (uri "https://salsa.debian.org/science-team/libsdsl/raw/debian/2.1.1+dfsg-2/debian/patches/0001-Patch-cmake-files.patch") | |
241 | (file-name "sdsl-lite-dont-use-bundled-libraries.patch") | |
242 | (sha256 | |
243 | (base32 | |
244 | "0m542xpys54bni29zibgrfpgpd0zgyny4h131virxsanixsbz52z"))))))) | |
ad6f1330 | 245 | (build-system cmake-build-system) |
aca2bf51 | 246 | (arguments |
ab15bbea | 247 | `(#:phases |
aca2bf51 EF |
248 | (modify-phases %standard-phases |
249 | (add-after 'install 'install-static-library | |
250 | (lambda* (#:key outputs #:allow-other-keys) | |
251 | (let ((out (assoc-ref outputs "out"))) | |
252 | (copy-file "lib/libsdsl_static.a" | |
253 | (string-append out "/lib/libsdsl.a"))) | |
ab15bbea EF |
254 | #t)) |
255 | (add-after 'install 'install-pkgconfig-file | |
256 | (lambda* (#:key outputs #:allow-other-keys) | |
a6b72a0f EF |
257 | (let* ((out (assoc-ref outputs "out")) |
258 | (lib (string-append out "/lib"))) | |
ab15bbea EF |
259 | (mkdir-p (string-append lib "/pkgconfig")) |
260 | (with-output-to-file (string-append lib "/pkgconfig/sdsl-lite.pc") | |
261 | (lambda _ | |
262 | (format #t "prefix=~a~@ | |
263 | exec_prefix=${prefix}~@ | |
264 | libdir=${exec_prefix}/lib~@ | |
265 | includedir=${prefix}/include~@ | |
266 | ~@ | |
267 | ~@ | |
268 | Name: sdsl~@ | |
269 | Version: ~a~@ | |
270 | Description: SDSL: Succinct Data Structure Library~@ | |
271 | Libs: -L${libdir} -lsdsl -ldivsufsort -ldivsufsort64~@ | |
272 | Cflags: -I${includedir}~%" | |
273 | out ,version))) | |
274 | #t)))))) | |
aca2bf51 EF |
275 | (native-inputs |
276 | `(("libdivsufsort" ,libdivsufsort))) | |
ad6f1330 RW |
277 | (home-page "https://github.com/simongog/sdsl-lite") |
278 | (synopsis "Succinct data structure library") | |
279 | (description "The Succinct Data Structure Library (SDSL) is a powerful and | |
280 | flexible C++11 library implementing succinct data structures. In total, the | |
281 | library contains the highlights of 40 research publications. Succinct data | |
282 | structures can represent an object (such as a bitvector or a tree) in space | |
283 | close to the information-theoretic lower bound of the object while supporting | |
284 | operations of the original object efficiently. The theoretical time | |
285 | complexity of an operation performed on the classical data structure and the | |
286 | equivalent succinct data structure are (most of the time) identical.") | |
287 | (license license:gpl3+))) | |
3546771c | 288 | |
0d59aecf MB |
289 | (define-public tllist |
290 | (package | |
291 | (name "tllist") | |
10e318bd | 292 | (version "1.0.5") |
0d59aecf MB |
293 | (home-page "https://codeberg.org/dnkl/tllist") |
294 | (source (origin | |
295 | (method git-fetch) | |
296 | (uri (git-reference (url home-page) (commit version))) | |
297 | (file-name (git-file-name name version)) | |
298 | (sha256 | |
299 | (base32 | |
10e318bd | 300 | "061mkg6hc9x89zya3bw18ymxlzd8fbhjipxpva8x01lh2vp1d4f0")))) |
0d59aecf MB |
301 | (build-system meson-build-system) |
302 | (arguments | |
303 | `(#:meson ,meson-0.55)) | |
304 | (synopsis "Typed link list for C") | |
305 | (description | |
306 | "@code{tllist} is a @dfn{typed linked list} C header file only library | |
307 | implemented using pre-processor macros. It supports primitive data types as | |
308 | well as aggregated ones such as structs, enums and unions.") | |
309 | (license license:expat))) | |
310 | ||
3546771c EF |
311 | (define-public libdivsufsort |
312 | (package | |
313 | (name "libdivsufsort") | |
314 | (version "2.0.1") | |
315 | (source (origin | |
316 | (method git-fetch) | |
317 | (uri (git-reference | |
b0e7b699 | 318 | (url "https://github.com/y-256/libdivsufsort") |
3546771c EF |
319 | (commit version))) |
320 | (file-name (git-file-name name version)) | |
321 | (sha256 | |
322 | (base32 | |
323 | "0fgdz9fzihlvjjrxy01md1bv9vh12rkgkwbm90b1hj5xpbaqp7z2")))) | |
324 | (build-system cmake-build-system) | |
325 | (arguments | |
326 | '(#:tests? #f ; there are no tests | |
327 | #:configure-flags | |
328 | ;; Needed for rapmap and sailfish. | |
329 | '("-DBUILD_DIVSUFSORT64=ON"))) | |
330 | (home-page "https://github.com/y-256/libdivsufsort") | |
331 | (synopsis "Lightweight suffix-sorting library") | |
332 | (description "libdivsufsort is a software library that implements a | |
333 | lightweight suffix array construction algorithm. This library provides a | |
334 | simple and an efficient C API to construct a suffix array and a | |
335 | Burrows-Wheeler transformed string from a given string over a constant-size | |
336 | alphabet. The algorithm runs in O(n log n) worst-case time using only 5n+O(1) | |
337 | bytes of memory space, where n is the length of the string.") | |
338 | (license license:expat))) | |
5eb97480 MW |
339 | |
340 | (define-public robin-map | |
341 | (package | |
342 | (name "robin-map") | |
343 | (version "0.6.3") | |
344 | (source (origin | |
345 | (method git-fetch) | |
346 | (uri (git-reference | |
347 | (url "https://github.com/Tessil/robin-map") | |
348 | (commit (string-append "v" version)))) | |
349 | (file-name (git-file-name name version)) | |
350 | (sha256 | |
351 | (base32 | |
352 | "1li70vwsksva9c4yly90hjafgqfixi1g6d52qq9p6r60vqc4pkjj")))) | |
353 | (build-system cmake-build-system) | |
354 | (native-inputs | |
355 | `(("boost" ,boost))) ; needed for tests | |
356 | (arguments | |
357 | `(#:phases | |
358 | (modify-phases %standard-phases | |
359 | (replace 'check | |
360 | (lambda _ | |
361 | (mkdir "tests") | |
362 | (with-directory-excursion "tests" | |
363 | (invoke "cmake" "../../source/tests") | |
364 | (invoke "cmake" "--build" ".") | |
365 | (invoke "./tsl_robin_map_tests"))))))) | |
366 | (home-page "https://github.com/Tessil/robin-map") | |
367 | (synopsis "C++ implementation of a fast hash map and hash set") | |
368 | (description "The robin-map library is a C++ implementation of a fast hash | |
369 | map and hash set using open-addressing and linear robin hood hashing with | |
370 | backward shift deletion to resolve collisions. | |
371 | ||
372 | Four classes are provided: tsl::robin_map, tsl::robin_set, tsl::robin_pg_map | |
373 | and tsl::robin_pg_set. The first two are faster and use a power of two growth | |
374 | policy, the last two use a prime growth policy instead and are able to cope | |
375 | better with a poor hash function.") | |
376 | (license license:expat))) |