cgit.sxemacs.org Git - sxemacs/blob - src/bloom.h

   1 /*
   2   bloom.c -- Bloom filters
   3   Copyright (C) 2006 Sebastian Freundt
   4
   5   Author:  Sebastian Freundt <hroptatyr@sxemacs.org>
   6
   7 This file is part of SXEmacs
   8
   9 SXEmacs is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 SXEmacs is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  21
  22
  23 /* Synched up with: Not in FSF. */
  24
  25 #ifndef INCLUDED_bloom_h_
  26 #define INCLUDED_bloom_h_
  27
  28 \f
  29 #define BLOOM_DEPTH_TYPE uint8_t /* which type to use for each slot */
  30
  31 typedef BLOOM_DEPTH_TYPE* bloom_vector;
  32
  33 struct Lisp_Bloom {
  34         struct lcrecord_header lheader;
  35
  36         bloom_vector vector;
  37         uint32_t order;
  38         uint32_t degree;
  39         uint32_t size;
  40         /* a scratch vector for the hash fun,
  41          * avoids dozens of xmalloc/xfree calls */
  42         uint32_t *scratch;
  43 };
  44 typedef struct Lisp_Bloom Lisp_Bloom;
  45
  46 extern Lisp_Object Qbloomp;
  47
  48 DECLARE_LRECORD(bloom, Lisp_Bloom);
  49 #define XBLOOM(x) XRECORD(x, bloom, Lisp_Bloom)
  50 #define XSETBLOOM(x, p) XSETRECORD(x, p, bloom)
  51 #define wrap_bloom(p) wrap_object(p)
  52 #define BLOOMP(x) RECORDP(x, bloom)
  53 #define CHECK_BLOOM(x) CHECK_RECORD(x, bloom)
  54 #define CONCHECK_BLOOM(x) CONCHECK_RECORD(x, bloom)
  55
  56 #define bloom_vector(ms) (ms)->vector
  57 #define bloom_order(ms) (ms)->order
  58 #define bloom_degree(ms) (ms)->degree
  59 #define bloom_size(ms) (ms)->size
  60 #define bloom_scratch(ms) (ms)->scratch
  61 #define XBLOOM_VECTOR(x) bloom_vector(XBLOOM(x))
  62 #define XBLOOM_ORDER(x) bloom_order(XBLOOM(x))
  63 #define XBLOOM_DEGREE(x) bloom_degree(XBLOOM(x))
  64 #define XBLOOM_SIZE(x) bloom_size(XBLOOM(x))
  65 #define XBLOOM_SCRATCH(x) bloom_scratch(XBLOOM(x))
  66
  67 \f
  68 extern Lisp_Object make_bloom(uint32_t, uint32_t);
  69 extern Lisp_Object make_bloom_universe(uint32_t, uint32_t);
  70 extern int bloom_owns_p(Lisp_Bloom*, Lisp_Object);
  71 extern void bloom_add(Lisp_Bloom*, Lisp_Object);
  72 extern void bloom_remove(Lisp_Bloom*, Lisp_Object);
  73 extern void bloom_union(Lisp_Bloom*, Lisp_Bloom*);
  74 extern void bloom_intersection(Lisp_Bloom*, Lisp_Bloom*);
  75
  76 #endif  /* INCLUDED_bloom_h_ */