gnu/packages/datastructures.scm

   1 ;;; GNU Guix --- Functional package management for GNU
   2 ;;; Copyright © 2015, 2016 Ricardo Wurmus <rekado@elephly.net>
   3 ;;; Copyright © 2016, 2017 Tobias Geerinckx-Rice <me@tobias.gr>
   4 ;;;
   5 ;;; This file is part of GNU Guix.
   6 ;;;
   7 ;;; GNU Guix is free software; you can redistribute it and/or modify it
   8 ;;; under the terms of the GNU General Public License as published by
   9 ;;; the Free Software Foundation; either version 3 of the License, or (at
  10 ;;; your option) any later version.
  11 ;;;
  12 ;;; GNU Guix is distributed in the hope that it will be useful, but
  13 ;;; WITHOUT ANY WARRANTY; without even the implied warranty of
  14 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 ;;; GNU General Public License for more details.
  16 ;;;
  17 ;;; You should have received a copy of the GNU General Public License
  18 ;;; along with GNU Guix.  If not, see <http://www.gnu.org/licenses/>.
  19
  20 (define-module (gnu packages datastructures)
  21   #:use-module (gnu packages)
  22   #:use-module (gnu packages perl)
  23   #:use-module ((guix licenses) #:prefix license:)
  24   #:use-module (guix packages)
  25   #:use-module (guix download)
  26   #:use-module (guix build-system gnu))
  27
  28 (define-public gdsl
  29   (package
  30     (name "gdsl")
  31     (version "1.8")
  32     (source (origin
  33               (method url-fetch)
  34               (uri (string-append "http://download.gna.org/gdsl/"
  35                                   "gdsl-" version ".tar.gz"))
  36               (sha256
  37                (base32
  38                 "1v64jvlnj8jfpphphgjgb36p0kv50kwfyqncf0y12f16v8ydyiaw"))))
  39     (build-system gnu-build-system)
  40     (home-page "http://home.gna.org/gdsl/")
  41     (synopsis "Generic data structures library")
  42     (description "The Generic Data Structures Library (GDSL) is a collection
  43 of routines for generic data structures manipulation.  It is a re-entrant
  44 library fully written from scratch in pure ANSI C.  It is designed to offer
  45 for C programmers common data structures with powerful algorithms, and hidden
  46 implementation.  Available structures are lists, queues, stacks, hash tables,
  47 binary trees, binary search trees, red-black trees, 2D arrays, permutations
  48 and heaps.")
  49     (license license:gpl2+)))
  50
  51 (define-public sparsehash
  52   (package
  53     (name "sparsehash")
  54     (version "2.0.3")
  55     (source (origin
  56               (method url-fetch)
  57               (uri (string-append "https://github.com/sparsehash/sparsehash/"
  58                                   "archive/sparsehash-" version ".tar.gz"))
  59               (sha256
  60                (base32
  61                 "133szz0ldwch0kd91l0sa57qsnl020njn622szd9cxrjqyjqds85"))))
  62     (build-system gnu-build-system)
  63     (synopsis "Memory-efficient hashtable implementations")
  64     (description
  65      "This library contains several hash-map implementations, similar in API
  66 to SGI's @code{hash_map} class, but with different performance
  67 characteristics.  @code{sparse_hash_map} uses very little space overhead, 1-2
  68 bits per entry.  @code{dense_hash_map} is very fast, particularly on lookup.
  69 @code{sparse_hash_set} and @code{dense_hash_set} are the set versions of these
  70 routines.  All these implementation use a hashtable with internal quadratic
  71 probing.  This method is space-efficient -- there is no pointer overhead --
  72 and time-efficient for good hash functions.")
  73     (home-page "https://github.com/sparsehash/sparsehash")
  74     (license license:bsd-3)))
  75
  76 (define-public ssdeep
  77   (package
  78     (name "ssdeep")
  79     (version "2.13")
  80     (source (origin
  81               (method url-fetch)
  82               (uri (string-append "mirror://sourceforge/ssdeep/"
  83                                   name "-" version "/"
  84                                   name "-" version ".tar.gz"))
  85               (sha256
  86                (base32
  87                 "1igqy0j7jrklb8fdlrm6ald4cyl1fda5ipfl8crzyl6bax2ajk3f"))))
  88     (build-system gnu-build-system)
  89     (home-page "http://ssdeep.sourceforge.net")
  90     (synopsis "Context-triggered piecewise hashing algorithm")
  91     (description "ssdeep computes and matches context triggered piecewise
  92 hashes (CTPH), also called fuzzy checksums.  It can identify similar files
  93 that have sequences of identical bytes in the same order, even though bytes
  94 in between these sequences may be different in both content and length.")
  95     (license license:gpl2+)))
  96
  97 (define-public liburcu
  98   (package
  99     (name "liburcu")
 100     (version "0.10.0")
 101     (source (origin
 102               (method url-fetch)
 103               (uri (string-append "https://www.lttng.org/files/urcu/"
 104                                   "userspace-rcu-" version ".tar.bz2"))
 105               (sha256
 106                (base32
 107                 "141imnd1s4bcd4wz0wk7sp3fj649kp8whp82gw49h48mlmxqmdbw"))))
 108     (build-system gnu-build-system)
 109     (native-inputs
 110      `(("perl" ,perl)))                 ; for tests
 111     (home-page "http://liburcu.org/")
 112     (synopsis "User-space RCU data synchronisation library")
 113     (description "liburcu is a user-space @dfn{Read-Copy-Update} (RCU) data
 114 synchronisation library.  It provides read-side access that scales linearly
 115 with the number of cores.  liburcu-cds provides efficient data structures
 116 based on RCU and lock-free algorithms.  These structures include hash tables,
 117 queues, stacks, and doubly-linked lists.")
 118     (license license:lgpl2.1+)))
 119
 120 (define-public uthash
 121   (package
 122     (name "uthash")
 123     (version "2.0.2")
 124     (source
 125      (origin
 126        (method url-fetch)
 127        (file-name (string-append name "-" version ".tar.gz"))
 128        (uri (string-append "https://github.com/troydhanson/uthash/archive/v"
 129                            version ".tar.gz"))
 130        (sha256
 131         (base32
 132          "1la82gdlyl7m8ahdjirigwfh7zjgkc24cvydrqcri0vsvm8iv8rl"))))
 133     (build-system gnu-build-system)
 134     (native-inputs
 135      `(("perl" ,perl)))
 136     (arguments
 137      `(#:make-flags
 138        (list "CC=gcc")
 139        #:phases
 140        (modify-phases %standard-phases
 141          (delete 'configure)            ; nothing to configure
 142          (delete 'build)                ; nothing to build
 143          (replace 'check
 144            (lambda* (#:key make-flags #:allow-other-keys)
 145              (with-directory-excursion "tests"
 146                (zero? (apply system* "make"
 147                              make-flags)))))
 148          (replace 'install
 149            ;; There is no top-level Makefile to do this for us.
 150            (lambda* (#:key outputs #:allow-other-keys)
 151              (let* ((out (assoc-ref outputs "out"))
 152                     (doc (string-append out "/share/doc/" ,name))
 153                     (include (string-append out "/include")))
 154                ;; Don't install HTML files: they're just the below .txt files
 155                ;; dolled up, can be stale, and regeneration requires asciidoc.
 156                (for-each (λ (file) (install-file file doc))
 157                          (find-files "doc" "\\.txt$"))
 158                (for-each (λ (file) (install-file file include))
 159                          (find-files "src" "\\.h$"))
 160                #t))))))
 161     (home-page "https://troydhanson.github.io/uthash/")
 162     (synopsis
 163      "Hash tables, lists, and other data structures implemented as C macros")
 164     (description
 165      "uthash implements a hash table and a few other basic data structures
 166 as C preprocessor macros.  It aims to be minimalistic and efficient: it's
 167 around 1,000 lines of code which, being macros, inline automatically.
 168
 169 Unlike function calls with fixed prototypes, macros operate on untyped
 170 arguments.  Thus, they are able to work with any type of structure and key.
 171 Any C structure can be stored in a hash table by adding @code{UT_hash_handle}
 172 to the structure and choosing one or more fields to act as the key.")
 173     (license license:bsd-2)))