Drizzled Public API Documentation

hp_write.cc
1 /* Copyright (C) 2000-2002, 2004-2006 MySQL AB
2 
3  This program is free software; you can redistribute it and/or modify
4  it under the terms of the GNU General Public License as published by
5  the Free Software Foundation; version 2 of the License.
6 
7  This program is distributed in the hope that it will be useful,
8  but WITHOUT ANY WARRANTY; without even the implied warranty of
9  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  GNU General Public License for more details.
11 
12  You should have received a copy of the GNU General Public License
13  along with this program; if not, write to the Free Software
14  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15 
16 /* Write a record to heap-databas */
17 
18 #include "heap_priv.h"
19 #ifdef __WIN__
20 #include <fcntl.h>
21 #endif
22 
23 #include <drizzled/error_t.h>
24 
25 #define LOWFIND 1
26 #define LOWUSED 2
27 #define HIGHFIND 4
28 #define HIGHUSED 8
29 
30 using namespace drizzled;
31 
32 static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
33  uint32_t records);
34 
35 int heap_write(HP_INFO *info, const unsigned char *record)
36 {
37  HP_KEYDEF *keydef, *end;
38  unsigned char *pos;
39  HP_SHARE *share=info->getShare();
40 
41  if ((share->records >= share->max_records && share->max_records) ||
42  (share->recordspace.total_data_length + share->index_length >= share->max_table_size))
43  {
44  return(errno=HA_ERR_RECORD_FILE_FULL);
45  }
46 
47  if (!(pos=hp_allocate_chunkset(&share->recordspace, 1)))
48  return(errno);
49  share->changed=1;
50 
51  for (keydef = share->keydef, end = keydef + share->keys; keydef < end;
52  keydef++)
53  {
54  if (hp_write_key(info, keydef, record, pos))
55  goto err;
56  }
57 
58  hp_copy_record_data_to_chunkset(share, record, pos);
59 
60  if (++share->records == share->blength)
61  share->blength+= share->blength;
62 
63  info->current_ptr=pos;
64  info->current_hash_ptr=0;
65  info->update|=HA_STATE_AKTIV;
66  if (share->auto_key)
67  heap_update_auto_increment(info, record);
68  return(0);
69 
70 err:
71  info->errkey= keydef - share->keydef;
72  while (keydef >= share->keydef)
73  {
74  if (hp_delete_key(info, keydef, record, pos, 0))
75  break;
76  keydef--;
77  }
78 
79  hp_free_chunks(&share->recordspace, pos);
80 
81  return(errno);
82 } /* heap_write */
83 
84 /*
85  Write a hash-key to the hash-index
86  SYNOPSIS
87  info Heap table info
88  keyinfo Key info
89  record Table record to added
90  recpos Memory buffer where the table record will be stored if added
91  successfully
92  NOTE
93  Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO
94  structs. Array size == number of entries in hash index.
95  hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
96  If there are several hash entries with the same hash array position P,
97  they are connected in a linked list via HASH_INFO::next_key. The first
98  list element is located at position P, next elements are located at
99  positions for which there is no record that should be located at that
100  position. The order of elements in the list is arbitrary.
101 
102  RETURN
103  0 - OK
104  -1 - Out of memory
105  HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was
106  still added and the caller must call hp_delete_key for it.
107 */
108 
109 int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
110  const unsigned char *record, unsigned char *recpos)
111 {
112  HP_SHARE *share = info->getShare();
113  int flag;
114  uint32_t halfbuff,hashnr,first_index;
115  unsigned char *ptr_to_rec= NULL,*ptr_to_rec2= NULL;
116  HASH_INFO *empty, *gpos= NULL, *gpos2= NULL, *pos;
117 
118  flag=0;
119  if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
120  return(-1); /* No more memory */
121  halfbuff= (long) share->blength >> 1;
122  pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
123 
124  /*
125  We're about to add one more hash array position, with hash_mask=#records.
126  The number of hash positions will change and some entries might need to
127  be relocated to the newly added position. Those entries are currently
128  members of the list that starts at #first_index position (this is
129  guaranteed by properties of hp_mask(hp_rec_hashnr(X)) mapping function)
130  At #first_index position currently there may be either:
131  a) An entry with hashnr != first_index. We don't need to move it.
132  or
133  b) A list of items with hash_mask=first_index. The list contains entries
134  of 2 types:
135  1) entries that should be relocated to the list that starts at new
136  position we're adding ('uppper' list)
137  2) entries that should be left in the list starting at #first_index
138  position ('lower' list)
139  */
140  if (pos != empty) /* If some records */
141  {
142  do
143  {
144  hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
145  if (flag == 0)
146  {
147  /*
148  First loop, bail out if we're dealing with case a) from above
149  comment
150  */
151  if (hp_mask(hashnr, share->blength, share->records) != first_index)
152  break;
153  }
154  /*
155  flag & LOWFIND - found a record that should be put into lower position
156  flag & LOWUSED - lower position occupied by the record
157  Same for HIGHFIND and HIGHUSED and 'upper' position
158 
159  gpos - ptr to last element in lower position's list
160  gpos2 - ptr to last element in upper position's list
161 
162  ptr_to_rec - ptr to last entry that should go into lower list.
163  ptr_to_rec2 - same for upper list.
164  */
165  if (!(hashnr & halfbuff))
166  {
167  /* Key should be put into 'lower' list */
168  if (!(flag & LOWFIND))
169  {
170  /* key is the first element to go into lower position */
171  if (flag & HIGHFIND)
172  {
173  flag=LOWFIND | HIGHFIND;
174  /* key shall be moved to the current empty position */
175  gpos=empty;
176  ptr_to_rec=pos->ptr_to_rec;
177  empty=pos; /* This place is now free */
178  }
179  else
180  {
181  /*
182  We can only get here at first iteration: key is at 'lower'
183  position pos and should be left here.
184  */
185  flag=LOWFIND | LOWUSED;
186  gpos=pos;
187  ptr_to_rec=pos->ptr_to_rec;
188  }
189  }
190  else
191  {
192  /* Already have another key for lower position */
193  if (!(flag & LOWUSED))
194  {
195  /* Change link of previous lower-list key */
196  gpos->ptr_to_rec=ptr_to_rec;
197  gpos->next_key=pos;
198  flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
199  }
200  gpos=pos;
201  ptr_to_rec=pos->ptr_to_rec;
202  }
203  }
204  else
205  {
206  /* key will be put into 'higher' list */
207  if (!(flag & HIGHFIND))
208  {
209  flag= (flag & LOWFIND) | HIGHFIND;
210  /* key shall be moved to the last (empty) position */
211  gpos2= empty;
212  empty= pos;
213  ptr_to_rec2=pos->ptr_to_rec;
214  }
215  else
216  {
217  if (!(flag & HIGHUSED))
218  {
219  /* Change link of previous upper-list key and save */
220  gpos2->ptr_to_rec=ptr_to_rec2;
221  gpos2->next_key=pos;
222  flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
223  }
224  gpos2=pos;
225  ptr_to_rec2=pos->ptr_to_rec;
226  }
227  }
228  }
229  while ((pos=pos->next_key));
230 
231  if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
232  {
233  /*
234  If both 'higher' and 'lower' list have at least one element, now
235  there are two hash buckets instead of one.
236  */
237  keyinfo->hash_buckets++;
238  }
239 
240  if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
241  {
242  gpos->ptr_to_rec=ptr_to_rec;
243  gpos->next_key=0;
244  }
245  if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
246  {
247  gpos2->ptr_to_rec=ptr_to_rec2;
248  gpos2->next_key=0;
249  }
250  }
251  /* Check if we are at the empty position */
252 
253  pos=hp_find_hash(&keyinfo->block, hp_mask(hp_rec_hashnr(keyinfo, record),
254  share->blength, share->records + 1));
255  if (pos == empty)
256  {
257  pos->ptr_to_rec=recpos;
258  pos->next_key=0;
259  keyinfo->hash_buckets++;
260  }
261  else
262  {
263  /* Check if more records in same hash-nr family */
264  empty[0]=pos[0];
265  gpos=hp_find_hash(&keyinfo->block,
266  hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
267  share->blength, share->records + 1));
268  if (pos == gpos)
269  {
270  pos->ptr_to_rec=recpos;
271  pos->next_key=empty;
272  }
273  else
274  {
275  keyinfo->hash_buckets++;
276  pos->ptr_to_rec=recpos;
277  pos->next_key=0;
278  hp_movelink(pos, gpos, empty);
279  }
280 
281  /* Check if duplicated keys */
282  if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
283  (!(keyinfo->flag & HA_NULL_PART_KEY) ||
284  !hp_if_null_in_key(keyinfo, record)))
285  {
286  pos=empty;
287  do
288  {
289  if (! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec, 1))
290  {
291  return(errno=HA_ERR_FOUND_DUPP_KEY);
292  }
293  } while ((pos=pos->next_key));
294  }
295  }
296  return(0);
297 }
298 
299  /* Returns ptr to block, and allocates block if neaded */
300 
301 static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
302  HP_BLOCK *block, uint32_t records)
303 {
304  uint32_t block_pos;
305  size_t length;
306 
307  if (records < block->last_allocated)
308  return hp_find_hash(block,records);
309  if (!(block_pos=(records % block->records_in_block)))
310  {
311  if (hp_get_new_block(block,&length))
312  return(NULL);
313  info->index_length+=length;
314  }
315  block->last_allocated=records+1;
316  return((HASH_INFO*) ((unsigned char*) block->level_info[0].last_blocks+
317  block_pos*block->recbuffer));
318 }