[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
gEDA-bug: pcb git segmentation fault in hid binary searchs
Forwarding to geda-bug for tracking...
---------- Forwarded message ----------
From: Oblivian <oblivian@xxxxxxxxxxxxxxxxxxxxx>
Date: Mon, May 25, 2009 at 12:00 AM
Subject: Re: gEDA-user: pcb git segmentation fault in hid binary searchs
To: gEDA user mailing list <geda-user@xxxxxxxxxxxxxx>
Here's a patch for the binary searches in actions.c and flags.c. I've
compiled and tested on Ubuntu, and it seems to work just fine. Also
added case insensitive search to the flags.c implementation as well.
Jason
On Sun, May 24, 2009 at 12:12 AM, Oblivian
<oblivian@xxxxxxxxxxxxxxxxxxxxx> wrote:
>
> DJ,
>
> Thanks, I'll see what I can do to remove the linear search as well.
>
> Jason
>
> On Sun, May 24, 2009 at 12:07 AM, DJ Delorie <dj@xxxxxxxxxxx> wrote:
>>
>> > I've tracked the problem to the binary search in hid_find_flag, when strcmp
>> > gets a null value from the flags being searched. This may be a recent
>> > change in glibc for Ubuntu and a test program that just does strcmp("some
>> > string",NULL); segfaults for me. I've changed it to use bsearch for now...
>> > my question is, is there a reason the stdlib bsearch function was not used?
>> > I notice that qsort is used right above it. If there is no complaint in
>> > changing the bsearch's in flags.c and actions.c, I'll submit a patch for it.
>>
>> No reason, go ahead.
>>
>> > Also, question in actions.c... It appears that the binary search is
>> > performed and a linear search is done if the action was not found in the
>> > binary search. Is there a reason for this or was it just overlooked in the
>> > hid upgrade?
>>
>> The binary search is case sensitive, the linear search isn't. What we
>> might consider is a hash based on tolower(name) instead.
>>
>>
>> _______________________________________________
>> geda-user mailing list
>> geda-user@xxxxxxxxxxxxxx
>> http://www.seul.org/cgi-bin/mailman/listinfo/geda-user
>
diff --git a/src/hid/common/actions.c b/src/hid/common/actions.c
index 0f2dfb4..cdb011a 100644
--- a/src/hid/common/actions.c
+++ b/src/hid/common/actions.c
@@ -129,18 +129,28 @@ hid_deregister_action (const char *name, void **context)
}
static int
-action_sort (const void *va, const void *vb)
+action_comp (const void *va, const void *vb)
{
HID_ActionContext *a = (HID_ActionContext *) va;
HID_ActionContext *b = (HID_ActionContext *) vb;
return strcmp (a->action.name, b->action.name);
}
+static int
+action_case_comp (const void *va, const void *vb)
+{
+ HID_ActionContext *a = (HID_ActionContext *) va;
+ HID_ActionContext *b = (HID_ActionContext *) vb;
+ return strcasecmp (a->action.name, b->action.name);
+}
+
+
HID_Action *
hid_find_action (const char *name, void **context)
{
HID_ActionNode *ha;
- int i, n, lower, upper;
+ int i, n;
+ HID_ActionContext key, *res;
if (name == NULL)
return 0;
@@ -155,36 +165,35 @@ hid_find_action (const char *name, void **context)
all_actions[n].context = ha->context;
n++;
}
- qsort (all_actions, n_actions, sizeof (HID_ActionContext), action_sort);
+ qsort (all_actions, n_actions, sizeof (HID_ActionContext), action_comp);
}
- lower = -1;
- upper = n_actions;
- /*printf("search action %s\n", name); */
- while (lower < upper - 1)
+ key.action.name = malloc (strlen(name) + 1);
+ strcpy (key.action.name, name);
+
+ /* Case sensitive search */
+ res = bsearch (&key, all_actions, n_actions, sizeof (HID_ActionContext), action_comp);
+ if (res != NULL)
{
- i = (lower + upper) / 2;
- n = strcmp (all_actions[i].action.name, name);
- /*printf("try [%d].%s, cmp %d\n", i, all_actions[i].name, n); */
- if (n == 0) {
- if (context != NULL)
- *context = all_actions[i].context;
- return &(all_actions[i].action);
- }
- if (n > 0)
- upper = i;
- else
- lower = i;
+ free (key.action.name);
+ if (*context != NULL)
+ *context = res->context;
+ return &(res->action);
}
- for (i = 0; i < n_actions; i++)
- if (strcasecmp (all_actions[i].action.name, name) == 0) {
+ /* Case insensitive search */
+ res = bsearch (&key, all_actions, n_actions, sizeof (HID_ActionContext), action_case_comp);
+ if (res != NULL)
+ {
+ free (key.action.name);
if (*context != NULL)
- *context = all_actions[i].context;
- return &(all_actions[i].action);
+ *context = res->context;
+ return &(res->action);
}
+ free (key.action.name);
+
printf ("unknown action `%s'\n", name);
return 0;
}
diff --git a/src/hid/common/flags.c b/src/hid/common/flags.c
index 8aba3ab..3d9b31a 100644
--- a/src/hid/common/flags.c
+++ b/src/hid/common/flags.c
@@ -52,18 +52,28 @@ hid_register_flags (HID_Flag * a, int n)
}
static int
-flag_sort (const void *va, const void *vb)
+flag_comp (const void *va, const void *vb)
{
HID_Flag *a = (HID_Flag *) va;
HID_Flag *b = (HID_Flag *) vb;
return strcmp (a->name, b->name);
}
+static int
+flag_case_comp (const void *va, const void *vb)
+{
+ HID_Flag *a = (HID_Flag *) va;
+ HID_Flag *b = (HID_Flag *) vb;
+ return strcasecmp (a->name, b->name);
+}
+
+
HID_Flag *
hid_find_flag (const char *name)
{
HID_FlagNode *hf;
- int i, n, lower, upper;
+ int i, n;
+ HID_Flag key, *res;
if (all_flags == 0)
{
@@ -72,24 +82,30 @@ hid_find_flag (const char *name)
for (hf = hid_flag_nodes; hf; hf = hf->next)
for (i = 0; i < hf->n; i++)
all_flags[n++] = hf->flags[i];
- qsort (all_flags, n_flags, sizeof (HID_Flag), flag_sort);
+ qsort (all_flags, n_flags, sizeof (HID_Flag), flag_comp);
}
- lower = -1;
- upper = n_flags + 1;
- /*printf("search flag %s\n", name); */
- while (lower < upper - 1)
+ key.name = malloc (strlen(name)+1);
+ strcpy (key.name, name);
+
+ /* Case sensitive search */
+ res = bsearch (&key, all_flags, n_flags, sizeof (HID_Flag), flag_comp);
+ if (res != NULL)
{
- i = (lower + upper) / 2;
- n = strcmp (all_flags[i].name, name);
- /*printf("try [%d].%s, cmp %d\n", i, all_flags[i].name, n); */
- if (n == 0)
- return all_flags + i;
- if (n > 0)
- upper = i;
- else
- lower = i;
+ free (key.name);
+ return res;
}
+
+ /* Case insensitive search */
+ res = bsearch (&key, all_flags, n_flags, sizeof (HID_Flag), flag_case_comp);
+ if (res != NULL)
+ {
+ free (key.name);
+ return res;
+ }
+
+ free (key.name);
+
printf ("unknown flag `%s'\n", name);
return 0;
}
_______________________________________________
geda-bug mailing list
geda-bug@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-bug