Insert Funktion für Array

[LisTenEr]

Hallo Leute,

Ich darf mich hier ein wenig mit C herumschlagen und stolpere doch glatt über Arrays. Aber die Story erst mal von Anfang an:

Ich habe Erfahrung mit Java (ca. 6 Jahre), Ruby ( 1/2 Jahr), JS (1/2 Jahr) und bin jetzt eben ein wenig an C geraten.
Meine Aufgabe/Idee:
Im Moment setzte ich bei mir Postgres als Datenbank-Server ein. In Ruby habe ich mir ein wenig Code gebastelt, der ein bewertetes Interval in bereits vorhandene Intervalle einordnet und evtl. betroffene Intervalle neu bewertet.
Beispiel:

# 3 Intervalle: [1,3],[3,7],[7,8]
intervals = [1,3,7,8]
# Gewichte der Intervalle
# d.h. w([1,3]) = 2,  w([1,3]) = 0,  w([1,3]) = 3
weights = [2,0,3]
# neues interval
new_interval = [1,6]
# neues gewicht
new_weight = 2
# neues interval einfügen
# Ergebnis: intervals = [1,3,6,7,8], weights = [4,2,0,3]; 
intervals,weights = insert_interval(intervals,weights, new_interval, new_weight)

Dieser Teil ist nicht rechen intensiv und dürfte in O(log n) laufen (Nagelt mich nicht fest, bins jetzt nicht ganz durchgegangen). Allerdings gibt es nach diesem Teil auch noch eine weitere Berechnung die mit der exponential funktion herumspielt und DIE ist rechenintenseiv. Kurzum, ich habe meinen Code in die Datenbank verlagert. Zuerst mit der integrierten Skriptsprache plpgsql (PostgreSQL: Documentation: Manuals: PostgreSQL 8.4: PL/pgSQL - SQL Procedural Language). Das war leider nicht so schnell wie erhofft. Nun probiere ich den Code in C zu übersetzen und in postgres entsprechende Funktionen aufzurufen.

Tja... in Ruby gibt es die Methode

Array.insert(pos,element)

die das übergebene Element vor dem index pos einfügt. In C gibt es die nicht. Also dachte ich mir: Die bastle ich mir. So lange nach einer Lösung habe ich schon lange nicht mehr gesucht. Ich habe ein wenig Testcode geschrieben, denn Ihr euch gerne ansehen und auch mal kompilieren könnt.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

#ifdef __cplusplus
#error No C-Compiler
#endif

typedef struct {
    // Size of the underlying borders array
    int borders_size;
    // The borders array
    double *interval_borders;
} result_type;

/*
 * Helper
 */
void print_res_type(result_type *t, char when[]) {
    int size = t->borders_size;
    int i;
    printf(when);
    printf("borders_size: %d \n", size); //t->borders_size);
    for (i = 0; i < size; i++) {
        printf("interval_border: %e \n", t->interval_borders[i]);
    }
}

void insert(result_type *res, int pos, double val) {
    // Range check
    if (pos > res->borders_size - 1) return;
    // Rellocate interval_borders; no NULL-Check
    res->interval_borders = (double *) realloc(res->interval_borders, ((++res->borders_size) * sizeof (double)));
    // Shift every entry after pos one to the right and set pos entry to val
    memmove(res->interval_borders + 1 + pos, res->interval_borders + pos, (res->borders_size - pos) * sizeof (double));
    *(res->interval_borders + pos) = val;
}

/*
 * Main
 */
int main(void) {
    result_type *t;
    int i;
    // init arrays
    double arr_b[3] = {10, 20, 30};
    // Allocate corresponding memory
    double *interval_b = (double *) malloc(sizeof (arr_b));
    // Copy arrs into memory
    interval_b = memmove(interval_b, arr_b, sizeof (arr_b));
    if (interval_b == NULL) {
        return EXIT_FAILURE;
    }
    // Alloc memory for struct
    t = (result_type *) malloc(sizeof (result_type));
    t->borders_size = sizeof (arr_b) / sizeof (double);
    t->interval_borders = interval_b;
    printf("Adress of t: %d \n", &t);
    print_res_type(t, "before insert \n");
    // First call is fine
    insert(t, 2, 2);
    // Failure ?
    insert(t, 0, 2);
    print_res_type(t, "after insert \n");

    return EXIT_SUCCESS;
}

Ich nutze MinGW GNU gcc 4.5.1 als Compiler und habe Windows 7 x64. Das Ganze soll später auf ner Ubuntu-Kiste (Server 10.10 x64) laufen. Als IDE nutze ich NetBeans. Als Debugger nutze ich gdb.

Mein Fehler:
* gdb spuckt mir ein SIGTRAP während dem zweiten insert Funktionsaufruf aus. Ich konnte den Fehler bis zum realloc in der Funktion insert nachvollziehen.

Was habe ich bis jetzt getan:
* In einer ersten Version habe ich wohl die C-Kuh geschlachtet und einfach den Pointer weiter nach rechts verschoben um an eine neue "freie" Speicherstelle zu gelangen. Tja, das war ein Griff ins Klo.
* In meiner zweiten Version habe ich im insert mit malloc 3 Speicherblöcke reserviert: first_part, second_part und result. first_part hatte die Größe bis eins vor der gewünschten Position +1 und second_part die Restgröße. An first_part habe ich den neuen Wert angehängt und dann alles in result vereinigt. Ebenfalls SIGTRAP während der Speicherallokierung.
* Herausgefunden, dass automatisch allokierter Speicher nicht "gefreet" werden kann.
* Auf Pointer umgeschrieben
* Verzweifelt

Was habe ich bei Google gefunden:
* The GNU C Library - Memory Allocation
* Wiki / StackOverflow etc.

Ich bin für jede Antwort dankbar.

Gruß,
Listener

 

[Tornhoof]

Muss es unbedingt ANSI-C sein? Ich seh zumindest auf die Schnelle keinen Fehler bei deinem Code.

Mit C++ und nem Vektor hättest du halt .Insert schon dabei.

vector::insert - C++ Reference

 

[herrhannes]

Ich habe es mir jetzt nicht genauer angeschaut, aber den Speicher für ein neues Array reservieren, dem Startpointer des alten Arrays die Adresse des neuen zuweisen und entsprechendend auch mit dem dann zu verschiebenden Teil des Arrays müsste klappen.
Hatte nämlich auch schon so etwas, wo ich keinen vector verwenden durfte.

 

[LisTenEr]

Ich habe jetzt nichts gefunden, ob postgres auch mit c++ erweiterbar ist. Allerdings habe ich meinen Fehler entdeckt. Ich erhöhe die border_size zu früh. Sonst klappts wunderbar. Danke für die Hilfe.