1/* gdbmseq.c - Routines to visit all keys.  Not in sorted order. */
2
3/*  This file is part of GDBM, the GNU data base manager, by Philip A. Nelson.
4    Copyright (C) 1990, 1991, 1993  Free Software Foundation, Inc.
5
6    GDBM is free software; you can redistribute it and/or modify
7    it under the terms of the GNU General Public License as published by
8    the Free Software Foundation; either version 2, or (at your option)
9    any later version.
10
11    GDBM is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with GDBM; see the file COPYING.  If not, write to
18    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
19
20    You may contact the author by:
21       e-mail:  phil@cs.wwu.edu
22      us-mail:  Philip A. Nelson
23                Computer Science Department
24                Western Washington University
25                Bellingham, WA 98226
26
27*************************************************************************/
28
29
30/* include system configuration before all else. */
31#include "autoconf.h"
32
33#include "gdbmdefs.h"
34#include "gdbmerrno.h"
35
36/* Special extern for this file. */
37extern char *_gdbm_read_entry __P((gdbm_file_info *, int));
38
39
40/* Find and read the next entry in the hash structure for DBF starting
41   at ELEM_LOC of the current bucket and using RETURN_VAL as the place to
42   put the data that is found. */
43
44static void
45get_next_key (dbf, elem_loc, return_val)
46     gdbm_file_info *dbf;
47     int elem_loc;
48     datum *return_val;
49{
50  int   found;			/* Have we found the next key. */
51  char  *find_data;		/* Data pointer returned by find_key. */
52
53  /* Find the next key. */
54  found = FALSE;
55  while (!found)
56    {
57      /* Advance to the next location in the bucket. */
58      elem_loc++;
59      if (elem_loc == dbf->header->bucket_elems)
60	{
61	  /* We have finished the current bucket, get the next bucket.  */
62	  elem_loc = 0;
63
64	  /* Find the next bucket.  It is possible several entries in
65	     the bucket directory point to the same bucket. */
66	  while (dbf->bucket_dir < dbf->header->dir_size / sizeof (off_t)
67		 && dbf->cache_entry->ca_adr == dbf->dir[dbf->bucket_dir])
68	    dbf->bucket_dir++;
69
70	  /* Check to see if there was a next bucket. */
71	  if (dbf->bucket_dir < dbf->header->dir_size / sizeof (off_t))
72	    _gdbm_get_bucket (dbf, dbf->bucket_dir);
73	  else
74	    /* No next key, just return. */
75	    return ;
76	}
77      found = dbf->bucket->h_table[elem_loc].hash_value != -1;
78    }
79
80  /* Found the next key, read it into return_val. */
81  find_data = _gdbm_read_entry (dbf, elem_loc);
82  return_val->dsize = dbf->bucket->h_table[elem_loc].key_size;
83  if (return_val->dsize == 0)
84    return_val->dptr = (char *) malloc (1);
85  else
86    return_val->dptr = (char *) malloc (return_val->dsize);
87  if (return_val->dptr == NULL) _gdbm_fatal (dbf, "malloc error");
88  bcopy (find_data, return_val->dptr, return_val->dsize);
89}
90
91
92/* Start the visit of all keys in the database.  This produces something in
93   hash order, not in any sorted order.  */
94
95datum
96gdbm_firstkey (dbf)
97     gdbm_file_info *dbf;
98{
99  datum return_val;		/* To return the first key. */
100
101  /* Set the default return value for not finding a first entry. */
102  return_val.dptr = NULL;
103
104  /* Initialize the gdbm_errno variable. */
105  gdbm_errno = GDBM_NO_ERROR;
106
107  /* Get the first bucket.  */
108  _gdbm_get_bucket (dbf, 0);
109
110  /* Look for first entry. */
111  get_next_key (dbf, -1, &return_val);
112
113  return return_val;
114}
115
116
117/* Continue visiting all keys.  The next key following KEY is returned. */
118
119datum
120gdbm_nextkey (dbf, key)
121     gdbm_file_info *dbf;
122     datum key;
123{
124  datum  return_val;		/* The return value. */
125  int    elem_loc;		/* The location in the bucket. */
126  char  *find_data;		/* Data pointer returned by _gdbm_findkey. */
127  int    hash_val;		/* Returned by _gdbm_findkey. */
128
129  /* Initialize the gdbm_errno variable. */
130  gdbm_errno = GDBM_NO_ERROR;
131
132  /* Set the default return value for no next entry. */
133  return_val.dptr = NULL;
134
135  /* Do we have a valid key? */
136  if (key.dptr == NULL) return return_val;
137
138  /* Find the key.  */
139  elem_loc = _gdbm_findkey (dbf, key, &find_data, &hash_val);
140  if (elem_loc == -1) return return_val;
141
142  /* Find the next key. */
143  get_next_key (dbf, elem_loc, &return_val);
144
145  return return_val;
146}
147