gnu/packages/datastructures.scm

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