← Back to branch summary

~ubuntu-branches/ubuntu/saucy/db/saucy-proposed

« back to all changes in this revision

Viewing changes to src/dbinc/hash.h

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson
  • Date: 2010-11-05 15:02:09 UTC
  • mfrom: (13.1.12 sid)
  • Revision ID: james.westby@ubuntu.com-20101105150209-ppvyn0619pu014xo
Tags: 5.1.19-1ubuntu1
* Resynchronise with Debian.  Remaining changes:
  - Pass --build/--host to configure to support cross-building, and don't
    override CC.
  - Disable the Java build when cross-building, for now.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/dbinc/hash.h
 
1
/*-
 
2
 * See the file LICENSE for redistribution information.
 
3
 *
 
4
 * Copyright (c) 1996, 2010 Oracle and/or its affiliates.  All rights reserved.
 
5
 */
 
6
/*
 
7
 * Copyright (c) 1990, 1993, 1994
 
8
 *      Margo Seltzer.  All rights reserved.
 
9
 */
 
10
/*
 
11
 * Copyright (c) 1990, 1993, 1994
 
12
 *      The Regents of the University of California.  All rights reserved.
 
13
 *
 
14
 * This code is derived from software contributed to Berkeley by
 
15
 * Margo Seltzer.
 
16
 *
 
17
 * Redistribution and use in source and binary forms, with or without
 
18
 * modification, are permitted provided that the following conditions
 
19
 * are met:
 
20
 * 1. Redistributions of source code must retain the above copyright
 
21
 *    notice, this list of conditions and the following disclaimer.
 
22
 * 2. Redistributions in binary form must reproduce the above copyright
 
23
 *    notice, this list of conditions and the following disclaimer in the
 
24
 *    documentation and/or other materials provided with the distribution.
 
25
 * 3. Neither the name of the University nor the names of its contributors
 
26
 *    may be used to endorse or promote products derived from this software
 
27
 *    without specific prior written permission.
 
28
 *
 
29
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 
30
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
31
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
32
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 
33
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
34
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
35
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
36
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
37
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
38
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
39
 * SUCH DAMAGE.
 
40
 *
 
41
 * $Id$
 
42
 */
 
43
 
 
44
#ifndef _DB_HASH_H_
 
45
#define _DB_HASH_H_
 
46
 
 
47
#if defined(__cplusplus)
 
