Mercurial > trustbridge > nss-cmake-static

comparison nss/lib/dbm/src/h_bigkey.c @ 3:150b72113545

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add DBM and legacydb support
author Andre Heinecke <andre.heinecke@intevation.de>
date Tue, 05 Aug 2014 18:32:02 +0200
parents
children
comparison
equal deleted inserted replaced
2:a945361df361 3:150b72113545
1 /*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Margo Seltzer.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. ***REMOVED*** - see
17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
18 * 4. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #if defined(LIBC_SCCS) && !defined(lint)
36 static char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94";
37 #endif /* LIBC_SCCS and not lint */
38
39 /*
40 * PACKAGE: hash
41 * DESCRIPTION:
42 * Big key/data handling for the hashing package.
43 *
44 * ROUTINES:
45 * External
46 * __big_keydata
47 * __big_split
48 * __big_insert
49 * __big_return
50 * __big_delete
51 * __find_last_page
52 * Internal
53 * collect_key
54 * collect_data
55 */
56
57 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
58 #include <sys/param.h>
59 #endif
60
61 #include <errno.h>
62 #include <stdio.h>
63 #include <stdlib.h>
64 #include <string.h>
65
66 #ifdef DEBUG
67 #include <assert.h>
68 #endif
69
70 #include "mcom_db.h"
71 #include "hash.h"
72 #include "page.h"
73 /* #include "extern.h" */
74
75 static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
76 static int collect_data __P((HTAB *, BUFHEAD *, int, int));
77
78 /*
79 * Big_insert
80 *
81 * You need to do an insert and the key/data pair is too big
82 *
83 * Returns:
84 * 0 ==> OK
85 *-1 ==> ERROR
86 */
87 extern int
88 __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
89 {
90 register uint16 *p;
91 uint key_size, n, val_size;
92 uint16 space, move_bytes, off;
93 char *cp, *key_data, *val_data;
94
95 cp = bufp->page; /* Character pointer of p. */
96 p = (uint16 *)cp;
97
98 key_data = (char *)key->data;
99 key_size = key->size;
100 val_data = (char *)val->data;
101 val_size = val->size;
102
103 /* First move the Key */
104 for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
105 space = FREESPACE(p) - BIGOVERHEAD) {
106 move_bytes = PR_MIN(space, key_size);
107 off = OFFSET(p) - move_bytes;
108 memmove(cp + off, key_data, move_bytes);
109 key_size -= move_bytes;
110 key_data += move_bytes;
111 n = p[0];
112 p[++n] = off;
113 p[0] = ++n;
114 FREESPACE(p) = off - PAGE_META(n);
115 OFFSET(p) = off;
116 p[n] = PARTIAL_KEY;
117 bufp = __add_ovflpage(hashp, bufp);
118 if (!bufp)
119 return (-1);
120 n = p[0];
121 if (!key_size) {
122 if (FREESPACE(p)) {
123 move_bytes = PR_MIN(FREESPACE(p), val_size);
124 off = OFFSET(p) - move_bytes;
125 p[n] = off;
126 memmove(cp + off, val_data, move_bytes);
127 val_data += move_bytes;
128 val_size -= move_bytes;
129 p[n - 2] = FULL_KEY_DATA;
130 FREESPACE(p) = FREESPACE(p) - move_bytes;
131 OFFSET(p) = off;
132 } else
133 p[n - 2] = FULL_KEY;
134 }
135 p = (uint16 *)bufp->page;
136 cp = bufp->page;
137 bufp->flags |= BUF_MOD;
138 }
139
140 /* Now move the data */
141 for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
142 space = FREESPACE(p) - BIGOVERHEAD) {
143 move_bytes = PR_MIN(space, val_size);
144 /*
145 * Here's the hack to make sure that if the data ends on the
146 * same page as the key ends, FREESPACE is at least one.
147 */
148 if (space == val_size && val_size == val->size)
149 move_bytes--;
150 off = OFFSET(p) - move_bytes;
151 memmove(cp + off, val_data, move_bytes);
152 val_size -= move_bytes;
153 val_data += move_bytes;
154 n = p[0];
155 p[++n] = off;
156 p[0] = ++n;
157 FREESPACE(p) = off - PAGE_META(n);
158 OFFSET(p) = off;
159 if (val_size) {
160 p[n] = FULL_KEY;
161 bufp = __add_ovflpage(hashp, bufp);
162 if (!bufp)
163 return (-1);
164 cp = bufp->page;
165 p = (uint16 *)cp;
166 } else
167 p[n] = FULL_KEY_DATA;
168 bufp->flags |= BUF_MOD;
169 }
170 return (0);
171 }
172
173 /*
174 * Called when bufp's page contains a partial key (index should be 1)
175 *
176 * All pages in the big key/data pair except bufp are freed. We cannot
177 * free bufp because the page pointing to it is lost and we can't get rid
178 * of its pointer.
179 *
180 * Returns:
181 * 0 => OK
182 *-1 => ERROR
183 */
184 extern int
185 __big_delete(HTAB *hashp, BUFHEAD *bufp)
186 {
187 register BUFHEAD *last_bfp, *rbufp;
188 uint16 *bp, pageno;
189 int key_done, n;
190
191 rbufp = bufp;
192 last_bfp = NULL;
193 bp = (uint16 *)bufp->page;
194 pageno = 0;
195 key_done = 0;
196
197 while (!key_done || (bp[2] != FULL_KEY_DATA)) {
198 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
199 key_done = 1;
200
201 /*
202 * If there is freespace left on a FULL_KEY_DATA page, then
203 * the data is short and fits entirely on this page, and this
204 * is the last page.
205 */
206 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
207 break;
208 pageno = bp[bp[0] - 1];
209 rbufp->flags |= BUF_MOD;
210 rbufp = __get_buf(hashp, pageno, rbufp, 0);
211 if (last_bfp)
212 __free_ovflpage(hashp, last_bfp);
213 last_bfp = rbufp;
214 if (!rbufp)
215 return (-1); /* Error. */
216 bp = (uint16 *)rbufp->page;
217 }
218
219 /*
220 * If we get here then rbufp points to the last page of the big
221 * key/data pair. Bufp points to the first one -- it should now be
222 * empty pointing to the next page after this pair. Can't free it
223 * because we don't have the page pointing to it.
224 */
225
226 /* This is information from the last page of the pair. */
227 n = bp[0];
228 pageno = bp[n - 1];
229
230 /* Now, bp is the first page of the pair. */
231 bp = (uint16 *)bufp->page;
232 if (n > 2) {
233 /* There is an overflow page. */
234 bp[1] = pageno;
235 bp[2] = OVFLPAGE;
236 bufp->ovfl = rbufp->ovfl;
237 } else
238 /* This is the last page. */
239 bufp->ovfl = NULL;
240 n -= 2;
241 bp[0] = n;
242 FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
243 OFFSET(bp) = hashp->BSIZE - 1;
244
245 bufp->flags |= BUF_MOD;
246 if (rbufp)
247 __free_ovflpage(hashp, rbufp);
248 if (last_bfp != rbufp)
249 __free_ovflpage(hashp, last_bfp);
250
251 hashp->NKEYS--;
252 return (0);
253 }
254 /*
255 * Returns:
256 * 0 = key not found
257 * -1 = get next overflow page
258 * -2 means key not found and this is big key/data
259 * -3 error
260 */
261 extern int
262 __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size)
263 {
264 register uint16 *bp;
265 register char *p;
266 int ksize;
267 uint16 bytes;
268 char *kkey;
269
270 bp = (uint16 *)bufp->page;
271 p = bufp->page;
272 ksize = size;
273 kkey = key;
274
275 for (bytes = hashp->BSIZE - bp[ndx];
276 bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
277 bytes = hashp->BSIZE - bp[ndx]) {
278 if (memcmp(p + bp[ndx], kkey, bytes))
279 return (-2);
280 kkey += bytes;
281 ksize -= bytes;
282 bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
283 if (!bufp)
284 return (-3);
285 p = bufp->page;
286 bp = (uint16 *)p;
287 ndx = 1;
288 }
289
290 if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
291 #ifdef HASH_STATISTICS
292 ++hash_collisions;
293 #endif
294 return (-2);
295 } else
296 return (ndx);
297 }
298
299 /*
300 * Given the buffer pointer of the first overflow page of a big pair,
301 * find the end of the big pair
302 *
303 * This will set bpp to the buffer header of the last page of the big pair.
304 * It will return the pageno of the overflow page following the last page
305 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
306 * bucket)
307 */
308 extern uint16
309 __find_last_page(HTAB *hashp, BUFHEAD **bpp)
310 {
311 BUFHEAD *bufp;
312 uint16 *bp, pageno;
313 uint n;
314
315 bufp = *bpp;
316 bp = (uint16 *)bufp->page;
317 for (;;) {
318 n = bp[0];
319
320 /*
321 * This is the last page if: the tag is FULL_KEY_DATA and
322 * either only 2 entries OVFLPAGE marker is explicit there
323 * is freespace on the page.
324 */
325 if (bp[2] == FULL_KEY_DATA &&
326 ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
327 break;
328
329 /* LJM bound the size of n to reasonable limits
330 */
331 if(n > hashp->BSIZE/sizeof(uint16))
332 return(0);
333
334 pageno = bp[n - 1];
335 bufp = __get_buf(hashp, pageno, bufp, 0);
336 if (!bufp)
337 return (0); /* Need to indicate an error! */
338 bp = (uint16 *)bufp->page;
339 }
340
341 *bpp = bufp;
342 if (bp[0] > 2)
343 return (bp[3]);
344 else
345 return (0);
346 }
347
348 /*
349 * Return the data for the key/data pair that begins on this page at this
350 * index (index should always be 1).
351 */
352 extern int
353 __big_return(
354 HTAB *hashp,
355 BUFHEAD *bufp,
356 int ndx,
357 DBT *val,
358 int set_current)
359 {
360 BUFHEAD *save_p;
361 uint16 *bp, len, off, save_addr;
362 char *tp;
363 int save_flags;
364
365 bp = (uint16 *)bufp->page;
366 while (bp[ndx + 1] == PARTIAL_KEY) {
367 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
368 if (!bufp)
369 return (-1);
370 bp = (uint16 *)bufp->page;
371 ndx = 1;
372 }
373
374 if (bp[ndx + 1] == FULL_KEY) {
375 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
376 if (!bufp)
377 return (-1);
378 bp = (uint16 *)bufp->page;
379 save_p = bufp;
380 save_addr = save_p->addr;
381 off = bp[1];
382 len = 0;
383 } else
384 if (!FREESPACE(bp)) {
385 /*
386 * This is a hack. We can't distinguish between
387 * FULL_KEY_DATA that contains complete data or
388 * incomplete data, so we require that if the data
389 * is complete, there is at least 1 byte of free
390 * space left.
391 */
392 off = bp[bp[0]];
393 len = bp[1] - off;
394 save_p = bufp;
395 save_addr = bufp->addr;
396 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
397 if (!bufp)
398 return (-1);
399 bp = (uint16 *)bufp->page;
400 } else {
401 /* The data is all on one page. */
402 tp = (char *)bp;
403 off = bp[bp[0]];
404 val->data = (uint8 *)tp + off;
405 val->size = bp[1] - off;
406 if (set_current) {
407 if (bp[0] == 2) { /* No more buckets in
408 * chain */
409 hashp->cpage = NULL;
410 hashp->cbucket++;
411 hashp->cndx = 1;
412 } else {
413 hashp->cpage = __get_buf(hashp,
414 bp[bp[0] - 1], bufp, 0);
415 if (!hashp->cpage)
416 return (-1);
417 hashp->cndx = 1;
418 if (!((uint16 *)
419 hashp->cpage->page)[0]) {
420 hashp->cbucket++;
421 hashp->cpage = NULL;
422 }
423 }
424 }
425 return (0);
426 }
427
428 /* pin our saved buf so that we don't lose if
429 * we run out of buffers */
430 save_flags = save_p->flags;
431 save_p->flags |= BUF_PIN;
432 val->size = collect_data(hashp, bufp, (int)len, set_current);
433 save_p->flags = save_flags;
434 if (val->size == (size_t)-1)
435 return (-1);
436 if (save_p->addr != save_addr) {
437 /* We are pretty short on buffers. */
438 errno = EINVAL; /* OUT OF BUFFERS */
439 return (-1);
440 }
441 memmove(hashp->tmp_buf, (save_p->page) + off, len);
442 val->data = (uint8 *)hashp->tmp_buf;
443 return (0);
444 }
445
446
447 /*
448 * Count how big the total datasize is by looping through the pages. Then
449 * allocate a buffer and copy the data in the second loop. NOTE: Our caller
450 * may already have a bp which it is holding onto. The caller is
451 * responsible for copying that bp into our temp buffer. 'len' is how much
452 * space to reserve for that buffer.
453 */
454 static int
455 collect_data(
456 HTAB *hashp,
457 BUFHEAD *bufp,
458 int len, int set)
459 {
460 register uint16 *bp;
461 BUFHEAD *save_bufp;
462 int save_flags;
463 int mylen, totlen;
464
465 /*
466 * save the input buf head because we need to walk the list twice.
467 * pin it to make sure it doesn't leave the buffer pool.
468 * This has the effect of growing the buffer pool if necessary.
469 */
470 save_bufp = bufp;
471 save_flags = save_bufp->flags;
472 save_bufp->flags |= BUF_PIN;
473
474 /* read the length of the buffer */
475 for (totlen = len; bufp ; bufp = __get_buf(hashp, bp[bp[0]-1], bufp, 0)) {
476 bp = (uint16 *)bufp->page;
477 mylen = hashp->BSIZE - bp[1];
478
479 /* if mylen ever goes negative it means that the
480 * page is screwed up.
481 */
482 if (mylen < 0) {
483 save_bufp->flags = save_flags;
484 return (-1);
485 }
486 totlen += mylen;
487 if (bp[2] == FULL_KEY_DATA) { /* End of Data */
488 break;
489 }
490 }
491
492 if (!bufp) {
493 save_bufp->flags = save_flags;
494 return (-1);
495 }
496
497 /* allocate a temp buf */
498 if (hashp->tmp_buf)
499 free(hashp->tmp_buf);
500 if ((hashp->tmp_buf = (char *)malloc((size_t)totlen)) == NULL) {
501 save_bufp->flags = save_flags;
502 return (-1);
503 }
504
505 /* copy the buffers back into temp buf */
506 for (bufp = save_bufp; bufp ;
507 bufp = __get_buf(hashp, bp[bp[0]-1], bufp, 0)) {
508 bp = (uint16 *)bufp->page;
509 mylen = hashp->BSIZE - bp[1];
510 memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], (size_t)mylen);
511 len += mylen;
512 if (bp[2] == FULL_KEY_DATA) {
513 break;
514 }
515 }
516
517 /* 'clear' the pin flags */
518 save_bufp->flags = save_flags;
519
520 /* update the database cursor */
521 if (set) {
522 hashp->cndx = 1;
523 if (bp[0] == 2) { /* No more buckets in chain */
524 hashp->cpage = NULL;
525 hashp->cbucket++;
526 } else {
527 hashp->cpage = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
528 if (!hashp->cpage)
529 return (-1);
530 else if (!((uint16 *)hashp->cpage->page)[0]) {
531 hashp->cbucket++;
532 hashp->cpage = NULL;
533 }
534 }
535 }
536 return (totlen);
537 }
538
539 /*
540 * Fill in the key and data for this big pair.
541 */
542 extern int
543 __big_keydata(
544 HTAB *hashp,
545 BUFHEAD *bufp,
546 DBT *key, DBT *val,
547 int set)
548 {
549 key->size = collect_key(hashp, bufp, 0, val, set);
550 if (key->size == (size_t)-1)
551 return (-1);
552 key->data = (uint8 *)hashp->tmp_key;
553 return (0);
554 }
555
556 /*
557 * Count how big the total key size is by recursing through the pages. Then
558 * collect the data, allocate a buffer and copy the key as you recurse up.
559 */
560 static int
561 collect_key(
562 HTAB *hashp,
563 BUFHEAD *bufp,
564 int len,
565 DBT *val,
566 int set)
567 {
568 BUFHEAD *xbp;
569 char *p;
570 int mylen, totlen;
571 uint16 *bp, save_addr;
572
573 p = bufp->page;
574 bp = (uint16 *)p;
575 mylen = hashp->BSIZE - bp[1];
576
577 save_addr = bufp->addr;
578 totlen = len + mylen;
579 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */
580 if (hashp->tmp_key != NULL)
581 free(hashp->tmp_key);
582 if ((hashp->tmp_key = (char *)malloc((size_t)totlen)) == NULL)
583 return (-1);
584 if (__big_return(hashp, bufp, 1, val, set))
585 return (-1);
586 } else {
587 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
588 if (!xbp || ((totlen =
589 collect_key(hashp, xbp, totlen, val, set)) < 1))
590 return (-1);
591 }
592 if (bufp->addr != save_addr) {
593 errno = EINVAL; /* MIS -- OUT OF BUFFERS */
594 return (-1);
595 }
596 memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], (size_t)mylen);
597 return (totlen);
598 }
599
600 /*
601 * Returns:
602 * 0 => OK
603 * -1 => error
604 */
605 extern int
606 __big_split(
607 HTAB *hashp,
608 BUFHEAD *op, /* Pointer to where to put keys that go in old bucket */
609 BUFHEAD *np, /* Pointer to new bucket page */
610 /* Pointer to first page containing the big key/data */
611 BUFHEAD *big_keyp,
612 uint32 addr, /* Address of big_keyp */
613 uint32 obucket,/* Old Bucket */
614 SPLIT_RETURN *ret)
615 {
616 register BUFHEAD *tmpp;
617 register uint16 *tp;
618 BUFHEAD *bp;
619 DBT key, val;
620 uint32 change;
621 uint16 free_space, n, off;
622
623 bp = big_keyp;
624
625 /* Now figure out where the big key/data goes */
626 if (__big_keydata(hashp, big_keyp, &key, &val, 0))
627 return (-1);
628 change = (__call_hash(hashp,(char*) key.data, key.size) != obucket);
629
630 if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) {
631 if (!(ret->nextp =
632 __get_buf(hashp, ret->next_addr, big_keyp, 0)))
633 return (-1);;
634 } else
635 ret->nextp = NULL;
636
637 /* Now make one of np/op point to the big key/data pair */
638 #ifdef DEBUG
639 assert(np->ovfl == NULL);
640 #endif
641 if (change)
642 tmpp = np;
643 else
644 tmpp = op;
645
646 tmpp->flags |= BUF_MOD;
647 #ifdef DEBUG1
648 (void)fprintf(stderr,
649 "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
650 (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
651 #endif
652 tmpp->ovfl = bp; /* one of op/np point to big_keyp */
653 tp = (uint16 *)tmpp->page;
654
655
656 #if 0 /* this get's tripped on database corrupted error */
657 assert(FREESPACE(tp) >= OVFLSIZE);
658 #endif
659 if(FREESPACE(tp) < OVFLSIZE)
660 return(DATABASE_CORRUPTED_ERROR);
661
662 n = tp[0];
663 off = OFFSET(tp);
664 free_space = FREESPACE(tp);
665 tp[++n] = (uint16)addr;
666 tp[++n] = OVFLPAGE;
667 tp[0] = n;
668 OFFSET(tp) = off;
669 FREESPACE(tp) = free_space - OVFLSIZE;
670
671 /*
672 * Finally, set the new and old return values. BIG_KEYP contains a
673 * pointer to the last page of the big key_data pair. Make sure that
674 * big_keyp has no following page (2 elements) or create an empty
675 * following page.
676 */
677
678 ret->newp = np;
679 ret->oldp = op;
680
681 tp = (uint16 *)big_keyp->page;
682 big_keyp->flags |= BUF_MOD;
683 if (tp[0] > 2) {
684 /*
685 * There may be either one or two offsets on this page. If
686 * there is one, then the overflow page is linked on normally
687 * and tp[4] is OVFLPAGE. If there are two, tp[4] contains
688 * the second offset and needs to get stuffed in after the
689 * next overflow page is added.
690 */
691 n = tp[4];
692 free_space = FREESPACE(tp);
693 off = OFFSET(tp);
694 tp[0] -= 2;
695 FREESPACE(tp) = free_space + OVFLSIZE;
696 OFFSET(tp) = off;
697 tmpp = __add_ovflpage(hashp, big_keyp);
698 if (!tmpp)
699 return (-1);
700 tp[4] = n;
701 } else
702 tmpp = big_keyp;
703
704 if (change)
705 ret->newp = tmpp;
706 else
707 ret->oldp = tmpp;
708 return (0);
709 }
This site is hosted by Intevation GmbH (Datenschutzerklärung und Impressum | Privacy Policy and Imprint)