+ be_lv_info_t *payload = arr + 1;
+
+ unsigned n = arr[0].head.n_members;
+ unsigned res = 0;
+ int lo = 0;
+ int hi = n;
+
+ if (n == 0)
+ return 0;
+
+ do {
+ int md = lo + ((hi - lo) >> 1);
+ unsigned md_idx = payload[md].node.idx;
+
+ if (idx > md_idx)
+ lo = md + 1;
+ else if (idx < md_idx)
+ hi = md;
+ else {
+ res = md;
+ assert(payload[res].node.idx == idx);
+ break;
+ }
+
+ res = lo;
+ } while (lo < hi);
+
+ return res;
+}
+
+be_lv_info_node_t *be_lv_get(const be_lv_t *li, const ir_node *bl,
+ const ir_node *irn)
+{
+ be_lv_info_t *irn_live;
+ be_lv_info_node_t *res = NULL;
+
+ stat_ev_tim_push();
+ irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
+ if (irn_live != NULL) {
+ unsigned idx = get_irn_idx(irn);
+
+ /* Get the position of the index in the array. */
+ int pos = _be_liveness_bsearch(irn_live, idx);
+
+ /* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
+ be_lv_info_node_t *rec = &irn_live[pos + 1].node;
+
+ /* Check, if the irn is in deed in the array. */
+ if (rec->idx == idx)
+ res = rec;
+ }
+ stat_ev_tim_pop("be_lv_get");
+
+ return res;
+}
+
+static be_lv_info_node_t *be_lv_get_or_set(be_lv_t *li, ir_node *bl,
+ ir_node *irn)
+{
+ be_lv_info_t *irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
+ if (irn_live == NULL) {
+ irn_live = OALLOCNZ(&li->obst, be_lv_info_t, LV_STD_SIZE);
+ irn_live[0].head.n_size = LV_STD_SIZE-1;
+ ir_nodehashmap_insert(&li->map, bl, irn_live);
+ }
+
+ unsigned idx = get_irn_idx(irn);
+
+ /* Get the position of the index in the array. */
+ unsigned pos = _be_liveness_bsearch(irn_live, idx);
+
+ /* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
+ be_lv_info_node_t *res = &irn_live[pos + 1].node;
+
+ /* Check, if the irn is in deed in the array. */
+ if (res->idx != idx) {
+ be_lv_info_t *payload;
+ unsigned n_members = irn_live[0].head.n_members;
+ unsigned n_size = irn_live[0].head.n_size;
+ unsigned i;
+
+ if (n_members + 1 >= n_size) {
+ /* double the array size. Remember that the first entry is
+ * metadata about the array and not a real array element */
+ unsigned old_size_bytes = (n_size + 1) * sizeof(irn_live[0]);
+ unsigned new_size = (2 * n_size) + 1;
+ size_t new_size_bytes = new_size * sizeof(irn_live[0]);
+ be_lv_info_t *nw = OALLOCN(&li->obst, be_lv_info_t, new_size);
+ memcpy(nw, irn_live, old_size_bytes);
+ memset(((char*) nw) + old_size_bytes, 0,
+ new_size_bytes - old_size_bytes);
+ nw[0].head.n_size = new_size - 1;
+ irn_live = nw;
+ ir_nodehashmap_insert(&li->map, bl, nw);
+ }
+
+ payload = &irn_live[1];
+ for (i = n_members; i > pos; --i) {
+ payload[i] = payload[i - 1];
+ }
+
+ ++irn_live[0].head.n_members;
+
+ res = &payload[pos].node;
+ res->idx = idx;
+ res->flags = 0;
+ }
+
+ return res;