48
extern "C" {
 
49
#endif
 
50
 
 
51
/* Hash internal structure. */
 
52
typedef struct hash_t {
 
53
        db_pgno_t meta_pgno;    /* Page number of the meta data page. */
 
54
        u_int32_t revision;     /* Revision of subdb metadata. */
 
55
        u_int32_t h_ffactor;    /* Fill factor. */
 
56
        u_int32_t h_nelem;      /* Number of elements. */
 
57
                                /* Hash and compare functions. */
 
58
        u_int32_t (*h_hash) __P((DB *, const void *, u_int32_t));
 
59
        int (*h_compare) __P((DB *, const DBT *, const DBT *));
 
60
} HASH;
 
61
 
 
62
/* Cursor structure definitions. */
 
63
typedef struct cursor_t {
 
64
        /* struct __dbc_internal */
 
65
        __DBC_INTERNAL
 
66
 
 
67
        /* Hash private part */
 
68
 
 
69
        /* Per-thread information */
 
70
        DB_LOCK hlock;                  /* Metadata page lock. */
 
71
        HMETA *hdr;                     /* Pointer to meta-data page. */
 
72
        PAGE *split_buf;                /* Temporary buffer for splits. */
 
73
 
 
74
        /* Hash cursor information */
 
75
        db_pgno_t       bucket;         /* Bucket we are traversing. */
 
76
        db_pgno_t       lbucket;        /* Bucket for which we are locked. */
 
77
        db_indx_t       dup_off;        /* Offset within a duplicate set. */
 
78
        db_indx_t       dup_len;        /* Length of current duplicate. */
 
79
        db_indx_t       dup_tlen;       /* Total length of duplicate entry. */
 
80
        u_int32_t       seek_size;      /* Number of bytes we need for add. */
 
81
        db_pgno_t       seek_found_page;/* Page on which we can insert. */
 
82
        db_indx_t       seek_found_indx;/* Insert position for item. */
 
83
        u_int32_t       order;          /* Relative order among deleted curs. */
 
84
 
 
85
#define H_CONTINUE      0x0001          /* Join--search strictly fwd for data */
 
86
#define H_CONTRACT      0x0002          /* Table contracted.*/
 
87
#define H_DELETED       0x0004          /* Cursor item is deleted. */
 
88
#define H_DUPONLY       0x0008          /* Dups only; do not change key. */
 
89
#define H_EXPAND        0x0010          /* Table expanded. */
 
90
#define H_ISDUP         0x0020          /* Cursor is within duplicate set. */
 
91
#define H_NEXT_NODUP    0x0040          /* Get next non-dup entry. */
 
92
#define H_NOMORE        0x0080          /* No more entries in bucket. */
 
93
#define H_OK            0x0100          /* Request succeeded. */
 
94
        u_int32_t       flags;
 
95
} HASH_CURSOR;
 
96
 
 
97
/* Test string. */
 
98
#define CHARKEY                 "%$sniglet^&"
 
99
 
 
100
/* Overflow management */
 
101
/*
 
102
 * The spares table indicates the page number at which each doubling begins.
 
103
 * From this page number we subtract the number of buckets already allocated
 
104
 * so that we can do a simple addition to calculate the page number here.
 
105
 */
 
106
#define BS_TO_PAGE(bucket, spares)              \
 
107
        ((bucket) + (spares)[__db_log2((bucket) + 1)])
 
108
#define BUCKET_TO_PAGE(I, B)    (BS_TO_PAGE((B), (I)->hdr->spares))
 
109
 
 
110
/* Constraints about much data goes on a page. */
 
111
 
 
112
#define MINFILL         4
 
113
#define ISBIG(I, N)     (((N) > ((I)->hdr->dbmeta.pagesize / MINFILL)) ? 1 : 0)
 
114
 
 
115
/* Shorthands for accessing structure */
 
116
#define NDX_INVALID     0xFFFF
 
117
#define BUCKET_INVALID  0xFFFFFFFF
 
118
 
 
119
/* On page duplicates are stored as a string of size-data-size triples. */
 
120
#define DUP_SIZE(len)   ((len) + 2 * sizeof(db_indx_t))
 
121
 
 
122
/* Log messages types (these are subtypes within a record type) */
 
123
/* These bits are obsolete and are only needed for down rev logs. */
 
124
#define PAIR_KEYMASK            0x1
 
125
#define PAIR_DATAMASK           0x2
 
126
#define PAIR_DUPMASK            0x4
 
127
#define PAIR_MASK               0xf
 
128
#define PAIR_ISKEYBIG(N)        (N & PAIR_KEYMASK)
 
129
#define PAIR_ISDATABIG(N)       (N & PAIR_DATAMASK)
 
130
#define PAIR_ISDATADUP(N)       (N & PAIR_DUPMASK)
 
131
#define OPCODE_OF(N)    (N & ~PAIR_MASK)
 
132
 
 
133
/* Operators for hash recover routines. */
 
134
#define PUTPAIR         0x20
 
135
#define DELPAIR         0x30
 
136
#define PUTOVFL         0x40
 
137
#define DELOVFL         0x50
 
138
#define HASH_UNUSED1    0x60
 
139
#define HASH_UNUSED2    0x70
 
140
#define SPLITOLD        0x80
 
141
#define SPLITNEW        0x90
 
142
#define SORTPAGE        0x100
 
143
 
 
144
/* Flags to control behavior of __ham_del_pair */
 
145
#define HAM_DEL_NO_CURSOR       0x01 /* Don't do any cursor adjustment */
 
146
#define HAM_DEL_NO_RECLAIM      0x02 /* Don't reclaim empty pages */
 
147
/* Just delete onpage items (even if they are references to off-page items). */
 
148
#define HAM_DEL_IGNORE_OFFPAGE  0x04
 
149
 
 
150
typedef enum {
 
151
        DB_HAM_CURADJ_DEL = 1,
 
152
        DB_HAM_CURADJ_ADD = 2,
 
153
        DB_HAM_CURADJ_ADDMOD = 3,
 
154
        DB_HAM_CURADJ_DELMOD = 4
 
155
} db_ham_curadj;
 
156
 
 
157
typedef enum {
 
158
        DB_HAM_CHGPG = 1,
 
159
        DB_HAM_DELFIRSTPG = 2,
 
160
        DB_HAM_DELMIDPG = 3,
 
161
        DB_HAM_DELLASTPG = 4,
 
162
        DB_HAM_DUP   = 5,
 
163
        DB_HAM_SPLIT = 6
 
164
} db_ham_mode;
 
165
 
 
166
#if defined(__cplusplus)
 
167
}
 
168
#endif
 
169
 
 
170
#include "dbinc_auto/hash_auto.h"
 
171
#include "dbinc_auto/hash_ext.h"
 
172
#include "dbinc/db_am.h"
 
173
#endif /* !_DB_HASH_H_ */